Finding Roots: Newton’s Method

Finding Roots: Newton’s Method
Calculus I Project
The purpose of this project is to derive and analyze a method for solving equations. This method is
iterative meaning that successive approximations to a solution are obtained with the intent that each
new approximation is an improvement over the previous ones. Many mathematical problems can be
restated in terms of root finding. (Recall that c is a root of a function f(x) provided f(c) = 0.)
Suppose for example that we wish to obtain a decimal approximation to the number π. Given a little
knowledge of trigonometry, we can restate this problem in terms of roots as:
Find the smallest positive number x such that tan
x
4

− 1 = 0.
For an iterative method, we start with some initial value (perhaps an educated guess) x0. We feed this
into some sort of scheme (a formula) which produces a new value x1. We then repeat the process to
build a sequence x0, x1, x2, . . . , xn of values that are increasing closer to the true solution. Newton’s
method gives such a scheme based on the observation that for some functions, the root of a tangent
line will be closer to the true root of a function.
Suppose that f is some function with true root α—note that α is an x-intercept. Let x0 be some value
assumed to be close to the root α, and let L(x) be the tangent line to f at the point (x0, f(x0)) as
shown in the figure. The number α is not known, and the goal is to determine its value. The number
x0 is an initial guess as to the value of α. We don’t expect it to be correct, but we hope to use it to
find a better estimate. Note that the x-intercept of the tangent line (x1 in the figure) is closer to the
Figure 1: Graph of f showing true root α and tangent line at (x0, f(x0)).
true root α. For Newton’s method, this new value x1 is taken as the next approximation. Then the
process is repeated by forming the tangent line to f at the new point (x1, f(x1)). The x-intercept of
this new line is called x2—the next, and hopefully better approximation to α. We continue to play
this game until we’re satisfied with the accuracy. In general, we stop the process when successive
approximations are deemed close enough together—that is, when |xn+1 − xn| < some preset erro
tolerance.
Newton’s method is widely used. When it works, it tends to work very quickly (requiring relatively
few iterations). But it’s not the only trick in the book, and it has its weaknesses. This project entails
deriving the method as well as investigating its strengths and pit-falls.
Carry out the following activities.
A. Suppose that f is a function that has a root α that we wish to determine, and assume that f is at
least a couple of times differentiable on an interval containing α. Let x0 be an initial guess, and write
the equation of the line L(x) that is tangent to the graph of f at the point (x0, f(x0)). Use this to find
a formula for x1 the x-intercept of L in terms of x0, f(x0), and f
0
(x0).
B. Repeat this process by writing the equation of a new tangent line L to the graph of f at the point
(x1, f(x1)), and find a formula for x2 the x-intercept of L in terms of x1, f(x1) and f
0
(x1). Notice
that the basic formula is the same one found before except with x2 replacing x1 and x1 replacing x0.
Write this as a general formula for which the new iterate xn+1 is given in terms of the old iterate xn,
f(xn), and f
0
(xn).
C. The equation 1
x = 1 + x
3 has one positive solution. Plot the two graphs y =
1
x
and y = 1 + x
3
together on the same set of axis to demonstrate that there is one solution. Use Newton’s method to
find it correct to six decimal places. (Note that you will have to restate the problem as a root finding
problem by defining an appropriate function f(x) that has the solution as its root.)
D. Older (and some modern) computers do not directly perform the operation of division; they are
restricted to computing with the operations of multiplication, addition, and subtraction. So, given a
positive number b, its reciprocal must be computed indirectly. Note that for any such number b, the
reciprocal 1
b
is the true root of the function
f(x) = b −
1
x
.
Use Newton’s method to find a sequence of approximations x0, x1, . . . , xk to the reciprocal 1
b
that
only requires the operations of ×, +, and/or −. (Your iteration formula should simplify nicely.)
Now use this formula to find the reciprocal of π. Try two different cases: (1) use an initial guess
of x0 = 0.5, and find it to at least six decimal places; (2) use an initial guess of x0 = 0.7 and comment
on what you observe.
E. For a numerical scheme, we consider an error measure called the relative error. Suppose a true
value is α and an estimate to this value is xn. Then the relative error is
Rel(xn) = true value − approximate
true value
=
α − xn
α
.
Consider the reciprocal finding process in part D. (with α =
1
b
for some positive b). Show that
Rel(xn) = 1 − bxn, and similarly Rel(xn+1) = 1 − bxn+1.
Use the formula for xn+1 to show that
Rel(xn+1) = (Rel(xn))2
.
This puts a restriction on how good (close to α) the initial guess must be to ensure that the method
works. Find a condition on x0 or on Rel(x0) that will guarantee that the approximations get better
with each iteration. Discuss what this means in terms of both the restriction on the method and how
fast it works when it does work. (For example, if the relative error at some step is about 10−4
, how
big would it be at the next step.)
F. There are fun examples for which Newton’s method produces interesting sequences of iterates.
Experiment with some of the following. Pick one (or two) and discuss the behavior of the method.
You may wish to include graphical illustration of what you observe in addition to a table of interations.
i. The true root of f(x) = √3 x is clearly α = 0. Newton’s method can not be used to find this root
for any choice of x0 6= 0.
ii. The equation x
3 −5x = 0 has three solutions 0,

5 and −

5. Consider Newton’s method with
x0 = 1 or x0 = −1.
iii. f(x) = x
3 − 2x + 2 has one real root close to −2. What happens with an initial gues of
x0 = 0? If an initial guess in the interval −0.1 < x < 0.1 is chosen, after several iterations,
some interesting behavior is seen. What is perhaps more surprising is what happens if a really
bad guess—e.g. x0 = 5—is taken.

Don't use plagiarized sources. Get Your Custom Essay on
Finding Roots: Newton’s Method
Just from $13/Page
Order Essay

Leave a Reply

Your email address will not be published. Required fields are marked *