## Newton's Method

Sometimes we are presented with a problem which cannot be solved by simple algebraic means. For instance, if we needed to find the roots of the polynomial , we would find that the tried and true techniques just wouldn't work. However, we will see that calculus gives us a way of finding approximate solutions.

A Simple Example

Let's start by computing . Of course, this is easy if you have a calculator, but it is a simple example which will illustrate a more general method.

First, we'll think about the problem in a slightly different way. We are looking for which is a solution of the equation .

The problem is that it is difficult to generate a numerical solution to this equation. But remember in the section on approximations , we saw how to approximate a function near a given point by its tangent line. The idea here will be to actually solve the approximate equation which is easy since it is a linear one.

If we think for a minute, we know that is between 2 and 3 so let's just choose to use the linear approximation at . We know that so that . The linear approximation is then

Notice that the linear equation is easy to solve. We will then approximate the solution to by the solution to which is . If you have a look on a calculator, you will see that . So you can see that we have found a fairly good approximation.

We can understand what we have done graphically. We are looking for a solution to which is where the graph of crosses the x-axis. We approximate that point by the point where the tangent line crosses the x-axis.

Now this is where the story becomes interesting since we can repeat what we have just done using the new approximate solution. That is, we will call and consider the linear approximation at that point.

Now if we call the solution to , we find that which is an even better approximate solution to the equation. We could continue this process generating better approximations to at every step. This is the basic idea of a technique known as Newton's Method.

The general method

More generally, we can try to generate approximate solutions to the equation using the same idea. Suppose that is some point which we suspect is near a solution. We can form the linear approximation at and solve the linear equation instead.

That is, we will call the solution to . In other words,

If our first guess was a good one, the approximate solution should be an even better approximation to the solution of . Once we have , we can repeat the process to obtain , the solution to the linear equation

Solving in the same way, we see that

Maybe now you see that we can repeat this process indefinitely: from , we generate and so on. If, after n steps, we have an approximate solution , then the next step is

Provided we have started with a good value for , this will produce approximate solutions to any degree of accuracy.

A realistic example

Let's now consider an example in which we want to find the roots of the polynomial . This is not found through any conventional means available to us so we can try to use Newton's method.

The sketch of the graph will tell us that this polynomial has exactly one real root. We first need a good guess as to where it is. This generally requires some creativity, but in this case, notice that and . This tells us that the root is between -2 and -1. We might then choose for our initial guess.

To perform the iteration, we need to know the derivative so that

With our initial guess of , we can produce the following values:

 -1 -1.5 -1.34783 -1.3252 -1.32472 -1.32472 -1.32472 -1.32472

Notice how the values for become closer and closer to the same value. This means that we have found the approximate solution to six decimal places. In fact, this was obtained after only five relatively painless steps.

Another example

Here we will find the critical points of the function . This means solving the equation .

To make an educated guess for the initial value , notice that is the same as and we can understand this graphically. It is given by an intersection of the graph with the line .

From this picture, it looks like is a pretty good place to start. The iteration is given by

The following tool will perform the iteration for you. (Note: you should enter the function as cos(x) - 2*x .) You should find a value of approximately 0.450183.

Calculators are not really that smart. They basically know how to add and multiply. Here is a way to make them find reciprocals. In fact, this is what happens inside your calculator when you hit the button which says "1/x".

Suppose we want to find . We can use Newton's method if we realize that is a solution to . This means that . So once an initial value is chosen, the iteration is given by

Notice that the operations involved in the iteration are additions and multiplications which are things that calculators can do!

You might try to show that the iteration

will compute square roots. This is how your calculator does it internally.

A pathological example

As a final example, let's try and find a root to the equation . Notice that so that

If we try an initial value , we find that

In other words, Newton's Method fails to produce a solution. Why is this? Because there is no solution to be found! We could rewrite a solution as . The following graph shows that there is no such solution.

Mathematicians are often very happy when, after a great deal of work, they are just able to say that a solution to a problem exists. This is because once they know it exists, there might be some nice method, such as Newton's Method, to actually compute the solution.