LU Decomposition

86. LU Decomposition

Given a matrix $𝐴$ , LU decomposition aims to express $𝐴$ as:

𝐴 = 𝐿 𝑈

Where:

$𝐿$ : Lower triangular matrix (all elements above the diagonal are zero)
$𝑈$ : Upper triangular matrix (all elements below the diagonal are zero)

Solve $𝐿 𝑦 = 𝑏$ Using Forward Substitution

𝐿 𝑦 = 𝑏

Where:

$𝐿$ : Lower triangular matrix (all elements above the diagonal are zero)
$𝑦$ : Intermediate vector we are solving for
$𝑏$ : Right-hand side vector

[\begin{matrix} 𝐿_{11} & 0 & 0 \\ 𝐿_{21} & 𝐿_{22} & 0 \\ 𝐿_{31} & 𝐿_{32} & 𝐿_{33} \end{matrix}] [\begin{matrix} 𝑦_{1} \\ 𝑦_{2} \\ 𝑦_{3} \end{matrix}] [\begin{matrix} 𝑏_{1} \\ 𝑏_{2} \\ 𝑏_{3} \end{matrix}]

First row: $𝐿_{11} 𝑦_{1} = 𝑏_{1}$ , so $𝑦_{1} = \frac{𝑏_{1}}{𝐿_{11}}$
Second row: $𝐿_{21} 𝑦_{1} + 𝐿_{22} 𝑦_{2} = 𝑏_{2}$ , substitute $𝑦_{1}$ into this equation and solve for $𝑦_{2}$ :

𝑦_{2} = \frac{𝑏_{2} - 𝐿_{21} 𝑦_{1}}{𝐿_{22}}

Third row: $𝐿_{31} 𝑦_{1} + 𝐿_{32} 𝑦_{2} + 𝐿_{33} 𝑦_{2} = 𝑏_{3}$ , substitute $𝑦_{1}$ and $𝑦_{2}$ into this equation, solve for $𝑦_{3}$ :

𝑦_{3} = \frac{𝑏_{2} - 𝐿_{31} 𝑦_{1} - 𝐿_{32} 𝑦_{2}}{𝐿_{33}}

Solve $𝑈 𝑥 = 𝑦$ Using Backward Substitution

𝑈 𝑥 = 𝑦

Where:

$𝑈$ : Upper triangular matrix (all elements below the diagonal are zero)
$𝑦$ : Vector of unknowns (solution)
$𝑏$ : Vector computed from the forward substitution step

[\begin{matrix} 𝑈_{11} & 𝑈_{12} & 𝑈_{13} \\ 0 & 𝑈_{22} & 𝑈_{23} \\ 0 & 0 & 𝑈_{33} \end{matrix}] [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ 𝑥_{3} \end{matrix}] [\begin{matrix} 𝑦_{1} \\ 𝑦_{2} \\ 𝑦_{3} \end{matrix}]

Third row: $𝑈_{33} 𝑥_{3} = 𝑦_{3}$ , so $𝑥_{3} = \frac{𝑦_{3}}{𝑈_{33}}$
Second row: $𝑈_{22} 𝑥_{2} + 𝑈_{23} 𝑥_{3} = 𝑦_{2}$ , substitute $𝑥_{3}$ from the previous step and solve for $𝑥_{2}$ :

𝑥_{2} = \frac{𝑦_{2} - 𝑈_{23} 𝑥_{3}}{𝑈_{22}}

First row: $𝑈_{11} 𝑥_{1} + 𝑈_{12} 𝑥_{2} + 𝑈_{13} 𝑥_{3} = 𝑦_{1}$ , substitute $𝑥_{2}$ and $𝑥_{3}$ from the previous step and solve for $𝑥_{1}$ :

𝑥_{1} = \frac{𝑦_{1} - 𝑈_{12} 𝑥_{2} - 𝑈_{13} 𝑥_{3}}{𝑈_{11}}

Example

𝐴 = [\begin{matrix} 2 & 3 & 1 \\ 4 & 7 & 3 \\ 6 & 18 & 5 \end{matrix}] 𝑏 = [\begin{matrix} 5 \\ 12 \\ 31 \end{matrix}]

Factor $𝐴$ into $𝐿$ and $𝑈$ :

𝐿 = [\begin{matrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 6 & 1 \end{matrix}] 𝑈 = [\begin{matrix} 2 & 3 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & - 2 \end{matrix}]

Solve $𝐴 𝑥 = 𝑏$

$𝑦_{1} = \frac{𝑏_{1}}{𝐿_{11}} = \frac{5}{1} = 5$
$𝑦_{2} = \frac{𝑏_{2} - 𝐿_{21} 𝑦_{1}}{𝐿_{22}} = \frac{12 - 2 \times 5}{1} = 2$
$𝑦_{2} = \frac{𝑏_{3} - 𝐿_{31} 𝑦_{1} - 𝐿_{32} 𝑦_{2}}{𝐿_{33}} = \frac{31 - 4 \times 5 - 3 \times 2}{1} = 5$

So,

𝑦 = [\begin{matrix} 5 \\ 2 \\ 5 \end{matrix}]

Solve $𝑈 𝑥 = 𝑦$

$𝑥_{3} = \frac{𝑦_{3}}{𝑈_{33}} = \frac{5}{-} 2 = - 2.5$
$𝑥_{2} = \frac{𝑦_{2} - 𝑈_{23} 𝑥_{3}}{𝑈_{22}} = \frac{2 - 1 \times - 2.5}{1} = 4.5$
$𝑥_{1} = \frac{𝑦_{1} - 𝑈_{12} 𝑥_{2} - 𝑈_{13} 𝑥_{3}}{𝑈_{11}} = \frac{5 - 3 \times 4.5 - 1 \times - 2.5}{2} = - 4$

So,

𝑥 = [\begin{matrix} - 4 \\ 4.5 \\ - 2.5 \end{matrix}]