Classroom Tips and Techniques:
FixedPoint Iteration
Robert J. Lopez
Emeritus Professor of Mathematics and Maple Fellow
Maplesoft

Introduction


Fixedpoint iteration, also called Picard iteration, linear iteration, and repeated substitution, is easy to investigate in Maple for the scalar case. The syntax for the vector case is a bit more complex, so we show how to define a vectorvalued function of a vector argument.
Note: In this article, our implementation of the Maple calculations is commandbased and uses Maple syntax for mathematical expressions. It is worthing noting that standard math notation is also available, and many of these calculations could also have been implemented interactively, using Clickable Math tools such as palettes and contextsensitive menus.


FixedPoint Iteration: Scalar Case


Starting from , fixedpoint iteration for the scalar function generates the sequence by computing
Under the right conditions on , this sequence converges to a fixed point defined by the equation . This process is easy to demonstrate in the scalar case. For example, the quadratic equation
has the two solutions
Rearranging the equation to the form by the steps
>

q1 := q + 6*x;
q2 := q1/6;

allows us to define the function via
>

g := unapply(lhs(q2),x):
'g'(x) = g(x);

The solutions of the quadratic equation are fixed points of , as we see from
The sequence defined by will converge to if is sufficiently close to 1 because , as shown by
To demonstrate that fixedpoint iteration starting at converges to , we work in floatingpoint arithmetic and write
>

X := 4.0;
for k from 1 to 10 do
X := g(X);
print(x[k] = X);
od:

Maple's ability to implement the scalar function makes fixedpoint calculations natural in the scalar case.


FixedPoint Iteration: Vector Case


If the vector satisfies the equation , where is a vectorvalued function of the vector argument x, then is a fixedpoint of . As in the scalar case, fixedpoint iteration can be used to find solutions to equations of the form , where is itself a vectorvalued function of the vector argument x.
For example, if x is the vector
and the function is the vector
>

F := <x^2 + y^2  5, 4*x^2 + 9*y^2  36>;

then Figure 1 shows that the equations determined by have four real solutions.
>

implicitplot(convert(F,list), x=3..3, y=2.5..2.5, color=[red,black], scaling=constrained, title="Figure 1");

Maple determines these four solutions to be
>

sol := solve(convert(F,set),{x,y},explicit);

Using exact arithmetic, these solutions can be written as the vectors
>

seq(eval(X,sol[k]),k=1..4);

or as the vectors
>

seq(eval(X,evalf(sol[k])),k=1..4);

in floatingpoint arithmetic.
The firstquadrant solution can be found by fixedpoint iteration if the equation is cast into the form by defining the vector as follows.
>

g := <solve(F[1],x)[1], solve(F[2],y)[1]>;

That the firstquadrant solution is a fixed point of this is demonstrated by the calculation
>

simplify(eval(X = g, sol[1]));

We next provide several Maple implementations of fixedpoint iteration for the vectorvalued function . First, we use the vector as an expression into which we must make substitutions of the form . To obtain the substitution rules at each step of the iteration, we use the toplevel Equate command. This command takes two lists or vectors, and forms the equations determined by equating like components. Thus, we equate the components of the vectors
and
and start the fixedpoint iteration at , so that we have
>

XX := <.1,.1>;
for k from 1 to 5 do
XXX := Equate(X,XX);
XX := eval(g,XXX);
print(XX);
od:

an iteration that slowly converges to the firstquadrant fixed point.
Alternatively, in an attempt to make a function out of the vector , we write
>

G := unapply(g,x,y):
'G'(x,y) = G(x,y);

The argument of this function is not a vector, and we did not create a vectorvalued function of a vector argument. The argument of this function is the sequence of coordinates . To implement fixedpoint iteration with this function, we need to convert the output vectors to a sequence of two coordinates. We do this by converting the output vector to a list, then removing the brackets from the list by appending the brackets . Thus, the iteration can be written as
>

X := <.1,.1>;
for k from 1 to 5 do
X := G(convert(X,list)[]);
od;

A true vectorvalued function of a vector argument, namely, , is most easily created with the following syntax.
>

h := v> Vector([sqrt(5v[2]^2), 2*sqrt(9v[1]^2)/3]);

Then, the requisite iteration can be implemented with
>

X := <.1,.1>;
for k from 1 to 5 do
X := h(X);
end do;


Legal Notice: © Maplesoft, a division of Waterloo Maple Inc. 2017. Maplesoft and Maple are trademarks of Waterloo Maple Inc. This application may contain errors and Maplesoft is not liable for any damages resulting from the use of this material. This application is intended for noncommercial, nonprofit use only. Contact Maplesoft for permission if you wish to use this application in forprofit activities.
