1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: LU Factorization

  1. Mar 1, 2010 #1
    1. The problem statement, all variables and given/known data

    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?

    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Mar 1, 2010 #2
    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.
     
  4. Mar 1, 2010 #3
    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.
     
  5. Mar 1, 2010 #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?
     
  6. Mar 1, 2010 #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.
     
  7. Mar 1, 2010 #6

    HallsofIvy

    User Avatar
    Science Advisor

    Yes, so you now have a lower triangular matrix, L, and an upper triangular matrix, U such that LU= A.
     
  8. Mar 1, 2010 #7
    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.
     
  9. Mar 1, 2010 #8
    rsa58, I don't know what you are asking. What does P stand for in your equation?
     
  10. Mar 2, 2010 #9
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook