Matrix Factorizations
LU Decomposition
LU Decomposition factorizes a square matrix $A$ as \[ A = LU, \] where $L$ is a lower triangular matrix with unit diagonal entries and $U$ is an upper triangular matrix.
Advantages: 1. Efficiently solves $Ax=b$ for multiple $b$ without repeating elimination. 2. Simplifies determinant computation: $\det(A) = \det(L)\det(U) = \prod_i u_{ii}$. 3. Simplifies computation of $A^{-1}$ by solving $LUx = e_i$ for each column of the identity.
Find the LU decomposition of \[ A = \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}. \]
Solution: Let \[ L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix}, \quad U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}. \]
Matching $LU = A$:
First row: $u_{11} = 2$, $u_{12} = 3$. Second row: $l_{21} u_{11} = 4 \implies l_{21} = 2$, $l_{21} u_{12} + u_{22} = 7 \implies 2 \cdot 3 + u_{22} = 7 \implies u_{22} = 1$.
Thus, \[ L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}. \]
Solve \[ \begin{bmatrix} 1 & 2 & 1 \\ 2 & 7 & 7 \\ -1 & 4 & 5 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 3 \\ 24 \\ 15 \end{bmatrix} \] using LU decomposition.
Solution: Factor $A = LU$, then solve $Ly = b$ (forward substitution): \[ y_1 = 3, \quad y_2 = 24 - 2\cdot3 = 18, \quad y_3 = 15 - (-1\cdot3 + 2\cdot18) = -21 \]
Next, solve $Ux = y$ (backward substitution): \[ x = 2, \quad y = 1, \quad z = 0 \]
For \[ A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}, \] find LU decomposition.
Solution: Let $L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1\end{bmatrix}$, $U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$.
From $LU = A$: $u_{11}=4$, $u_{12}=3$, $l_{21} u_{11}=6 \implies l_{21}=1.5$, $l_{21} u_{12}+u_{22}=3 \implies u_{22}=-1.5$.
\[ L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1\end{bmatrix}, \quad U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5\end{bmatrix}. \]
Determine LU decomposition of \[ A = \begin{bmatrix} 2 & -1 & 1 \\ 3 & 3 & 9 \\ 3 & 3 & 5 \end{bmatrix}. \]
Solution: Apply elimination: \[ L = \begin{bmatrix} 1 & 0 & 0 \\ 1.5 & 1 & 0 \\ 1.5 & 0 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & -1 & 1 \\ 0 & 4.5 & 7.5 \\ 0 & 0 & -4 \end{bmatrix}. \]
Applications of LU Factorization
Applications of LU Factorization:
1. Solving linear systems efficiently: Avoid repeated elimination for multiple RHS vectors.
2. Determinant computation: $\det(A) = \prod u_{ii}$.
3. Matrix inversion: Solve $LUx = e_i$ for each column of identity.
4. Numerical stability: LU with pivoting improves solution accuracy.
5. Engineering and scientific computations: Widely used in simulations and optimization problems.