Newton's Method

Teacher Version

What is Newton's Method for?

It's a numerical method for finding the roots/zeroes of equations.

We have formulas to solve linear, quadratic, cubic and quartic equations, some more complicated than others. But when we get to polynomials of degree higher than 4 and to many other types of equations (trigonometric, logarithmic, exponential), there are not any formulas. Then what? We have to look for approximations to the curve in order to find the zeroes. Newton's method uses linear equations (successive tangent lines) to approximate the curve and finds the zeroes of these tangent lines.

Students might ask, "Why can't we just use the root solver to find the zeroes?" What do you say to this?

Someone needs to be able to program the calculator, right? Maybe someday you could find a better way to program it and end up making calculators for a living and getting RICH! Either you're the one who punches buttons on a calculator or you're the one who programs the calculator. Who do you want to be?
A calculator should be used as a tool, not as a crutch. When you ask it to do something, it's a good idea to have an idea of how it is doing it. It's the same with other electronics, cars, etc.
In scientific computer programming, it is sometimes necessary to find roots repeatedly -- possibly as part of a large loop. Newton's method (or a variation) works well.

Let's derive the formula for Newton's Method.

We use our initial guess, x₀, to find the equation of the tangent line to our curve through that point.

y - f(x₀) = f'(x₀) (x-x₀)

Then we want to know where it hits the x-axis, or where y=0.

0 - f(x₀) = f'(x₀) (x-x₀)

Solve for x:

x = x₀ - f(x₀) /f'(x₀)

X tells you your next "guess" or approximation to the zero of the graph. You can do the same process with this x, call it x₁, and you will find x₂. In general, this will lead you to a root of the equation. Let's write the general recursive formula.

Newton's Formula

1. Guess a root, using the graph to help.

2. Use the first approximation, x₀, to find the next, x₁, and repeat the process until you have the desired accuracy.

x_n+1 = x_n - f(x_n) / f'(x_n), f'(x_n) ¹ 0, n=0,1,2,3…

How do we put this into the calculator? You can use NEWTMETH, as in the example below. If you do not have access to the program, you can do it without a program (See Appendix).

EXAMPLE:

f(x) = 2sinx + cos2x [0, 3p /2] * Make sure your calculator is in radian mode

Go into the Y = screen and put f(x) into Y₁.

Go to the GRAPH screen and look at where the graph is hitting the x-axis. You might have to change the WINDOW and/or use TRACE to find the right region. ** If you pick just any number for your initial guess, you may end up finding a different root from the one you want or you may not find a root at all. Find a reasonable approximation to use for x₀.

Start the program NEWTMETH by pressing PRGM and selecting the appropriate option. The program will ask you for the function, the derivative and your guess. After you hit ENTER, it will give you two numbers. The first number is your x₁ and the second number is the value of your original function at the value of x₁. Each time you press ENTER, the next x-value will appear, along with its respective function value. The program is set up to do a certain number of iterations, but you change that by editing the function (see the copy of the program at the end of the lab).

What is your approximation to the root of the function, accurate to 5 decimal places?

NEWTMETH also stores your values in a table so that you can study the convergence of the root. To see the table, press STAT and select option (1) Edit… The x-values will be in L1 and the corresponding y-values will be in L2.

NEWTMETH also plots your table values. To see the plots, press GRAPH. Zoom in or out as necessary.

CHECK:

You can also use the root solver to find an answer. To do this, highlight only Y₁ on the Y = screen and then press 2^nd CALC and go to (2) Zero. It asks for a left bound, a right bound, and a guess. Just move your cursor and then press ENTER in the appropriate location at each stage. It gives 3.5163271. Does your calculator agree?

Let's try one in pairs:

Consider the function f(x) = x³ - 3x² + 3.

(a) Use a graphing utility to obtain the graph of f(x).

(b) Use Newton's Method with x₁ = 1 as an initial guess.

