Page 54 - Numerical methods for chemical engineering

40 1 Linear algebra

We now extract from this matrix the lower and upper triangular matrices
 
a 11 a 12 a 13 ... a 1N
1
 
 (2,1) (2,1) 
2N
 λ 21 1   a 22 a 23 ... a (2,1) 
 
   
λ 31 λ 32 U =  (3,2) 
 1  (3,2)
L =   a ... a
 . . . .   33 3N 
 . . . . . . . .   . . . . . . 


λ N1 λ N2 λ N3 ... 1  (N,N−1) 
a
NN
(1.196)
We demonstrate that A = LU by forming the product
 
1
  a 11 a 12 a 13 ... a 1N
(2,1) (2,1) (2,1)
 
 λ 21 1   a 22 a 23 ... a 2N 
   
λ 31 λ 32 a ... a (1.197)
 1   (3,2) (3,2) 
LU = 
  33 3N 
 . . . .
 . . . . . . . .   . . . . 
 

 . . 
... 1 (N,N−1)
λ N1 λ N2 λ N3
a
NN
For the elements in the first row of LU, matrix multiplication yields
(1.198)
(LU) 1 j = (1)(a 1 j ) = a 1 j
Next, in the second row, we have
(2,1)
(LU) 2 j = (λ 21 )(a 1 j ) + a (1.199)
2 j
(2,1)
But, since in Gaussian elimination, a 2 j = a 2 j − λ 21 × a 1 j ,
(LU) 2 j = (λ 21 )(a 1 j ) + [a 2 j − λ 21 × a 1 j ] = a 2 j (1.200)
We can continue this process to find that each row of LU equals the corresponding row of
A, and thus A = LU.
As an example, consider the system (1.2),
111 x 1 4
     
213 = 7 (1.201)
   x 2   
316 x 3 2
Gaussian elimination (without partial pivoting) for this system was demonstrated earlier,
and from (1.70)–(1.89) we obtain the factorization
1 1 1 1
   
L =  21  U =  −11  (1.202)
321 1
Multiplying these two matrices shows that indeed they satisfy A = LU.
We have seen that to make Gaussian elimination robust, we must include partial pivoting
so that all λ kj are finite. When the factorization is performed using Gaussian elimination
with partial pivoting, the book-keeping is a bit more complex, but the result is similar. We
obtain lower and upper triangular matrices L and U, and a permutation matrix P, such that
PA = LU (1.203)