Based in Maryland, Mathwizurd.com is REVOLUTIONIZINg the world, one post at a time. With topics ranging from Biology to Multivariable Calculus, this website covers the entire academic spectrum.

LU Factorization

Ax = B

MathJax TeX Test Page Let $A = \begin{bmatrix}1 & 3 & 4\\-3 & 2& -6\\-3 & -2 & -7\end{bmatrix}$ and $b = \begin{bmatrix}4 \\ -25 \\ -18.5\end{bmatrix}$. Find the vector $\vec{x}$ such that $A\vec{x} = b$. Normally you would combine it into one augmented matrix and solve it, or calculate $A^{-1}$, and solve $A^{-1}b$ What we're going to be doing is going to make this much more efficient.

Basic Idea

MathJax TeX Test Page If you have many equations $Ax = B$, so $Ax = b_1, Ax = b_2, Ax = b_3$, it is less efficient to calculate x by multiplying the inverse by each column vector, instead we will be row reducing and obtaining an LU factorization at the same time. This means we will be finding the upper and lower triangular matrices that, when multiplied, equal the original matrix $A$. This is how it goes: $$Ax = b, (LU)x = b, L(Ux) = b$$ So you solve the equations in this order: $$Ly = b \rightarrow Ux = y$$

How do you get L and U?

MathJax TeX Test Page First, it's important to see that row echelon form is equivalent to the U matrix. So, going back to our original example, U would be equal to $$REF(\begin{bmatrix}1 & 3 & 4\\-3 & 2& -6\\-3 & -2 & -7\end{bmatrix})$$ While we convert it to REF, let's keep track of the operations. $$\begin{bmatrix}1 & 3 & 4\\0 & 11& 6\\-3 & -2 & -7\end{bmatrix} \text{$E_1$: Row 2 = Row 2 + 3 Row 1}$$ $$\begin{bmatrix}1 & 3 & 4\\0 & 11& 6\\0& 7 & 5\end{bmatrix} \text{$E_2$: Row 3 = Row 3 + 3 Row 1}$$ $$\begin{bmatrix}1 & 3 & 4\\0 & 11& 6\\0& 0 & \frac{13}{11}\end{bmatrix} \text{$E_3$: Row 3 = Row 3 - $\frac{7}{11}$ Row 2}$$ So, $E_3E_2E_1A = U$, $A = LU = (E_3E_2E_1)^{-1}U, L = (E_3E_2E_1)^{-1}, L = E_1^{-1}E_2^{-1}E_3^{-1}$ To find L, we must start with the identity matrix, then perform the inverse of the operations in order. $$\begin{bmatrix}1 & 0 & 0\\0 & 1& 0\\0& 0 & 1\end{bmatrix}$$ $$\begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\0& 0 & 1\end{bmatrix} \text{$E_1^{-1}$ = Row 2 = Row 2 - 3 Row 1}$$ $$\begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\-3& 0 & 1\end{bmatrix} \text{$E_2^{-1}$ = Row 3 = Row 3 - 3 Row 1}$$ $$\begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\-3& \frac{7}{11} & 1\end{bmatrix}\text{$E_3^{-1}$ = Row 3 = Row 3 + $\frac{7}{11}$ Row 2}$$ $$L = \begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\-3& \frac{7}{11} & 1\end{bmatrix}$$

Solving the Equation

MathJax TeX Test Page So, we have $L = \begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\-3& \frac{7}{11} & 1\end{bmatrix}$, and $U = \begin{bmatrix}1 & 3 & 4\\0 & 11& 6\\0& 0 & \frac{13}{11}\end{bmatrix}$ So, we must do $Ly = b$ first. $$\begin{bmatrix}1 & 0 & 0\\-3 & 1& 0\\-3& \frac{7}{11} & 1\end{bmatrix}y = \begin{bmatrix}4\\-25\\-18.5\end{bmatrix}$$ We can turn this into a system of equations, with the variables being $y_1, y_2,$ and $y_3$ $$\begin{bmatrix}1 & 0 & 0 & 4\\-3 & 1& 0 & -25\\-3& \frac{7}{11} & 1 & -18.5\end{bmatrix}$$ Let's start with the first row. Here, we instantly see that $y_1 = 4$. Now, we move on to the second row. $-3(4) + y_2 = -25$. So, $y_2 = -13$. Last, we move on to the third row. $-3(4) - 13(7)/11 + y_3 = -18.5$ So, $y_3 = \frac{19.5}{11}$. We now have to solve the equation $Ux = Y$. $$\begin{bmatrix}1 & 3 & 4\\0 & 11& 6\\0& 0 & \frac{13}{11}\end{bmatrix}x = \begin{bmatrix}4\\-13\\\frac{19.5}{11}\end{bmatrix}$$ Once again, we turn this into a system of equations, where the columns correspond to $x_1, x_2, and x_3$. $$\begin{bmatrix}1 & 3 & 4 & 4 \\0 & 11& 6 & -13\\0& 0 & \frac{13}{11} & \frac{19.5}{11}\end{bmatrix}$$ Let's start in the third row this time, because there is only one element present. We can see that $x_3 = \frac{19.5}{13} = 1.5$ We now move one row up $11x_2 + 6(1.5) = -13$. So, $x_2 = -2$. Now, we move to the top row $x_1 + 3(-2) + 4(1.5) = 4$, so $x_1 = 4$. Finally, we get our solution: $\boxed{x = \begin{bmatrix}4\\-2\\1.5\end{bmatrix}}$

TFAE

Matrix Equation Ax = b