2010-07-06

2.5 LU decomposition (3) Why do we do LU decomposition?

Finally I can conclude LU decomposition. If you are not interested in linear algebra, unfortunately this is not for you.

Until the last two blog entries, we say LU decomposition is just an elimination, but keeping the elimination matrices as the inverse of them. As I understand, LU decomposition has two advantages.

The first point is, L and U are triangler matrix. A triangler matrix is the easiest matrix to be solved by back substitution. For example, if we want to solve the following triangler matrix system,
this is simple. I rewrite this as simultaneous equations:

Equation 12 shows directory x=5. Equation 13 is x + y = 2, we know x=5, therefore, y=-3. Equation 14 is x + 2y + z = 2, therefore, 5 - 6 + z = 2, then z = 3. We don't need any elimination process. Actually, we have done elimination to get this triangler matrix, therefore, we don't need to wonder. It is so easy to solve a triangler matrix.

The second point is LU decomposition needs only matrices. Recall the elimination needs augmented matrix to get a solution. LU decomposition doesn't have that. When we want to solve the system with many right hand sides, LU decomposition needs only one decomposition as long as the system stays the same, we could repeat back substitution for each right hand side, that is simple.

As a conclusion, the reason of doing LU decomposition is: L and U are both triangler matrix and easy to solve, for each system, we need only one decomposition and back substitution. If only the right hand side changes, we don't need perform decomposition again. LU decomposition has these two advantages compare to pure elimination.

Now we solve the system by LU decomposition. We use the following observations:

This is an example system.

LU decomposition has been done by elimination. We just solve two systems and both are triangler matrices. We have already seen how simple to solve the triangler system. This is why LU decomposition has an advantage.