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