Newton's Method

Newton's Method is a tool that uses calculus to estimate the roots (zeros or x-intercepts) of a function.

In a previous lab, we considered the find_root and solve commands in Sage, which can be used to find roots. The purpose of this lab is to give us some idea of the math behind these commands. There is no practical reason to use Newton's Method (unless you really need to find a root without a computer/calculator). However, it is instructive to see how calculus (which is not directly related to roots) can be used to estimate roots.

Newton's basic idea is that a differentiable function is "close" to its tangent lines (at least near the point of tangency). So if we know the root of a tangent line (easy algebra), we suppose that the root of the function is somewhere close.

Example 1

Estimate the roots of $f(x)=x^2+2x-1$. [Of course, we can find the roots of a quadratic function with the Quadratic Formula, but it's just an example.] Let's look at a graph:

From this graph, it appears that there is a root near $x=\frac{1}{2}$.

Let's find the tangent line at this point. Remember, an equation for the tangent line at $x=a$ is $y=f(a)+f'(a)(x-a)$.

Notice that the tangent line and the graph of $f$ are close together near $x=\frac{1}{2}$, and we can see that the root of the tangent line is close to the root of $f$.

Sage gives the equation of the tangent line as $y=3x-\frac{5}{4}$. To find the root of this line, just plug in 0 for $y$ and solve for $x$:

$0=3x-\frac{5}{4}$

$\frac{5}{4}=3x$

$\frac{\frac{5}{4}}{3}=x$

$x=\frac{5}{12}\approx 0.41666$

Let's zoom in on the graph and plot this root.

On this window, we can see that the root of $f$ is not exactly $\frac{5}{12}$, but this is a good approximation.

If we want a better approximation, we can repeat the process, starting with a point of tangency that's closer to the root. Remember we started this example using $x=\frac{1}{2}$ as our point of tangency. This time, we'll use $x=\frac{5}{12}$, the approximation we got last time. We can see from the graph that this is closer to the root of $f$ than $\frac{1}{2}$, so the tangent line we get from $x=\frac{5}{12}$ should be even closer to the actual root of $f$.

So let's find a new tangent line:

We can see that the tangent line and $f$ are very close together on this window, so the root of the tangent line is very close to the root of $f$.

Let's find the root of the tangent line:

$0=\frac{17}{6}x-\frac{169}{144}$

$\frac{169}{144}=\frac{17}{6}x$

$\frac{\frac{169}{144}}{\frac{17}{6}}=x$

$x=\frac{169}{408}\approx0.414216$

Just for comparison, let's find the exact root of $f$.

There are two solutions, $x=-\sqrt{2}-1$ and $x=\sqrt{2}-1$. We have been trying to estimate the postive root, which is $x=\sqrt{2}-1\approx0.414214$.

This is very close to our estimate, which is off by only $\frac{169}{408}-(\sqrt{2}-1)\approx0.0000021239$ (about $0.0005\%$ error).

If we wanted to improve our estimate even more, then we could repeat the process again, using $x=\frac{169}{408}$ as our new point of tangency.

I hope you see from this short example that this process involves repetition of the same steps over and over with different numbers. It lends itself very easily to be made into an algorithm that can be automated.

Let's develop the algorithm.

Generalizing Newton's Method

First, notice that we had to start the process with a point of tangency (we used $\frac{1}{2}$ in our example above). The closer this point is to the actual root, the better. In fact, if our point of tangency is chosen poorly, Newton's Method might never get close to the actual root, or it might take more repetitions than we want to use.

Also notice that Newton's Method only estimates one root at a time. If we had chosen a different point of tangency, we may have ended up at the other root of $f$ (in our example, $f$ has two roots).

We'll use a graph to get a ballpark estimate of the root. We'll use this initial guess as our first point of tangency. We'll call this initial guess $x_0$.

So here's the setup: We have a function $f$ with at least one root, and we have a ballpark guess that this root is close to $x_0$.

Now we find the tangent line to $f$ when $x=x_0$:

Then we find the root of the tangent line by setting it equal to 0 and solving for $x$:

First, distribute:

Then gather like terms:

Now divide both sides by $f'(x_0)$:

And simplify:

This is the root of the tangent line, so this becomes our new estimate for the root of $f$. Let's call it $x_1$. Thus,

To improve our approximation, use $x=x_1$ as our new point of tangency and repeat the process. The algebra is exactly the same. Simply replace all the $x_0$ in the above equations with $x_1$.

What we get is a new approximation, $x_2$, given by

In general, if we have repeated this process $n$ times to get an estimate $x_n$, then repeating the process again will give a new estimate, $x_{n+1}$ given by:

Example 2

Now we're ready to lay out an algorithm for Newton's Method.

As I go through the steps, I'll use the example of $f(x)=x^3+2x-1$.

Step 1 Define the function

Step 2 Choose an initial value by graphing the function

From this graph, we can see that $f$ has one (real) root, somewhere in the neighborhood of $x=1$.

We'll use this as our initial guess. I'm going to abandon subscripts to make it easier to do this in Sage. Instead, I'll call our estimate "$r$," and we'll replace $r$ with better approximations as we go:

Step 3 Define the number of repetitions

Now we have to decide how many times we want to repeat the process. I'll call this number "$n$."

Step 4 Define the derivative

Step 5 Iterate Newton's Method

Our estimates get better as we go down the list, so our best estimate for the root of $f$ is $x\approx0.453397651516404$.

Let's have Sage compute the root and compare:

The only real solution is $$\left(\frac{1}{18}\sqrt{59}\sqrt{3} + \frac{1}{2}\right)^{1/3} - \frac{\frac{2}{3}}{\left(\frac{1}{18}\sqrt{59}\sqrt{3} + \frac{1}{2}\right)^{1/3}}\approx0.453397651516404$$

To 15 decimal places, our estimate matches the actual root exactly - and that's after only 5 repetitions.

Note 1 It is possible to use Newton's Method to find complex roots as well (just start with a complex guess), but we will not do this in this class.

Note 2 As mentioned above, Newton's Method does not always work. An obvious example is when our initial guess is a local minimum or maximum. Then we get a horizontal tangent line, which has no roots.

In fact, if you choose an initial guess that is close to a local minimum or maximum, then the root of the tangent line may be very far from the root of $f$ (although the algorithm may eventually get back to the right place).

Example 3

Here's an example of a poor choice of initial guess. I have chosen an initial guess of $x=0.1$ which is close to the minimum at $x=0$. Although the root of the function is $\sqrt{2}\approx1.41$, the root of the tangent line is $10.05$.

In this case, Newton's Method will eventually get back to the root, but it requires a few more repetitions.

Example 4

Here's another poor choice of initial guess. Consider the function $f(x)=\ln(3x)$. I'm going to choose an initial guess of $x=1$.

Below is a graph of $f$ with the tangent line at $x=1$.

Notice that the root of the tangent line is a negative number, which is not in the domain of $f$. That means we can't find a new tangent line using that root for the point of tangency.

If we try Newton's Method, we end up with complex numbers!

Newton's Method in One Cell

You can copy and paste the input below to implement Newton's Method.

Change the function $f$, then hit run.

If no root is visible, adjust the plot window and run until you find a root.

Once you see a root, choose an initial guess in the ballpark of the root, change the number $r$, and hit run.

Example 5

Find the roots of $f(x)=x^2-2$.

We found a root near $1.4142$.

Notice how the answers stabilize after a few repetitions. This suggests we have the right answer.

For this example, the graph shows two roots. We have found the positive root; to find the negative root, change the initial guess and run it again.

Now we have found the second root, around $-1.4142$.

Using Newton's Method to find a point of intersection

If you have two functions, $f_1$ and $f_2$, and you want to know where they cross, then define a new function $f=f_1-f_2$ and find the roots of $f$. This gives you the x-coordinate of a point of intersection. Plug this into either $f_1$ or $f_2$ to get the corresponding y-coordinate.

Example 6

Find the point of intersection of $f_1(x)=\sqrt[3]{2\sin(x)}$ and $f_2(x)=e^{-2x}$.

Let's check using find_root:

Our estimate looks good. This is the x-coordinate of the point of intersection.

To find the y-coordinate, plug this into $f_1$ or $f_2$. I'll plug it into both as a check (I'd better get the same answer).

So our point of intersection is approximately $(0.175423347115679,0.704091686899284)$.

Here's a graph:

Newton's Method Assignment

Question 1

Estimate the roots of the function $f$ using the algorithm developed in class:

• Graph the function.

• Use the graph to choose a guess close to one root.

• Use your guess to perform Newton's Method (use 5 iterations).

• Repeat the process for any additional roots.

Part a

$f(x)=x^3-3x^2+2x-1$

Part b

$f(x)=3\ln(x)-x$

Question 2

Find the points of intersection of two functions $f_1$ and $f_2$:

• Define a new function $f(x)=f_1(x)-f_2(x)$.

• Follow the steps above to find the roots of $f$. These are the x-coordinates of the points of intersection.

• Find the y-coordinates of the points of intersection by plugging the roots into both $f_1$ and $f_2$ (you should get the same answer).

Practice your $\LaTeX$: display nicely the points of intersection (ordered pairs).

Part a

$f_1(x)=e^x$, $f_2(x)=2-x$ [Hint: there is one answer.]

Part b

$f_1(x)=\ln(x)$, $f_2(x)=x^2-10$ [Hint: there are two answers, and one is really close to 0.]