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 x_{0} and x _{1} be initial approximations. where x_{n} is a better approximation of the exact root, assuming convergence. Repeat iterative step until either

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 x_{n1} 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:
.
Since f(x)=0 and recalling that e_{n}=x_{n}x, we can rewrite the last line above as:

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

(
)
According to the Mean Value Theorem, on [x_{n1},x_{n}], there exists some between x_{n1} and x_{n} such that

(
)
Now using a Taylor expansion of around , we have

(
)
Next, we can combine equations (2), (3), and (4) to show that .
Returning to (1), we now have:

(
)
Again applying the Mean Value Theorem, there exists some in [x_{n1},x_{n}] 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 x_{0} = 3 and x_{1} = 4.
Next, using our recurrence formula where
and
we have:
In the next iteration, we use f(x_{1}) = .6835 and f(x_{2}) = .0342 and see that
Similarly, we can compute x_{4} and x_{5}. 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=x1y1*(x1x0)/(y1y0)
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 .
Solution:
We know .
Let x_{0} = 2 and x_{1} = 3. Then f(x_{0}) = f(2) = 1 and f(x_{1}) = f(3) = 4.
In our first iteration, we have:
In the second iteration, f(x_{1}) = 4, f(x_{2}) = 0.16 and we thus have
Similarly, x_{3} and x_{4} can be calculated, and are shown in the table below:
0  1  2  3  4  5  
2  3  2.2  2.2333  2.2361  2.2361 
Thus after 4 iterations, the secant method converges to 2.2361, an approximation to correct to four decimal places.
Exercise 2 edit
Find a root of by performing five iterations of the secant method beginning with x_{0} = 1 and x_{1} = 0.
Solution:
2nd Iteration: x_{1} = 0, x_{2} = .6127, f(x_{1}) = 1, and f(x_{2}) = .07081. Then
3rd Iteration: x_{2} = .6127, x_{3} = .57218, f(x_{2}) = .07081, and f(x_{3}) = .00789. Then
4th Iteration: x_{3} = .57218, x_{4} = .5671, f(x_{3}) = .00789, and f(x_{4}) = 6.7843*10^{5}. Then
5th Iteration: x_{4} = .5671, x_{5} = .56714, f(x_{4}) = 6.7843*10^{5}, and f(x_{5}) = 5.1565*10^{6}. Then
Thus after 5 iterations, the method converges to .56714 as one of the roots of .
Quiz edit
The following is a quiz covering information presented on the associated secant method page on Wikipedia as well as the current page.