Numerical Analysis/The Secant Method

The Secant Method

The secant method is an algorithm used to approximate the roots of a given function f. The method is based on approximating f using secant lines.

The Algorithm

The secant method algorithm requires the selection of two initial approximations x ₀ and x ₁, which may or may not bracket the desired root, but which are chosen reasonably close to the exact root.

Secant Method Algorithm
Given f(x)=0: Let x0 and x 1 be initial approximations. Then $x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}$ where xn is a better approximation of the exact root, assuming convergence. Repeat iterative step until either The total number of iterations N is met A sufficient degree of accuracy, $\epsilon$, is achieved.

Order of Convergence

We would like to be able to find the order of convergence, p, for the secant method. Hence, we want to find some p so that $\left\vert {x_{n+1}-x}\right\vert \approx C^{p}\left\vert {x_{n}-x}\right\vert$ where C is a constant.

Given a function f, let x be such that f(x)=0 and let x_n-1 and x_n be approximations to x. Assume x is a simple root and f is twice continuously differentiable (from the assumptions leading to convergence noted on Wikipedia). Let the error at the nth step be denoted by e_n: e_n=x_n-x. Then we have:

${\begin{aligned}e_{n+1}=x_{n+1}-x&=x_{n}-f(x_{n}){\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}-x\\&={\frac {(x_{n-1}-x)f(x_{n})-(x_{n}-x)f(x_{n-1})}{f(x_{n})-f(x_{n-1})}}\\&={\frac {e_{n-1}f(x_{n})-e_{n}f(x_{n-1})}{f(x_{n})-f(x_{n-1})}}\\&=e_{n}e_{n-1}{\Bigg (}{\frac {{\frac {f(x_{n})}{e_{n}}}-{\frac {f(x_{n-1})}{e_{n-1}}}}{f(x_{n})-f(x_{n-1})}}{\Bigg )}\end{aligned}}$.

Since f(x)=0 and recalling that e_n=x_n-x, we can rewrite the last line above as:

$e_{n+1}=e_{n}e_{n-1}{\Bigg (}{\frac {{\frac {f(x_{n})-f(x)}{x_{n}-x}}-{\frac {f(x_{n-1})-f(x)}{x_{n-1}-x}}}{f(x_{n})-f(x_{n-1})}}{\Bigg )}.$

(1)

Next, let's just consider the numerator in (1). Let $F(\omega )={\frac {f(\omega )-f(x)}{\omega -x}}$ where $\omega =...x_{n-1},x_{n},x_{n+1},...$. Thus

$F'(\omega )={\frac {f'(\omega )(\omega -x)+f(x)-f(\omega )}{(\omega -x)^{2}}}.$

(2)

According to the Mean Value Theorem, on [x_n-1,x_n], there exists some $\zeta _{n}$ between x_n-1 and x_n such that $F'(\zeta _{n})={\frac {F(x_{n})-F(x_{n-1})}{x_{n}-x_{n-1}}}$

$\Longleftrightarrow F(x_{n})-F(x_{n-1})=F'(\zeta _{n})(x_{n}-x_{n-1}).$

(3)

Now using a Taylor expansion of $f(x)$ around $\omega$, we have

${\begin{aligned}f(x)&=f(\omega )+(x-\omega )f'(\omega )+{\frac {(x-\omega )^{2}}{2}}f''(\nu _{n})\\\Rightarrow f(x)-f(\omega )-(x-\omega )f'(\omega )&={\frac {(x-\omega )^{2}}{2}}f''(\nu _{n}).\end{aligned}}$

(4)

Next, we can combine equations (2), (3), and (4) to show that $F(x_{n})-F(x_{n-1})={\frac {(x_{n}-x_{n-1})}{2}}f''(\nu _{n})$.

Returning to (1), we now have:

$e_{n+1}=e_{n}e_{n-1}{\Bigg (}{\frac {F(x_{n})-F(x_{n-1})}{f(x_{n})-f(x_{n-1})}}{\Bigg )}={\frac {e_{n}e_{n-1}(x_{n}-x_{n-1})}{2[f(x_{n})-f(x_{n-1})]}}f''(\nu _{n}).$

