ITERATION and
NEWTON'S METHOD
for FINDING ROOTS
of a FUNCTION

Maxiproject for Mathematica  Workshop Summer '93
                by Dave Lystila

Introduction:
Mathematical iteration is a process for generating a sequence in which one or more initial terms are given and each subsequent term is determined form its predecessor in the same way.  An equation that describes the relationship between a term and its predecessor is called a recurrence relation.

Major curriculum groups have suggested for many years that iteration be included in the mathematics curriculum.  Experience with mathematical iteration in a variety of situations will encourage students to look for relationships between quantities, as well as to generate and test patterns.  The study of iteration may also help students develop an understanding of various methods of mathematical reasoning, in particular mathematical induction, which moves from the nÊÓ case to the (n+1)ÍÊ.  Computing technology has made mathematical iteration more important.

When teaching mathematical iteration, the teacher should emphasize the iterative procedures have three parts:  the initial values, the recurrence relation that describes how to get subsequent terms of the sequence, and a rule for stoping the procedure.  The stopping rule is governed by which term or terms of the sequence are needed to solve the problem.

In the process of iteration, we are working with sequence of numbers.  When we iterate a particular function f[x], then the numbers that appear are x, f[x], f[f[x]], f[f[f[x]]],. . .  If we can write an equation in the form x=f[x], our goal is a sequence that converges - at least in a machine sense - to a fixed point of the function.  Geometrically, a fixed point of a function is a point where the graph of the function y=f[x] meets the line y=x.

In the upcoming example, the iterative procedure will be used to show the convergence of the functions y=x€ and y=x with an intial guess of x=.5.  The table of values listed first ceases when the difference of the iteration is less than .001.  This step was required because when the procedure was ran for the first time it did not stop iterating itself.  The screen showed ordered pairs that were identical to six degrees of accuracy but the computer did not stop it because it had computed to fifteen degrees of accuracy.

Clear[f,t,line,k,h,g,xtemp,newxo,oldx]
x0 = .5;
g[x_]=x^2;
h[x_]=x;

newxo[oldx_] := x/.FindRoot[g[x] == oldx,{x,oldx}]

pointlist = {};

xtemp = x0;

While[

N[Abs[g[xtemp]-xtemp]] > .001,

AppendTo[pointlist,{xtemp,g[xtemp]}];

xtemp=N[newxo[xtemp]]]


pointlist

In the graphics to follow, I stopped the iterator sooner at .01 because you could not tell the difference between the last few plotted points.  You will see the curve y=x€, the line y=x, and a series of horizontal and vertical lines that show the iterative process taking you from the curve to the line.

Clear[xmax,xmin,ymax,ymin]
xmax=Max[(Transpose[pointlist])[[1]]]+1;
xmin=Min[(Transpose[pointlist])[[1]]]-1;
ymax=Max[(Transpose[pointlist])[[2]]]+1;
ymin=Min[(Transpose[pointlist])[[2]]]-1;
Clear[x,pts,xtemp]
xtemp = x0;

pts = {};
hlines = {};
vlines = {};

Clear[vert,horiz]
While[
N[Abs[g[xtemp]-xtemp]] > .01,

AppendTo[vlines,Line[{{xtemp,xtemp},
{xtemp,g[xtemp]}}]];

AppendTo[hlines,Line[{{xtemp,xtemp},
{newxo[xtemp],g[newxo[xtemp]]}}]];

AppendTo[pts,{PointSize[.02],Point[{xtemp,g[xtemp]}]}];

gr = Join[pts,hlines,vlines];

Plot[{g[x],h[x]},{x,xmin,xmax},
Epilog->gr,
DisplayFunction->$DisplayFunction,
AspectRatio->Automatic,
PlotRange->{{xmin,xmax},{ymin,ymax}}];

xtemp = N[newxo[xtemp]];
]

Iteration was also used by Newton in his efforts to find roots of a function.  Many applications of calculus involve solving equations that are in the form of f[x]=0 or that can be put in this form.  Algebraic techniques such as factoring can be used to solve only a handful of the possibilities.  In most situations exact solutions cannot be determined but approximate solutions can be found.  Here we will look at Newton's Methods, which involves approximating the graph of f[x] by its tangent lines.

We start by picking a value xº  that we expect to be fairly close to a solution and calculate f[xº ].  If f[xº ]=0, we have our desired solution.  Otherwise, we consider the tangent line to the graph y=f[x] at x=xº .  If f'[x]Æ0, the tangent line is not horizontal and we let x¡  denote the value of x where the tangent line intersects the x-axis.  In the following graphics, we will be using the function y=x‹-x , with our initial guess xº =1.5

Since f[x¡ ] and f'[x¡ ] are not zero, we let x™  be the point where the tangent line at x=x¡  intersects the x-axis.  Here is the second run.

Continuing in this fashion, we obtain a succession of numbers xº ,x¡ ,x™ ,. . . and in many cases, the number xå  for a reasonably small interger a is the desired approximate solution of f[x]=0.  In this process x¡  is computed from xº , x™  is computed from x¡ , and in general xå ≠ ¡  is computed from xå .  The following table is a list of ordered pairs of the iteration process and the graphics of Newton's method for approximate solution of a function.  The code was rigged to round to the fifth decimal place in order to minimize needless calculations, since we are dealing with approximate solutions anyhow.

