4.6 Miscellaneous methods

#%config InlineBackend.figure_format = 'svg'
from pylab import *

The secant method approximates the function by an affine polynomial and finds the root of the polynomial. We can improve this method by constructing a quadratic polynomial approximation.

4.6.1Muller’s method¶

Given three initial guesses $x_0, x_1, x_2$, construct a quadratic polynomial $p(x)$ such that

The next approximation to the root $x_3$ is taken as the root of $p$

We can write the Newton form of the interpolating polynomial^[1]

or equivalently

where

Now find the root $x_3$ that is closest to $x_2$

We have to choose the sign in the numerator that leads to small numerator. However this can lead to loss of significant figures. We can rewrite this as

Now we choose sign in denominator so that denominator is large in magnitude. We apply this algorithm recursively to obtain a sequence of iterates $\{ x_n \}$. If $x_n \to \alpha$ and $f'(\alpha) \ne 0$, then $\alpha$ is a root of $f$. To prove this, show that

so that in the limit the iteration looks like

But $f'(\alpha) \ne 0$ and so the denominator is not zero, which implies that $f(\alpha) = 0$.

The order of convergence $p \approx 1.84$ and is a root of

So this method converges faster than secant method but slower than Newton-Raphson method. Moreover

Muller’s method can give rise to complex roots even when starting with real initial guesses.

4.6.2Inverse quadratic interpolation¶

We treat $x$ as a function of $f$, i.e., $x = x(f)$. Like in Muller’s method, let us take $x_0, x_1,x_2$ and $f_i = f(x_i)$, $i=0,1,2$, but now construct an approximation

such that

Once the quadratic polynomial $q$ is found, we estimate the root as

This can be used to generate the iteration

Note that all the iterates will be real if we start with real initial guess.

4.6.3Linear fractional method¶

Suppose $f(x)$ has a vertical and horizontal asymptote, e.g., $f(x) = \frac{1}{x} - a$. Then the secant method may not converge, see figure (xxx), where $x_3$ can go to $-\infty$. Instead of linear approximation, we can use a fractional approximation.

Given $x_0, x_1, x_2$, fit a rational polynomial

using

The solution is simplified if we shift the origin, $y = x - x_2$ and

The next approximation is $x_3 = x_2 + a$.