(5)

Again applying the Mean Value Theorem, there exists some $\xi _{n}$ in [x_n-1,x_n] such that $f'(\xi _{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}$. Then (5) becomes:

$e_{n+1}=e_{n}e_{n-1}{\frac {f''(\nu _{n})}{2f'(\xi _{n})}}\approx e_{n}e_{n-1}{\frac {f''(x)}{2f'(x)}}.$

Next, recall that we have convergence of order p when $\lim _{n\to \infty }{\frac {\left\vert {x_{n+1}-x}\right\vert }{\left\vert {x_{n}-x}\right\vert ^{p}}}=\lim _{n\to \infty }{\frac {\left\vert {e_{n+1}}\right\vert }{\left\vert {e_{n}}\right\vert ^{p}}}=\mu$ for some constant $\mu >0$. Our goal is to figure out what p is for the secant method.

Let $S_{n}={\frac {\left\vert {e_{n+1}}\right\vert }{\left\vert {e_{n}^{p}}\right\vert }}$
$\Leftrightarrow \left\vert {e_{n+1}}\right\vert =S_{n}\left\vert {e_{n}}\right\vert ^{p}=S_{n}(S_{n-1}\left\vert {e_{n-1}^{p}}\right\vert )^{p}=S_{n}S_{n-1}^{p}\left\vert {e_{n-1}}\right\vert ^{p^{2}}$.

Then we have: ${\frac {\left\vert {e_{n+1}}\right\vert }{\left\vert {e_{n}}\right\vert \left\vert {e_{n-1}}\right\vert }}={\frac {S_{n}S_{n-1}^{p}\left\vert {e_{n-1}}\right\vert ^{p^{2}}}{S_{n-1}\left\vert {e_{n-1}}\right\vert ^{p}\left\vert {e_{n-1}}\right\vert }}=S_{n}S_{n-1}^{p-1}\left\vert {e_{n-1}}\right\vert ^{p^{2}-p-1}$.

We want $\lim _{n\to \infty }{\Big (}S_{n}S_{n-1}^{p-1}\left\vert {e_{n-1}}\right\vert ^{p^{2}-p-1}{\Big )}=\mu$, again where $\mu$ is some constant. Since $S_{n}$ and $S_{n-1}^{p-1}$ are constants and $\lim _{n\to \infty }e_{n}=0$ (assuming convergence) we must have $p^{2}-p-1=0$. Thus $p={\frac {1+{\sqrt {5}}}{2}}\approx 1.618$.

A Numerical Example

The function $f(x)=\sin x+xe^{x}$ has a root between -3 and -4. Let's approximate this root accurate to four decimal places.

Let x₀ = -3 and x₁ = -4.

Next, using our recurrence formula where

$f(x_{0})=f(-3)=\sin(-3)-3e^{-3}\approx -0.2905$

and

$f(x_{1})=f(-4)=\sin(-4)-4e^{-4}\approx 0.6835$,

we have:

$x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}=-4-.6835({\frac {-4+3}{.6835+.2905}})\approx -3.2983.$

In the next iteration, we use f(x₁) = .6835 and f(x₂) = .0342 and see that

$x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}=-3.2983-.0342({\frac {-3.2983+4}{.0342-.6835}})\approx -3.2613.$

Similarly, we can compute x₄ and x₅. These calculations have been organized in the table below:

$i$	0	1	2	3	4	5
$x_{i}$	-3	-4	-3.2983	-3.2613	-3.2665	-3.2665

Hence the iterative method converges to -3.2665 after 4 iterations.

Pseudo Code

Below is pseudo code that will perform iterations of the secant method on a given function f.

Input: x0 and x1
Set y0=f(x0) and y1=f(x1)
Do 
   x=x1-y1*(x1-x0)/(y1-y0)
   y=f(x)
   Set x0=x1 and x1=x
   Set y0=y1 and y1=y
