Study Notes of "Introduction to MATRIX ALGEBRA": 7. LU Decomposition

PDF format lecture Chapter 7 LU Decomposition

Printable version Study Notes of “Introduction to MATRIX ALGEBRA”

Summary

• For a nonsingular matrix $[A]$ on which one can always write it as $$[A] = [L][U]$$ where $[L]$ is a lower triangular matrix, $[U]$ is a upper triangular matrix.
• Note that not all matrices have LU decomposition, such as $\begin{bmatrix}0& 2\\ 2& 0\end{bmatrix}$. $$\begin{bmatrix}0& 2\\ 2& 0\end{bmatrix}=\begin{bmatrix}1& 0\\ a& 1\end{bmatrix} \begin{bmatrix}b& c\\ 0& d\end{bmatrix} \Rightarrow \begin{cases} b=0\\ ab=2\end{cases}$$ which is contradiction.
• If one is solving a set of equations $$[A][X]=[B]$$ then $$LUX=B$$ $$\Rightarrow L^{-1}LUX=L^{-1}B$$ $$\Rightarrow UX=L^{-1}B=Y$$ then we have $$\begin{cases}LY=B\\ UX=Y\end{cases}$$ So we can solve the first equation for $[Y]$by using forward substitution and then use the second equation to calculate the solution vector $[X]$ by back substitution.
• For instance, solve the following set of equations: $$\begin{bmatrix}1& 2& 3\\ 2& 1& -4\\ 1& 5& 2\end{bmatrix}\cdot \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} 14\\ -8\\ 17\end{bmatrix}$$ Applying LU decomposition on the coefficient matrix,
  
  • Firstly write down an identity matrix (the same size as the coefficient matrix) on the left and the coefficient matrix on the right. $$L\leftarrow\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} \begin{bmatrix}1& 2& 3\\ 2& 1& -4\\ 1& 5& 2\end{bmatrix}\rightarrow U$$
  • Then applying elementary row operation on the right while simultaneously updating successive columns of the matrix on the left. For example, if we are doing $R_1 + m R_2$ on the right then we will do $C_2-mC_1$ on the left. That is, we will keep the equivalent of the product. $$\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} \begin{bmatrix}1& 2& 3\\ 2& 1& -4\\ 1& 5& 2\end{bmatrix}$$ $$\Rightarrow\begin{cases}R_2-2R_1 \\ C_1+2C_2\end{cases} \begin{bmatrix}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1 \end{bmatrix} \begin{bmatrix}1& 2& 3\\ 0& -3& -10\\ 1& 5& 2\end{bmatrix}$$ $$\Rightarrow\begin{cases}R_3-R_1 \\ C_1+C_3\end{cases} \begin{bmatrix}1& 0& 0\\ 2& 1& 0\\ 1& 0& 1 \end{bmatrix} \begin{bmatrix}1& 2& 3\\ 0& -3& -10\\ 0& 3& -1\end{bmatrix}$$ $$\Rightarrow\begin{cases}R_3+R_2 \\ C_2-C_3\end{cases} \begin{bmatrix}1& 0& 0\\ 2& 1& 0\\ 1& -1& 1 \end{bmatrix} \begin{bmatrix}1& 2& 3\\ 0& -3& -10\\ 0& 0& -11\end{bmatrix}$$ Thus far, the right matrix is an upper triangular matrix (i.e. $U$) and the left one is a lower triangular matrix (i.e. $L$).
  • Solving $[L][Y]=[B]$, that is $$\begin{bmatrix}1& 0& 0\\ 2& 1& 0\\ 1& -1& 1 \end{bmatrix}\cdot Y=\begin{bmatrix} 14\\ -8\\ 17\end{bmatrix}\Rightarrow Y=\begin{bmatrix}14\\ -36\\ -33\end{bmatrix}$$
  • Solving $[U][X]=[Y]$, that is $$\begin{bmatrix}1& 2& 3\\ 0& -3& -10\\ 0& 0& -11\end{bmatrix}\cdot \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix}14\\ -36\\ -33\end{bmatrix}$$ $$ \Rightarrow\begin{cases}x=1\\ y=2 \\ z=3\end{cases}$$

