Page 159 - Matrix Analysis & Applied Linear Algebra

3.10 The LU Factorization 153

Solution: The LU decomposition with partial pivoting was computed in Ex-
ample 3.10.4. Permute the components in b according to the permutation
˜
˜
p = ( 2413 ) , and call the result b. Now solve Ly = b by applying
forward substitution:
1 0 0 0 y 1 60 y 1 60
         
 −3/4 1 0 0   y 2   5   y 2   50 
1/4 0 1 0 y 3 3 y 3 −12
    =   =⇒ y =   =   .
1/2 −1/5 1/31 y 4 1 y 4 −15

Then solve Ux = y by applying back substitution:

48 12 −8 x 1 60 12
       
 05 10 −10   x 2   50   6 
00 −6 6 x 3 −12 −13
    =   =⇒ x =   .
00 0 1 x 4 −15 −15

LU Factorization with Row Interchanges
• For each nonsingular matrix A, there exists a permutation matrix
P such that PA possesses an LU factorization PA = LU.

• To compute L, U, and P, successively overwrite the array origi-
nally containing A. Replace each entry being annihilated with the
multiplier used to execute the annihilation. Whenever row inter-
changes such as those used in partial pivoting are implemented, the
multipliers in the array will automatically be interchanged in the
correct manner.

• Although the entire permutation matrix P is rarely called for, it
can be constructed by permuting the rows of the identity matrix
I according to the various interchanges used. These interchanges
can be accumulated in a “permutation counter column” p that is
initially in natural order ( 1, 2,...,n )—see Example 3.10.4.

• To solve a nonsingular linear system Ax = b using the LU de-
composition with partial pivoting, permute the components in b to
˜
construct b according to the sequence of interchanges used—i.e.,
˜
according to p —and then solve Ly = b by forward substitution
followed by the solution of Ux = y using back substitution.