Page 393 - 35Linear Algebra
P. 393
G.6 Matrices 393
Using an LU Decomposition
Lets go through how to use a LU decomposition to speed up solving a system of
equations. Suppose you want to solve for x in the equation Mx = b
1 0 −5 6
3 −1 −14 x = 19
1 0 −3 4
where you are given the decomposition of M into the product of L and U which
are lower and upper and lower triangular matrices respectively.
1 0 −5 1 0 0 1 0 −5
M = 3 −1 −14 = 3 1 0 0 −1 1 = LU
1 0 −3 1 0 2 0 0 1
First you should solve L(Ux) = b for Ux. The augmented matrix you would use
looks like this
1 0 0 6
3 1 0 19
1 0 2 4
This is an easy augmented matrix to solve because it is upper triangular. If
you were to write out the three equations using variables, you would find that
the first equation has already been solved, and is ready to be plugged into
the second equation. This backward substitution makes solving the system much
faster. Try it and in a few steps you should be able to get
1 0 0 6
0 1 0 1
0 0 1 −1
6
This tells us that Ux = 1 . Now the second part of the problem is to solve
−1
for x. The augmented matrix you get is
1 0 −5 6
0 −1 1 1
0 0 1 −1
It should take only a few step to transform it into
1 0 0 1
0 1 0 −2 ,
0 0 1 −1
1
which gives us the answer x = −2 .
−1
393
