98
5. Solution of Linear Equation Systems
where dn = 4n+' - c$n is called the correction or update and is an approximation to the iteration error.
For an iterative method to be effective, solving the system (5.16) must be
cheap and the method must converge rapidly. Inexpensive iteration requires
that computation of N @ and solution of the system must both be easy to
perform. The first requirement is easily met; since A is sparse, N is also
sparse, and computation of N 4 " is simple. The second requirement means
that the iteration matrix M must be easily inverted; from a practical point
of view, M should be diagonal, tridiagonal, triangular, or, perhaps, block
tridiagonal or triangular; another possibility is described below. For rapid
convergence, M should be a good approximation to A, making N 4 small in
some sense. This is discussed further below.
5.3.2 Convergence
As we have noted, rapid convergence of an iterative method is key to its effectiveness. Here we give a simple analysis that is useful in understanding what
determines the convergence rate and provides insight into how to improve it.
To begin, we derive the equation that determines the behavior of the
iteration error. To find it, we recall that, a t convergence, c$n+l = c$n = 4 , so
that the converged solution obeys the equation:
Subtracting this equation from Eq. (5.16) and using the definition (5.14) of
the iteration error, we find:
The iterative method converges if lim en = 0. The critical role is played by
n+co
the eigenvalues Xk and eigenvectors + k of the iteration matrix M-'N which
are defined by:
M - ' N + ~ =
, k = 1,. . . , K ,
(5.23)
where K is the number of equations (grid points). We assume that the eigenvectors form a complete set i.e. a basis for R n , the vector space of all ncomponent vectors. If that is so, the initial error may be expressed in terms
of them:
5. Solution of Linear Equation Systems
where dn = 4n+' - c$n is called the correction or update and is an approximation to the iteration error.
For an iterative method to be effective, solving the system (5.16) must be
cheap and the method must converge rapidly. Inexpensive iteration requires
that computation of N @ and solution of the system must both be easy to
perform. The first requirement is easily met; since A is sparse, N is also
sparse, and computation of N 4 " is simple. The second requirement means
that the iteration matrix M must be easily inverted; from a practical point
of view, M should be diagonal, tridiagonal, triangular, or, perhaps, block
tridiagonal or triangular; another possibility is described below. For rapid
convergence, M should be a good approximation to A, making N 4 small in
some sense. This is discussed further below.
5.3.2 Convergence
As we have noted, rapid convergence of an iterative method is key to its effectiveness. Here we give a simple analysis that is useful in understanding what
determines the convergence rate and provides insight into how to improve it.
To begin, we derive the equation that determines the behavior of the
iteration error. To find it, we recall that, a t convergence, c$n+l = c$n = 4 , so
that the converged solution obeys the equation:
Subtracting this equation from Eq. (5.16) and using the definition (5.14) of
the iteration error, we find:
The iterative method converges if lim en = 0. The critical role is played by
n+co
the eigenvalues Xk and eigenvectors + k of the iteration matrix M-'N which
are defined by:
M - ' N + ~ =
, k = 1,. . . , K ,
(5.23)
where K is the number of equations (grid points). We assume that the eigenvectors form a complete set i.e. a basis for R n , the vector space of all ncomponent vectors. If that is so, the initial error may be expressed in terms
of them: