 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)); 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*sqrt(9-v^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.