Line 39: | Line 39: | ||
* this way both $L$ and $U$ will have ones on their diagonals - if $L$ had ones and $U$ didn't | * this way both $L$ and $U$ will have ones on their diagonals - if $L$ had ones and $U$ didn't | ||
+ | == Solving [[System of Linear Equations|$A \mathbf x = \mathbf b$]] with LU Decomposition == | ||
+ | Solving $A\mathbf x = \mathbf b$ | ||
+ | * Can do that with Gaussian Elimination via LU Decomposition | ||
+ | * Let $LU = A$ | ||
+ | * then $A \mathbf x = \mathbf b$ becomes $LU \mathbf x = \mathbf b$ | ||
+ | * Now let $U \mathbf x = \mathbf y$ and $L \mathbf y = \mathbf x$ | ||
+ | * With this substitution we need to solve two equations now | ||
+ | ** Solve $L \mathbf y = \mathbf b$ to get $\mathbf y$ | ||
+ | ** Solve $U \mathbf x = \mathbf y$ to get $\mathbf x$ | ||
+ | * These two equations are simpler than the original one because: | ||
+ | ** $L$ is lower-diagonal, and $L \mathbf y = \mathbf b$ can be solved with "Forward Substitution" and | ||
+ | ** $U$ is upper-diagonal, and $U \mathbf x = \mathbf y$ can be solved with "Back Substitution" | ||
− | == [[Inverse Matrices|Matrix Inversion]] | + | === Forward Substitution === |
+ | First, we solve $L \mathbf x = \mathbf b$ | ||
+ | |||
+ | $2 \times 2$ case: | ||
+ | * <math>\begin{bmatrix} | ||
+ | l_{11} & 0 \\ | ||
+ | l_{21} & l_{22} \\ | ||
+ | \end{bmatrix} | ||
+ | \begin{bmatrix} | ||
+ | x_1 \\ | ||
+ | x_2 \\ | ||
+ | \end{bmatrix} | ||
+ | = | ||
+ | \begin{bmatrix} | ||
+ | b_1 \\ | ||
+ | b_2 \\ | ||
+ | \end{bmatrix} | ||
+ | </math> | ||
+ | * $x_1 = b_1 / l_{11}$ | ||
+ | * $x_2 = (b_2 - l_{21} x_2) / l_{22}$ | ||
+ | |||
+ | General procedure: | ||
+ | * $x_i = (b - \sum_{j=1}^{i - 1} l_{ij} x_j) / l_{ii}$ | ||
+ | |||
+ | |||
+ | === Back Substitution === | ||
+ | Then we solve $U \mathbf x = \mathbf b$ | ||
+ | |||
+ | $2 \times 2$ case: | ||
+ | * <math>\begin{bmatrix} | ||
+ | u_{11} & u_{12} \\ | ||
+ | 0 & u_{22} \\ | ||
+ | \end{bmatrix} | ||
+ | \begin{bmatrix} | ||
+ | x_1 \\ | ||
+ | x_2 \\ | ||
+ | \end{bmatrix} | ||
+ | = | ||
+ | \begin{bmatrix} | ||
+ | b_1 \\ | ||
+ | b_2 \\ | ||
+ | \end{bmatrix} | ||
+ | </math> | ||
+ | |||
+ | General procedure: | ||
+ | * $x_i = (b - \sum_{j=i+1}^{n} u_{ij} x_j) / u_{ii}$ | ||
+ | |||
+ | |||
+ | === [[Inverse Matrices|Matrix Inversion]] === | ||
To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$ | To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$ | ||
* Let's decompose $A = LU$, so we have: $LUX = I$ | * Let's decompose $A = LU$, so we have: $LUX = I$ | ||
Line 58: | Line 118: | ||
* [[Linear Algebra MIT 18.06 (OCW)]] | * [[Linear Algebra MIT 18.06 (OCW)]] | ||
* https://www.gamedev.net/resources/_/technical/math-and-physics/matrix-inversion-using-lu-decomposition-r3637 | * https://www.gamedev.net/resources/_/technical/math-and-physics/matrix-inversion-using-lu-decomposition-r3637 | ||
+ | * [[Matrix Computations (book)]] | ||
[[Category:Linear Algebra]] | [[Category:Linear Algebra]] | ||
[[Category:Matrix Decomposition]] | [[Category:Matrix Decomposition]] |
This is the simplest factorization that can be seen as a by-product of Gaussian Elimination
When we do elimination, we have some elimination matrices:
$L$
Types of $LU$ decomposition:
We can go further:
Solving $A\mathbf x = \mathbf b$
First, we solve $L \mathbf x = \mathbf b$
$2 \times 2$ case:
General procedure:
Then we solve $U \mathbf x = \mathbf b$
$2 \times 2$ case:
General procedure:
To find the matrix inverse, we need to solve the equation $AX = I$, where $X = A^{-1}$