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
edit
The secant method algorithm requires the selection of two initial approximations x 0 and x 1 , 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 x 0 and x 1 be initial approximations.
Then
x
n
=
x
n
−
1
−
f
(
x
n
−
1
)
x
n
−
1
−
x
n
−
2
f
(
x
n
−
1
)
−
f
(
x
n
−
2
)
{\displaystyle 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 x n 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,
ϵ
{\displaystyle \epsilon }
Order of Convergence
edit
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
|
x
n
+
1
−
x
|
≈
C
p
|
x
n
−
x
|
{\displaystyle \left\vert {x_{n+1}-x}\right\vert \approx C^{p}\left\vert {x_{n}-x}\right\vert }
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:
e
n
+
1
=
x
n
+
1
−
x
=
x
n
−
f
(
x
n
)
x
n
−
x
n
−
1
f
(
x
n
)
−
f
(
x
n
−
1
)
−
x
=
(
x
n
−
1
−
x
)
f
(
x
n
)
−
(
x
n
−
x
)
f
(
x
n
−
1
)
f
(
x
n
)
−
f
(
x
n
−
1
)
=
e
n
−
1
f
(
x
n
)
−
e
n
f
(
x
n
−
1
)
f
(
x
n
)
−
f
(
x
n
−
1
)
=
e
n
e
n
−
1
(
f
(
x
n
)
e
n
−
f
(
x
n
−
1
)
e
n
−
1
f
(
x
n
)
−
f
(
x
n
−
1
)
)
{\displaystyle {\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
(
f
(
x
n
)
−
f
(
x
)
x
n
−
x
−
f
(
x
n
−
1
)
−
f
(
x
)
x
n
−
1
−
x
f
(
x
n
)
−
f
(
x
n
−
1
)
)
.
{\displaystyle 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
F
(
ω
)
=
f
(
ω
)
−
f
(
x
)
ω
−
x
{\displaystyle F(\omega )={\frac {f(\omega )-f(x)}{\omega -x}}}
ω
=
.
.
.
x
n
−
1
,
x
n
,
x
n
+
1
,
.
.
.
{\displaystyle \omega =...x_{n-1},x_{n},x_{n+1},...}
F
′
(
ω
)
=
f
′
(
ω
)
(
ω
−
x
)
+
f
(
x
)
−
f
(
ω
)
(
ω
−
x
)
2
.
{\displaystyle 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
ζ
n
{\displaystyle \zeta _{n}}
x n-1 and x n such that
F
′
(
ζ
n
)
=
F
(
x
n
)
−
F
(
x
n
−
1
)
x
n
−
x
n
−
1
{\displaystyle F'(\zeta _{n})={\frac {F(x_{n})-F(x_{n-1})}{x_{n}-x_{n-1}}}}
⟺
F
(
x
n
)
−
F
(
x
n
−
1
)
=
F
′
(
ζ
n
)
(
x
n
−
x
n
−
1
)
.
{\displaystyle \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
)
{\displaystyle f(x)}
ω
{\displaystyle \omega }
f
(
x
)
=
f
(
ω
)
+
(
x
−
ω
)
f
′
(
ω
)
+
(
x
−
ω
)
2
2
f
″
(
ν
n
)
⇒
f
(
x
)
−
f
(
ω
)
−
(
x
−
ω
)
f
′
(
ω
)
=
(
x
−
ω
)
2
2
f
″
(
ν
n
)
.
{\displaystyle {\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 4
F
(
x
n
)
−
F
(
x
n
−
1
)
=
(
x
n
−
x
n
−
1
)
2
f
″
(
ν
n
)
{\displaystyle F(x_{n})-F(x_{n-1})={\frac {(x_{n}-x_{n-1})}{2}}f''(\nu _{n})}
Returning to (1
e
n
+
1
=
e
n
e
n
−
1
(
F
(
x
n
)
−
F
(
x
n
−
1
)
f
(
x
n
)
−
f
(
x
n
−
1
)
)
=
e
n
e
n
−
1
(
x
n
−
x
n
−
1
)
2
[
f
(
x
n
)
−
f
(
x
n
−
1
)
]
f
″
(
ν
n
)
.
{\displaystyle 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
ξ
n
{\displaystyle \xi _{n}}
x n-1 ,x n ] such that
f
′
(
ξ
n
)
=
f
(
x
n
)
−
f
(
x
n
−
1
)
x
n
−
x
n
−
1
{\displaystyle f'(\xi _{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}
5
e
n
+
1
=
e
n
e
n
−
1
f
″
(
ν
n
)
2
f
′
(
ξ
n
)
≈
e
n
e
n
−
1
f
″
(
x
)
2
f
′
(
x
)
.
{\displaystyle 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
→
∞
|
x
n
+
1
−
x
|
|
x
n
−
x
|
p
=
lim
n
→
∞
|
e
n
+
1
|
|
e
n
|
p
=
μ
{\displaystyle \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 }
μ
>
0
{\displaystyle \mu >0}
Let
S
n
=
|
e
n
+
1
|
|
e
n
p
|
{\displaystyle S_{n}={\frac {\left\vert {e_{n+1}}\right\vert }{\left\vert {e_{n}^{p}}\right\vert }}}
⇔
|
e
n
+
1
|
=
S
n
|
e
n
|
p
=
S
n
(
S
n
−
1
|
e
n
−
1
p
|
)
p
=
S
n
S
n
−
1
p
|
e
n
−
1
|
p
2
{\displaystyle \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:
|
e
n
+
1
|
|
e
n
|
|
e
n
−
1
|
=
S
n
S
n
−
1
p
|
e
n
−
1
|
p
2
S
n
−
1
|
e
n
−
1
|
p
|
e
n
−
1
|
=
S
n
S
n
−
1
p
−
1
|
e
n
−
1
|
p
2
−
p
−
1
{\displaystyle {\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
→
∞
(
S
n
S
n
−
1
p
−
1
|
e
n
−
1
|
p
2
−
p
−
1
)
=
μ
{\displaystyle \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 }
μ
{\displaystyle \mu }
S
n
{\displaystyle S_{n}}
S
n
−
1
p
−
1
{\displaystyle S_{n-1}^{p-1}}
lim
n
→
∞
e
n
=
0
{\displaystyle \lim _{n\to \infty }e_{n}=0}
p
2
−
p
−
1
=
0
{\displaystyle p^{2}-p-1=0}
p
=
1
+
5
2
≈
1.618
{\displaystyle p={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}
[1]
A Numerical Example
edit
The function
f
(
x
)
=
sin
x
+
x
e
x
{\displaystyle f(x)=\sin x+xe^{x}}
Let x 0 = -3 and x 1 = -4.
Next, using our recurrence formula where
f
(
x
0
)
=
f
(
−
3
)
=
sin
(
−
3
)
−
3
e
−
3
≈
−
0.2905
{\displaystyle f(x_{0})=f(-3)=\sin(-3)-3e^{-3}\approx -0.2905}
f
(
x
1
)
=
f
(
−
4
)
=
sin
(
−
4
)
−
4
e
−
4
≈
0.6835
{\displaystyle f(x_{1})=f(-4)=\sin(-4)-4e^{-4}\approx 0.6835}
,
x
2
=
x
1
−
f
(
x
1
)
x
1
−
x
0
f
(
x
1
)
−
f
(
x
0
)
=
−
4
−
.6835
(
−
4
+
3
.6835
+
.2905
)
≈
−
3.2983.
{\displaystyle 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(x1 ) = .6835 and f(x2 ) = .0342 and see that
x
3
=
x
2
−
f
(
x
2
)
x
2
−
x
1
f
(
x
2
)
−
f
(
x
1
)
=
−
3.2983
−
.0342
(
−
3.2983
+
4
.0342
−
.6835
)
≈
−
3.2613.
{\displaystyle 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 4 and x 5 . These calculations have been organized in the table below:
i
{\displaystyle i}
0
1
2
3
4
5
x
i
{\displaystyle 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
edit
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
edit
Exercise 1
edit
Find an approximation to
5
{\displaystyle {\sqrt {5}}}
f
(
x
)
=
x
2
−
5
{\displaystyle f(x)=x^{2}-5}
We know
5
=
2.2361
{\displaystyle {\sqrt {5}}=2.2361}
x 0 = 2 and x 1 = 3. Then f(x0 ) = f(2) = -1 and f(x1 ) = f(3) = 4 .
x
2
=
x
1
−
f
(
x
1
)
x
1
−
x
0
f
(
x
1
)
−
f
(
x
0
)
=
3
−
4
(
3
−
2
4
+
1
)
=
2.2
{\displaystyle 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(x1 ) = 4 , f(x2 ) = -0.16 and we thus have
x
3
=
x
2
−
f
(
x
2
)
x
2
−
x
1
f
(
x
2
)
−
f
(
x
1
)
=
2.2
+
.16
(
2.2
−
3
−
.16
−
4
)
≈
2.2333.
{\displaystyle 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 3 and x 4 can be calculated, and are shown in the table below:
i
{\displaystyle i}
0
1
2
3
4
5
x
i
{\displaystyle 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
5
{\displaystyle {\sqrt {5}}}
Exercise 2
edit
Find a root of
f
(
x
)
=
x
+
e
x
{\displaystyle f(x)=x+e^{x}}
x 0 = -1 and x 1 = 0.
1st Iteration:
x 0 = -1,
x 1 = 0,
f(x0 ) = -0.63212, and
f(x1 ) = 1. Then
x
2
=
x
1
−
f
(
x
1
)
x
1
−
x
0
f
(
x
1
)
−
f
(
x
0
)
=
(
−
1
1
+
.63212
)
=
−
.6127
{\displaystyle 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 1 = 0,
x 2 = -.6127,
f(x1 ) = 1, and
f(x2 ) = -.07081. Then
x
3
=
x
2
−
f
(
x
2
)
x
2
−
x
1
f
(
x
2
)
−
f
(
x
1
)
=
−
.6127
+
.07081
(
−
.6127
−
.07081
−
1
)
=
−
.57218
{\displaystyle 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 2 = -.6127,
x 3 = -.57218,
f(x2 ) = -.07081, and
f(x3 ) = -.00789. Then
x
4
=
x
3
−
f
(
x
3
)
x
3
−
x
2
f
(
x
3
)
−
f
(
x
2
)
=
−
.57218
+
.00789
(
−
.57218
+
.6127
−
.00789
+
.07081
)
=
−
.5671
{\displaystyle 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 3 = -.57218,
x 4 = -.5671,
f(x3 ) = -.00789, and
f(x4 ) = 6.7843*
10 -5 . Then
x
5
=
x
4
−
f
(
x
4
)
x
4
−
x
3
f
(
x
4
)
−
f
(
x
3
)
=
−
.5671
−
6.7843
×
10
−
5
(
−
.5671
+
.57218
6.7843
×
10
−
5
+
.00789
)
=
−
.56714
{\displaystyle 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 4 = -.5671,
x 5 = -.56714,
f(x4 ) = 6.7843*
10 -5 , and
f(x5 ) = 5.1565*
10 -6 . Then
x
6
=
x
5
−
f
(
x
5
)
x
5
−
x
4
f
(
x
5
)
−
f
(
x
4
)
=
−
.56714
−
5.1565
×
10
−
6
(
−
.56714
+
.5671
5.1565
×
10
−
6
−
6.7843
×
10
−
5
)
=
−
.56714
{\displaystyle 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
{\displaystyle f(x)=x+e^{x}}
The following is a quiz covering information presented on the associated secant method page on Wikipedia as well as the current page.
References
edit
![{\displaystyle 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}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/429f38612dd9082120ff76c11864c8c40d53d96f)
