LU factorization

LU factorization decomposes a matrix into a lower-triangular matrix and an upper-triangular matrix .

We get the lower-triangular matrix by multiplying the inverse of elementary matrices we get from Gaussian elimination. And the remaining matrix in row echelon form is the upper-triangular matrix .

Find the LU decomposition of

We can perform Gaussian elimination and write down the elementary matrices. First, add row 1 to row 2:
$Misplaced &3 & -7 & -2 \\ 0 & -2 & -1 \\ 6 & -4 & 0 \end{array}\right),\ \mathrm{E_1}=\left(\begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)$$ Then Subtract row 1 multiplied by 2 from row 3 $$\mathrm{A_2}=\left(\begin{array}{rrr} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 10 & 4 \end{array}\right),\ \mathrm{E_2}=\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{array}\right)$$ Then add row 2 multiply by 5 from row 3 $$\mathrm{A_3}=\left(\begin{array}{rrr} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{array}\right),\ \mathrm{E_3}=\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{array}\right)$$ $\mathrm{A}_3$ is in the [[./row echelon form|row echelon form]] so it is $\mathrm{U}$, and $$\mathrm{L}=\mathrm{E_3}^{-1}\mathrm{E_2}^{-1}\mathrm{E_1}^{-1}=\left(\begin{array}{rrr} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{array}\right)$

Compare to Gaussian elimination, LU decomposition can save computation when we solve repeatedly with different s. To solve , we can let and then first solve for and then for . Since and are triangular matrices, we can solve the above equation trivially by forward and back substitution.

Continue from above example

Let . To solve in , we can let . Then by forward substitution, . And then we can do back substitution in and .

Lesley's Digital Garden

Explorer

LU factorization

Graph View

Backlinks