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
write
A = B − C
where B^{−1} exists. Then the system is of the form
Bx = Cx + b
and so the solution is solves
−1 −1
x = B Cx + B b ≡ Tx
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
space.
Definition 15.4.1A normed vector space, E with norm
||⋅||
is called a Banach space if it is alsocomplete.This means that every Cauchy sequence converges. Recall that a sequence
{xn}
_{n=1}^{∞}is a Cauchysequence if for every ε > 0 there exists N such that whenever m,n > N,
||x − x || < ε.
n m
Thus whenever
{xn}
is a Cauchy sequence, there exists x such that
lim ||x − xn|| = 0.
n→ ∞
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.2Let E be a Banach space and let Ω be a nonempty subset of a normed linear space F.Let B
(Ω;E )
denote those functions f for which
||f|| ≡ sup {||f (x)||E : x ∈ Ω} < ∞
Denote by BC
(Ω; E)
the set of functions in B
(Ω;E )
which are also continuous.
Lemma 15.4.3The above
∥⋅∥
is a norm on B
(Ω;E)
. The subspace BC
(Ω;E)
with the given normis a Banach space.
Proof:It is obvious
||⋅||
is a norm. It only remains to verify BC
(Ω;E)
is complete. Let
{fn}
be a
Cauchy sequence. Since
∥fn − fm∥
→ 0 as m,n →∞, it follows that
{fn (x)}
is a Cauchy sequence in E
for each x. Let f
(x)
≡ lim_{n→∞}f_{n}
(x)
. Then for any x ∈ Ω.
||fn(x)− fm (x )||E ≤ ||fn − fm || < ε
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,
||fn(x)− f (x )||E ≤ ε
and so for all x,
∥f (x )∥E ≤ ε+ ∥fn (x)∥E ≤ ε+ ∥fn∥.
It follows that
∥f∥
≤
∥fn∥
+ ε and
∥f − fn∥
≤ ε.
It remains to verify that f is continuous.
∥f (x )− f (y)∥E ≤ ∥f (x)− fn (x )∥E + ∥fn(x)− fn(y)∥E + ∥fn (y)− f (y)∥E
≤ 2∥f − fn∥+ ∥fn(x)− fn(y)∥ < 2ε+ ∥fn (x) − fn (y)∥
E 3 E
for all n large enough. Now pick such an n. By continuity, the last term is less than
ε3
if
∥x − y∥
is small
enough. Hence f is continuous as well. ■
The most familiar example of a Banach space is F^{n}. The following lemma is of great importance so it is
stated in general.
Lemma 15.4.4Suppose T : E → E where E is a Banach space with norm
|⋅|
. Also suppose
|Tx− T y| ≤ r|x− y| (15.9)
(15.9)
for some r ∈
(0,1)
. Then there exists a unique fixed point, x ∈ E such that
Tx = x. (15.10)
(15.10)
Letting x^{1}∈ E, this fixed pointx,is the limit of the sequence of iterates,
x1,T x1,T2x1,⋅⋅⋅. (15.11)
(15.11)
In addition to this, there is a nice estimate which tells how close x^{1}is to x in terms of things which can becomputed.
| | 1 | |
|x1 − x| ≤----|x1 − T x1|. (15.12)
1− r
(15.12)
Proof:This follows easily when it is shown that the above sequence,
which converges to 0 as N →∞. Therefore, this is a Cauchy sequence so it must converge to x ∈ E.
Then
x = lim T kx1 = lim T k+1x1 = T lim Tkx1 = Tx.
k→∞ k→∞ k→∞
This shows the existence of the fixed point. To show it is unique, suppose there were another one, y.
Then
|x − y| = |Tx − T y| ≤ r|x− y |
and so x = y.
It remains to verify the estimate.
|| 1 || ||1 1|| || 1 || ||1 1|| || 1 ||
x − x ≤ x| − T x |+ T|x − x| = x − Tx + T x − T x
≤ |x1 − T x1|+ r|x1 − x|
and solving the inequality for
||x1 − x||
gives the estimate desired. ■
The following corollary is what will be used to prove the convergence condition for the various iterative
procedures.
Corollary 15.4.5Suppose T : E → E, forsome constant C
|Tx − Ty| ≤ C |x− y|,
for allx,y∈ E, and for some N ∈ ℕ,
| N N |
|T x − T y| ≤ r|x− y |,
for allx,y∈ E where r ∈
(0,1)
. Then there exists a unique fixed point for T and it is still the limit of thesequence,
{Tkx1}
for any choice of x^{1}.
Proof:From Lemma 15.4.4 there exists a unique fixed point for T^{N} denoted here as x. Therefore,
T^{N}x = x. Now doing T to both sides,
N
T T x = T x.
By uniqueness, Tx = x because the above equation shows Tx is a fixed point of T^{N} and there is only one
fixed point of T^{N}. In fact, there is only one fixed point of T because a fixed point of T is automatically a
fixed point of T^{N}.
It remains to show T^{k}x^{1}→x, the unique fixed point of T^{N}. If this does not happen, there exists ε > 0
and a subsequence, still denoted by T^{k} such that
| |
|T kx1 − x| ≥ ε
Now k = j_{k}N + r_{k} where r_{k}∈
{0,⋅⋅⋅,N − 1}
and j_{k} is a positive integer such that lim_{k→∞}j_{k} = ∞. Then
there exists a single r ∈
{0,⋅⋅⋅,N − 1}
such that for infinitely many k,r_{k} = r. Taking a further
subsequence, still denoted by T^{k} it follows
Now return to our system Ax = b. Recall it was a fixed point of T where
x = B−1Cx + B −1b ≡ Tx
Then the fundamental theorem on convergence is the following. First note the following.
2 −1 ( −1 ) −1
T x = B C B Cx + b + B b
= (B −1C)2 + e2(b)
where e_{2}
(b)
does not depend on x. Similarly,
T nx = (B −1C)n + en (b)
where e_{n}
(b)
does not depend on x. Thus
|| ||
|T nx− T ny| ≤ ||||(B −1C)n|||||x − y|.
Theorem 15.4.6Suppose ρ
(B −1C)
< 1. Thenthe iterates in??converge to the unique solutionof??.
Proof: Consider the iterates in ??. Let Tx = B^{−1}Cx + B^{−1}b. Then
| | |( ) ( ) | ∥( )∥
|T kx− T ky| = ||B −1C k x− B −1C ky|| ≤ ∥∥B −1C k∥∥ |x − y|.
Here
||⋅||
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
E. Since ρ
( −1 )
B C
< 1, it follows from Gelfand’s theorem, Theorem 15.2.4 on Page 1071, there exists N
such that if k ≥ N, then
||||( )k||||
|| B−1C ||
≤ r < 1. Consequently,
| N N |
|T x− T y| ≤ r|x − y |.
Also
|T x− T y|
≤
|| ||
||B −1C ||
|x − y |
and so Corollary 15.4.5 applies and gives the conclusion of this
theorem. ■
In the Jacobi method, you have
( )
| ∗ ∗ |
A = |( ... |)
∗ ∗
and you let B be the diagonal matrix whose diagonal entries are those of A and you let C be
(− 1)
times
the matrix obtained from A by making the diagonal entries 0 and retaining all the other entries of A.
Thus
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
zeros.
Observation 15.4.7Note that if A is diagonally dominant, meaning
∑
|aii| > |aij|
j⁄=i
then in both cases above,
ρ (B −1C ) < 1
so the two iterative procedures will converge.
To see this, suppose
B− 1Cx = λx, |λ| ≥ 1.
Then you get
(λB − C )x = 0
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 ρ