Finding Newton method order of convergence

Question

I'm trying to determine how you find the order of convergence of newton's method. I have the formula $$\frac {|x^*-x_{n+1}|}{ |x^*-x_n|^q} = \alpha$$ I'm setting $q=2$ to test for quadratic convergence and as far as I know, if $\alpha > 0$ then the convergence is quadratic.

Approximate results for root from Newtons method with initial guess $-2$:

$$-2.45819577, -2.32858671, -2.31342784, -2.31322658$$

If I apply the formula, for each iteration, I get $\alpha$ values as: $0.7308756055$, $0.8530366402$, $0$

Which does not make sense $\alpha$ should be $> 0$ since Newton convergences quadratically when the initial guess is close to the root?

Answer 1

As you said, α (asymptotic error constant) does change along the iterations, but theorically, in order to be able to calculate the order, you should assume that once its reaching the convergence, it does not change and remains constant. So, in that scenario: $$ \frac {|x^*-x_{n+1}|}{ |x^*-x_n|^q} = \alpha \\ \frac {|x^*-x_{n}|}{ |x^*-x_{n-1}|^q} = \alpha $$

Given that, you can expand with math :

$$ |x^*-x_{n+1}|\cdot|x^*-x_{n-1}|^q = |x^*-x_{n}|\cdot |x^*-x_n|^q \\ ln(|x^*-x_{n+1}|) +q \cdot ln(|x^*-x_{n-1}|) = ln(|x^*-x_{n}|) + q \cdot ln(|x^*-x_n|) \\ ln(|x^*-x_{n+1}|) - ln(|x^*-x_{n}|)= q \cdot ln(|x^*-x_n|) - q \cdot ln(|x^*-x_{n-1}|) \\ ln(\frac{|x^*-x_{n+1}|}{|x^*-x_{n}|}) = q \cdot ln(\frac{|x^*-x_n|}{|x^*-x_{n-1}|}) \\ \therefore q \simeq \frac{ln(\frac{|x^*-x_{n+1}|}{|x^*-x_{n}|})}{ln(\frac{|x^*-x_n|}{|x^*-x_{n-1}|})} $$

Now, with yours results given, with a simple code:

import numpy as np

a = np.array([ -2.45819577, -2.32858671, -2.31342784,-2.31322658 ])

np.log( np.absolute(a[3]-a[2]) / np.absolute(a[2] - a[1]) ) / np.log(  np.absolute(a[2] - a[1]) /  np.absolute(a[1] - a[0]) )

we can calculate the convergence order which gives us $$ q \simeq 2.013 $$ which confirms the convergence order of Newton-Raphson method.