# 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{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 en=xn-x, we can rewrite the last line above as:

$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 ). 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{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 ), 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_{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 $\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_{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\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_{n}S_{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_{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\to \infty }{\Big (}S_{n}S_{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$ .

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