In practice, what does it mean for the Newton's method to converge quadratically (when it converges)?

Question

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?

Answer 1

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.

Answer 2

1. Why is that?

Because of the definitions you quoted, and the way that Newton's Method is defined. The point of linear, quadratic, etc. convergence is that it measures in a sense how fast the sequence of approximations will converge to the correct answer. It is not trivial, but also not terribly difficult, to prove directly that when Newton's Method converges, it does so quadratically (or better). Exception: If the root desired is of multiplicity greater than 1, then the convergence rate is only linear.

2. How can I see in practice if a sequence of iterations of the Newton's method is converging or not quadratically?

For this, the rate of convergence is not as important and having a criterion for determining whether or not Newton's Method will converge. A sufficient condition for convergence of Newton's Method is known (I don't recall exactly what it is off the top of my head). If you have established that it does in fact converge, then you can verify whether it is quadratic or not by checking the relevant limit(s) (typically, if it's better than quadratic, that is because one of the iterations landed exactly on the correct solution, hence it is no longer an approximation but the actual exact answer).

Answer 3

Let $\epsilon_n=|x_n-L|$ be the error on the $n$th step. Supposing the claimed limit does indeed hold, this means

$$\frac{\epsilon_{n+1}}{\epsilon_n^2}\sim\mu\implies\epsilon_{n+1}\simeq\mu\epsilon_n^2$$

i.e. the error on the next step is roughly a quadratic function of the error on the current step (hence the name). Similarly for linear convergence,

$$\epsilon_{n+1}\simeq\mu\epsilon_n$$

is a linear function of the current error.

Visually, however, one cannot easily "see" the value of $\epsilon_n$, but rather $\log(\epsilon_n)$, the number of digits accurate. Taking the logarithm of both sides, one may see that quadratic convergence implies

$$\log(\epsilon_{n+1})\simeq2\log(\epsilon_n)+\log(\mu)\simeq2\log(\epsilon_n)$$

meaning that the amount of digits accurate per iteration will double. You may obtain the order of convergence by observing the limit

$$\frac{\log(\epsilon_{n+1})}{\log(\epsilon_n)}\to2\quad(\text{or 1 for linear convergence})$$

with the additional caveat that the second term, $\log(\mu)$, is bounded (and less than $0$ for linear convergence), though usually if it isn't one doesn't worry too much about it.

For example, let us estimate $\sqrt2$ using Newton's method starting from $x_0=1$.

\begin{array}{c|c} n&x_n\\\hline 0&1.000000000\\ 1&1.500000000\\ 2&1.\underline{41}6666666\\ 3&1.\underline{41421}5686\\ 4&1.\underline{414213562}\\ 5&1.414213562 \end{array}

It is easy to visually see that the number of digits accurate will roughly double per iteration.

---

If your question concerns why Newton's method (usually) converges quadratically, the proof follows from a quick Taylor expansion:

$$f(L)=f(x)+f'(x)(L-x)+\underbrace{\frac12f''(\xi)(L-x)^2}_{\mathcal O(\epsilon_n^2)}$$

Letting $f(L)=0$ and solving for $L$ from the second term leads to

$$L=\underbrace{x-\frac{f(x)}{f'(x)}}_{x_\mathrm{newton}}-\underbrace{\frac12\frac{f''(\xi)}{f'(x)}(L-x)^2}_{\mathcal O(\epsilon_n^2)}$$

which shows that

$$\epsilon_{n+1}=|L-x_\mathrm{newton}|=\left|\frac12\frac{f''(\xi)}{f'(x)}(L-x)^2\right|\simeq\mu\epsilon_n^2$$