Convergence Rate of Secant Method

Subtracting $\alpha$ from both sides of equation (), we find

$$\begin{array} {lcl}x_{n+1}-\alpha & = & \frac{(x_{n-1}-\alph... ...)(x_{n-1}-\alpha )\frac{f''(\xi _n)}{f'(\eta _n)} .\end{array}$$

with values of $\xi _n,\eta _n$ in appropriate intervals. Set $e_n=\left\vert \kern.05em x_n-\alpha \kern.05em \right\vert,~\left\vert \kern.05em \frac{f''(\xi _n)}{f'(\eta _n)} \kern.05em \right\vert=\kappa _{n-1}$ for $n=0,1,\ldots$; then

$$e_{n+1}=\kappa _{n-1}e_ne_{n-1}.$$

Increasing each subscript by 1, taking logs and setting $v_n=\log e_n, ~c_n=\log \kappa _n$, we obtain the difference equation

v_n+2-v_n+1-v_n=c_n.

We use the displacement operator, E, defined by Ev_n=v_n+1 to write this as (E²-E-1)v_n=c_n, or (E-q)(E-p)v_n=c_n, where $p=\frac{1+\sqrt{5}}{2},~q=\frac{1-\sqrt{5}}{2}$. Now set

 

(E-p)v_n=u_n, (3)

whence we obtain

$$\begin{array} {lcl}u_n & = & c_{n-1}+qu_{n-1}\\ & = & c_{n-1... ... & = & c_{n-1}+qc_{n-2}+\cdots +q^{n-1}c_0+q^nu_0. \end{array}$$

Putting this back into (), we find

$$v_{n+1}-pv_n=c_{n-1}+qc_{n-2}+\cdots +q^{n-1}c_0+q^n(v_1-pv_0).$$

Provided that the $c_i,~i=0,1,\ldots ,c_{n-1}$ are all of the same sign, the first n terms of the right hand side form an alternating series, since -1<q<0, and so $v_{n+1}-pv_n\to L$, say, where $\left\vert \kern.05em L \kern.05em \right\vert<\infty$,which gives

$$\frac{e_{n+1}}{e_n^p}\to e^L.$$

This gives the order of the secant method as $p=\frac{1+\sqrt{5}}{2}\approx 1.618$; as we had suspected, the rate of convergence is somewhere between linear and second order. In order to be sure that $c_1,c_2,\ldots ,c_n$ are of the same sign, we need $\kappa _1,\kappa _2,\ldots ,\kappa _n$ to be all greater than 1 or all less than 1. Since $\kappa _n\to \left\vert \kern.05em \frac{f''(\alpha )}{f'(\alpha )} \kern.05em \right\vert$, we can achieve this by starting with an x₀ sufficiently near to $\alpha$.

Finally, there is a classical variant of the secant method, which is defined by

$$x_{n+1}=\frac{x_0f(x_n)-x_nf(x_0)}{f(x_n)-f(x_0)}.$$

Here the first and last values of the iterate are used. Following through the convergence analysis above, we find

$$x_{n+1}-\alpha =\frac{1}{2}(x_0-\alpha )(x_n-\alpha )\frac{f''(\xi )}{f'(\eta )},$$

which shows that the convergence is only linear.