Numerical Analysis/The Secant Method

The Secant Method

edit

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 x0 and x 1 be initial approximations.

Then
 

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,  , is achieved.

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

 .

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

 

 

 

 

 

(1)

Next, let's just consider the numerator in (1). Let   where  . Thus

 

 

 

 

 

(2)

According to the Mean Value Theorem, on [xn-1,xn], there exists some   between xn-1 and xn such that  

 

 

 

 

 

(3)

Now using a Taylor expansion of   around  , we have

 

 

 

 

 

(4)

Next, we can combine equations (2), (3), and (4) to show that  .

Returning to (1), we now have:

 

 

 

 

 

(5)

Again applying the Mean Value Theorem, there exists some   in [xn-1,xn] such that  . Then (5) becomes:

 

Next, recall that we have convergence of order p when   for some constant  . Our goal is to figure out what p is for the secant method.

Let  
 .

Then we have:  .

We want  , again where   is some constant. Since   and   are constants and   (assuming convergence) we must have  . Thus  .[1]

A Numerical Example

edit

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

 


and

 ,


we have:

 

In the next iteration, we use f(x1) = .6835 and f(x2) = .0342 and see that

 

Similarly, we can compute x4 and x5. These calculations have been organized in the table below:

  0 1 2 3 4 5
  -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   correct to four decimal places using the secant method on  .

Exercise 2

edit

Find a root of   by performing five iterations of the secant method beginning with x0 = -1 and x1 = 0.

Quiz

edit

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


References

edit