Numerical Analysis/The Secant Method

< Numerical Analysis

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 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 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

  1. The total number of iterations N is met
  2. 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 xn-1 and xn 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 en: en=xn-x. Then we have:

\begin{align}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_nf(x_{n-1})}{f(x_n)-f(x_{n-1})} \\&=e_ne_{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{align}.

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

e_{n+1}=e_ne_{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 [xn-1,xn], there exists some \zeta_n between xn-1 and xn 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{align}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{align}

 

 

 

 

(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_ne_{n-1}\Bigg(\frac{F(x_n)-F(x_{n-1})}{f(x_n)-f(x_{n-1})}\Bigg)=\frac{e_ne_{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 [xn-1,xn] 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_ne_{n-1}\frac{f''(\nu_n)}{2f'(\xi_n)}\approx e_ne_{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_nS_{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_nS_{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_nS_{n-1}^{p-1}\left\vert {e_{n-1}}\right\vert^{p^2-p-1}.

We want \lim_{n \to \infty}\Big(S_nS_{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.[1]

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 x0 = -3 and x1 = -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(x1) = .6835 and f(x2) = .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 x4 and x5. 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.

Exercise 2

Find a root of f(x)=x+e^x by performing five iterations of the secant method beginning with x0 = -1 and x1 = 0.

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 x0 = 1 and x1 = 2. Then x2 is equal to:

1.2311
1.5714
1.6231
1.7312

Your score is 0 / 0

References

  1. ↑ http://www.radford.edu/~thompson/Fall10/434/Chapter4/secant_convergence.pdf
This article is issued from Wikiversity - version of the Saturday, April 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.