calc: Nesting and Fixed Points
10.8.4 Nesting and Fixed Points
-------------------------------
The ‘H V R’ [‘nest’] command applies a function to a given argument
repeatedly. It takes two values, ‘a’ and ‘n’, from the stack, where ‘n’
must be an integer. It then applies the function nested ‘n’ times; if
the function is ‘f’ and ‘n’ is 3, the result is ‘f(f(f(a)))’. The
number ‘n’ may be negative if Calc knows an inverse for the function
‘f’; for example, ‘nest(sin, a, -2)’ returns ‘arcsin(arcsin(a))’.
The ‘H V U’ [‘anest’] command is an accumulating version of ‘nest’:
It returns a vector of ‘n+1’ values, e.g., ‘[a, f(a), f(f(a)),
f(f(f(a)))]’. If ‘n’ is negative and ‘F’ is the inverse of ‘f’, then
the result is of the form ‘[a, F(a), F(F(a)), F(F(F(a)))]’.
The ‘H I V R’ [‘fixp’] command is like ‘H V R’, except that it takes
only an ‘a’ value from the stack; the function is applied until it
reaches a “fixed point,” i.e., until the result no longer changes.
The ‘H I V U’ [‘afixp’] command is an accumulating ‘fixp’. The first
element of the return vector will be the initial value ‘a’; the last
element will be the final result that would have been returned by
‘fixp’.
For example, 0.739085 is a fixed point of the cosine function (in
radians): ‘cos(0.739085) = 0.739085’. You can find this value by
putting, say, 1.0 on the stack and typing ‘H I V U C’. (We use the
accumulating version so we can see the intermediate results: ‘[1,
0.540302, 0.857553, 0.65329, ...]’. With a precision of six, this
command will take 36 steps to converge to 0.739085.)
Newton’s method for finding roots is a classic example of iteration
to a fixed point. To find the square root of five starting with an
initial guess, Newton’s method would look for a fixed point of the
function ‘(x + 5/x) / 2’. Putting a guess of 1 on the stack and typing
‘H I V R ' ($ + 5/$)/2 <RET>’ quickly yields the result 2.23607. This
is equivalent to using the ‘a R’ (‘calc-find-root’) command to find a
root of the equation ‘x^2 = 5’.
These examples used numbers for ‘a’ values. Calc keeps applying the
function until two successive results are equal to within the current
precision. For complex numbers, both the real parts and the imaginary
parts must be equal to within the current precision. If ‘a’ is a
formula (say, a variable name), then the function is applied until two
successive results are exactly the same formula. It is up to you to
ensure that the function will eventually converge; if it doesn’t, you
may have to press ‘C-g’ to stop the Calculator.
The algebraic ‘fixp’ function takes two optional arguments, ‘n’ and
‘tol’. The first is the maximum number of steps to be allowed, and must
be either an integer or the symbol ‘inf’ (infinity, the default). The
second is a convergence tolerance. If a tolerance is specified, all
results during the calculation must be numbers, not formulas, and the
iteration stops when the magnitude of the difference between two
successive results is less than or equal to the tolerance. (This
implies that a tolerance of zero iterates until the results are exactly
equal.)
Putting it all together, ‘fixp(<(# + A/#)/2>, B, 20, 1e-10)’ computes
the square root of ‘A’ given the initial guess ‘B’, stopping when the
result is correct within the specified tolerance, or when 20 steps have
been taken, whichever is sooner.
Info Catalog
calc: Reducing
calc: Reducing and Mapping
calc: Generalized Products