Page 152 - Matrix Analysis & Applied Linear Algebra

146 Chapter 3 Matrix Algebra

set
y 1 = b 1 , y 2 = b 2 − ' 21 y 1 , y 3 = b 3 − ' 31 y 1 − ' 32 y 2 , etc.
The forward substitution algorithm can be written more concisely as
i−1

and for i =2, 3,...,n. (3.10.10)
y 1 = b 1 y i = b i − ' ik y k
k=1
After y is known, the upper-triangular system Ux = y is solved using the
standard back substitution procedure by starting with x n = y n /u nn , and setting
n
1
x i = y i − u ik x k for i = n − 1,n − 2,. . . , 1. (3.10.11)
u ii
k=i+1
2
It can be verified that only n 2 multiplications/divisions and n − n addi-
tions/subtractions are required when (3.10.10) and (3.10.11) are used to solve
the two triangular systems Ly = b and Ux = y, so it’s relatively cheap to
solve Ax = b once L and U are known—recall from §1.2 that these operation
3
counts are about n /3 when we start from scratch.
If only one system Ax = b is to be solved, then there is no significant
difference between the technique of reducing the augmented matrix [A|b]to
a row echelon form and the LU factorization method presented here. However,
˜
suppose it becomes necessary to later solve other systems Ax = b with the
same coefficient matrix but with different right-hand sides, which is frequently
the case in applied work. If the LU factors of A were computed and saved
when the original system was solved, then they need not be recomputed, and
˜
the solutions to all subsequent systems Ax = b are therefore relatively cheap
to obtain. That is, the operation counts for each subsequent system are on the
3
2
order of n , whereas these counts would be on the order of n /3 if we would
start from scratch each time.
Summary

• To solve a nonsingular system Ax = b using the LU factorization
A = LU, first solve Ly = b for y with the forward substitution
algorithm (3.10.10), and then solve Ux = y for x with the back
substitution procedure (3.10.11).

• The advantage of this approach is that once the LU factors for
˜
A have been computed, any other linear system Ax = b can
2
be solved with only n 2 multiplications/divisions and n − n ad-
ditions/subtractions.