Section06 Elimination = Factorization: $A = LU$

• Each elimination step $E_{ij}$ is inverted by $L_{ij}$. Off the main diagonal change $-\ell_{ij}$ to $\ell_{ij}$

• The whole forward elimination process ($(E_{n,n-1}) \cdots (E_{n2} \cdots E_{42}E_{32})(E_{n1} \cdots E_{41} E_{31} E_{21})$) is inverted by $L$ $$(L_{21}L_{31}L_{41} \cdots L_{n1})(L_{32}L_{42} \cdots L_{n2})\cdots (L_{n,n-1})$$

• The Matrix $\boldsymbol{L}$ is lower triangular

$$\begin{array}{c} \textbf{Factorization:} \text{ Matrix } \boldsymbol{A} \text{ could be represented by a product of two or more other matrices.} \\ \boldsymbol{A} = \boldsymbol{LU} \text{(An important method of factorization.)}\\\\ \left\{ \begin{array}{ll} \boldsymbol{L} & \text{Lower triangular} \\ \boldsymbol{U} & \text{Upper triangular (The result of elimination)} \end{array} \right. \end{array}$$

Defination

• Come from elimination
  • $\boldsymbol{U}$ is the elimination result of $\boldsymbol{A}$
  • $\boldsymbol{L}$ is the inverted matrix of $\boldsymbol{E}\ (\boldsymbol{L} = \boldsymbol{E}^{-1})$

Explanation and Example

1. Every inverse matrix $\boldsymbol{E}^{-1}$ is lower triangular. Its off-diagonal entry is $\ell_{ij}$ which undo the subtraction produced by $-\ell_{ij}$
2. The lower triangular product of invetse is $\boldsymbol{L}$
3. Each multiplier $\ell_{ij}$ goes directly into the $i,j$ position -- Unchanged -- in the product of inverses which is $\boldsymbol{L}$
4. Zeros
   • When a row of $\boldsymbol{A}$ starts with zeros, so does that row of $\boldsymbol{L}$
   • When a column of $\boldsymbol{A}$ starts with zeros, so does that column of $\boldsymbol{U}$
   • if a row starts with zero, we don't need an elimination step. $\boldsymbol{L}$ has a zero. If a column stats with zero, It doesn't need to elimination.
   • Zeros in the middle of matrix are likely to be filled.

$\boldsymbol{LDU}$

Why?

• $\boldsymbol{LU}$ is unsymmetric, because $\boldsymbol{U}$ has pivots on its diagonal where $\boldsymbol{L}$ has 1s.

  $\boldsymbol{D}$

• be used to split the matrix $\boldsymbol{U}$ into $$\left[ \begin{matrix} d_{1} & & & \\ & d_{2} & & \\ & & \ddots & \\ & & & d_{n} \\ \end{matrix} \right] \left[ \begin{matrix} 1 & u_{12}/d1 & u_{13}/d_{1} & \cdot\\ & 1 & u_{23}/d_{2} & \cdot\\ & & \ddots & \vdots \\ & & & 1 \\ \end{matrix} \right] = \boldsymbol{D}\boldsymbol{U}$$

Why $\boldsymbol{A} = \boldsymbol{LU}$

$$\begin{array}{ll} & \text{Suppose matrix } \boldsymbol{A} \text{ is a 3-dimension matrix.}\\ & \boldsymbol{U} \text{ is the elimination result of } \boldsymbol{A} \\ \therefore & \boldsymbol{u}_{3 \boldsymbol{\cdot}} = \boldsymbol{a}_{3 \boldsymbol{\cdot}} - \ell_{31}\boldsymbol{u}_{1 \boldsymbol{\cdot}} - \ell_{32}\boldsymbol{u}_{2 \boldsymbol{\cdot}}\\ \therefore & \boldsymbol{a}_{3 \boldsymbol{\cdot}} = \ell_{31}\boldsymbol{u}_{1 \boldsymbol{\cdot}} + \ell_{32} \boldsymbol{u}_{2 \boldsymbol{\cdot}} + 1 \cdot \boldsymbol{u}_{3 \boldsymbol{\cdot}} = \left[ \begin{matrix} \ell_{31} & \ell_{32} & 1 \end{matrix} \right] \left[ \begin{matrix} u_{1 \boldsymbol{\cdot}} \\ u_{2 \boldsymbol{\cdot}} \\ u_{3 \boldsymbol{\cdot}} \\ \end{matrix} \right] = \boldsymbol{l}_{3 \boldsymbol{\cdot}} \boldsymbol{U} \\ \therefore & \text{And so on, } \boldsymbol{A} = \boldsymbol{LU} \\ \end{array}$$

One Square System = Two Triangular Systems

Solve Steps

1. Factor (into $\boldsymbol{L}$ and $\boldsymbol{U}$, by elimination on the left side matrix $\boldsymbol{A}$)
2. Solve (forward elimination on $\boldsymbol{b}$ using $\boldsymbol{L}$, then back subsitution for $\boldsymbol{x}$ using $\boldsymbol{U}$)

$$\text{solve }\boldsymbol{Lc} = \boldsymbol{b} \text{ and then solve } \boldsymbol{Ux} = \boldsymbol{c}$$

The Cost of Elmination

nonzero matrix

1. Elimination on a n-dimension matrix $\boldsymbol{A} (\boldsymbol{A} \rightarrow \boldsymbol{U})$ requires about $\frac{1}{3}{n^{3}}$ multiplications and $\frac{1}{3}{n^{3}}$ subsitutions.
2. Right side $\boldsymbol{b} \rightarrow \boldsymbol{c} \rightarrow \boldsymbol{x}$ needs $n^{2}$ multiplications and $n^{2}$ subsitutions.

band matrix

• has only $w$ nonzero diagonals below and above the main diagonal.
• $\boldsymbol{A} \rightarrow \boldsymbol{U}$: $nw^{2}$
• $\boldsymbol{b} \rightarrow \boldsymbol{c} \rightarrow \boldsymbol{x}$: $2nw$.

Properties from Exercise

1. When zero appears in a pivot position. $\boldsymbol{A} = \boldsymbol{LU}$ is impossible!, because $\frac{c}{0}$ is impossible.
2. When matrix $\boldsymbol{A}$ is symmetric, $\boldsymbol{A} = \boldsymbol{LDU} = \boldsymbol{LDL^{T}}$ $$\begin{array}{ll} \boldsymbol{A} = \left[ \begin{matrix} a & a & a & a \\ a & b & b & b \\ a & b & c & c \\ a & b & c & d \\ \end{matrix} \right] \\ E_{21} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right]; E_{31} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right]; E_{32} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right]; \\ E_{41} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ \end{matrix} \right]; E_{42} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ \end{matrix} \right]; E_{43} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \\ \end{matrix} \right]\\ \boldsymbol{U} = \left[ \begin{matrix} a & a & a & a \\ 0 & b-a & b-a & b-a \\ 0 & 0 & c-b & c-b \\ 0 & 0 & 0 & d-c \end{matrix} \right] = \left[ \begin{matrix} a & 0 & 0 & 0 \\ 0 & b-a & 0 & 0 \\ 0 & 0 & c-b & 0 \\ 0 & 0 & 0 & d-c \end{matrix} \right] \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{matrix} \right] = \boldsymbol{DU} \\ \boldsymbol{L} = [(E_{43}E_{42}E_{41})(E_{32}E_{31})(E_{21})]^{-1} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{matrix} \right] \end{array}$$
3. submatrices $\boldsymbol{A}_{k}$ of matrix $\boldsymbol{A}$
   • $\boldsymbol{A}_{k} = \boldsymbol{L}_{k}\boldsymbol{U}_{k}$