Selected Problems

1. Find the $[L]$ and $[U]$ matrices of the following matrix $$\begin{bmatrix}25& 5& 4\\ 75& 7& 16\\ 12.5& 12& 22 \end{bmatrix}$$
Solution:
$$\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix}\begin{bmatrix}25& 5& 4\\ 75& 7& 16\\ 12.5& 12& 22 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_2-3R_1\\ R_3-{1\over2}R_1\\ C_1+3C_2\\ C_1+{1\over2}C_3\end{cases} \begin{bmatrix}1& 0& 0\\ 3& 1& 0\\ {1\over2}& 0& 1 \end{bmatrix} \begin{bmatrix}25& 5& 4\\ 0& -8& 4\\ 0& 9.5& 20 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_3+{19\over16}R_2\\C_2-{19\over16}C_3\end{cases} \begin{bmatrix}1& 0& 0\\ 3& 1& 0\\ {1\over2}& -{19\over16}& 1 \end{bmatrix} \begin{bmatrix}25& 5& 4\\ 0& -8& 4\\ 0& 0& {99\over4} \end{bmatrix}$$ That is, $$L= \begin{bmatrix}1& 0& 0\\ 3& 1& 0\\ {1\over2}& -{19\over16}& 1 \end{bmatrix},\ U = \begin{bmatrix}25& 5& 4\\ 0& -8& 4\\ 0& 0& {99\over4} \end{bmatrix}.$$
2. Using LU decomposition to solve: $$\begin{cases} 4x_1 + x_2 - x_3 = -2\\ 5x_1+x_2+2x_3=4\\ 6x_1+x_2+x_3=6 \end{cases}$$
Solution:
$$\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} \begin{bmatrix}4& 1& -1\\ 5& 1& 2\\ 6& 1& 1\end{bmatrix}$$ $$\Rightarrow \begin{cases}R_2-{5\over4}R_1\\ R_3-{3\over2}R_1\\ C_1+{5\over4}C_2\\ C_1+{3\over2}C_3\end{cases} \begin{bmatrix}1& 0& 0\\ {5\over4}& 1& 0\\ {3\over2}& 0& 1 \end{bmatrix} \begin{bmatrix}4& 1& -1\\ 0& -{1\over4}& {13\over4}\\ 0& -{1\over2}& {5\over2}\end{bmatrix}$$ $$\Rightarrow \begin{cases}R_3-2R_2\\ C_2+2C_3\end{cases} \begin{bmatrix}1& 0& 0\\ {5\over4}& 1& 0\\ {3\over2}& 2& 1 \end{bmatrix} \begin{bmatrix}4& 1& -1\\ 0& -{1\over4}& {13\over4}\\ 0&0& -4\end{bmatrix}$$ That is, $$L = \begin{bmatrix}1& 0& 0\\ {5\over4}& 1& 0\\ {3\over2}& 2& 1 \end{bmatrix},\ U= \begin{bmatrix}4& 1& -1\\ 0& -{1\over4}& {13\over4}\\ 0&0& -4\end{bmatrix}.$$ Then we solve $[L][Y]=[B]$, $$\begin{bmatrix}1& 0& 0\\ {5\over4}& 1& 0\\ {3\over2}& 2& 1 \end{bmatrix}\cdot Y=\begin{bmatrix}-2\\4\\6\end{bmatrix} \Rightarrow Y=\begin{bmatrix}-2\\{13\over2}\\ -4\end{bmatrix}$$ Finally, we solve $[U][X]=[Y]$, $$\begin{bmatrix}4& 1& -1\\ 0& -{1\over4}& {13\over4}\\ 0&0& -4\end{bmatrix}\cdot X= \begin{bmatrix}-2\\{13\over2}\\ -4\end{bmatrix}\Rightarrow X=\begin{bmatrix}3\\-13\\1\end{bmatrix}$$ Thus the solution is $$\begin{cases}x_1 = 3\\ x_2 = -13\\ x_3 = 1\end{cases}$$
3. Find the inverse of $$[A]=\begin{bmatrix}3& 4& 1\\ 2& -7& -1\\ 8& 1& 5\end{bmatrix}$$
Solution:
To find the inverse of a matrix, actually it is to solve a set of equations: $$\begin{cases}AX_1=[1, 0, 0]^{T}\\ AX_2 = [0, 1, 0]^{T}\\ AX_3 = [0, 0, 1]^{T} \end{cases}$$ Firstly, we will find the $[L]$ and $[U]$. $$\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} \begin{bmatrix}3& 4& 1\\ 2& -7& -1\\ 8& 1& 5\end{bmatrix}$$ $$\Rightarrow \begin{cases}R_2-{2\over3}R_1\\ R_3-{8\over3}R_1\\ C_1+{2\over3}C_2\\ C_1+{8\over3}C_3\end{cases} \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 0& 1 \end{bmatrix} \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0& -{29\over3}& {7\over3}\end{bmatrix}$$ $$\Rightarrow \begin{cases}R_3-R_2\\ C_2+C_3\end{cases} \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 1& 1 \end{bmatrix} \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0&0& 4\end{bmatrix}$$ That is, $$L = \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 1& 1 \end{bmatrix},\ U= \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0&0& 4\end{bmatrix}.$$ Then we solve $[L][Y]=[I]$, note that there are three columns of $[Y]$: $$LY_1 = \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 1& 1 \end{bmatrix} \cdot Y_1 = \begin{bmatrix}1\\0\\0\end{bmatrix} \Rightarrow Y_1=\left[1, -{2\over3}, -2\right]^{T}$$ $$LY_2 = \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 1& 1 \end{bmatrix} \cdot Y_2 = \begin{bmatrix}0\\1\\0\end{bmatrix} \Rightarrow Y_2=\left[0, 1, -1\right]^{T}$$ $$LY_3 = \begin{bmatrix}1& 0& 0\\ {2\over3}& 1& 0\\ {8\over3}& 1& 1 \end{bmatrix} \cdot Y_3 = \begin{bmatrix}0\\0\\1\end{bmatrix} \Rightarrow Y_3=\left[0, 0, 1\right]^{T}$$ Finally we can solve $[X]$ by $[U][X]=[Y]$: $$UX_1=Y_1\Rightarrow \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0&0& 4\end{bmatrix} \cdot X_1 = \begin{bmatrix}1\\ -{2\over3}\\ -2\end{bmatrix}\Rightarrow X_1= \left[{17\over58}, {9\over58}, -{1\over2}\right]^{T}$$ $$UX_2=Y_2\Rightarrow \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0&0& 4\end{bmatrix} \cdot X_2 = \begin{bmatrix}0\\ 1\\ -1\end{bmatrix}\Rightarrow X_2= \left[{19\over116}, -{7\over116}, -{1\over4}\right]^{T}$$ $$UX_3=Y_3\Rightarrow \begin{bmatrix}3& 4& 1\\ 0& -{29\over3}& -{5\over3}\\ 0&0& 4\end{bmatrix} \cdot X_3 = \begin{bmatrix}0\\ 0\\ 1\end{bmatrix}\Rightarrow X_3= \left[-{3\over116}, -{5\over116}, {1\over4}\right]^{T}$$ Thus the inverse of the original matrix is $$[A]^{-1} = \begin{bmatrix}{17\over58} & {19\over116} & -{3\over116}\\ {9\over58} & -{7\over116} & -{5\over116}\\ -{1\over2} & -{1\over4} & {1\over4}\end{bmatrix}$$