• Support PF! Buy your school textbooks, materials and every day products Here!

LU Factorization

  • #1

Homework Statement



My book is awful and I need clarification on a few things regarding LU factorization:
-If I am trying to express matrix A as a product of its upper triangular matrix (U) and the lower triangular matrix (L). I understand that I should find U first by Gauss-Jordon elimination method. But does U have to have all 1s in the diagonal or is U found once you have all zeros below the diagonal regardless of whether you have all ones in the diagonal or not?

-Once you have U, to get L, I understand that you need to multiply the inverses of all elementary matrices used to get U. But I'm unclear on the quick process of getting the inverses of the elementary matrices of a 3x3 square matrix (without having to go through Gauss Jordon elimination method again on each one).

Help?

Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
85
0
Okay, first the LU decomposition is typically used to solve a system of linear equations, right? now in the process of Gaussian elimination for a system of lin. eqs. we use multipliers which when applied to a matrix A, (the coefficient matrix) perform the function of reducing A to a unit upper triangular matrix. in order to solve the system it is not necessary for the coefficients on the diagonal to be 1 once the operation has been perform but this is what makes the decomposition UNIQUE. The permutation matrix is there to attempt to make sure that we don't divide by zero during the calculation of multipliers. It will come in handy when we are actually confronted with a system of the form Ax=b because we need to remember how we changed A so that we can change b as well during the backward subsitution phase. The inverse of an elementary matrix can be obtained from the reverse operation on the identity matrix.
 
  • #3
85
0
note, that L and U can be obtained from A after A has been reduced to a lower triangular system with multipliers on its upper triangular half in which can we take U to be the upper triangle part of the modified matrix A'. and L the lower triangle part.
 
  • #4
I'm still a little fuzzy, so can I use an example?

Let's say I have the coefficient matrix:

[tex] \left(\begin{array}{ccc}{1&-1&3\\2&0&1\\3&0&0\end{array}\right) [/tex]

I know I can perform 3 elementary operations to get the following:

[tex] \left(\begin{array}{ccc}{1&-1&3\\0&2&-5\\0&0&-3/2\end{array}\right) [/tex]

I did these elem. operations in this order to get the above matrix:
-2R1 + R2 replace R2
-3R1 + R3 replace R3
(-3/2)R2 +R3 replace R3

I now have an Upper Triangular Matrix. If I take the inverses of the elementary matrices it took to get to this point I would have:

[tex] \left(\begin{array}{ccc}{1&0&0\\2&1&0\\0&0&1\end{array}\right) [/tex]

[tex] \left(\begin{array}{ccc}{1&0&0\\0&1&0\\3&0&1\end{array}\right) [/tex]

[tex] \left(\begin{array}{ccc}{1&0&0\\0&1&0\\0&3/2&1\end{array}\right) [/tex]

Right?
 
  • #5
OK, duh...I think I just figured out the rest (guess i had to actually multiply it all out to see what happens)

so my lower triangular matrix turns into:

[tex] \left(\begin{array}{ccc}{1&0&0\\2&1&0\\3&3/2&1\end{array}\right) [/tex]


And then when I multiply this lower triangular with the previous upper triangular, I get my original matrix.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
955
Yes, so you now have a lower triangular matrix, L, and an upper triangular matrix, U such that LU= A.
 
  • #7
85
0
okay now i'm confused. you end up with PA=LU, right? or A=((P^-1)L)U. anyway i don't think your decomposition is unique because you stopped the elementary operations before you came up against a unit upper triangle.
 
  • #8
rsa58, I don't know what you are asking. What does P stand for in your equation?
 
  • #9
85
0
I guess what I'm asking is, what form of LU decomposition are you trying to perform, your version is incorrect of you are seeking a unique LU decomposition. what class is this for? P is known as a permutation matrix. It is an elementary matrix used for pivoting the rows and columns of A. I guess you are not using partial pivoting in your problem. Usually, if you are trying to write an algorithm for LU you must use partial pivoting (or some other method) which helps avoid divison by zero when calculating the multipliers.
 

Related Threads on LU Factorization

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
7K
Replies
1
Views
4K
  • Last Post
Replies
5
Views
661
  • Last Post
Replies
0
Views
7K
Replies
2
Views
10K
  • Last Post
Replies
5
Views
2K
Top