402 CHAPTER 14. ANALYSIS OF LINEAR TRANSFORMATIONS

Theorem 14.4.6 Suppose ρ(B−1C

)< 1. Then the iterates described above converge to

the unique solution of Ax= b.

Proof: Consider the above iterates. Let Tx= B−1Cx+B−1b. Then∣∣∣T kx−T ky∣∣∣= ∣∣∣(B−1C

)kx−

(B−1C

)ky∣∣∣≤ ∥∥∥(B−1C

)k∥∥∥ |x−y| .

Here ||·|| refers to any of the operator norms. It doesn’t matter which one you pick becausethey are all equivalent. I am writing the proof to indicate the operator norm taken withrespect to the usual norm on E. Since ρ

(B−1C

)< 1, it follows from Gelfand’s theorem,

Theorem 14.2.4 on Page 392, there exists N such that if k ≥ N, then∣∣∣∣∣∣(B−1C

)k∣∣∣∣∣∣≤ r < 1.

Consequently, ∣∣T Nx−T Ny∣∣≤ r |x−y| .

Also |Tx−Ty| ≤∣∣∣∣B−1C

∣∣∣∣ |x−y| and so Corollary 14.4.5 applies and gives the conclu-sion 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 allthe other entries of A. Thus

B =

∗ 0

. . .

0 ∗

 , C =−

0 ∗

. . .

∗ 0

In the Gauss Seidel method, you let

B =

∗ 0

. . .

∗ ∗

 , C =−

0 ∗

. . .

0 0

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 andon the main diagonal with zeros.

Observation 14.4.7 Note that if A is diagonally dominant, meaning

|aii|> ∑j ̸=i

∣∣ai j∣∣

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 bediagonally dominant and so by Gerschgorin’s theorem will have no zero eigenvalues whichrequires that this matrix be one to one. Thus there are no eigenvectors for such λ and henceρ(B−1C

)< 1.