Skip to main content

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.

Comments

Popular posts from this blog

Why A^{T}A is invertible? (2) Linear Algebra

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the null spa

Gauss's quote for positive, negative, and imaginary number

Recently I watched the following great videos about imaginary numbers by Welch Labs. https://youtu.be/T647CGsuOVU?list=PLiaHhY2iBX9g6KIvZ_703G3KJXapKkNaF I like this article about naming of math by Kalid Azad. https://betterexplained.com/articles/learning-tip-idea-name/ Both articles mentioned about Gauss, who suggested to use other names of positive, negative, and imaginary numbers. Gauss wrote these names are wrong and that is one of the reason people didn't get why negative times negative is positive, or, pure positive imaginary times pure positive imaginary is negative real number. I made a few videos about explaining why -1 * -1 = +1, too. Explanation: why -1 * -1 = +1 by pattern https://youtu.be/uD7JRdAzKP8 Explanation: why -1 * -1 = +1 by climbing a mountain https://youtu.be/uD7JRdAzKP8 But actually Gauss's insight is much powerful. The original is in the Gauß, Werke, Bd. 2, S. 178 . Hätte man +1, -1, √-1) nicht positiv, negative, imaginäre (oder gar um

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) .