Application Center - Maplesoft

# Classroom Tips and Techniques: Fixed-Point Iteration

You can switch back to the summary page by clicking here.

Classroom Tips and Techniques:

Fixed-Point Iteration

Robert J. Lopez

Emeritus Professor of Mathematics and Maple Fellow

Maplesoft

 Introduction Fixed-point 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 vector-valued function of a vector argument.   Note: In this article, our implementation of the Maple calculations is command-based 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 context-sensitive menus.

Initializations

 > restart;
 > with(plots):

Fixed-Point Iteration: Scalar Case

Starting from , fixed-point 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

 > q := x^2-6*x+5 = 0;

has the two solutions

 > solve(q,x);

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

 > 1 = g(1); 5 = g(5);

The sequence defined by  will converge to  if  is sufficiently close to 1 because , as shown by

 > `g'`(1) = D(g)(1);

To demonstrate that fixed-point iteration starting at  converges to , we work in floating-point 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 fixed-point calculations natural in the scalar case.

Fixed-Point Iteration: Vector Case

If the vector  satisfies the equation , where  is a vector-valued function of the vector argument x, then  is a fixed-point of .  As in the scalar case, fixed-point iteration can be used to find solutions to equations of the form , where  is itself a vector-valued function of the vector argument x.

For example, if x is the vector

 > X := ;

and the function  is the vector

 > F := ;

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 floating-point arithmetic.

The first-quadrant solution can be found by fixed-point iteration if the equation  is cast into the form  by defining the vector  as follows.

 > g := ;

That the first-quadrant 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 fixed-point iteration for the vector-valued 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 top-level 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 fixed-point 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 first-quadrant 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 vector-valued function of a vector argument.  The argument of this function is the sequence of coordinates .  To implement fixed-point 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 vector-valued function of a vector argument, namely, , is most easily created with the following syntax.

 > h := v-> Vector([sqrt(5-v[2]^2), 2*sqrt(9-v[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 non-commercial, non-profit use only. Contact Maplesoft for permission if you wish to use this application in for-profit activities.