10.10 Automatic Newton Iteration Formulas
This setting is needed to get Newton's iterations to converge.
We resume our continuing saga of arrows and complex functions. Suppose we want to investigate the behavior of Newton's iteration function Newton iteration in the complex plane. Given a function , we want to find the complex values such that .
The first step is to produce a Newton iteration formula for a given : We represent this formula by a function that performs the computation on the right-hand side, that is, .
The type Expression Integer (abbreviated EXPR INT) is used to represent general symbolic expressions in Axiom. Expression To make our facility as general as possible, we assume has this type. Given , we want to produce a Newton iteration function which, given a complex point , delivers the next Newton iteration point .
This time we write an input file called newton.input. We need to import MakeUnaryCompiledFunction (discussed in the last section), call it with appropriate types, and then define the function which references it. Here is the function :
C := Complex DoubleFloat The complex numbers
complexFunPack:=MakeUnaryCompiledFunction(EXPR INT,C,C)
Package for making functions
newtonStep(f) == Newton's iteration function
fun := complexNumericFunction f Function for $f$
deriv := complexDerivativeFunction(f,1) Function for $f'$
(x:C):C +-> Return the iterator function
x - fun(x)/deriv(x)
complexNumericFunction f == Turn an expression $f$ into a
v := theVariableIn f function
compiledFunction(f, v)$complexFunPack
complexDerivativeFunction(f,n) == Create an nth derivative
v := theVariableIn f function
df := D(f,v,n)
compiledFunction(df, v)$complexFunPack
theVariableIn f == Returns the variable in $f$
vl := variables f The list of variables
nv := # vl The number of variables
nv > 1 => error "Expression is not univariate."
nv = 0 => 'x Return a dummy variable
first vl
Do you see what is going on here? A formula is passed into the function newtonStep. First, the function turns into a compiled program mapping complex numbers into complex numbers. Next, it does the same thing for the derivative of . Finally, it returns a function which computes a single step of Newton's iteration.
The function complexNumericFunction extracts the variable from the expression and then turns into a function which maps complex numbers into complex numbers. The function complexDerivativeFunction does the same thing for the derivative of . The function theVariableIn extracts the variable from the expression , calling the function error if has more than one variable. It returns the dummy variable if has no variables.
Let's now apply newtonStep to the formula for computing cube roots of two.
Read the input file with the definitions.
The cube root of two.
Get Newton's iteration formula.
Let denote the result of applying Newton's iteration once to the complex number .
Now apply it repeatedly. How fast does it converge?
Check the accuracy of the last iterate.
In MappingPackage1, we show how functions can be manipulated as objects in Axiom. A useful operation to consider here is , which means composition. For example causes the Newton iteration formula to be applied twice. Correspondingly, means to apply the iteration formula times.
Apply twice to the point .
Apply 11 times.
Look now at the vector field and surface generated after two steps of Newton's formula for the cube root of two. The poles in these pictures represent bad starting values, and the flat areas are the regions of convergence to the three roots.
The vector field.
The surface.
