Page 160 - 35Linear Algebra

160 Matrices

    
1 0 0 d  x = d   x = d
a 1 0 e ⇒ y = e − ax ⇒ y = e − ad .
 
b c 1 f  z = f − bx − cy   z = f − bd − c(e − ad)
For lower triangular matrices, forward substitution gives a quick solution; for upper
triangular matrices, back substitution gives the solution.

7.7.1 Using LU Decomposition to Solve Linear Systems

Suppose we have M = LU and want to solve the system

MX = LUX = V.
 
u
v
• Step 1: Set W =   = UX.
w

• Step 2: Solve the system LW = V . This should be simple by forward
substitution since L is lower triangular. Suppose the solution to LW =
V is W 0 .

• Step 3: Now solve the system UX = W 0 . This should be easy by
backward substitution, since U is upper triangular. The solution to
this system is the solution to the original system.

We can think of this as using the matrix L to perform row operations on the
matrix U in order to solve the system; this idea also appears in the study of
determinants.

Reading homework: problem 7

Example 97 Consider the linear system:

6x + 18y + 3z = 3
2x + 12y + z = 19
4x + 15y + 3z = 0

An LU decomposition for the associated matrix M is
     
6 18 3 3 0 0 2 6 1
2 12 1 = 1 6 0 0 1 0 .
     
4 15 3 2 3 1 0 0 1

160