Convergence of Secant method or IQI

Question

We have drawn a graph that shows that the methods do converge but is it possible to obtain values for the rate of convergence of the secant and inverse quadratic interpolation methods for a particular function on MATLAB?

Thank you!

Answer 1

It can be proven that the rate of convergence of the secant method is superlinear (meaning, better than linear but less than quadratic).

Theorem

Convergence of the Secant method. Suppose that $f$ and its first two derivatives are continuous in an interval $I$ that contains a zero $c$ of $f$ , and suppose that there exists a positive constant $\gamma$ such that $|f'(x)| \gt \gamma \gt 0$ for all $x$ in $I$. Then there exists a constant $M$ such that for all starting values $x_0$ and $x_1$ sufficiently close to $c$, the sequence produced by the Secant Method will converge to $c$ and the error $e_n = c- x_n$ will satisfy

$$|e_n| \lt M~|e_{n-1}|^r, n = 2, 3, \ldots,$$

where

$$r = \dfrac{1}{2} ( 1 + \sqrt{5}) \approx 1.618033988749894848204587.$$

Observation When the Secant method converges to a zero $c$ with $f'(c) \ne 0$, the number of correct digits increases by about $62 \%$ per iteration.

Example

$$f(x) = x^2 - 2, (x_0, x_1) = (1.5, 2.0)$$

The exact root of this is (lets use $25-$digits of accuracy):

$$c = \sqrt{2} \approx 1.414213562373095048801688$$

Using Taylor's Theorem, we can find $M$ as:

$M = \left|\dfrac{f''(c)}{2f'(c)}\right|^{r-1} = \left|\dfrac{f''(\sqrt{2})}{2f'(\sqrt{2})} \right|^{0.618033} = \left|\dfrac{2}{2\sqrt{2}} \right|^{0.618033} = 0.525932303452186758952445$

Using the Secant Method, we generate the following iterates:

$$ \begin{array}{c|cccc} n & x_n & x_{n+1}-x_{n} & e_n = c - x_n \\ \hline 1 & 1.500000000000000000000000 & 0.500000000000000000000000 & - \\ 2 & 2.000000000000000000000000 & 0.571428571428571428571429 & - \\ 3 & 1.428571428571428571428571 & 0.011904761904761904761905 & 1.435786619833352262688 \times 10^{-2} \\ 4 & 1.416666666666666666666667 & 0.002440725244072524407252 & 2.45310429357161786498 \times 10^{-3} \\ 5 & 1.414225941422594142259414 & 0.000012368322458657593815 & 1.237904949909345773 \times 10^{-5} \\ 6 & 1.414213573100135484665599 & 1.0726993487515235 \times 10^{-8} & 1.072704043586391 \times 10^{-8} \\ 7 & 1.414213562373141997150364 & 4.6948348497 \times 10^{-14} & 4.694834868 \times 10^{-14} \\ 8 & 1.414213562373095048801867 & 1.78 \times 10^{-22} & 1.8 \times 10^{-22} & \end{array} $$

Now, using the above data (or the data in your problem), just compare and verify:

$$|~e_{n+1}~| \approx |e_n|^{1.618} \left| \dfrac{f''(c)}{2f'(c)}\right|^{0.618}$$

All of this tells you that the convergence rate for the Secant Method is:

$$r = \dfrac{1}{2} ( 1 + \sqrt{5}) \approx 1.618033988749894848204587.$$