How to Perform an LU Factorization

Co-authored by Kevin Wang

Last Updated: December 3, 2021

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— $U,$ for upper triangular, and $L,$ 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.

Steps

Download Article

1
Begin with the matrix equation. Fundamentally, a system of equations can be written in terms of a matrix equation $A{\mathbf {x}}={\mathbf {b}},$ where matrix $A$ acts on a vector ${\mathbf {x}}$ to output another vector ${\mathbf {b}}.$ It is often the case that we wish to know ${\mathbf {x}},$ and this is no exception. In LU factorization, we will see that we can define the relation $A=LU,$ where $L$ and $U$ are both triangular matrices.
- ${\begin{pmatrix}2&4&1\\-1&1&3\\3&2&5\end{pmatrix}}{\mathbf {x}}={\begin{pmatrix}2\\1\\7\end{pmatrix}}$
2
Row-reduce $A$ to row-echelon form. The row-echelon form will become our matrix $U.$
- $R_{{2}}\to 2R_{{2}}+R_{{1}},\ R_{{3}}\to 2R_{{3}}-3R_{{1}}$
  - ${\begin{pmatrix}2&4&1\\0&6&7\\0&-8&7\end{pmatrix}}$
- $R_{{3}}\to 3R_{{3}}+4R_{{2}}$
  - ${\begin{pmatrix}2&4&1\\0&6&7\\0&0&49\end{pmatrix}}=U$
- The matrix is in row-echelon form now.
Advertisement
3
Obtain $L$ 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 $R_{{3}}\to 3R_{{3}}+4R_{{2}}.$ 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.
  - $R_{{3}}^{{{\text{old}}}}\to {\frac {R_{{3}}-4R_{{2}}}{3}}$
- This undoes the second row-reduction. Now, we put it in matrix form. Let's call this matrix $S_{{2}}.$ 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.
  - ${\begin{pmatrix}1&0&0\\0&1&0\\0&-4/3&1/3\end{pmatrix}}{\begin{pmatrix}R_{{1}}\\R_{{2}}\\R_{{3}}\end{pmatrix}}$
- 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 $S_{{1}}.$
  - $R_{{2}}^{{{\text{old}}}}={\frac {R_{{2}}-R_{{1}}}{2}}$
  - $R_{{3}}^{{{\text{old}}}}={\frac {R_{{3}}+3R_{{1}}}{2}}$
  - $S_{{1}}={\begin{pmatrix}1&0&0\\-1/2&1/2&0\\3/2&0&1/2\end{pmatrix}}$
- Multiply the $S$ matrices in the order that we found them. This means that $S_{{2}}S_{{1}}=L.$ If you did the multiplication correctly, you should get a lower triangular matrix.
  - $L={\begin{pmatrix}1&0&0\\-1/2&1/2&0\\3/2&-4/6&1/6\end{pmatrix}}$
4
Rewrite the matrix equation $A{\mathbf {x}}={\mathbf {b}}$ in terms of $LU$ . Now that we have both matrices, we can see below that $L$ acting on the vector $U{\mathbf {x}}$ outputs ${\mathbf {b}}.$
- $L(U{\mathbf {x}})={\mathbf {b}}$
- Since $U{\mathbf {x}}$ is a vector, let ${\mathbf {y}}=U{\mathbf {x}}.$ Then, we see that $L{\mathbf {y}}={\mathbf {b}}.$ The goal here is to first solve for ${\mathbf {y}},$ then plug into $U{\mathbf {x}}={\mathbf {y}}$ to solve for ${\mathbf {x}}.$
5
Solve for ${\mathbf {y}}$ . Because we are dealing with triangular matrices, back-substitution is the way to go.
- $L{\mathbf {y}}={\begin{pmatrix}y_{{1}}\\-{\frac {1}{2}}y_{{1}}+{\frac {1}{2}}y_{{2}}\\{\frac {3}{2}}y_{{1}}-{\frac {2}{3}}y_{{2}}+{\frac {1}{6}}y_{{3}}\end{pmatrix}}={\begin{pmatrix}2\\1\\7\end{pmatrix}}$
- ${\mathbf {y}}={\begin{pmatrix}2\\4\\40\end{pmatrix}}$
6
Solve for ${\mathbf {x}}$ . This will again involve back-substitution, because $U$ is triangular.
- $U{\mathbf {x}}={\begin{pmatrix}2x_{{1}}+4x_{{2}}+x_{{3}}\\6x_{{2}}+7x_{{3}}\\49x_{{3}}\end{pmatrix}}={\begin{pmatrix}2\\4\\40\end{pmatrix}}$
- ${\mathbf {x}}={\begin{pmatrix}57/49\\-2/7\\40/49\end{pmatrix}}$
- 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.