5.3 Iterative Methods
105
available via Internet; see appendix for details. The performance of SIP for
a model problem will be presented in Sect. 5.8.
Unlike other methods, Stone's method is both a good iterative technique
in its own right and a good basis for conjugate gradient methods (where
it is called a preconditioner) and multigrid methods (where it is used as a
smoother). These methods will be described below.
5.3.5 AD1 a n d O t h e r Splitting M e t h o d s
A common method of solving elliptic problems is t o add a term containing the
first time derivative to the equation and solve the resulting parabolic problem
until a steady state is reached. At that point, the time derivative is zero and
the solution satisfies the original elliptic equation. Many iterative methods of
solving elliptic equations, including most of those already described, can be
interpreted in this way. In this section we present a method whose connection
to parabolic equations is so close that it might not have been discovered if
one were thinking only of elliptic equations.
Considerations of stability require methods for parabolic equations to be
implicit in time. In two or three dimensions, this requires solution of a two or
three dimensional elliptic problem a t each time step; the cost can be enormous
but it can be reduced considerably by using the alternating direction implicit
or AD1 method. We give only the simplest such method in two dimensions
and a variant. AD1 is the basis for many other methods; for more details of
some of these methods see Hageman and Young (1981).
Suppose we want to solve Laplace equation in two dimensions. Adding a
time derivative to it converts it to the heat equation in two dimensions:
If this equation is discretized using the trapezoid rule in time (called CrankNicolson when applied to partial differential equations; see next chapter),
and central differences are used to approximate the spatial derivatives on a
uniform grid, we obtain:
where we have used the shorthand notation:
105
available via Internet; see appendix for details. The performance of SIP for
a model problem will be presented in Sect. 5.8.
Unlike other methods, Stone's method is both a good iterative technique
in its own right and a good basis for conjugate gradient methods (where
it is called a preconditioner) and multigrid methods (where it is used as a
smoother). These methods will be described below.
5.3.5 AD1 a n d O t h e r Splitting M e t h o d s
A common method of solving elliptic problems is t o add a term containing the
first time derivative to the equation and solve the resulting parabolic problem
until a steady state is reached. At that point, the time derivative is zero and
the solution satisfies the original elliptic equation. Many iterative methods of
solving elliptic equations, including most of those already described, can be
interpreted in this way. In this section we present a method whose connection
to parabolic equations is so close that it might not have been discovered if
one were thinking only of elliptic equations.
Considerations of stability require methods for parabolic equations to be
implicit in time. In two or three dimensions, this requires solution of a two or
three dimensional elliptic problem a t each time step; the cost can be enormous
but it can be reduced considerably by using the alternating direction implicit
or AD1 method. We give only the simplest such method in two dimensions
and a variant. AD1 is the basis for many other methods; for more details of
some of these methods see Hageman and Young (1981).
Suppose we want to solve Laplace equation in two dimensions. Adding a
time derivative to it converts it to the heat equation in two dimensions:
If this equation is discretized using the trapezoid rule in time (called CrankNicolson when applied to partial differential equations; see next chapter),
and central differences are used to approximate the spatial derivatives on a
uniform grid, we obtain:
where we have used the shorthand notation: