Suggest edit — LU-Factorization

Title

Name

Note

---
title: "LU-Factorization"
type: concept
related: [Elimination Matrix]
source: https://www.jemoka.com/posts/kbhlu_factorization/
confidence: high
status: active
---

Elimination Matricies can be used to derive a LU factorization:
First, this gives an upper triangular matrix
\begin{equation} U = M_{n-1, n-1} \dots M_{22} M_{11} A \end{equation}
We can also create the inverses of each of these:
\begin{equation} A = L_{11} L_{22} \dots L_{n-1,n-1} \cdot M_{n-1,n-1} \dots M_{22} \cdot M_{11} \cdot A \end{equation}
The first half \(L_{j}\) composes a lower triangular matrix; the second half \(M_{j}\) which composes a upper triangular matrix.
Then, this helps solve:
\begin{equation} Ac = b \end{equation}
Because we can factor first to:
\begin{equation} \qty(LU) c = b \end{equation}
Then, this makes it really easy to solve, because we can.
\begin{equation} \hat{c} = Uc \end{equation}
then, we can solve \(L\hat{c} = b\) using forward substitution; then we can solve \(Uc = \hat{c}\) using back substitution.
Notice that for every new \(b\), we don&rsquo;t need to perform Gaussian elimination.