Clear[f,t,line,k]

x0 = 1.5;

f[x_] = x^3-x;

line[k_] := f'[k](x-k)+f[k];

t[k_]:= (x/.Solve[line[k] == 0,x])[[1]]
pointlist = {};

xtemp = x0;

While[Chop[N[f[t[xtemp]]]] != 0,
      AppendTo[pointlist,{xtemp,f[xtemp]}];
      xtemp = t[xtemp]];
AppendTo[pointlist,{Chop[xtemp,10^-5],0}]

Now you will see the complete graphics iteration that yielded the table from above.  I will leave the previous iterative points to show that it does converge numerically to an approximation of a root for the function f[x]=x‹-x.

xmax=Max[(Transpose[pointlist])[[1]]]+1;
xmin=Min[(Transpose[pointlist])[[1]]]-1;
ymax=Max[(Transpose[pointlist])[[2]]]+1;
ymin=Min[(Transpose[pointlist])[[2]]]-1;
Clear[x,pts]



xtemp = x0;

pts = {};

While[ Chop[N[f[t[xtemp]]]] != 0,

Plot[{f[x],line[xtemp]},{x,xmin,xmax},
     Epilog->{AppendTo[pts,
         {PointSize[.02],Point[{xtemp,f[xtemp]}]}],
          Line[{{t[xtemp],0},{t[xtemp],f[t[xtemp]]}}]},
     DisplayFunction->$DisplayFunction,
     PlotRange->{{xmin,xmax},{ymin,ymax}}];

xtemp = t[xtemp];
]

Newton's method is not flawless.  There are two such situations that would cause his iteration process to fail.  One such failure occurs when our initial guess has a horizontal tangent and will not let us move to the next step because each point comes from the previous step.  The following is an example using the function f[x]=1-x€ with initial guess xº =0.

Clear[f,x]
k=0;
f[x_]=1-x^2;
tanlin=f'[k] (x-k)+f[k];

Plot[{f[x],tanlin},{x,-1.5,1.5}]

Another way Newton's method can fail is by choosing a bad initial guess to start the iteration.  In the following example we will use the arctan function with initial guess xº =1.5.  I stop the iteration process after eight rounds because the iterations are getting larger instead of smaller.

Clear[f,t,line,k]

x0 = 1.5;

f[x_] = ArcTan[x];

line[k_] := f'[k](x-k)+f[k];

t[k_]:= (x/.Solve[line[k] == 0,x])[[1]]
pointlist = {};

xtemp = x0;

Do[
      AppendTo[pointlist,{xtemp,f[xtemp]}];
      xtemp = t[xtemp],{n,1,8}];
      Print[pointlist]

For the graphics display I stopped the loop after five intervals to make the graphics more proportional.

xmax=40;
xmin=-50;
ymax=3;
ymin=-3;
Clear[x,pts]



xtemp = x0;

pts = {};

Do[

Plot[{f[x],line[xtemp]},{x,xmin,xmax},
     Epilog->{AppendTo[pts,
         {PointSize[.02],Point[{xtemp,f[xtemp]}]}],
          Line[{{t[xtemp],0},{t[xtemp],f[t[xtemp]]}}]},
     DisplayFunction->$DisplayFunction,
     PlotRange->{{xmin,xmax},{ymin,ymax}}];

xtemp = t[xtemp];,{n,1,5}
]

Notice the last segment for the iteration is nearly parallel.  We are going in the wrong direction to find a root.  With a better initial guess the iteration process will work.  We will use the same function, but start with an xº =.8 and an approximate root appears after only six iterations.  I stopped the graphics after five, because you can not tell the difference between the last few anyhow.

Clear[f,t,line,k]

x0 = .8;

f[x_] = ArcTan[x];

line[k_] := f'[k](x-k)+f[k];

t[k_]:= (x/.Solve[line[k] == 0,x])[[1]]
pointlist = {};

xtemp = x0;

Do[
      AppendTo[pointlist,{xtemp,f[xtemp]}];
      xtemp = t[xtemp],{n,1,6}];
      Print[pointlist]

xmax=1.5;
xmin=-1.5;
ymax=1.5;
ymin=-1.5;
Clear[x,pts]



xtemp = x0;

pts = {};

Do[

Plot[{f[x],line[xtemp]},{x,xmin,xmax},
     Epilog->{AppendTo[pts,
         {PointSize[.02],Point[{xtemp,f[xtemp]}]}],
          Line[{{t[xtemp],0},{t[xtemp],f[t[xtemp]]}}]},
     DisplayFunction->$DisplayFunction,
     PlotRange->{{xmin,xmax},{ymin,ymax}}];

xtemp = t[xtemp];,{n,1,5}
]

A knowledge of mathematical iteration may give students a conceptual framework for understanding complex concepts, for exploring problems, and for carrying out procedures.  Instruction in the process of iteration, which is important in both mathematics and computer science, allows students to develop their powers of induction as they recognize and identify patterns and to explore such important mathematical concepts as limits and convergence.