338 CHAPTER 14. NUMERICAL SOLUTIONS OF LINEAR SYSTEMS

are of the formBxr+1 =−Cxr +b

where A=B+C. In the Jacobi procedure, the matrix C was obtained by setting the diagonalof A equal to zero and leaving all other entries the same while the matrix B was obtainedby making every entry of A equal to zero other than the diagonal entries which are leftunchanged. In the Gauss Seidel procedure, the matrix B was obtained from A by makingevery entry strictly above the main diagonal equal to zero and leaving the others unchanged,and C was obtained from A by making every entry on or below the main diagonal equal tozero and leaving the others unchanged. Thus in the Jacobi procedure, B is a diagonal matrixwhile in the Gauss Seidel procedure, B is lower triangular. Using matrices to explicitlysolve for the iterates, yields

xr+1 =−B−1Cxr +B−1b. (14.7)

Theorem 14.2.4 Let A = B+C and suppose all eigenvalues of B−1C have absolute valueless than 1 where A = B+C. Then the iterates in 14.7 converge to the unique solution of14.6.

A complete explanation of this important result is found in more advanced linear al-gebra books. You can also see it in [13]. It depends on a theorem of Gelfand which iscompletely proved in this reference. Theorem 14.2.4 is very remarkable because it givesan algebraic condition for convergence, which is essentially an analytical question.

14.3 The Operator Norm∗

Recall that for x ∈ Cn,|x| ≡

√⟨x,x⟩

Also recall Theorem 3.2.17 which says that

|z| ≥ 0 and |z|= 0 if and only if z = 0 (14.8)

If α is a scalar, |αz|= |α| |z| (14.9)

|z+w| ≤ |z|+ |w| . (14.10)

If you have the above axioms holding for ∥·∥ replacing |·| , then ∥·∥ is called a norm. Forexample, you can easily verify that

∥x∥ ≡max{|xi| , i = 1, · · · ,n : x = (x1, · · · ,xn)}

is a norm. However, there are many other norms.One important observation is that x7→∥x∥ is a continuous function. This follows from

the observation that from the triangle inequality,

∥x−y∥+∥y∥ ≥ ∥x∥∥x−y∥+∥x∥ = ∥y−x∥+∥x∥ ≥ ∥y∥

Hence

∥x∥−∥y∥ ≤ ∥x−y∥∥y∥−∥x∥ ≤ ∥x−y∥