Superlinear convergence of the secant method

Remarks

The secant method satisfies $e_{k+1} = C_k e_k e_{k-1}$ with $C_k \to C = f''(r)/(2f'(r))$. Clause 1 follows at once: $\abs{e_{k+1}}/\abs{e_k} = \abs{C_k} \abs{e_{k-1}} \to 0$. For clause 2, the logarithms $y_k = \log \abs{e_k}$ satisfy approximately $y_{k+1} = y_k + y_{k-1} + \log \abs{C}$. This is a Fibonacci-type recursion, whose solutions grow like $\varphi^k$. A careful version of this argument gives the limit; the exponent $\varphi - 1 = 1/\varphi$ comes from $\varphi^2 = \varphi + 1$. Example: for $f(x) = x^2 - 2$ from $x_0 = 1$, $x_1 = 2$, the errors are about $4.1 \times 10^{-1}$, $5.9 \times 10^{-1}$, $8.1 \times 10^{-2}$, $1.4 \times 10^{-2}$, $4.2 \times 10^{-4}$, $2.1 \times 10^{-6}$, $3.2 \times 10^{-10}$. Once the errors are small, the number of correct digits grows by a factor of about $1.6$ per step. At a zero with $f'(r) = 0$ the conclusion fails: for $f(x) = x^2$ the convergence is only linear.

Going deeper

For a student

In terms of rate of convergence, the secant method has order $\varphi \approx 1.618$ and Newton's method has order $2$. One Newton step costs a value of $f$ and a value of $f'$. If these cost about the same, two secant steps cost as much as one Newton step, and together they have order $\varphi^2 \approx 2.618 > 2$. This efficiency is why secant-type steps appear in practical solvers such as Brent's method. The appearance of the golden ratio comes from the recursion $e_{k+1} \approx C e_k e_{k-1}$, whose exponents follow the Fibonacci numbers.