Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I find many sites explaining how to use Newton's method, but none explaining why it works. Could someone give me the intuition behind it? Thanks.

share|improve this question
2  
Somebody must have provided a picture. Let $x_n$ be our current estimate. Then the next estimate $x_{n+1}$ is obtained as follows. Draw the tangent line at $(x_n, f(x_n))$. Then $x_{n+1}$ is the point where the tangent line meets the $x$-axis. Draw a smooth curve that crosses the $x$-axis at $r$. Let $x_n$ be close to $r$. Draw the tangent line described above. It meets the $x$-axis at a point often much closer to $r$ than $x_n$ is. –  André Nicolas Apr 4 '13 at 3:18
1  
One thing to note is that it doesn't always work. –  Thomas Andrews Apr 4 '13 at 4:04
1  
There are two Newton's method, one for root finding and one for optimisation. While the two are closely related, the community can offer better help if you could clarify which Newton's method you are talking about. –  user1551 Apr 4 '13 at 4:37
    
@user1551, ...and the "optimization" version is more or less applying the "root finding" version to the derivative of your function, of course. –  J. M. Apr 4 '13 at 5:21
1  
@J.M. Sure, but seeing that all you guys here were only talking about the "root finding" version, if the OP was asking about the "optimisation" version, I thought he might be puzzled. :-D –  user1551 Apr 4 '13 at 5:36

2 Answers 2

up vote 16 down vote accepted

The method is easiest to justify in one dimension. Say that I have some complicated function $f(x)$ whose root I want to find:

some dumb function

"I don't know how to find its root; it's complicated!" Thus, we use a general idea that has always been used in the design of numerical methods:

Replace a complicated function with a simple approximation.

One of the simplest functions one can deal with is a linear function:

$$f(x)=mx+b$$

In particular, if you want the root of a linear function, it's quite easily figured:

$$x=-\frac{b}{m}$$

Now, it is well-known (or at least, ought to be) that the tangent line of a function is the "best" linear approximation of a function in the vicinity of its point of tangency:

dumb function with tangent line

The first idea of the Newton-Raphson method is that, since it is easy to find the root of a linear function, we pretend that our complicated function is a line, and then find the root of a line, with the hope that the line's crossing is an excellent approximation to the root we actually need.

Mathematically, if we have the tangent line of $f(x)$ at $x=a$, where $a$ is the "starting point":

$$f(x)\approx f(a)+f^\prime(a)(x-a)=0$$

If we want $x$, then

$$x=a-\frac{f(a)}{f^\prime(a)}$$

Let's call this $x_1$.

dumb function with tangent and approximate root

As you can see, the blue point corresponding to the approximation is a bit far off, which brings us to the second idea of Newton-Raphson: if at first you don't succeed, try again:

dumb function with new root approximation

As you can see, the new blue point is much nearer to the red point. Mathematically, this corresponds to finding the root of the new tangent line at $x=x_1$:

$$x_2=x_1-\frac{f(x_1)}{f^\prime(x_1)}$$

We can keep playing this game (with $x_2, x_3, \dots x_n$), up until the point that we find a value where the quantity $\dfrac{f(x_n)}{f^\prime(x_n)}$ is "tiny". We then say that we have converged to an approximation of the root. That is the essence of Newton-Raphson.

As an aside, the previous discussion should tip you on what might happen if the tangent line is nearly horizontal, which is one of the disastrous things that can happen while applying the method.

share|improve this answer
1  
Great Answer, thanks a lot! –  user70518 Apr 4 '13 at 5:13
    
A minor quibble to a great answer: in the third graph I would mark the point of tangency with blue to show the function value at the first approximation, then make the new putative root some other color. –  Ross Millikan May 19 '13 at 4:41
    
@Ross, I'll see if I can redo the images later; I lost the code for generating them... anyway, the idea I had with the coloring is to denote the previous approximation with a lighter hue than the current one, as if leaving a "shadow". –  J. M. May 19 '13 at 4:45
    
+1 Excellent answer, really intuitive :) –  jjepsuomi Jul 11 '13 at 8:56

This animation from the Wikipedia page for Newton's Method might be useful:

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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