2010-07-03

What is LU decomposition, why do I care it? (1)

Gilbert Strang's Introduction to Linear Algebra 2.5

There is a method called LU decomposition. I, a Sunday researcher, always start a kind of stupid question.
- What is the LU decomposition?
- Why do I care about that?
LU decomposition is actually almost the Elimination method. The reason we do Elimination is we want to solve the system of linear equations.  I think the most important thing is understanding the problem. If we could not get the answer, but only understand the problem, it is a bit sad for me. I hope I can have a solution also. Elimination is one of the methods to solve the system. This method adds or subtracts one equation from other equation to remove some of the variables. In a junior high school in Japan, I learned this as elimination of simultaneous equation (連立一 次方程式の消去法). Let's see an elimination example using the following matrix A.

Remove a_{21}, a_{31} of A by applying Elimination matrices E_{21},E_{31}. For example, E_{21} subtracts row 1 from row 2 of A to removes a_{21}, therefore, the component of E_{21} is -1, the rest is identity matrix. E_{32} is not known at this point.


E_{21} E_{31} A is the following, this removes a_{21} and a_{31}. You see now they are zeros.
Now we know a_{32} of A is _2_. To make this triangular matrix, E_{32} is the following. The result of Elimination is:

 This is U of LU decomposition. L is the following.

When you see the component of the equation L = (E_{32} E_{31} E_{21})^{-1}, each component shows up in the L with the sign inverted. I put the corresponding component the same color in Equation (5).

I was surprised of this correspondences. Because I know the exact result of multiplication of the matrices without multiplying them. How convenient this is. Today, I stop here and I would like to think about the reason of this.

No comments: