Let be a differentiable function from to . Newton’s method consists of starting at an for the equation . Then the function is linearized at by replacing the increment by a linear function of the increment .
Now we can solve the linear equation . Since this is a system of n linear equations in n unknowns, can be likened to the general linear system .
Therefore, if is invertible, then . By renaming to , you can reiterate Newton’s method to get an . Thus, Newton’s method states
Thus we get a series of ’s that we hope will converge to such that . When we solve an equation of the form , we call the solution a root of the equation. Thus, Newton’s method is used to find roots of nonlinear equations.
Unfortunately, Newton’s method does not always converge. There are tests for neighborhoods of ’s where Newton’s method will converge however. One such test is Kantorovitch’s theorem, which combines what is needed into a concise mathematical equation.
Corollary 1: Newton’s Method in one dimension - The above equation is simplified in one dimension to the well-used
This intuitively cute equation is pretty much the equation of first year calculus. :)
Corollary 2: Finding a square root - So now that you know the equation, you need to know how to use it, as it is an algorithm. The construction of the primary equation, of course is the important part. Let’s see how you do it if you want to find a square root of a number b.
We want to find a number x (x for unknown), such that . You might think “why not find a number such that ?” Well, the problem with that approach is that we don’t have a value for , so we’d be right back where we started. However, squaring both sides of the equation to get lets us work with the number we do know, .) Back to . With some manipulation, we see this means that ! Thus we have our scenario.
We can see that thus, and . Now we have all we need to carry out Newton’s method. By renaming to be , we have
The equation on the far right is also known as the divide and average method, for those who have not learned the full Newton’s method, and just want a fast way to find square roots. Let’s see how this works out to find the square root of a number like 2:
Thus, by Newton’s method,…
All we did was plug in the expressions and where Newton’s method asks for them. Now we have to pick an . Hmm, since
let’s pick a reasonable number between 1 and 2 like 1.5
Looks like our guess was too high. Let’s see what the next iteration says
getting better =) You can use your calculator to find that
Geometric Interpretation: Consider an arbitrary function such as . Say you wanted to find a root of this function. You know that in the neighborhood of , there is a root (Maybe you used Kantorovitch’s theorem or tested and saw that the function changed signs in this neighborhood). We want to use our knowledge to find an that is a better approximation to (in this case, closer to it on the x-axis).
So we know that or in another case . What is an efficient algorithm to bridge the gap between and ? Let’s look at a tangent line to the graph.
Note that the line intercepts the x-axis between and , which is exactly what we want. The slope of this tangent line is by definition of the derivative at , and we know one point on the line is , since that is the x-intercept. That is all we need to find the formula of the line, and solve for .
|Aesthetic change. Flipped the equation around.|
|Date of creation||2013-03-22 11:58:05|
|Last modified on||2013-03-22 11:58:05|
|Last modified by||alozano (2414)|