USING a linear model problem, the
Runge--Kutta map is also linear. This means that the Runge--Kutta method is
bound to have only one fixed point, as has the model problem. The basin of
attraction is bound to be infinite if the fixed point is attractive, and merely
the point itself otherwise, as in the model problem. This need not be the case
with a nonlinear model problem; a Runge--Kutta method which has a certain
absolute-stability region with the linear model problem could have quite a
different region of stability with a nonlinear problem. The conventional
absolute-stability analysis can be extended to nonlinear model problems as
long as they have a stable fixed point. In this case a nonlinear
absolute-stability test can
be carried out in the same way as the linear absolute-stability test,
by finding values of 
in complex space
at which the fixed point loses stability. For example, let us look at the
simplest nonlinear equation, the logistic equation
This has the analytical solution
The problem has a stable fixed point at y=0 for 
, and a
stable
fixed point at y=1 for 
. It turns out that for this
nonlinear model problem, the nonlinear absolute-stability function is the same
as Eq.(49) for the fixed point at y=0, so that the nonlinear
absolute-stability regions for Runge--Kutta methods of orders one to four
for this fixed point are the same as those shown in Fig. 1. They are
merely the reflections of these regions in the imaginary axis of the
-plane for the other fixed point at y=1.
The breakdown of stability in the two cases though is very different. In the linear model problem one merely has a change of stability of a fixed point. After the fixed point has become unstable, all orbits diverge to infinity, and so integration of the system on a computer rapidly leads to overflow. In the case of the nonlinear model problem from the logistic equation, things are far more interesting. Let us for a moment look at the Euler method for this problem. One obtains the map
This can be put in the form
by a linear coordinate transformation 
with 
. (Any complex quadratic map can be
transformed into Eq.(54) with a similar linear coordinate
transformation.) Now Eq.(54) is immediately
recognizable as giving the Mandelbrot set
when iterated with z and c
complex and the initial z value, 
, set to the critical point of the map,
. The Mandelbrot set is then the set of complex c values for which the
z orbit remains bounded. From Julia and Fatou ,
it is known that the basin of attraction of any finite attractor will contain
the critical point (see, for example, Devaney devaney), so the
Mandelbrot set catalogues the parameter values for which a finite attractor
exists. Other initial conditions may not fall in the basin of attraction
of a finite attractor even if one exists; thus the Mandelbrot set is the
maximum region in parameter space for which orbits can remain bounded.
That is to say that using other initial conditions will lead to subsets
of the Mandelbrot set.
Figure 2:
The Mandelbrot set for the map 
, which arises
from applying the Euler method to the logistic equation, is shown in red.
The different coloured regions surrounding it indicate the speed of escape to
infinity at that point of complex 
-space. The two large circles in
this Mandelbrot set map to the prominent cardioid seen in the normal
parameterization 
of the Mandelbrot set.
The Mandelbrot set for Eq.(53) is shown in Fig. 2.
The set itself is shown in red and the different coloured regions around it
indicate the speed of escape to infinity. One can see the two nonlinear
absolute-stability regions mentioned earlier;
the circle of radius 1 and centre -1
which contains all parameter values for which the fixed point at 0 is stable,
and the circle of radius 1 and centre 1 containing the parameter values for
which the fixed point at 1 is stable. These circles map to the cardioid of
the well-known Mandelbrot set of Eq.(54) under the coordinate
transformation given above. The successively smaller circles
further along the real axis in both directions are of periods 2, 4, 8,
;
this is the well-known period-doubling cascade of the logistic map. Off the
real axis the largest buds on the main circles are of period 3. Periods
4 and 5 are the next most prominent. We can see that the breakdown of
nonlinear absolute stability on moving from inside to outside the
main circles will not necessarily immediately lead to divergence and overflow
in the computer. The result will depend on the point at which 
crosses the boundary in complex space, but it might well enter one of the buds
surrounding the main circles for which the attractor has a higher period.
The attracting set for initial conditions other than the critical point (which
is 
in these coordinates) is a subset of
the Mandelbrot set since even if 
lies inside the boundary of the
Mandelbrot set, there is no guarantee that the orbit will converge to an
attractor other than infinity, because the basin boundaries of the attractors
are finite. The basin boundary at the point 
is known as the Julia
set of 
.
Here we start to see the big difference between this model problem and
the previous linear one. We have finite basins of attraction in this
nonlinear problem, so to arrive at the required fixed point solution,
not only must one use a sufficiently small step length, but one must also
be within the Julia set at that value of 
. That is not all; it is
possible for the Runge--Kutta map of an autonomous problem to have a set of
fixed points that is larger than the set of fixed points of the differential
equation [Iserles1990,Yee et al. 1991]. This is obvious for an explicit method if in
, 
is a polynomial, since the Runge--Kutta map will be a higher-degree
polynomial than 
due to the construction of the Runge--Kutta method, and
so must have more fixed points. In fact, the fixed-point set of the
Runge--Kutta
map contains the fixed-point set of the differential equation as a subset.
If 
is a fixed point of 
then 
.
The Runge--Kutta map
has fixed points given by
where
for an explicit method.
Now if 
, 
and 
for all i.
For an implicit method
so if 
, 
for all i is again a solution.
Thus 
and so the fixed points of the differential equation are also
fixed points of the map, but they are not necessarily the only fixed points of
the map.
Figure 3:
(a) & (b).
The two ghost fixed points of two-stage explicit Runge--Kutta maps of
the logistic equation are shown as functions of 
and the Runge-Kutta
parameter 
.
Notice that they tend to infinity as 
, and that they are in general
dependent on 
and 
, whereas the real fixed points of the
logistic equation, 0 and 1, are independent of these parameters.
The Euler method is an exception: since the Euler map
is 
,
the fixed points will be given by 
, like those of the differential
equation. Iserles iserles terms methods like the Euler method,
for which the fixed-point sets of the differential equation and the map are
the same, regular methods.
He gives an example of an implicit two-stage method
that is regular. The commonly-used Runge--Kutta schemes are not implicit and
are not regular, so additional ghost
fixed points occur in the map that are not present in the differential
equation. For instance, consider the integration of the logistic equation
with a second-order explicit method. In this case, the fixed points of the
differential equation are given by a quadratic
and those of the Runge--Kutta method are given by a quartic
Thus we get two extra fixed points, and it turns out that one of these ghost
fixed points remains stable as the step length tends to zero.
In Fig. 3 we show the ghost fixed points plotted against
and 
with all variables real. Notice that the ghost roots
are dependent on the step length and the Runge--Kutta parameter whereas the
real roots are not.
Figure 4:
Nonlinear absolute-stability regions of the four fixed points of the two-stage,
second-order explicit Runge--Kutta method with 
applied to the
logistic equation are plotted in complex 
-space.
The absolute stability regions are shown in grey. The ordinate and abscissa
are 
and 
respectively.
The two absolute-stability regions from the real fixed points of the logistic
equation, the large single regions, are independent of 
, but those
of the ghost fixed points, the two disconnected circles, are not, so
we have chosen 
here. The absolute-stability regions of the
real and ghost fixed points overlap in some areas. In these cases, which
fixed point is found depends on the initial conditions.
Since consistency tells us that 
, we know that there must,
for an irregular method, be fewer fixed points when the step length is zero
than when it is nonzero. One can ask what happens to the ghost fixed points
as the step length tends to zero. Figure 3 shows that in this case
the ghost fixed points tend to infinity as the step
length decreases. In Fig. 4 we show the nonlinear
absolute-stability regions of all four fixed points for the Runge--Kutta
method with 
.
(It is interesting that whereas the two
absolute-stability regions of the real fixed points are independent of
, the two regions of the ghost fixed points are not; we choose
as our example.) The union of these four regions is the part of
the Mandelbrot set for this map in which iterates tend to a fixed point.
In addition to these regions, the Mandelbrot set
will have further regions where periodic orbits of period greater than one
are stable, similar to the buds off the most prominent circles in the
Mandelbrot set shown in Fig. 2.
Figure:
Bifurcation diagram for the well-known fourth-order Runge--Kutta method
(often called the Runge--Kutta Method), applied to the model problem
, the logistic equation, with 
.
Notice that the first bifurcation occurs at 
. Comparing this
with the picture for p=4 in Fig. 1, and remembering that
the nonlinear absolute-stability regions for the logistic equation are the same
as the linear regions of Fig. 1, we conclude that this first
bifurcation, a transcritical bifurcation where the real fixed point at 1
and a ghost fixed point meet and exchange stability, occurs as 
crosses the absolute-stability boundary. At higher values of 
, we see
the panoply of period-doubling bifurcations leading to chaos and finally escape
to infinity.
In Fig. 5, we show a
bifurcation diagram
for a fourth-order
Runge--Kutta scheme integrating the logistic equation. What we are doing here
is just looking along the real axis of the Mandelbrot set for this case;
we are keeping 
real.
The complete Mandelbrot set would be much more difficult to compute
than the quadratic case of Fig. 2, since one would have to follow
fifteen critical points. One can however say that it would have the
fourth-order
absolute-stability region of Fig. 1 and its mirror image in
the imaginary axis as subsets, in a similar fashion to the circles of
Fig. 2. The map is a sextodecic (sixteenth degree) polynomial in
, but one can see that period doubling leading to chaos and eventually
escape to infinity occurs along the real axis in a similar way to the cascade
in the logistic map. Since the fourth-order
absolute-stability regions are larger than the first-order ones, the behaviour
remains stable up to larger step lengths here than in the logistic-map case.
Figure 6:
The ghost fixed points of two-stage explicit Runge--Kutta maps of 
are shown here as a function of the step length h, and the Runge--Kutta
parameter 
.
They coalesce and disappear at a nonzero value of h. Below this limit
the ghost fixed points are imaginary. This picture is repeated periodically
in 
. The ghost fixed points disappear for 
, when we have
the regular first-order Euler method.
For another example of the appearance of ghost fixed points, we integrate
the equation 
, which has real fixed points at
where m is an integer, with a second-order explicit
Runge--Kutta method. In addition to the real fixed points, we also get ghost
fixed points which are the roots of
We plot a pair of these ghost fixed points against h and 
in Fig. 6.
The ghost fixed points, which are stable, come together and coalesce
at a nonzero h. At smaller values of h, the ghost fixed points are
imaginary even when the other variables are real. The pattern shown in
Fig. 6 is repeated periodically in 
and for all values
of 
. (There are no ghost fixed points for 
,
since in this case we have the first-order Euler method.)
Although ghost fixed points have been known about for some time
[Yamaguti & Ushiki1981,Ushiki1982,Prüfer1985], it is only recently that it has been
appreciated that, in some cases, they exist for all step lengths, i.e., at step
lengths below the linear absolute-stability boundary [Yee et al. 1991].
Thus we can see that irregularity in the numerical method can be a serious
problem. Convergence , because it is a limit concept, ties
the dynamics of the
map from the numerical method only loosely to that of the differential
equation, leaving room for major differences to occur. These differences
manifest themselves in ghost fixed points. As we have seen, the ghost
fixed points must disappear when the step length is zero, but they may be
present for all nonzero step lengths. They can be stable for arbitrarily
small step lengths, in which case a trajectory may converge to a fixed
point which does not exist in the original system. Even if they are unstable,
they still greatly affect the dynamics of the discrete system compared to the
continuous original.
The difference between linear and nonlinear absolute-stability regions is that
basin boundaries are infinite in the linear case, but finite in the nonlinear
case. Thus convergence to the fixed point is guaranteed if 
is
within the linear absolute-stability region, whereas this is not true in the
nonlinear case since, in addition, 
must be inside the Julia set.
