Secant method with double roots

Question

The order of convergence of the secant method is the golden number. Knowing that the function $f$ satisfies $f(r)=0$ and $f'(r)$ is not 0. What is the order of convergence if f has a double root? (When $f(r)=f'(r)=0$)

Answer 1

For a root of order $d>1$, such as a double root $d=2$, the convergence is linear (order $=1$). In more extreme cases, the cases, the convergence may be sublinear.

The rate at which the secant method converges for higher order roots is somewhat strange. The secant method has a tendency of making more progress every other iteration and less progress on others.

It can be easily solved for the "middle" point where all iterations progress towards the root at roughly the same speed. This may be done by observing the case of $f(x)=|x|^d$ with the points $x_0=x>1$ and $x_1=1$ to get

$$x_2=\frac{1\cdot|x|^d-x\cdot|1|^d}{|x|^d-|1|^d}=\frac{x^d-x}{x^d-1}$$

and solving for when the ratios $x_2/x_1=x_2$ and $x_1/x_0=1/x$ are equal. Setting them so gives the equation

$$\frac{x^d-x}{x^d-1}=\frac1x$$

$$x^{d+1}-x^d-x^2-1=0$$

In the case of $d=2$, we have

$$x^3-2x^2-1=0$$

$$x\approx2.2056$$

Thus it can be expected that the secant method will give results roughly $2.2056$ times closer to the root each iteration. One can furthermore see that

$$x_2=\frac{x^2-x}{x^2-1}=\frac x{x+1}\le\frac x2$$

which confirms the secant method at least halves the error on every two iterations. For $x$ arbitrarily large, one can also see that $x_2$ may be arbitrarily close to $x_1$, reaffirming the claim that the secant method has a tendency to rapidly converge every other iteration (in this case $x_0\to x_1$) but slowly on the next iteration (in this case $x_1\to x_2$).