Triangular Decomposition

矩阵的LU分解

矩阵的分解在矩阵的研究中有着极其重要的地位，而LU分解则是矩阵分析中一种常见而又重要的分解.

LU分解——从高斯消元法说起

LU分解的来龙去脉

在高斯消元法中，我们使用了多次倍加把主对角元以外的元素变为零，这个过程可以看成是用一系列的初等矩阵来左乘系数矩阵。

$$A^{(0)}=A \quad\quad\quad A^{(1)}\triangleq \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&\dots&a_{1n}^{(0)}\\ 0&a_{22}^{(1)}&\dots&a_{2n}^{(1)}\\ \vdots&\vdots&&\vdots\\ 0&a_{n2}^{(1)}&\dots&a_{nn}^{(1)} \end{pmatrix}\quad\quad\quad\\ \quad\\ L_{1}\triangleq \begin{pmatrix} 1&&&&\\ -l_{12}&1\\ -l_{13}&&1&&\\ \vdots&&&\ddots\\ -l_{1n}&&&&1 \end{pmatrix}$$

则有$A^{(1)}=L_{1}A^{(0)}$,同理有

$$A^{(2)}\triangleq \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&a_{}13^{(0)}&\dots&a_{1n}^{(0)}\\ 0&a_{22}^{(1)}&a_{23}^{(1)}&\dots&a_{2n}^{(1)}\\ 0&0&a_{33}^{(2)}&\cdots&a_{3n}^{(2)}\\ \vdots&\vdots&\vdots&&\vdots\\ 0&0&a_{n3}^{(2)}&\dots&a_{nn}^{(1)} \end{pmatrix}\quad\quad\quad\\ \quad\\ \quad\\ L_{2}\triangleq \begin{pmatrix} 1&&&&\\ &1\\ &-l_{32}&1\\ &-l_{42}&&1&&\\ &\vdots&&&\ddots\\ &-l_{n2}&&&&1 \end{pmatrix} \\A^{(2)}=L_{2}A^{(1)}$$

一般的，有

$$A^{(k-1)}\triangleq \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&&\dots &\dots&a_{1n}^{(0)}\\ &a_{22}^{(1)}&&\dots&\dots&a_{2n}^{(1)}\\ &&\ddots&&&\vdots\\ &&&a_{kk}^{(k-1)}&\dots&a_{kn}^{(k-1)}\\ &&&\vdots&\dots&\vdots\\ &&&a_{nk}^{(k-1)}&\dots&a_{nn}^{(k-1)} \end{pmatrix}\quad\quad\quad\\ \quad\\ \quad\\ L_{2}\triangleq \begin{pmatrix} 1&&&&\\ &\ddots\\ &&1\\ &&-a_{k+1,k}&1\\ &&-l_{k+2,k}&&1&&\\ &&\vdots&&&\ddots\\ &&-l_{nk}&&&&1 \end{pmatrix}\\ \quad\\ \quad\\ \quad\\ A^{(k)}\triangleq A^{(k-1)}\triangleq \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&&\dots&a_{1,k+1}^{(0)} &\dots&a_{1n}^{(0)}\\ &a_{22}^{(1)}&&\dots&a_{2,k+1}^{(1)} &\dots&a_{2n}^{(1)}\\ &&\ddots&&\vdots&&\vdots\\ &&&a_{kk}^{(k-1)}&a_{k,k+1}^{(k-1)} &\dots&a_{kn}^{(k-1)}\\ &&&&a_{k+1,k+1}^{k}&\dots&a_{k+1,n}^{(k)}\\ &&&&\vdots&&\vdots\\ &&&&a_{n,k+1}^{(k)}&\dots&a_{nn}^{(k)} \end{pmatrix}\quad\quad\quad A^{(k)}=L_{k}A^{(k-1)}=\dots=L_{k}L_{k-1}\dots L_{1}A^{(0)}.$$

因为一共有n-1步消元，所以$A^{(n-1)}=L_{n}L{n-1}\dots L_{k}\dots L_{2}L_{1}A^{(0)}$

$$A^{(n-1)}= \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&\dots&a_{1n}^{(0)}\\ &a_{22}^{(1)}&\dots&a{2n}^{(1)}\\ &&\ddots&\vdots\\ &&&a_{nn}^{n-1} \end{pmatrix}$$

我们注意到$L_{k}$的逆矩阵为

$$L_{k}^{-1}= \begin{pmatrix} 1&&&\\ &\ddots&&\\ &&1&&\\ &&-l_{k+1,k}&1\\ &&\vdots&&\ddots\\ &&l_{n,k}&&&1 \end{pmatrix}$$

则$A=A^{(0)}=L_{1}^{-1}L{2}^{-1}\dots L_{n-1}^{-1}A^{(n-1)}=LU$

其中

$$L\triangleq L_{1}^{-1}L_{2}^{-1}\dots L_{n-1}^{-1}= \begin{pmatrix} 1&&&&\\ l_{21}&1\\ l_{31}&l_{32}&1\\ \vdots&\vdots&&\ddots\\ l_{n1}&l_{n2}&\dots&l_{n,n-1}&l_{n,n} \end{pmatrix}\\ \quad\\ \quad\\ U\triangleq A^{(n-1)} \begin{pmatrix} u_{11}&u_{12}&\dots&u_{1n}\\ &u_{22}&\dots&u_{2n}\\ &&\ddots&\vdots\\ &&&u_{nn} \end{pmatrix}$$

显然可知L为下三角矩阵而U为上三角矩阵

LU分解的公式推导

根据$A=LU$,由矩阵乘法可得

$$a_{ij}=\sum_{k=1}^{n}l_{ik}u_{kj},\quad i,j=1,2,\dots,n \quad(1)$$

注：由L为下三角矩阵可知$l_{ij}=0, when j>i$ 同样的因为U是上三角矩阵，所以$u_{ij}=0, when i>j$

由（1）可先计算U的元

$$a_{ij}=\sum_{k=1}^{i}l_{ik}u_{kj}=\sum_{k=1}^{i-1}l_{ik}u_{kj}+u_{ij}\quad\quad 故\\ u_{ij}=a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj}\quad i=1,2,\dots,n;j=i,i+1,\dots,n \\ 特别的,当i=1时，u_{1j}=a_{1j}(j=1,2,\dots,n)$$

然后再计算L的元

$$a_{ij}=\sum_{k=1}^{j}l_{ik}u_{kj}=\sum_{k=1}^{j-1}l_{ik}u_{kj}+l_{ij}u_{jj}\\ \quad\\ l_{ij}=\frac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj}}{u_{jj}}\\ 特别的，当j=1时，l_{i1}=\frac{a_{i1}}{u_{11}}$$

综上所述，我们可以得到如下公式

$$\left\{ \begin{array}\ u_{1j}=a_{1j},\quad\quad\quad\quad\quad j=1,2,\dots,n\\ l_{i1}=\frac{a_{i1}}{u_{11}},\quad\quad\quad\quad\quad i=2,3,\dots,n\\ u_{ij}=a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj},\quad\quad\quad\quad\quad i=2,3,\dots,n;j=i,i+1,\dots,n\quad\quad\quad（2）\\ l_{ij}=\frac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj}}{u_{jj}},\quad\quad j=2,3,\dots,n-1;i=j+1,j+2,\dots,n \end{array} \right.$$