In most programming languages numerical operations are usually done by iteration (i.e. loops and jumps) and/or by recursion (i.e. recursive function calls).  Many of these operations can easily be done in Derive using its built-in calculus and vector functions (see Calculus commandsCalculus_commands and Vectors and MatricesVectors_and_Matrices).  For example, SUM and PRODUCT can be used to add or multiply a sequence of expressions.  VECTOR can be used to generate a table of data.  The SUB operator can be used to extract data from a vector or table.


In addition to these specialized functions, Derive provides two built-in functions for general-purpose iteration:  ITERATE and ITERATES.  Simplifying or approximating an expression of the form

ITERATES (u, x, x0)

causes the update formula

x  ←  u(x)

to be repeatedly applied, starting with x=x0, until x is equal to one of its earlier values.  The result is a vector of these values, starting with x0.


The fixed-point iteration method for solving an equation provides a good illustration of the use of ITERATES.  For example, to solve the transcendental equation x = exp(-x/20) plot the difference in the two sides of the equation

x - EXP(-x/20)

and note that a solution exists in the neighborhood of x=1.  To refine this initial guess, substitute the guess into the right side of the equation, and then approximate the result to determine a second approximation for x.  Then substitute this second approximation for x in the right side to determine a third approximation, and so on.


The function ITERATES can be used to automate this process.  For example, using the Simplify > Approximate command1LCSBCN at 6 digits of precision,

solns := ITERATES(EXP(-x/20), x, 1)

approximates to the vector

[1, 0.951229, 0.953551, 0.953441, 0.953446, 0.953446, 0.953446, 0.953446]

of successively better approximations to x = exp(-x/20).


If the above expression involving ITERATES is simplified rather than approximated, no iterate would ever equal an earlier one and the iteration would never terminate.  Therefore, approximation is the appropriate operation to apply for this particular application of ITERATES.


Note that displayed in decimal notation the last four approximations in the above vector appear equal.  However if solns is simplified, the approximations are displayed in rational notation as

⎡    4681    349    8437    19559    21013    18412    18412 ⎤
⎢1, ——————, —————, ——————, ———————, ———————, ———————, ———————⎥
⎣    4921    366    8849    20514    22039    19311    19311 ⎦

and it becomes apparent that only the last two values are actually equal.  The decimal notation only makes it appear that ITERATES did more iterations than necessary.


ITERATES takes an optional fourth argument giving exactly how many iterations to perform.  For example, at 6 digits of precision

ITERATES(EXP(-x/20), x, 1, 5)

approximates to the six element vector

[1, 0.951229, 0.953551, 0.953441, 0.953446, 0.953446]


If the fourth argument of ITERATES is a negative integer, the inverse of the first argument is iterated upon.  For example,

ITERATES(TAN(x), x, x, -1)

simplifies to [x, ATAN(x)].  This feature is used to define INVERSE in MiscellaneousFunctions.mth144O15P.


The fixed-point iteration method often diverges since the magnitudes of successive iterates get bigger and bigger until memory is exhausted.  Thus, it is usually a good idea to make the fourth argument of ITERATES a small positive integer.  See EquationSolving.mth.S02QQ for more detailed discussion of fixed-point iteration.


Newton's method for solving an equation provides another good illustration of the use of ITERATES.  For example, if the function NEWTON is defined as

NEWTON(u, x, x0, n) := ITERATES(x - u/DIF(u, x), x, x0, n)

NEWTON can be used to solve equations of the form u=0 with an initial guess of x=x0.  It repeatedly applies the update formula

x ← x - u/u’

to correct the current approximation for x by subtracting u divided by the derivative of u and evaluating the result at x.  If n is a positive integer, the iteration is repeated n times; otherwise, it is repeated until x is equal to one of its earlier values.  For example,

NEWTON(x^2-3, x, 2)

approximates to a vector of successively better approximations to the square root of 3.  See EquationSolving.mth.S02QQ for a more detailed discussion of Newton's method.


As another example of the use of ITERATES, consider the continued fraction

              a           
b + ————————————————————— 
                a         
    b + ————————————————— 
               ...        
                     a    
              b + ——————— 
                       a  
                  b + ——— 
                       x  


where there are n divisions.  Entering such expressions on the expression entry line would be tedious, especially for large n.  However, using ITERATES it is possible to generate the continued fraction by applying the update formula

r  ←  b+ a/r

to itself n times, starting with r=x.  For example, if the function CF is defined as

CF(b, a, x, n) := ITERATES(b + a/r, r, x, n)

trivially factoring

CF(1, 1, x, 6)

yields a vector that allows you to guess the general form of the continued fraction a=1 and b=1 for n divisions.


Other Programming in DERIVEProgramming 

Created with the Personal Edition of HelpNDoc: Easily create EBooks