The Secant Method

We can obtain this from Newton's method by replacing the tangent slope f'(x) by the chord or secant slope $\frac{f(x)-f(x-h)}{h}$. Using a Taylor expansion of f about x, we find

$$\begin{array} {lcl}\frac{f(x)-f(x-h)}{h} & = & \frac{f(x)+hf... ...f(x)}{h}\\ & = & f'(x)+\frac{h}{2}f''(x+\theta h), \end{array}$$

so that the error is O(h) if f'' is bounded. The obvious choice for h is so that if x=x_n, the nth iterate, x-h=x_n-1, the previous iterate. Putting this into Newton's method, we obtain

$$\begin{array} {lcl}x_{n+1} & = & x_n-\frac{f(x_n)}{\{ f(x_n)... ... x_n-\frac{f(x_n)(x_n-x_{n-1})}{f(x_n)-f(x_{n-1})}.\end{array}$$

In this method, f has to be evaluated just once on each iteration, while f' does not have to be evaluated at all. However, it does need two starting values.

The formula can be written with a common denominator as  

$$x_{n+1}=\frac{x_{n-1}f(x_n)-x_nf(x_{n-1})} {f(x_n)-f(x_{n-1})},$$ (2)

which is recognisable as the formula for inverse interpolation, that is, it linearly interpolates the values of f at x_n and x_n-1 to approximate the value of x at which f vanishes. This form should not be used in practical evaluation, since it computes the ratio of two quantities which are liable to be differences of nearly equal numbers.

This formulation suggests a variant of the method, in which convergence is guaranteed provided starting values can be found for which the values of f are opposite in sign. This is defined by

$$x_{n+1}=\frac{x_mf(x_n)-x_nf(x_m)}{f(x_n)-f(x_m)},$$

where $m\leq n-1$ is the greatest index for which $\, {\rm sgn}\, f_m\not= \, {\rm sgn}\, f_n$. Convergence is guaranteed because there is always a zero of f between x_n and x_m. The rate of convergence is better than linear, but not as good as that of the original secant method.

Example Evaluate $\sqrt{15}$.

We use the secant method to solve the equation x²-15=0. The secant formula is

$$\begin{array} {lcl}x_{n+1} & = & x_n-\frac{(x_n^2-15)(x_n-x_... ...{n-1}^2}\\ & = & x_n-\frac{x_n^2-15}{x_n+x_{n-1}}. \end{array}$$

Starting with x₀=3, x₁=4, we calculate to 9D successively x₂=3.857142857,  x₄=3.872983871, x₅=3.872983347,x₆=3.872983347. This looks nearly as good as Newton's method, but our starting values were fairly close.