100
5. Solution of Linear Equation Systems
We see that the error is reduced quickly if n / m is small i.e. if n is small,
which means that m = a. In constructing iterative methods for systems, we
shall find that an analogous result holds: the more closely M approximates
A, the more rapid the convergence.
In an iterative method it is important to be able to estimate the iteration
error in order to decide when to stop iterating. Calculation of the eigenvalues
of the iteration matrix is difficult (it is often not explicitly known), so approximations have to be used. We shall describe some methods of estimating
the iteration error and criteria for stopping iterations later in this chapter.
5.3.3 Some Basic Methods
In the simplest method, the Jacobi method, M is a diagonal matrix whose
elements are the diagonal elements of A. For the five-point discretization
of Laplace equation, if each iteration is begun a t the lower left (southwest)
corner of the domain and we use the geographic notation introduced above,
the method is:
It may be shown that, for convergence, this method requires a number of
iterations proportional to the square of the number of grid points in one
direction. This means that it is more expensive than a direct solver so there
is little reason to use it.
In the Gauss-Seidel method, M is the lower triangular portion of A. As
it is a special case of the SOR method given below, we shall not give the
equations separately. It converges twice as fast as the Jacobi method but this
is not enough of an improvement to be useful.
One of the better methods is an accelerated version of the Gauss-Seidel
method called successive over-relaxation or SOR, which we shall describe below. For an introduction and analysis of the Jacobi and Gauss-Seidel methods, see an introductory text on numerical methods such as Ferziger (1998)
or Press et al. (1987).
If each iteration is begun a t the lower left (southwest) corner of the domain
and we again use the geographic notation, the SOR method can be written:
where w is the over-relaxation factor, which must be greater than 1 for acceleration, and n is the iteration counter. There is theory to guide the selection
of the optimum over-relaxation factor for simple problems such as Laplace
equation in a rectangular domain but it is hard to apply that theory to more
complex problems; fortunately, the behavior of the method is usually similar
to that found in the simple case. Generally, the larger the grid, the larger the
5. Solution of Linear Equation Systems
We see that the error is reduced quickly if n / m is small i.e. if n is small,
which means that m = a. In constructing iterative methods for systems, we
shall find that an analogous result holds: the more closely M approximates
A, the more rapid the convergence.
In an iterative method it is important to be able to estimate the iteration
error in order to decide when to stop iterating. Calculation of the eigenvalues
of the iteration matrix is difficult (it is often not explicitly known), so approximations have to be used. We shall describe some methods of estimating
the iteration error and criteria for stopping iterations later in this chapter.
5.3.3 Some Basic Methods
In the simplest method, the Jacobi method, M is a diagonal matrix whose
elements are the diagonal elements of A. For the five-point discretization
of Laplace equation, if each iteration is begun a t the lower left (southwest)
corner of the domain and we use the geographic notation introduced above,
the method is:
It may be shown that, for convergence, this method requires a number of
iterations proportional to the square of the number of grid points in one
direction. This means that it is more expensive than a direct solver so there
is little reason to use it.
In the Gauss-Seidel method, M is the lower triangular portion of A. As
it is a special case of the SOR method given below, we shall not give the
equations separately. It converges twice as fast as the Jacobi method but this
is not enough of an improvement to be useful.
One of the better methods is an accelerated version of the Gauss-Seidel
method called successive over-relaxation or SOR, which we shall describe below. For an introduction and analysis of the Jacobi and Gauss-Seidel methods, see an introductory text on numerical methods such as Ferziger (1998)
or Press et al. (1987).
If each iteration is begun a t the lower left (southwest) corner of the domain
and we again use the geographic notation, the SOR method can be written:
where w is the over-relaxation factor, which must be greater than 1 for acceleration, and n is the iteration counter. There is theory to guide the selection
of the optimum over-relaxation factor for simple problems such as Laplace
equation in a rectangular domain but it is hard to apply that theory to more
complex problems; fortunately, the behavior of the method is usually similar
to that found in the simple case. Generally, the larger the grid, the larger the