Laboratory 9
Newton's Method

Introduction

Newton's method is one of the best known algorithms for finding a solution r to the equation f(x)=0. It relies on the continuity of f '(x) and f ''(x) near r in computing the sequence

                                    (Subscript[x, n+1])= (Subscript[x, n]) - ((f ((Subscript[x, n])))/(f ' ((Subscript[x, n])))) ;         n= 0, 1, 2, 3, ...

with (Subscript[x, 0]) being some starting value which may be guessed. A process like this, where a step is executed repeatedly, is usually called an iteration.

9.1 The Functions "Nest" and "NestList"

It is quite easy to do iteration in Mathematica. The built-in function NestList does that. You can get a description of this function using ?NestList. Here is an example illustrating its use when applied to the function u(x)=(x^2).

u[x_]:=x^2

Applying the squaring function u, repeatedly to the input 3, one can get a list of the three iterates (the initial input and the intermediate and final outputs) with the help of the function NestList as follows.

NestList[u,3,2]

Notice that the argument of the function u was not typed in the previous commands.

Experiment 9.1

Apply the sine function 15 times (repeatedly) to the real number 0.4 using the function NestList with the appropriate parameters (first define  a function, say h(x), that equals sin x). Comment on the resulting sequence of numbers.

9.2 Newton's Iteration

Newton's method may be summarized as follows. To find a root r of the equation f(x)=0, we pick a value (Subscript[x, 1]) near r (possibly by looking at the graph of f), then substitute (Subscript[x, 1]) in the equation (Subscript[x, 2])=(Subscript[x, 1])-f((Subscript[x, 1]))/f '((Subscript[x, 1])). Generally, (Subscript[x, 2]) is closer to the true root r than (Subscript[x, 1]) is. We then repeat the process using (Subscript[x, 2]) instead of (Subscript[x, 1]) to get a better approximation (Subscript[x, 3]), and so on. In other words, we iterate the equation (Subscript[x, n+1])=g((Subscript[x, n])) where g(x)=x-f(x)/f '(x), and n=1, 2, 3, .... That is to say that we only need apply the function g repeatedly to its own output. This is readily done with the help of the built-in function NestList as explained above.

We now illustrate the method by applying it, as outlined in the previous paragraph, to the equation f(x)=(x^2)-2=0. One exact solution to this equation is r=(Sqrt[2]). We will follow the steps below:

1.  Define the function.

Clear[f,x];
f[x_]:=x^2-2

2. We now graph y=f(x) using the Plot command. This should show, as expected, that there is a root at approximately x=1.4.

Plot[f[x],{x,0,2}]

3. We now define the function g as explained above.

g[x_]:=x-f[x]/f'[x]

4. Starting with the initial guess (Subscript[x, 0])=0.5 (this was intentionally chosen far from the exact root only for the sake of illustration), we compute the first iterate (Subscript[x, 2]) by applying NestList to the new function g once.

NestList[g,.5,1]

5. To generate subsequent iterates (approximations), we apply NestList repeatedly. Here is the result of 6 applications.

NestList[g,.5,6]

The sequence of iterates generated above is getting closer and closer to a certain limit. This limit is the root r in question. Such a sequence is said to converge to r or to be convergent with a limit r.

Experiment 9.2a

The  equation f(x)=sin(ln x) -0.2 has two roots in [1, 30].
	(a) Clear f and x and define the new function f.
	(b) Plot the function in the interval indicated.
	(c) Starting with a suitable initial guess for the smaller of the two roots and 5 iterations find a better estimate of that root, if possible.
	(d) Repeat (c) for the larger root.

Experiment 9.2b

The  equation f(x)=sin( x+ cos(π x))-0.4 has two roots in [0, 1.5].
	(a) Clear f and x and define the new function f.
	(b) Plot the function in the interval indicated.
	(c) Starting with a suitable initial guess for the smaller of the two roots and 5 iterations find a better estimate of that root, if possible.
	(d) Repeat (c) for the larger root.

9.3 Geometric Interpretation

Newton's method for solving f(x)=0 is equivalent to the following geometric process. Pick a starting number (Subscript[x, 1]) near the root r. Draw the tangent line to the graph of f at the point ((Subscript[x, 1]), f((Subscript[x, 1])) ). The x-intercept, (Subscript[x, 2]), of the tangent line is generally closer to r than (Subscript[x, 1]) was. The process is then repeated until some prescribed accuracy is attained. The following Module, called iterate, will create an animation showing the progress of the iteration process.

The calling parameters of the Module are:
	f = the function f.
	a = the left end of some interval that contains r.
	b = the right end of the interval.
	(Subscript[x, 0])= the initial value to start the iteration.
	n= the number of iterations

iterate[g_,a_,b_,x0_,n_]:=Module[{x,f,t},f[x_]=g[x];
	t[x_]:=x-f[x]/f'[x];
DynamicModule[{m=0,data={x0},data2,data3,data4},
  Manipulate[
data=NestList[t,x0,m];data2=Flatten[Table[{data[[i]],0,data[[i]],f[data[[i]]]},{i,Length[data]}]];
		data3=Partition[data2,2];
		data4=Drop[data3,-1];
Plot[ f[x],{x,a,b},PlotStyle->{Red,Thickness->0.005},
Epilog->{Blue, Line[data4] }],
{{m,0,Dynamic[Panel[Row[{Column[{"n=","x="}],
                     Column[{m,N[data[[-1]]]}]}]] ]},0,n,1}]
]]

We now apply this Module to the function f(x)=(x^2)-2 with (Subscript[x, 1])=0.5 and the interval [0, 2.5]  in order to obtain a geometric illustration of the first iteration.

Clear[f,x];f[x_]:=x^2-2;

iterate[f,0,2.5,.5,10]

The first iterate (the x-intercept of the slanted tangent line) may be verified from the graph to equal 2.25, which is in agreement with the result obtained in Section 13.2. We now increase the number of iterations n by moving the slider. We see that after 3 iterations the approximation of the root is very close to the actual solution of the equation f(x)=0.

Experiment 9.3a

Apply the Module iterate to the function f(x)=sin(ln x)-0.2 in order to generate a visualization of the iteration process that approximates the root near x=2. Choose a suitable value for n.

Experiment 9.3b

Repeat Experiment 9.3a for the function f(x)=sin[x+cos(π x)]-0.4 in [0, 1.5].

Experiment 9.3c

The equation cos((x^2)+1)=x-1 has a solution in the interval [-1,2]. Verify this assertion by graphing an appropriate function f(x). Applying the Module iterate to this function with a suitable initial guess (Subscript[x, 0]), create a geometric illustration of Newton's method for finding this solution. Give the approximate value of the solution.

9.4 Some Difficulties

The previous examples (and most of the previous experiments) show situations where Newton's method converges nicely. The method does not always work this well. The following will show some of what could happen.

A Divergent Monotone Sequence

If the initial guess (Subscript[x, 1]) is not close enough to the root r, the resulting sequence may diverge. Consider the function f(x)=x (e^(-x)) in the interval [- 0.1,7] with (Subscript[x, 0])=2 and three iterations.

Clear[f,x];f[x_]:=x*E^(-x);iterate[f,-.1,7,2,15]

Notice that the sequence thus generated is moving away from the root r=0.

Experiment 9.4

Each of the functions below has a root in the indicated interval. Apply the module Iterate to each one with the initial value (Subscript[x, 1]) indicated and comment on the resulting graph and the resulting sequence of iterates. Suggest a way to fix the difficulty which arises in each case.
 1.  f(x)=(x^3)-6 (x^2)+7 x+2 in the interval [0,4]  and (Subscript[x, 0])=1. 
 2.  f(x)=(x^3)-x-3 in the interval [-3.2,2] and (Subscript[x, 0])=- 3.0.

Credits

These laboratories were created by Raouf Boules, Geoff Goodson, Ohoe Kim and Mike O'Leary for use in the Calculus courses of Towson University. Commercial use is prohibited without permission of the authors. Non-commercial use is permitted, provided this credit section is retained.