[Math] Finding convergence rate for Bisection, Newton, Secant Methods

Question

I have implemented the bisection, Newton, and secant methods for solving nonlinear equations in one dimension. I know my methods work to find at least one root, however how would I go about solving for the convergence rate for each method? For example if my nonlinear equation is $x^3 – 2x – 5 = 0$ and I use the bisection method, I get a root of $2.09455$, however I am not sure how I can use this to find the convergence rate.

Answer 1

The convergence rate connects the error in one step with the error in another step by $$|x_{n+1} - x| \leqslant c |x_{n} - x|^p$$

So if $$\lim_{n→∞}\frac{|x_{n+1}-x|}{|x_n-x|^p}>0$$ you have convergence of order $p$.

Since you usually don't know the exact solution you can use the following formula:

$$ p\approx \frac{\log|\frac{x_{n+1}-x_n}{x_n-x_{n-1}}|}{\log|\frac{x_{n}-x_{n-1}}{x_{n-1}-x_{n-2}}|}$$

You should expect results around $1$ for the bisection method, increasing convergence up to $1.6$ for the secant method and increasing convergence up to $2$ for Newton's method.