PDF download Download Article PDF download Download Article

To solve systems of three or more linear equations, you'll typically convert the problem into an augmented matrix and row reduce from there. However, this process can be slow and inefficient with more equations. The number of arithmetic operations you need to compute goes up by the factorial of the dimension of the matrix, so that it's impractical to solve systems of six or more equations by hand. In real life, systems of 1000 equations are not uncommon - even 50 equations involve computing a number of operations comparable to the number of atoms in the visible universe.

That's why lower-upper factorization (called LU factorization or LU decomposition) is important—it reduces the amount of operations to the cube of the dimension of the matrix. LU factorization lets you decompose a matrix into two triangular matrices— for upper triangular, and for lower triangular. After you've set up the matrices, you can find the solutions by back substitution. Some computers use this method to quickly solve systems that would be impractical to deal with via row-reduction.

In this article, we'll show how to perform an LU factorization for a system of three equations, for simplicity.

  1. 1
    Begin with the matrix equation. Fundamentally, a system of equations can be written in terms of a matrix equation where matrix acts on a vector to output another vector It is often the case that we wish to know and this is no exception. In LU factorization, we will see that we can define the relation where and are both triangular matrices.
  2. 2
    Row-reduce to row-echelon form. The row-echelon form will become our matrix
    • The matrix is in row-echelon form now.
    Advertisement
  3. 3
    Obtain by undoing your row-reduction steps. This step may be a bit tricky at first, but we are essentially constructing a matrix by going backwards.
    • Let's look at the most recent row reduction We found the new row 3 by replacing it with a linear combination of the old rows of the matrix. Now, we wish to find the old row 3, so simply solve.
    • This undoes the second row-reduction. Now, we put it in matrix form. Let's call this matrix The column vector to the right simply clarifies what we are doing - this matrix we are constructing is a linear transformation that does the same thing as what we just wrote above. Observe that, since we didn't do anything to the top two rows, the resulting elements for the two rows in this matrix are the same as in the identity matrix. Only the third row changes.
    • Construct the matrix that undoes the first row-reduction. Similarly, we are solving for the old row 2 and 3. We'll call this matrix
    • Multiply the matrices in the order that we found them. This means that If you did the multiplication correctly, you should get a lower triangular matrix.
  4. 4
    Rewrite the matrix equation in terms of . Now that we have both matrices, we can see below that acting on the vector outputs
    • Since is a vector, let Then, we see that The goal here is to first solve for then plug into to solve for
  5. 5
    Solve for . Because we are dealing with triangular matrices, back-substitution is the way to go.
  6. 6
    Solve for . This will again involve back-substitution, because is triangular.
    • Although this method may not seem very efficient to you (and indeed, LU factorization for systems of three equations is no better than row-reduction), computers are well-equipped to perform back-substitution, so the results really show as the number of equations goes up.
  7. Advertisement

Expert Q&A

Ask a Question
200 characters left
Include your email address to get a message when this question is answered.
Submit
Advertisement

Tips

Submit a Tip
All tip submissions are carefully reviewed before being published
Name
Please provide your name and last initial
Thanks for submitting a tip for review!

About This Article

Kevin Wang
Co-authored by:
Math Tutor
This article was co-authored by Kevin Wang. Kevin Wang is a Math Tutor based in New York, New York. Kevin has been tutoring math for over 10 years, and specializes in K-12 math topics and standardized tests, such as SAT and ACT. Kevin has an economics background and a career in both finance and marketing analytics. His interest in tutoring goes back even longer than his career. He discovered tutoring at the start of his university career and enjoys it as a way to stay sharp with fundamental skills and remain up to date with trends in our education system. Kevin received a BS in Economics from Duke University. This article has been viewed 40,223 times.
16 votes - 73%
Co-authors: 3
Updated: December 3, 2021
Views: 40,223
Categories: Linear Algebra
Thanks to all authors for creating a page that has been read 40,223 times.

Did this article help you?

Advertisement