# 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
${\displaystyle 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, ${\displaystyle \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 ${\displaystyle \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:

{\displaystyle {\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:

${\displaystyle 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 ${\displaystyle F(\omega )={\frac {f(\omega )-f(x)}{\omega -x}}}$ where ${\displaystyle \omega =...x_{n-1},x_{n},x_{n+1},...}$. Thus

${\displaystyle 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 ${\displaystyle \zeta _{n}}$ between xn-1 and xn such that ${\displaystyle F'(\zeta _{n})={\frac {F(x_{n})-F(x_{n-1})}{x_{n}-x_{n-1}}}}$

${\displaystyle \Longleftrightarrow F(x_{n})-F(x_{n-1})=F'(\zeta _{n})(x_{n}-x_{n-1}).}$

(3)

Now using a Taylor expansion of ${\displaystyle f(x)}$ around ${\displaystyle \omega }$, we have

{\displaystyle {\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 ${\displaystyle F(x_{n})-F(x_{n-1})={\frac {(x_{n}-x_{n-1})}{2}}f''(\nu _{n})}$.

Returning to (1 ), we now have:

${\displaystyle 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 ${\displaystyle \xi _{n}}$ in [xn-1,xn] such that ${\displaystyle f'(\xi _{n})={\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$. Then (5 ) becomes:

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \mu >0}$. Our goal is to figure out what p is for the secant method.

Let ${\displaystyle S_{n}={\frac {\left\vert {e_{n+1}}\right\vert }{\left\vert {e_{n}^{p}}\right\vert }}}$
${\displaystyle \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: ${\displaystyle {\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 ${\displaystyle \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 ${\displaystyle \mu }$ is some constant. Since ${\displaystyle S_{n}}$ and ${\displaystyle S_{n-1}^{p-1}}$ are constants and ${\displaystyle \lim _{n\to \infty }e_{n}=0}$ (assuming convergence) we must have ${\displaystyle p^{2}-p-1=0}$. Thus ${\displaystyle p={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}$.[1]

## A Numerical Example

The function ${\displaystyle 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

${\displaystyle f(x_{0})=f(-3)=\sin(-3)-3e^{-3}\approx -0.2905}$

and

${\displaystyle f(x_{1})=f(-4)=\sin(-4)-4e^{-4}\approx 0.6835}$,

we have:

${\displaystyle 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

${\displaystyle 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:

 ${\displaystyle i}$ 0 1 2 3 4 5 ${\displaystyle 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 ${\displaystyle {\sqrt {5}}}$ correct to four decimal places using the secant method on ${\displaystyle f(x)=x^{2}-5}$.

### Exercise 2

Find a root of ${\displaystyle 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 ${\displaystyle 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