Iterative Methods and Complex Dynamics
Iterative Methods and Complex Dynamics
by
Research supported by NSF,
Research Experience for Undergraduates
(REU)
Program, at DIMACS (Center for Discrete
Mathematics and Theoretical Computer Science), Rutgers University.
How does the Newton method work for complex roots?
Consider the equation
f(z)=0
where f is analytic, and the
Newton iteration
z := N(z)
used for solving it. In the real case, the geometric interpretation of the
Newton iteration is well known: at a point x_, the
next iterate N(x_) is the zero of the line
y = f(x_) + f'(x_)(x-x_)
tangent to the graph of f at (x_,f(x_)).
What is the geometric interpretation
of Newton's iteration in the complex case?
For convenience we identify the complex number z = x+iy with the
2-dimensional vector (x,y). Let F(x,y) := |f(x+iy)| be
the absolute value of f.
At a point z_ = x_ + i y_, consider:
-
the plane T tangent to the graph of F at
(x_,y_,F(x_,y_)), and
-
the line L where T intersects
the xy-plane (assuming non-horizontal tangent, i.e. f'(z_) nonzero).
Then the next Newton iterate N(z_) corresponds to the point on
the line L which is closest to (x_,y_), i.e. the
perpendicular projection of (x_,y_) on the line L.
We prove this in Ref. [2], Theorem 1.
See illustration in Fig. 2.
|
Fig. 1: Level sets of |z^4-1|
Fig. 2: Several Newton iterations
|
Same for the Halley method
Consider again the equation f(z) = 0, and the Halley iteration
z := H(z)
for its solution. The geometric interpretation of the Halley iteration
is given as follows.
Let w = h(z) be the Möbius transformation which is
osculating to f at z_, i.e.
h(z_) = f(z_)
h'(z_) = f'(z_)
h''(z_) = f''(z_)
Equivalently, let w = h(z) be the Möbius transformation whose
level set {z: |h(z)| = |h(z_)|} is the
osculating circle of the level set of |f| at z_.
Then the next Halley iterate H(z_) is the zero of h.
This is proved in Ref. [2], Theorem 2.
|
Fig. 3:
Two Halley iterations, level sets and osculating circles
|
Same for the quasi-Halley method
The quasi-Halley method is a method of order 2.41, which uses the
same information as Newton's method (except for an additional point z- and
derivative f'(z-) at the initial iteration), see Ref. [1].
The geometric interpretation of the quasi-Halley iteration
z := Q(z)
is: the new iterate Q(z) is the zero of the Möbius transformation
w = h(z) which is tangent ("1.5 order") of f at z, in the sense that
h(z) = f(z)
h'(z) = f'(z)
h''(z) = (f'(z) - f'(z-))/(z - z-)
The level set {z: |h(z)| = |h(z_)|} is no longer the osculating circle
of {z: |f(z)| = |f(z_)|}, but approximates it near a root to which the
method converges.
The attraction basins of the Newton and Halley methods
Consider a polynomial equation
f(z) = 0
and an iterative method for its solution.
Given a root of f, its basin
(or domain of attraction) is the set of points from where the
iterative method eventually converges to that root.
The global behavior of the Newton method is chaotic: the (common) boundary
of the different basins is a Julia set of intricate shape,
see Fig. 4.
The level sets of |f(z)| shed some light on the Julia set of the Newton basins,
as can be seen in
Fig. 5,
obtained by superimposing the level sets
(Fig. 1) on the
Newton basins (Fig. 4).
Fig. 4: Newton basins for f(z) = z^4-1
Fig. 5:
Same with superimposed level sets of |z^4-1|
The global behavior of the Halley method is "less" chaotic,
compare Fig. 4 and Fig. 6.
The Julia set
is on the boundary of circular "half-moons" (comets?), see
Fig. 6 and Fig. 7.
Fig. 6: Halley basins for f(z) = z^4-1
Fig. 7: Detail of the Halley comets for f(z) = z^4-1
Fig. 8: Halley basins for f(z) = z^3-1
Fig. 9: Halley basins for f(z) = z^3-z
Fig. 10: Superimposing the level sets of f(z) = z^4-1 on
its Halley basins.
References
- Ref. [1]
Adi Ben-Israel,
Newton's method with modified functions,
Contemporary Mathematics 204(1997), 39-50
- Ref. [2]
Lily Yau and Adi Ben-Israel,
The Newton and Halley methods for complex roots,
Amer. Math. Monthly 105(1998), 806-818
Related links
You are the
th visitor to our page
since Fri Aug 16 14:25:52 EST 1996
Thank you for visiting us! Please E-mail us at
ty35@columbia.edu or
bisrael@rutcor.rutgers.edu
if you have comments, suggestions, or just to say hello.
Pictures will be added from time to time.
Fig. 4: Newton basins for f(z) = z^4-1
Fig. 5:
Same with superimposed level sets of |z^4-1|
Fig. 6: Halley basins for f(z) = z^4-1
Fig. 7: Detail of the Halley comets for f(z) = z^4-1
Fig. 8: Halley basins for f(z) = z^3-1
Fig. 9: Halley basins for f(z) = z^3-z
