NUMERICAL-ANALYSIS Course
LU factorization
This is also called LU decomposition or LowerUpper decomposition. We are transforming our matrix A into two matrices L and U, which are both diagonal matrices. Then, we are solving the equation with LU instead of A.
About
- Requirements
The matrix must be invertible, and every leading minor must be not null.
- Complexity
The complexity is $O(\frac{2n^3}{3})$.
Process
Your goal is to write $A = L * U$ with
- $L$: a lower strict diagonal matrix
- $U$: an upper diagonal matrix
It's quite easy. You will use the GAUSS elimination, but limited to this only one rule
\[ L_i \leftarrow L_i - k * L_j \]
meaning you can only subtract a line by another line that will be multiplied by k. Please, note all k values that you used. Your main job is starting from U, and remove all values below the diagonal. U matrix should look like this one
If you remoted the number at $a_{ij}$, using $k=7$ then in the L matrix, the value at $a_{ij}$ is 7. The L matrix should look like this one
Once you have these, to get $AX = b$, you need to
- solve $Y$ in $LY = b$
- then, you got $X$ by solving $UX = Y$
Example
Find the LU factorization of A and solve $AX = b$.
\[ A = \begin{pmatrix} 4 & 2 & 2 \\ 2 & 10 & 7 \\ 2 & 7 & 21 \\ \end{pmatrix} \quad b = \begin{pmatrix} 12 \\ -9 \\ -20 \\ \end{pmatrix} \]
We are checking that A is
-
leading minors not null, ok
- $det(\Delta_1) = 4 \ne 0$
- $det(\Delta_2) = 36 \ne 0$
- $det(\Delta_3) = 576 \ne 0$
- The steps are on the Cholesky factorization page
- invertible: ok, $det(A) = det(\Delta_3) \neq 0$
So we're starting, my steps were
- $L_2 \leftarrow L_2 - {\color{blue}1/2} L_1$
- $L_3 \leftarrow L_3 - {\color{blue}1/2} L_1$
\[ \begin{pmatrix} 4 & 2 & 2 \\ 0 & 9 & 6 \\ 0 & 6 & 20 \\ \end{pmatrix} \]
- $L_3 \leftarrow L_3 - {\color{blue}2/3} L_1 $
\[ U = \begin{pmatrix} 4 & 2 & 2 \\ 0 & 9 & 6 \\ 0 & 0 & 16 \\ \end{pmatrix} \]
Using the $k$ we removed, I have
\[ L = \begin{pmatrix} 1 & 0 & 0 \\ 1/2 & 1 & 0 \\ 1/2 & 2/3 & 1 \\ \end{pmatrix} \]
As we did for Cholesky, we are solving $LY=b$
- $x = 12$
- $y = -9 - \frac{12}{2} = -15$
- $z = -20 - \frac{12}{2} + \frac{2*15}{3} = -16$
So we have $Y = (12,-15,-16)$. And now, we are solving $UX=Y$
- $z = \frac{16}{-16} = -1$
- $y = \frac{-15 +6}{9} = -1$
- $x = \frac{12 + 2 + 2}{4} = 4$
Giving us $X = (4,-1,-1)$, as we expected.
LU factorization in R
Here is the code in R
A <- matrix(c(4,2,2,2,10,7,2,7,21), nrow = 3, ncol = 3, byrow = TRUE)
b <- c(12,-9,-20)
res <- lu(A)
L <- res$L
U <- res$U
# L
# [,1] [,2] [,3]
# [1,] 1.0 0.0000000 0
# [2,] 0.5 1.0000000 0
# [3,] 0.5 0.6666667 1
#
# U
# [,1] [,2] [,3]
# [1,] 4 2 2
# [2,] 0 9 6
# [3,] 0 0 16
# check
identical(L %*% U, A)
# [1] TRUE
# LY = b
Y <- forwardsolve(L, b)
# [1] 12 -15 -16
# UX = Y
X <- backsolve(U, Y)
# [1] 4 -1 -1