Numerical Analysis/The Secant Method

From Wikiversity
Jump to navigation Jump to search

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]