LU Decomposition

From bio-physics-wiki

Jump to: navigation, search

In the articles on Matrices it was explained where matrices come from and we have discussed the column picture, which gives an intuitive way to think about matrix multiplication.

\begin{align} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \\ \gamma \\ \end{bmatrix}= \alpha \begin{bmatrix} a \\ d \\ g \end{bmatrix}+ \beta \begin{bmatrix} b \\ e \\ h \end{bmatrix} + \gamma\begin{bmatrix} c \\ f \\ i \\ \end{bmatrix} \end{align}

On the other hand, if we multiply on the left by a row vector \begin{align} \begin{bmatrix} \alpha & \beta & \gamma \end{bmatrix} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} = \alpha \begin{bmatrix} a & b & c \end{bmatrix}+ \beta \begin{bmatrix} d & e & f\\ \end{bmatrix} + \gamma\begin{bmatrix} g & h & i \end{bmatrix} \end{align}
this corresponds to a linear combination of the rows of matrix $\mathbf{A}$. So row vectors multiplying from the left allow us to do row operations on the columns of $\mathbf{A}$. This means we can write the steps of Matrix Elimination in a neat way using Matrices. Remember the matrix \begin{align} \begin{bmatrix} \color{red}{1} & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix} \end{align}
in the first step we multiplied the first row by $3$ and subtracted it from row two. \begin{align} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 3 & 8 & 1 & 12\\ 0 & 4 & 1&2 \end{array} \overset{row2-3 \cdot row1}{\longrightarrow} \begin{array}{rrr|r} \color{red}{1} & 2 & 1 &2 \\ 0 & \color{red}{2} & -2 & 6\\ 0 & 4 & 1&2 \end{array} \end{align} Which matrix multiplying on the left does this row operation? \begin{align} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} {1} & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=\begin{bmatrix} {1} & 2 & 1\\ 0 & 2 & -2\\ 0 & 4 & 1 \end{bmatrix} \end{align}
The first and the last row shall just stay the same, so the first row vector in the unknown matrix - let's call it $\mathbf{E}_{21}$ for elimination matrix - must be \begin{align} \begin{bmatrix} 1 & 0 & 0\\ d & e & f\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} {1} & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=\begin{bmatrix} {1} & 2 & 1\\ 0 & 2 & -2\\ 0 & 4 & 1 \end{bmatrix} \end{align}
the third row vector in $\mathbf{E}_{21}$ should multiply the first row by $3$ and subtracted it from row two to give zero in the $21$ ($row \, column$) entry of $\mathbf{E}$. This is done by \begin{align} \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} {1} & 2 & 1\\ 3 & 8 & 1\\ 0 & 4 & 1 \end{bmatrix}=\begin{bmatrix} {1} & 2 & 1\\ 0 & 2 & -2\\ 0 & 4 & 1 \end{bmatrix} \end{align}
so the first elimination matrix is \begin{align} \mathbf{E}_{21}=\begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{align}
similarly the elimination matrix $\mathbf{E}_{32}$ for row $3$ and column $2$ is \begin{align} \mathbf{E}_{32}=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix} \end{align} it takes two times row $2$ away from row $3$. \begin{align} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix} \begin{bmatrix} {1} & 2 & 1 \\ 0 & {2} & -2 \\ 0 & 4 & 1 \end{bmatrix}= \begin{bmatrix} {1} & 2 & 1 \\ 0 & {2} & -2 \\ 0 & 0 & {5} \end{bmatrix} \end{align} If we combine both elimination steps, we can write the row operations in a neat way. First we applied $\mathbf{E}_{21}$ and then $\mathbf{E}_{32}$ \begin{align} \mathbf{E}_{32}(\mathbf{E}_{21}\mathbf{A})=\mathbf{U} \end{align} We call the resulting matrix $\mathbf{U}$ for upper triangular. Now we can use that matrix multiplication is associative, so we can move the parentheses \begin{align} (\mathbf{E}_{32}\mathbf{E}_{21})\mathbf{A}&=\mathbf{U}\\ \mathbf{E}\mathbf{A}&=\mathbf{U} \end{align} However we are not allowed to change the order $\mathbf{E}_{32}\mathbf{E}_{21}$, meaning that matrix multiplication is not commutative. Now we can bring the elimination matrices on the other side of the equation by multiplying by their inverses on the left. \begin{align} \mathbf{E}_{21}^{-1}\mathbf{E}_{32}^{-1}\mathbf{E}_{32}\mathbf{E}_{21}\mathbf{A}&=\mathbf{E}_{21}^{-1}\mathbf{E}_{32}^{-1}\mathbf{U}\\ \mathbf{A}&=\underbrace{\mathbf{E}_{21}^{-1}\mathbf{E}_{32}^{-1}}_{\mathbf{L}} \mathbf{U}\\ \end{align} we call the product of matrices $\mathbf{E}_{21}^{-1}\mathbf{E}_{32}^{-1}=\mathbf{L}$ for lower triangular. In the article on inverse matrices we have seen, that the inverse of an elimination matrix is easily found by inverting a sign. Thus we can calculate $\mathbf{L}$ without much effort. \begin{align} \mathbf{L}&=\mathbf{E}_{21}^{-1}\mathbf{E}_{32}^{-1}\\ &=\begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}\\ \end{align} We can factor the Matrix $\mathbf{A}$ in two matrices $\mathbf{L}$ and $\mathbf{U}$ \begin{align} \mathbf{A}&=\mathbf{L}\mathbf{U}\\ \end{align} a lower triangular matrix $\mathbf{L}$ and a upper triangular matrix $\mathbf{U}$.




Video Lectures:

  • Gilbert Strang - Introduction to Linear Algebra Lec. 2
  • Gilbert Strang - Introduction to Linear Algebra Lec. 4