Fixed-Point Iteration in Mathematica

Sergey Fomel   02/05/2002

Example Function

We will study the fixed-point iteration using function

f[x_] := (x^2) - x - (E^(-x))

Plotting the function shows that it has the root around 1.25:

Plot[f[x], {x, 0, 3}, PlotStyle -> {Thickness[0.01]}]

Mathematica can find the root of f(x)=0 using FindRoot:

FindRoot[f[x] == 0, {x, 1}]

Transformation

There are several ways to transform the equation f(x)=0 to the form x=g(x) suitable for the fixed-point iteration:

g1[x_] := -(E^(-x)) + 
          (x^2);
g2[
          x_] := (Sqrt[(E^(-x)) + x]);
g3[x_] := -Log[-x + (x^2)];
g4[x_] := 1 + ((E^(-x))/x)

Convergence study

Which of these functions cause a convergent fixed-point iteration?

Let us study this graphically. The following horrible-looking function is used for plotting.

<< Graphics`Arrow`

fpoint[g_, glist_, n_, xrange_, yrange_] := 
      Plot[{x, g[x]}, xrange, PlotStyle -> {Thickness[0.01]}, 
        AspectRatio -> Automatic, PlotRange -> yrange, 
        Frame -> True, 
Epilog -> 
          Flatten[{Table[
{Arrow[{glist[[k]], 
                      0}, {glist[[k]], glist[[k + 1]]}, 
                    HeadCenter -> 0.5],  
                  Arrow[{glist[[k]], 
                      glist[[k + 1]]}, {glist[[k + 1]], 
                      glist[[k + 1]]}, HeadCenter -> 0.5], 
                  Text[StringJoin["C", ToString[k - 1]], {glist[[k]], 
                      0}, {0, 2}]}, {k, 1, n}], 
              Table[Arrow[{glist[[k]], glist[[k]]}, {glist[[k]], 
                    glist[[k + 1]]}, HeadCenter -> 0.5], {k, 2, 
                  n}]}], PlotLabel -> g[x], 
        DefaultFont -> {"Times-Roman", 12}, 
        FrameLabel -> {StringJoin[
              Table[StringJoin["C", ToString[k - 1], "=", 
                  ToString[glist[[k]]], "\n"], {k, 1, n + 1}]], 
            None}]

A sequence of fixed-point iterations can be generated with NestList.

fpoint[g1, NestList[g1, 1.4, 3], 
        3, {x, 0, 4}, {-1, 4}];

The first function clearly causes the iteration to diverge away from the root.

fpoint[g2, NestList[g2, 3.9, 3], 
        3, {x, 0, 4}, {-1, 4}];

The second function leads to convergence, although the rate of convergence is slow.

fpoint[g3, NestList[g3, 1.2, 2], 
        2, {x, 0, 3}, {-1, 3}];

In the third case, the iteration diverges, spiraling away from the root. The error messages are caused by the fact that the third function is discontinuous at x=1.

fpoint[g4, NestList[g4, 1.9, 4], 
        4, {x, 0.5, 2}, {-0.5, 2}];

In the fourth case, the iteration converges, spiraling towards the root.

Newton's iteration

Newton's iteration can be defined with the help of the function.

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

fpoint[g, NestList[g, 2.9, 3], 
        3, {x, 0, 3}, {-0.5, 3}];

The iteration convergence very fast due to the fact that the function g(x) has zero slope around the root.

SetPrecision[NestList[g, 2.9, 8], 16]

Six iterations are sufficient to locate the root with 16 significant digits.

Another way to display the Newton iteration is by using tangent lines.

newt[f_, glist_, n_, xrange_, yrange_] := 
      Plot[f[x], xrange, PlotStyle -> {Thickness[0.01]}, 
        AspectRatio -> Automatic, PlotRange -> yrange, 
        Frame -> True, 
Epilog -> 
          Flatten[{Table[
{Line[{{glist[[k]], 
                        f[glist[[k]]]}, {glist[[k + 1]], 0}}], 
                  Arrow[{glist[[k]], 0}, {glist[[k]], 
                      f[glist[[k]]]}, HeadCenter -> 0.5], 
                  Text[StringJoin["C", ToString[k - 1]], {glist[[k]], 
                      0}, {0, 2}]}, {k, 1, n}]}], 
        PlotLabel -> "Newton's method", 
        DefaultFont -> {"Times-Roman", 12}, 
        FrameLabel -> {StringJoin[
              Table[StringJoin["C", ToString[k - 1], "=", 
                  ToString[glist[[k]]], "\n"], {k, 1, n + 1}]], 
            None}]

newt[f, NestList[g, 2.9, 3], 3, {x, 0, 3}, {-1, 6}];