MATH 131, section 1 – Calculus for Physical and Life Sciences, 1 Lab Day 3 – Newton’s Method November 20, 2007

Goals

The goal for this lab is to use and investigate the numerical root-finding method known as Newton’s Method (sometimes also called the Newton-Raphson method). Using Maple, you will apply Newton’s Method to find numerical approximations to solutions of various equations f(x) = 0. In the process you will see cases where the method succeeds and others where it fails quite badly. You should work in pairs for this assignment (the previous lab pairs, or other pairings of your choice are OK).

The Mathematical Background

As we saw in class yesterday, the idea behind Newton’s Method is that we can use the linear functions defining the tangent lines to a graph y = f(x) to approximate that function and approximate where the graph crosses the x-axis. If we start at some “seed” value x = x_{0}, then Newton’s Method essentially determines where the tangent line to the graph y = f(x) at x_{0} crosses the x-axis. This number is called x_{1}. Then the method finds where the tangent line at x = x_{1} crosses the x-axis and calls that number x_{2}. Repeating the process gives a sequence of x-values,

x_{0}, x_{1}, x_{2}, …, x_{n}, …

that should get closer and closer to a root of f, that is, a solution of the equation f(x) = 0. We say that the sequence converges to a root r if

lim_{n→∞} x_{n} = r.

We will study convergence of sequences in the course next semester when we study infinite series.

Ideally, the iterative process above will eventually head toward a root of f(x) = 0. Different “seeds” x_{0} may produce different sequences of approximations, though, and those different sequences of approximations may converge to different roots of the equation(!). There are also cases where Newton’s Method can fail to converge.

In terms of equations, Newton’s Method reduces to performing the following computations:

x_{n} = x_{n−1} − \frac{f(x_{n−1})}{f′(x_{n−1})}

for n = 1, 2, 3, … one after the other. We need a seed x_{0} to produce x_{1}, but then x_{1} produces x_{2}, x_{2} produces x_{3}, and so on. This process is an example of iteration, an important topic in numerical mathematics and applications. It is also something for which computers are ideally suited.

A Worked Example – Newton’s Method in Maple

Maple has a “built-in” Newton’s Method procedure that we will use in today’s lab. To use it, you first enter the command

                         with(Student[Calculus1]):

(note capitalization!) Then to apply Newton’s Method to try to find approximations to a solution of f(x) = 0, you would proceed as follows. For instance, say we want to look at what happens for the equation f(x) = x^{2} − 1 = 0 (where we know what the solutions are so we can see how well the process is working!). The command

                 NewtonsMethod(x^2-1, x=2, iterations=3);

will do three iterations (finding x_{3} in the sequence of approximations) starting from the seed x_{0} = 2. The output is the value x_{3}. Of course, we might also want to see all the terms in the sequence of approximations starting from the seed. This can be shown by putting in an option as follows:

         NewtonsMethod(x^2-1, x=2, iterations=3, output=sequence);

Other nice features that can help us visualize what is happening are to have Maple actually draw the graph and the tangent lines used to produce the sequence x_{n}. The way to do this is to use different options in the NewtonsMethod command. For instance,

          NewtonsMethod(x^2-1, x=2, iterations=3, output= plot);

generates a single plot showing all the tangent lines, while

        NewtonsMethod(x^2-1, x=2, iterations=3, output= animation);

adds them in one at a time so you can see the order in which they are generated. (You “play” the animation here in a fashion similar to some of the other animated plots we saw in previous labs.) You should enter all of these and compare what they do so that you understand exactly what is happening here. Also try increasing the number of iterations to 5, then 10 and see what happens.

Lab Questions

A)

1) Continuing with the worked example above, using f(x) = x^{2} − 1, what happens if you start with the seed x_{0} = −2 rather than x_{0} = +2? What root of the equation x^{2} − 1 = 0 are we approaching now?

2) What if we start with x_{0} = 0? Could we have predicted this? What does this say about the choice of the seed for Newton’s Method?

3) By looking at the graph y = x^{2} − 1, try to guess which initial seeds will produce sequences converging to the root r = −1 and which will produce sequences converging to the root r = 1. Confirm your guess by testing several different seeds.

B) Effectiveness of Newton’s Method. Let’s explore how well Newton’s Method converges to a root by computing the error at each step of the process. First enter the command

                               Digits := 20;

which tells Maple to do all numerical computations using 20 decimal digits in its numbers. Then use Newton’s Method to compute the first 6 iterations applied to x^{2} − 1 = 0 starting from x_{0} = 2. What is the error at each step (how far is the approximate root x_{n} from the true root r = 1 for each n = 0, 1, 2, 3, 4, 5, 6)? Give your numbers in “scientific notation,” for example 2.3 × 10^{−3}. How much does the approximation improve at each step? How many decimal places accuracy are gained at each step?

C) Computing π. One equation that has the number π as a solution is tan(x/4) − 1 = 0 (do you see why?) Set Digits:=50; now. Use Newton’s Method to compute the first 40 decimal digits of π. How can you be sure those first 40 digits are correct?

D) Use Newton’s Method to compute the first 20 digits of the (real) fifth root of 2. (What equation has this number as a root?)

E) Use Newton’s Method to approximate all real solutions of the equation

3 cos(x^{2} + 2) − x = 0

to 10 decimal places. Hint: Start by plotting this function to get an idea how many roots there are and to get some possible seeds to use.

F) Complete Success. Explain why Newton’s Method finds the solution to a linear equation mx + b = 0 in exactly one step, with no error, for all choices of seed x_{0}(!)

G) Failure of Newton’s Method. What happens if you apply Newton’s Method to find roots of x^{4} − 6x^{2} − 11 = 0 starting from the seed x_{0} = 1? Try 10 iterations, first show the sequence of iterations, then the plot to explain what happens. What if you try changing the seed slightly to x_{0} = 0.8 or x_{0} = 1.25? Does this help? By making better choices of seed, find all the real roots of this equation, to 10 decimal places.