Tuesday, May 1, 2012

Calculus Revisited #9: Newton's Method

Welcome to blog entry #9 of 21 of our Calculus Revisited. Today we will cover Newton's Method: an effective and powerful way of finding roots of functions.

Process: Newton's Method

Goal: Find roots of the function f(x). That is, solve for x: f(x) = 0

1. Start with an initial guess. Let this be x_n.

2. Calculate x_(n+1) = x_n - f(x_n)/f'(x_n) (function over its derivative)

3. If x_n+1 matches x_n, you are done, with the root being x_n+1. You determine how accurate the answer is by selecting how many decimal points to match. Calculator accuracy (what you see on the screen) varies from 10 to 12 decimal points.

Caution: The choice of initial value is important. Usually, selecting initial guesses close to the root works the best, but this does not always work.

Also, this method is not 100% in finding roots. If you get x_n and x_n+1 flopping between two distinct values, you are caught in a loop - a root will not be found.


I recommend that you use a calculator when working with Newton's Method. On scientific calculators, you may be able to take advantage of the last answer feature, setting x_n = ans.

Example: (TI -36X Pro, TI-30 Multiview, Casio fx-300, Casio fx-115ES, most graphing calculators)
2 ENTER (2 is stored in ans)
ans - f(ans)/f'(ans) (calculates x_1 with x_n = 2)
Keep pressing ENTER

Problems
Newton's Method will often be used to estimate nth roots (square root, cube root, etc). The first problem will be an example of such.

1. Estimate √6 to 5 decimal places.

Observe that √4 = 2 and √9 = 3, which means √6 lies in between 2 and 3. Let's make an initial guess 2.5.

Use the function f(x) = x^2 - 6. Why?

x^2 = 6
x^2 - 6 = 0

Finding the root to the above equation leads to √6.

Then f'(x) = 2x and

x_n+1 = x_n - (x^2 - 6)/(2x)

Having x_0 as the initial guess,
x_0 = 2.50000
x_1 = 2.45000
x_2 = 2.44949
x_3 = 2.44949

(x_1 = 2.5 - (2.5^2 - 6)/(2*2.5) = 2.45,
x_2 = 2.45 - (2.45^2 - 6)/(2*2.45) = 2.44949, and so on)

So to five decimal places, √6 ≈ 2.44949

2. Find a root of the equation e^x - x = 5 for any x > 0. Let x_0 = 2. (the initial guess)

Get the equation in form of f(x) = 0:
e^x - x = 5
e^x - x - 5 = 0

Then f(x) = e^x - x - 5, f'(x) = e^x - 1, and

x_n+1 = x_n - (e^x_n - x_n - 5)/(e^x_n - 1)

By calculation, we get:

x_0 = 2.00000
x_1 = 1.93911
x_2 = 1.93685
x_3 = 1.93685

Then a root of f(x) is x≈1.93685.

3. Solve x^4 - 4x - 4 = 0 with the condition -1 < x < 1. Find the root to five decimal places.

Hint: You may want to graph f(x) to estimate an appropriate initial guess.

Let x0 = -.5

Then f(x) = x^4 - 4x - 4, f'(x) = 4x^3 - 4, and

x_n+1 = x_n - (x_n^4 - 4x_n - 4)/(4x_n^3 - 4)

By calculation, we get:
x_0 = -0.50000
x_1 = -0.93056
x_2 = -0.86520
x_3 = -0.86198
x_4 = -0.86198

A root of f(x) where -1
Here is a situation where Newton's Method does not work for three picks. Not all f(x) will be successful.
4. Find a root of f(x) = √(x^2 - 4) Fortunately, we can find them using algebraic methods (x = ± 2).

f(x) = √(x^2 - 4)
f'(x) = 1/(2 * √(x^2 - 4) * 2x = x/√(x^2 - 4)
x_n+1 = x_n - (x^2 - 4)/x

If x_0 = 1, then subsequent calculations result in a loop between 1 and 4.
If x_0 = 1.5, then subsequent calculations result in a loop between 1.5 and 2.66667.
If x_0 = 1.75, then subsequent calculations result in a loop between 1.75 and 2.828571.

You may try this with other x_0 and run into similar trouble.

Just be aware.

That wraps it up on Newton's Method. Next we head into integration! - Eddie


This blog is property of Edward Shore. © 2012