Until |y1|<tol

Exercises

Exercise 1

Find an approximation to ${\sqrt {5}}$ correct to four decimal places using the secant method on $f(x)=x^{2}-5$.

Solution:

We know ${\sqrt {5}}=2.2361$.
Let x₀ = 2 and x₁ = 3. Then f(x₀) = f(2) = -1 and f(x₁) = f(3) = 4.
In our first iteration, we have:

$x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}=3-4({\frac {3-2}{4+1}})=2.2$

In the second iteration, f(x₁) = 4, f(x₂) = -0.16 and we thus have

$x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}=2.2+.16({\frac {2.2-3}{-.16-4}})\approx 2.2333.$

Similarly, x₃ and x₄ can be calculated, and are shown in the table below:

$i$	0	1	2	3	4	5
$x_{i}$	2	3	2.2	2.2333	2.2361	2.2361

Thus after 4 iterations, the secant method converges to 2.2361, an approximation to ${\sqrt {5}}$ correct to four decimal places.

Exercise 2

Find a root of $f(x)=x+e^{x}$ by performing five iterations of the secant method beginning with x₀ = -1 and x₁ = 0.

Solution:

1st Iteration: x₀ = -1, x₁ = 0, f(x₀) = -0.63212, and f(x₁) = 1. Then

$x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}=({\frac {-1}{1+.63212}})=-.6127$

2nd Iteration: x₁ = 0, x₂ = -.6127, f(x₁) = 1, and f(x₂) = -.07081. Then

$x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}=-.6127+.07081({\frac {-.6127}{-.07081-1}})=-.57218$

3rd Iteration: x₂ = -.6127, x₃ = -.57218, f(x₂) = -.07081, and f(x₃) = -.00789. Then

$x_{4}=x_{3}-f(x_{3}){\frac {x_{3}-x_{2}}{f(x_{3})-f(x_{2})}}=-.57218+.00789({\frac {-.57218+.6127}{-.00789+.07081}})=-.5671$

4th Iteration: x₃ = -.57218, x₄ = -.5671, f(x₃) = -.00789, and f(x₄) = 6.7843*10^-5. Then

$x_{5}=x_{4}-f(x_{4}){\frac {x_{4}-x_{3}}{f(x_{4})-f(x_{3})}}=-.5671-6.7843\times 10^{-5}({\frac {-.5671+.57218}{6.7843\times 10^{-5}+.00789}})=-.56714$

5th Iteration: x₄ = -.5671, x₅ = -.56714, f(x₄) = 6.7843*10^-5, and f(x₅) = 5.1565*10^-6. Then

$x_{6}=x_{5}-f(x_{5}){\frac {x_{5}-x_{4}}{f(x_{5})-f(x_{4})}}=-.56714-5.1565\times 10^{-6}({\frac {-.56714+.5671}{5.1565\times 10^{-6}-6.7843\times 10^{-5}}})=-.56714$

Thus after 5 iterations, the method converges to -.56714 as one of the roots of $f(x)=x+e^{x}$.

Quiz

The following is a quiz covering information presented on the associated secant method page on Wikipedia as well as the current page.

1 True or False: The secant method converges faster than the bisection method.

	TRUE.
	FALSE.

2 True or False: The secant method converges faster than Newton's method.

	TRUE.
	FALSE.

3 Check all that apply: The secant method may be less computationally expensive than Newton's method because...

	Newton's method requires evaluating the given function f and its derivative f'.
	The secant method requires evaluating the given function f and its derivative f'.
	The secant method requires only one new function evaluation in each iteration.
	Newton's method requires only one new function evaluation in each iteration.

4 Given the function $f(x)=x^{4}-x-8$, perform 1 iteration of the secant method starting with x₀ = 1 and x₁ = 2. Then x₂ is equal to:

	1.2311
	1.5714
	1.6231
	1.7312

References

• Convergence of Secant Method
• Secant method convergence
• Secant method details