2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It means that instead of gaining say another correct decimal after each iteration, you typically double the number of correct decimals each time. So it converges fast. $\endgroup$ – Captain Lama Apr 9 '16 at 21:41
  • $\begingroup$ @CaptainLama I observed in some calculations that I did that it seems that the $x_k$ is behaving similarly to what you're saying, i.e. suppose that at a certain iteration $x_k = 0.00012312..$, at the next one maybe it is something like $x_k = 0.000000123..$. But what's the relation between this and the definitions above in my question? It would be nice to see a concrete example where it's applied the definition, say. $\endgroup$ – nbro Apr 9 '16 at 21:43
  • $\begingroup$ It doubles the number of zeros of the error after the decimal point every iteration. Basically it means it is very fast. $\endgroup$ – copper.hat Apr 9 '16 at 21:46
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We can also see the error by simply inserting into the formula $x^2 - 17$ the $x_i$ that we find, right? Or would it be different? $\endgroup$ – nbro Apr 10 '16 at 9:54
  • $\begingroup$ No different! I just wanted to show how quickly we approximate calculator values $\endgroup$ – qbert Apr 10 '16 at 13:50
  • $\begingroup$ Ok, thanks. But of course it's not necessarily and strictly true that every time the number 0s after the dot doubles, it could double $-1$ or $+1$... But in general that should be the behaviour, right? $\endgroup$ – nbro Apr 10 '16 at 13:51
  • $\begingroup$ I'm not sure what you mean by double 1 or -1 but no not strictly true, just an illustration $\endgroup$ – qbert Apr 10 '16 at 13:55
0
$\begingroup$
  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.

  1. 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).

$\endgroup$
  • $\begingroup$ "when Newton's Method converges, it does so quadratically" ...as long as the derivative of the function is nonzero at the root. $\endgroup$ – Rahul Apr 10 '16 at 1:47
  • $\begingroup$ Right, forgot that little detail (been quite some time since I dealt with the Newton-Raphson Method), $\endgroup$ – Justin Benfield Apr 10 '16 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.