# 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 x$_0$ 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 x$_n$ is a better approximation of the exact root, assuming convergence.
* Repeat iterative step until either
* The total number of iterations N is met
* 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 x$_{n-1}$ 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:
${\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 e$_n$=x$_n$-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 [x$_{n-1}$,x$_n$], there exists some $\zeta _{n}$ between x$_{n-1}$ and x$_n$ 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 [x$_{n-1}$,x$_n$] 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 }{\BigS_{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 x$_0$ = -3 and x$_1$ = -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(x$_1$) = .6835 and f(x$_2$) = .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 x$_4$ and x$_5$. 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.

## Exercises
### Exercise 1

Find an approximation to ${\sqrt {5}}$ correct to four decimal places using the secant method on $f(x)=x^{2}-5$.
Solution:
We know ${\sqrt {5}}=2.2361$.
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:
    $x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}=3-4({\frac {3-2}{4+1}})=2.2$
In the second iteration, f(x$_1$) = 4, f(x$_2$) = -0.16 and we thus have
    $x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}=2.2+.16({\frac {2.2-3}{-.16-4}})\approx 2.2333.$
Similarly, x$_3$ and x$_4$ can be calculated, and are shown in the table below:
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 |
| $x_{i}$ | 2 | 3 | 2.2 | 2.2333 | 2.2361 | 2.2361 |
Thus after 4 iterations, the secant method converges to 2.2361, an approximation to ${\sqrt {5}}$ correct to four decimal places.

### Exercise 2

Find a root of $f(x)=x+e^{x}$ by performing five iterations of the secant method beginning with x$_0$ = -1 and x$_1$ = 0.
Solution:
$x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}=({\frac {-1}{1+.63212}})=-.6127$
$x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}=-.6127+.07081({\frac {-.6127}{-.07081-1}})=-.57218$
$x_{4}=x_{3}-f(x_{3}){\frac {x_{3}-x_{2}}{f(x_{3})-f(x_{2})}}=-.57218+.00789({\frac {-.57218+.6127}{-.00789+.07081}})=-.5671$
$x_{5}=x_{4}-f(x_{4}){\frac {x_{4}-x_{3}}{f(x_{4})-f(x_{3})}}=-.5671-6.7843\times 10^{-5}({\frac {-.5671+.57218}{6.7843\times 10^{-5}+.00789}})=-.56714$
$x_{6}=x_{5}-f(x_{5}){\frac {x_{5}-x_{4}}{f(x_{5})-f(x_{4})}}=-.56714-5.1565\times 10^{-6}({\frac {-.56714+.5671}{5.1565\times 10^{-6}-6.7843\times 10^{-5}}})=-.56714$
Thus after 5 iterations, the method converges to -.56714 as one of the roots of $f(x)=x+e^{x}$.

## Quiz

The following is a quiz covering information presented on the associated secant method page on Wikipedia as well as the current page.