Chapter 14

Numerical Solutions of Linear Systems14.1 Iterative Methods For Linear Systems

Consider the problem of solving the equation

Ax = b (14.1)

where A is an n× n matrix. In many applications, the matrix A is huge and composedmainly of zeros. For such matrices, the method of Gauss elimination (row operations) isnot a good way to solve the system because the row operations can destroy the zeros andstoring all those zeros takes a lot of room in a computer. These systems are called sparse.To solve them it is common to use an iterative technique. The idea is to obtain a sequenceof approximate solutions which get close to the true solution after a sufficient number ofiterations.

Definition 14.1.1 Let {xk}∞

k=1 be a sequence of vectors in Fn. Say

xk =(

xk1, · · · ,xk

n

).

Then this sequence is said to converge to the vector x =(x1, · · · ,xn) ∈ Fn, written as

limk→∞

xk = x

if for each j = 1,2, · · · ,n,limk→∞

xkj = x j.

In words, the sequence converges if the entries of the vectors in the sequence converge tothe corresponding entries of x.

Example 14.1.2 Consider xk =(

sin(1/k) , k2

1+k2 , ln(

1+k2

k2

)). Find limk→∞ xk.

From the above definition, this limit is the vector (0,1,0) because

limk→∞

sin(1/k) = 0, limk→∞

k2

1+ k2 = 1, and limk→∞

ln(

1+ k2

k2

)= 0.

A more complete mathematical explanation is given in [13].

14.1.1 The Jacobi MethodThe first technique to be discussed here is the Jacobi method which is described in the fol-lowing definition. In this technique, you have a sequence of vectors,

{xk}

which convergeto the solution to the linear system of equations and to get the ith component of the xk+1,you use all the components of xk except for the ith. The precise description follows.

Definition 14.1.3 The Jacobi iterative technique, also called the method of simultaneouscorrections, is defined as follows. Let x1 be an initial vector, say the zero vector or someother vector. The method generates a succession of vectors, x2,x3,x4, · · · and hopefully this

333