(d) Explain in detail what is happening, and why, with the graph of the points Newton's Method is calculating.

(e) To understand why the results in parts (b) and (c) are different, sketch the tangent lines to the graph of f(x) at the points (1,f(1)) and (,f()). Find the x-intercept of each tangent line and compare the intercepts with the first iteration of Newton's Method using the respective initial guesses.

(f) Write a short paragraph summarizing how Newton's Method works. Use the results of this exercise to describe why it is important to select the initial guess carefully.

NOTE:

There are many ways to ask the same question. Think about why the following end up posing the same mathematical problem?

(a) Find the roots of f(x) = x³ - 3x - 1.

(b) Find the x-coordinates of the intersections of the curve y = x³ and the line y = 3x + 1.

(d) Find the values of x where the derivative of g(x) = x⁴ - x² - x + 5 equals zero.

Newton's Method doesn't always work so smoothly.

If you end up with a situation in which you bounce back between the same x-values on successive iterations, then you'll never attain that root.

Can you draw a picture of a situation where this would happen?

If you hit a place where f'(x) = 0, then you won't find the root because the formula will not be usable.

Again, draw a picture to show why this is true.

If the neighborhood of a zero is very flat, you can get very slow convergence. Look at f(x)=x⁶ as an example.

Going further. Chaos refers to sensitive dependency on initial conditions.

Let's look at f(x) = 4x⁴ - 4x²

The real roots of this are -1, 0, and 1.

Choose an initial condition between and . Run NEWTMETH. What root are you converging to? ______________

Choose a couple of other different initial conditions between these same two values and see what root you converge to in each case.

Try to explain what might be happening (hint: draw a picture of the function).

Between and , there are open intervals of points attracted to 1 and open intervals of points attracted to -1. This behavior is mirrored in the interval between - and -. This is the beginning of chaos theory.

Can you think of why and might be the numbers which define the interval of chaotic behavior?

What root do you converge to if you start with x= ? Why do you think this is so?

Let's look at f(x) = x² + 1, which has no real roots.

If you use Newton's formula for this equation, what do you get? x_n+1 = __________________

Pick an initial guess. x₀ = 3. When you look at your graph, zoom into a box quite small, for example x Î [-2,2] and y Î [-2,2] to see the behavior more closely.

Explain what is happening with the plot of your data.

Look in the list your calculator has created (press STAT, select (1) Edit…). Write down the first 5-6 entries in the columns.

Try this again with x₀ = 3.1 instead. Again, look in the list your calculator has created. Compare the beginnings of this table with what was in the first table. Note the very different entries even though your initial values were very close to each other. This displays the idea of chaos since the output from Newton’s method was sensitive to the starting value. That is, 3.0 and 3.1 are fairly close to each other, but after 5 or 6 iterations of Newton’s method, the values have diverged considerably.

Appendix: How to Put Newton’s Method into your Calculator Without Using a Program

If you don't have the program NEWTMETH handy, here are alternate instructions for Newton's Method. This method will not plot the data nor put it in a list form for you, but it will find a solution.

In the Y = screen, put f(x) into Y₁ and f’(x) into Y₂.

Put Newton's formula into Y₃, Y₃ = x - Y₁/Y₂

Note: You can put a more specific formula in for Y₃ as well (i.e. actually put in the function for Y₁ and the derivative for Y₂, but if you do it in the way described above, then you can change the functions Y₁ and Y₂ and Y₃ still holds.)

2^nd QUIT takes you back to the home screen.

We want to store our initial guess into x. This is our x₀. For example, try 3.5.

STO x

Press ENTER

Now, we want to put that value in for Y₃ and get an answer, x₁. We then want to use that answer in Y₃ again to find the next answer, x₂. This process repeats itself. The way we type that in on the calculator is

Y3 STO x

Press ENTER

Keep pressing ENTER until you have the desired accuracy and you have the approximation to the root of the equation.