5.3 Iterative Methods
99
where a k is a constant. Then the iterative procedure (5.22) yields:
and, by induction, it is not difficult to show that
It is clear that, if en is t o become zero when n is large, the necessary and
sufficient condition is that all of the eigenvalues must be less than unity in
magnitude. In particular, this must be true of the largest eigenvalue, whose
magnitude is called the spectral radius of the matrix M - ' N . In fact, after
a number of iterations, the terms in Eq. (5.26) that contain eigenvalues of
small magnitude become very small and only the term containing the largest
eigenvalue (which we can take to be X 1 and assume t o be unique) remains:
If convergence is defined as the reduction of the iteration error below some
tolerance 6, we require:
Taking the logarithm of both sides of this equation, we find an expression for
the required number of iterations:
We see that, if the spectral radius is very close to unity, the iterative procedure
will converge very slowly.
As a simple (trivial might be more descriptive) example consider the case
of a single equation (for which one would never dream of using an iterative
method). Suppose we want to solve:
and we use the iterative method (note that m = a + n and p is the iteration
counter):
Then the error obeys the scalar equivalent of Eq. (5.22):
99
where a k is a constant. Then the iterative procedure (5.22) yields:
and, by induction, it is not difficult to show that
It is clear that, if en is t o become zero when n is large, the necessary and
sufficient condition is that all of the eigenvalues must be less than unity in
magnitude. In particular, this must be true of the largest eigenvalue, whose
magnitude is called the spectral radius of the matrix M - ' N . In fact, after
a number of iterations, the terms in Eq. (5.26) that contain eigenvalues of
small magnitude become very small and only the term containing the largest
eigenvalue (which we can take to be X 1 and assume t o be unique) remains:
If convergence is defined as the reduction of the iteration error below some
tolerance 6, we require:
Taking the logarithm of both sides of this equation, we find an expression for
the required number of iterations:
We see that, if the spectral radius is very close to unity, the iterative procedure
will converge very slowly.
As a simple (trivial might be more descriptive) example consider the case
of a single equation (for which one would never dream of using an iterative
method). Suppose we want to solve:
and we use the iterative method (note that m = a + n and p is the iteration
counter):
Then the error obeys the scalar equivalent of Eq. (5.22):