Page 34 - Numerical methods for chemical engineering

20 1 Linear algebra

We avoid such divisions by zero through the technique of partial pivoting. Before begin-
ning any row operations, let us examine the first column of A,

 
a 11
 a 21 
 
(1.103)
 
a 31 
A(:, 1) = 
 . 
.
 . 
a N1
and search all elements in this column to find the row j that contains the element with the
largest magnitude,
|a j1 |= max k∈[1, N] {|a k1 |} (1.104)

Since the order in which the equations appear is irrelevant, we are perfectly free to exchange
rows 1 and j to form the equivalent system

 
a j1 a j2 a j3 ... a jN b j
 ... 
 a 21 a 22 a 23 a 2N b 2 
. . . . . 

 . . . . . 
¯ ¯  . . . . . 
(A, b) =   (1.105)
 a 11 a 12 a 13 ... a 1N b 1 
 . . . . 

 . . . . . . . . . . 
. 
a N1 a N2 a N3 ... a NN b N
As long as any of the elements of the first column of A are nonzero, a j1 = ¯ a 11 is
nonzero and the scalar λ 21 = ¯ a 21 /¯ a 11 is finite. We may then perform without difficulty
¯ ¯
the row operations on ( A, b) that place zeros in the first column below the diagonal.
By contrast, if all of the elements of the first column are zero, as they must be if ¯ a 11 =
a j1 = 0, there can be no unique solution. We thus stop the elimination procedure at this
point.
In Gaussian elimination with partial pivoting, when moving to column i, we first examine
all elements in this column at or below the diagonal, and select the row j ≥ i with the largest
magnitude element,

|a ji |≥|a ki | ∀ k = i, i + 1,..., N (1.106)

If j = i,weswaprows j and i, and thus, unless all elements at or below the diagonal
in column i are zero, |a ji | = 0. We then can compute the scalars λ i+1,i,..., λ N,i without
having to divide by zero. If |a ji | is zero, then all of the elements a i,i , a i+1,i,... , a N,i must be
zero.
To see what happens in this case, consider the following system, obtained after placing
zeros successfully below the diagonal in the first three columns. When preparing to eliminate
the values in the fourth column, we find that all values at or below the diagonal are already