15.4 Iterative Methods For Linear Systems
Consider the problem of solving the equation
where A is an n × n matrix. In many applications, the matrix A is huge and composed mainly of
zeros. For such matrices, the method of Gauss elimination (row operations) is not a good way
to solve the system because the row operations can destroy the zeros and storing all those
zeros takes a lot of room in a computer. These systems are called sparse. The method is to
where B−1 exists. Then the system is of the form
and so the solution is solves
In other words, you look for a fixed point of T. There are standard methods for finding such fixed
points which hold in general Banach spaces which is the term for a complete normed linear
Definition 15.4.1 A normed vector space, E with norm
is called a Banach space if it is also
complete. This means that every Cauchy sequence converges. Recall that a sequence
n=1∞ is a Cauchy
sequence if for every ε >
0 there exists N such that whenever m,n > N,
is a Cauchy sequence, there exists x such that
The following is an example of an infinite dimensional Banach space. We have already observed that
finite dimensional normed linear spaces are Banach spaces.
Example 15.4.2 Let E be a Banach space and let Ω be a nonempty subset of a normed linear space F.
denote those functions f for which
Denote by BC
the set of functions in B
which are also continuous.
Lemma 15.4.3 The above
is a norm on B
. The subspace BC
with the given norm
is a Banach space.
Proof: It is obvious
is a norm. It only remains to verify
is complete. Let
Cauchy sequence. Since
0 as m,n →∞,
it follows that
is a Cauchy sequence in
for each x
. Let f
. Then for any
whenever m,n are large enough, say as large as N. For n ≥ N, let m →∞. Then passing to the limit, it
follows that for all x,
and so for all x,
It follows that
It remains to verify that f is continuous.
for all n
large enough. Now pick such an n
. By continuity, the last term is less than
is continuous as well. ■
The most familiar example of a Banach space is Fn. The following lemma is of great importance so it is
stated in general.
Lemma 15.4.4 Suppose T : E → E where E is a Banach space with norm
. Also suppose
for some r ∈
. Then there exists a unique fixed point, x ∈ E such that
Letting x1 ∈ E, this fixed point x, is the limit of the sequence of iterates,
In addition to this, there is a nice estimate which tells how close x1 is to x in terms of things which can be
Proof: This follows easily when it is shown that the above sequence,
is a Cauchy
sequence. Note that
By induction, this shows that for all k ≥
is valid. Now let k > l ≥ N.
which converges to 0 as N →∞.
Therefore, this is a Cauchy sequence so it must converge to x ∈ E.
This shows the existence of the fixed point. To show it is unique, suppose there were another one, y.
and so x = y.
It remains to verify the estimate.
and solving the inequality for
gives the estimate desired.
The following corollary is what will be used to prove the convergence condition for the various iterative
Corollary 15.4.5 Suppose T : E → E, for some constant C
for all x,y ∈ E, and for some N ∈ ℕ,
for all x,y ∈ E where r ∈
. Then there exists a unique fixed point for T and it is still the limit of the
for any choice of x1.
Proof: From Lemma 15.4.4 there exists a unique fixed point for TN denoted here as x. Therefore,
TNx = x. Now doing T to both sides,
By uniqueness, Tx = x because the above equation shows Tx is a fixed point of TN and there is only one
fixed point of TN. In fact, there is only one fixed point of T because a fixed point of T is automatically a
fixed point of TN.
It remains to show Tkx1 → x, the unique fixed point of TN. If this does not happen, there exists ε > 0
and a subsequence, still denoted by Tk such that
Now k = jkN + rk where rk ∈
is a positive integer such that limk→∞jk
there exists a single r ∈
such that for infinitely many
Taking a further
subsequence, still denoted by Tk
and this contradicts 15.14. ■
Now return to our system Ax = b. Recall it was a fixed point of T where
Then the fundamental theorem on convergence is the following. First note the following.
does not depend on
does not depend on
Theorem 15.4.6 Suppose ρ
1. Then the iterates in ?? converge to the unique solution
Proof: Consider the iterates in ??. Let Tx = B−1Cx + B−1b. Then
refers to any of the operator norms. It doesn’t matter which one you pick because they are all
equivalent. I am writing the proof to indicate the operator norm taken with respect to the usual norm on
. Since ρ
it follows from Gelfand’s theorem, Theorem 15.2.4
on Page 1071
, there exists N
such that if k ≥ N,
≤ r <
and so Corollary
applies and gives the conclusion of this
In the Jacobi method, you have
and you let B be the diagonal matrix whose diagonal entries are those of A and you let C be
the matrix obtained from
by making the diagonal entries 0 and retaining all the other entries of A
In the Gauss Seidel method, you let
Thus you keep the entries of A which are on or below the main diagonal in order to get B. To get C you
take −1 times the matrix obtained from A by replacing all entries below and on the main diagonal with
Observation 15.4.7 Note that if A is diagonally dominant, meaning
then in both cases above,
so the two iterative procedures will converge.
To see this, suppose
Then you get
However, in either the case of Jacobi iteration or Gauss Seidel iteration, the matrix λB − C will be
diagonally dominant and so by Gerschgorin’s theorem will have no zero eigenvalues which requires that this
matrix be one to one. Thus there are no eigenvectors for such λ and hence ρ