UBC Calculus Online Course Notes

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 $ x^3 - x + 1 = 0 $ , 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 $ \sqrt{5} $ . 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 $ \sqrt{5} $ which is a solution of the equation $ f(x) = x^2 - 5 = 0 $ .

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 $ \sqrt{5} $ is between 2 and 3 so let's just choose to use the linear approximation at $ x_0 = 2 $ . We know that $ f(x) = x^2 - 5 $ so that $ f^\prime(x) = 2x $ . The linear approximation is then

\begin{eqnarray*} f(x) \approx l(x) & = & f(x_0) + f^\prime(x_0)(x - x_0) \\ f(x) \approx l(x) & = & -1 + 4(x - 2) = 4x - 9 \end{eqnarray*}

Notice that the linear equation is easy to solve. We will then approximate the solution to $ f(x) = 0 $ by the solution to $ l(x) = 4x - 9 = 0 $ which is $ x = \frac 94 = 2.25 $ . If you have a look on a calculator, you will see that $ \sqrt{5} = 2.236068... $ . 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 $ f(x) = 0 $ which is where the graph of $ f(x) $ 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 $ x_1 = \frac 94 $ and consider the linear approximation at that point.

\begin{eqnarray*} f(x) \approx l(x) & = & f(x_1) + f^\prime(x_1)(x - x_1) \\ f(x) \approx l(x) & = & (\frac{81}{16} - 5)+ \frac{9}{2}(x - \frac{9}{4}) = \frac 92x - \frac{161}{16} \end{eqnarray*}

Now if we call $ x_2 $ the solution to $ l(x) = 0 $ , we find that $ x_2 = 2.236111 $ which is an even better approximate solution to the equation. We could continue this process generating better approximations to $ \sqrt{5} $ 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 $ f(x) = 0 $ using the same idea. Suppose that $ x_0 $ is some point which we suspect is near a solution. We can form the linear approximation at $ x_0 $ and solve the linear equation instead.

That is, we will call $ x_1 $ the solution to $ l(x) = f(x_0) + f^\prime(x_0)(x-x_0) = 0 $ . In other words,

\begin{eqnarray*} f(x_0) + f^\prime(x_0)(x_1 - x_0) & = & 0 \\ x_1 - x_0 & = & -\frac{f(x_0)}{f^\prime(x_0)} \\ x_1 & = & x_0 -\frac{f(x_0)}{f^\prime(x_0)} \end{eqnarray*}

If our first guess $ x_0 $ was a good one, the approximate solution $ x_1 $ should be an even better approximation to the solution of $ f(x) = 0 $ . Once we have $ x_1 $ , we can repeat the process to obtain $ x_2 $ , the solution to the linear equation

\[ l(x_2) = f(x_1) + f^\prime(x_1)(x_2 - x_1) = 0 \]

Solving in the same way, we see that

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

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

\[ x_{n+1} = x_n - \frac{f(x_n)}{f^\prime(x_n)} \]

Provided we have started with a good value for $ x_0 $ , 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 $ f(x) = x^3 - x + 1 = 0 $ . 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 $ f(-2) = -5 $ and $ f(-1) = 1 $ . This tells us that the root is between -2 and -1. We might then choose $ x_0 = -1 $ for our initial guess.

To perform the iteration, we need to know the derivative $ f^\prime(x) = 3x^2 - 1 $ so that

\[ x_{n+1} = x_n - \frac{x_n^3 - x_n + 1}{3x_n^2 - 1} \]

With our initial guess of $ x_0 = -1 $ , we can produce the following values:

$ x_0 $ -1
$ x_1 $ -1.500000
$ x_2 $ -1.347826
$ x_3 $ -1.325200
$ x_4 $ -1.324718
$ x_5 $ -1.324717
$ x_6 $ -1.324717
$ x_7 $ -1.324717

Notice how the values for $ x_n $ 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 $ g(x) = \sin(x) - x^2 $ . This means solving the equation $ f(x) = g^\prime(x) = \cos(x) - 2x = 0 $ .

To make an educated guess for the initial value $ x_0 $ , notice that $ \cos(x) - 2x = 0 $ is the same as $ \cos(x) = 2x $ and we can understand this graphically. It is given by an intersection of the graph $ y=\cos(x) $ with the line $ y = 2x $ .

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

\[ x_{n+1} = x_n - \frac{\cos(x_n) - 2x_n}{-\sin(x_n) - 2} \]

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.



How your calculator works

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 $ \frac 1a $ . We can use Newton's method if we realize that $ \frac 1a $ is a solution to $ f(x) = \frac 1x - a = 0 $ . This means that $ f^\prime(x) = -\frac {1}{x^2} $ . So once an initial value is chosen, the iteration is given by

\begin{eqnarray*} x_{n+1} & = & x_n - \frac{\frac 1{x_n} - a}{-\frac{1}{x_n^2}} \\ & = & x_n + x_n - ax_n^2 \\ & = & 2x_n - ax_n^2 \end{eqnarray*}

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

\[ x_{n+1} = \frac 12(x_n + \frac{a}{x_n}) \]

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 $ f(x) = e^x - 2x = 0 $ . Notice that $ f^\prime(x) = e^x - 2 $ so that

\[ x_{n+1} = x_n - \frac{e^{x_n} - 2x_n}{e^{x_n} - 2} \]

If we try an initial value $ x_0 = 1 $ , we find that

\[ x_1 = 0,~~~x_2 = 1,~~~x_3=0,~~~x_4=1,... \]

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 $ e^x = 2x $ . 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.

For your consideration:

  1. Suppose you are performing an iteration and you arrive at a place where $ x_{n+1} = x_n $ . What can you conclude about $ x_n $ ? (Hint: Have a look at the formula for the iteration.)

  2. The initial guess $ x_0 $ is really important. Notice that the function $ f(x) = xe^{-x^2} $ has a zero at $ x = 0 $ . Use the tool below to apply Newton's Method to try and find this zero by choosing $ x_0 = 1 $ .

    Why doesn't this find the zero $ x = 0 $ ? The graph of the function below might help to explain.

    What happens and why when the initial value $ x_0 = 0.5 $ is chosen?

    Now use the graph to make another initial guess which will lead to the solution.