I was studying about the Newton's method (and other root-finding methods) and apparently Newton's method converges quadratically (or more) when it does.
Suppose that the sequence $\{x_k \}$ converges to the number $L$. We say that this sequence converges linearly to $L$, if $\exists$ a number $\mu \in (0, 1)$, such that $$\lim_{k \to \infty} \frac{|x_{k+1} – L|}{|x_{k} – L|} = \mu$$
and $\mu$ is called the rate of convergence.
Similarly, it would converge quadratically to $L$ if
$$\lim_{k \to \infty} \frac{|x_{k+1} – L|}{|x_{k} – L|^2} = \mu$$
where $\mu > 0$.
Why is that?
How can I see in practice if a sequence of iterations of the Newton's method is converging or not quadratically?
I guess I need to check for all $x_k$ that the second limit above is $\mu$ for some $\mu$ greater than $zero$…but how would I check this practically for a real concrete example?
Best Answer
A great example is to do what your calculator does when it computes $\sqrt{x}$ for some number. This way, you can see quadratic convergence in practice.
Say you want to figure out $\sqrt{17}$, this is really equivalent to finding zero's of the polynomial $f(x)=x^{2}-17$ given some initial guess.
Let's try it. Given an initial guess say, 4.2 ($4^{2}=16$ too small, and $5^2=25$, too big), we use newton's method to find the root.
$x_1=4.2-\frac{(4.2)^2-17}{8.4}=4.12380952380952381$ With error from the calculators output of $\sqrt{17}$of $|4.12380952380952380-4.12310562561766054982|=0.0007$
Let's run it again and see what happens to our error: $x_2=4.12380952380952381-\frac{(4.12380952380952381)^2-17}{2(4.12380952380952381)}=4.1231056856922907731$ with a new error of: $|4.1231056856922907731-4.12310562561766054982|\sim 6*10^{-8}$
So after one iteration we went from an error on the order of $10^{-4}$, to one of $(10^{-4})^2$, showing our error shrinking quadratically. This is really really fast, and why your calculator still uses this method.