LU Factorization

Ax = B

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

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?

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

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}}$