三角分解与标准型
將學(xué)習(xí)到什么
介紹關(guān)于三角分解的定理. 包括 \(LU\) 分解、 \(LDU\) 分解、\(PLU\) 分解、\(LPU\) 分解以及 \(LPDU\) 分解.
?
\(LU\) 分解
我們知道，如果一個(gè)線性方程組 \(Ax=b\) 的系數(shù)矩陣 \(A \in M_n\) 是非奇異的三角矩陣，則其唯一的解計(jì)算很容易，受此啟發(fā)，如果 \(A \in M_n\) 不是三角的，我們將非奇異的 \(A\) 分解成 \(A=LU\), 其中 \(L\) 是下三角的，而 \(U\) 是上三角的：首先求解 \(Ly=b\), 然后求解 \(Ux=y\).
?
??定義 1： 設(shè) \(A \in M_n\), 表達(dá)式 \(A=LU\) 稱為 \(A\) 的 \(LU\) 分解 , 其中 \(L \in M_n\) 是下三角的，而 \(U \in M_n\) 是上三角的.
?
下面兩個(gè)說法等價(jià)：
??(1) \(A\in M_n\) 有 \(LU\) 分解， 其中 \(L(U)\) 是非奇異的
??(2) \(A\in M_n\) 有 \(LU\) 分解，其中 \(L(U)\) 是單位下三角（單位上三角）的.
因?yàn)槿绻?\(L\) 是非奇異的，記 \(L=L'D\), 其中 \(L'\) 是單位下三角的，\(D\) 是對(duì)角的，如果 \(L\) 是單位下三角的，顯然也是非奇異的.
?
??引理 1： 設(shè) \(A \in M_n\), 又假設(shè) \(A=LU\) 是 \(LU\) 分解. 對(duì)任何一個(gè)分塊的 \(2 \times 2\) 分劃
\begin{align}
A=\begin{bmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{bmatrix}, \quad L=\begin{bmatrix} L_{11} & 0 \ L_{21} & L_{22} \end{bmatrix}, \quad U=\begin{bmatrix} U_{11} & U_{12} \ 0 & U_{22} \end{bmatrix}
\end{align}
其中 \(A_{11},L_{11},U_{11} \in M_k\) 且 \(k \leqslant n\), 我們有 \(A_{11}=L_{11}U_{11}\). 由此可見，\(A\) 的每一個(gè)前主子矩陣都有 \(LU\) 分解，且分解式中的因子是 \(L\) 與 \(U\) 的對(duì)應(yīng)的前主子矩陣.
?
為了解釋下個(gè)定理，我們借上個(gè)引理說明一下：矩陣 \(A\) 的 行包容性質(zhì)是說行向量 \(A_{21}\) 可以由 \(A_{11}\) 的行線性表示. 其實(shí)，它有更強(qiáng)的性質(zhì)，\(A_{21}\) 不一定是行向量，它的每一行也可以由 \(A_{11}\) 的行線性表示.
?
??定理 1：設(shè)給定 \(A \in M_n\), 那么
??(a) \(A\) 有 \(LU\) 分解（其中 \(L\) 是非奇異的），當(dāng)且僅當(dāng) \(A\) 有行包容性質(zhì)：對(duì)每個(gè) \(i=1,\cdots,n-1\), \(A[\{i+1;1,\cdots ,i\}]\) 是 \(A[\{1,\cdots,i\}]\) 的行的線性組合.
??(b) \(A\) 有 \(LU\) 分解（其中 \(U\) 是非奇異的），當(dāng)且僅當(dāng) \(A\) 有列包容性質(zhì)：對(duì)每個(gè) \(j=1,\cdots,n-1\), \(A[\{1,\cdots ,j;j+1\}]\) 是 \(A[\{1,\cdots,j\}]\) 的列的線性組合.
?
??證明：如果 \(A=LU\), 由引理 1 知 \(A[\{1,\cdots,i+1\}]=L[\{1,\cdots,i+1\}] U[\{1,\cdots,i+1\}]\). 這樣一來，為了驗(yàn)證行包容性質(zhì)的必要性，只需要在引理 1 中給出的分劃中取 \(i=k=n-1\) 就夠了. 由于 \(L\) 是非奇異的且是三角矩陣，\(L_{11}\) 也是非奇異的，這樣我們就有 \(A_{21}=L_{21}U_{11}=L_{21}L_{11}^{-1}L_{11}U_{11}=(L_{21}L_{11}^{-1})A_{11}\), 這樣就驗(yàn)證了行包容性質(zhì) .
反之，如果 \(A\) 有行包容性質(zhì)，我們就可以歸納地構(gòu)造出 \(LU\) 分解，其中的 \(L\) 是非奇異的（\(n=1,2\) 的情形容易驗(yàn)證）：假設(shè) \(A_{11}=L_{11}U_{11}\), \(L_{11}\) 是非奇異的，且行向量 \(A_{21}\) 是 \(A_{11}\) 的行的線性組合. 這樣就存在一個(gè)向量 \(y\) 使得 \(A_{21}=y^TA_{11}=y^TL_{11}U_{11}\), 我們就可以取 \(U_{12}=L_{11}^{-1}A_{12}\), \(L_{21}=y^TL_{11}\), \(L_{22}=1\) 以及 \(U_{22}=A_{22}-L_{21}U_{12}\), 從而得到 \(A\) 的一個(gè) \(LU\) 分解，其中 \(L\) 是非奇異的.
關(guān)于列包容性質(zhì)的結(jié)論可以通過考慮 \(A^T\) 的 \(LU\) 分解得出.
?
舉個(gè)例子：考慮矩陣 \(J_n \in M_n\), 它所有的元素都是 \(1\). 則 \(J_n\) 的一個(gè) \(LU\) 分解是 \(L\) 是單位下三角的（對(duì)角元素是 \(1\)），其它的元素只有第一列為 \(1\), \(U\) 只有第一行元素是 \(1\). \(J_n=J_n^T=U^TL^T\) 就是 \(J_n\) 的帶有一個(gè)單位上三角因子的 \(LU\) 分解.
?
如果 \(A \in M_n\), \(\mathrm{rank}\,A=k\), 且 \(\mathrm{det}\,A[\{1,\cdots,j\}] \neq 0\), \(j=1,\cdots,k\), 那么 \(A\) 既有行包容性質(zhì)，也有列包容性質(zhì). 下面的結(jié)果由 定理 1 推出.
?
??推論 1： 假設(shè) \(A \in M_n\) 以及 \(\mathrm{rank}\,A=k\). 如果對(duì)所有 \(j=1,\cdots,k\), \(A[\{1,\cdots, j\}]\) 都是非奇異的，那么 \(A\) 有 \(LU\) 分解. 此外，哪一個(gè)因子都可以取作為單位上三角矩陣；\(L\) 與 \(U\) 兩者都是非奇異的，當(dāng)且僅當(dāng) \(k=n\), 即當(dāng)且僅當(dāng) \(A\) 與它所有的前主子矩陣都是非奇異的.
?
不是每個(gè)矩陣都有 \(LU\) 分解. 如果 \(A=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) 可以寫成 \(A=LU=\begin{bmatrix} \ell_{11} & 0 \\ \ell_{21} & \ell_{22} \end{bmatrix} \begin{bmatrix} u_{11}& u_{12} \\ 0 & u_{22} \end{bmatrix}\), 那么 \(\ell_{11} u_{11}=0\) 蘊(yùn)含 \(L\) 與 \(U\) 中有一個(gè)是奇異的，但 \(LU=A\) 是非奇異的. 其實(shí)有奇異的前主子矩陣的非奇異的矩陣不可能有 \(LU\) 分解. 可以驗(yàn)證
\begin{align}
A= \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} =\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \notag
\end{align}
有 \(LU\) 分解，盡管 \(A\) 既沒有行包容性質(zhì)，也沒有列包容性質(zhì). 考慮 \(A=\begin{bmatrix} 1 & 0 \\ a & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 0 & 2-a \end{bmatrix} =\begin{bmatrix} 0 & 1 \\ 0 & 2 \end{bmatrix}\), \(A\) 與 \(a\) 的值無關(guān)，說明即使要求 \(L\) 是單位下三角矩陣， \(LU\) 分解也不一定是唯一的. 種種不確定性會(huì)有很多麻煩，然而，利用引理 1 和定理 1, 我們可以在非奇異的情形給出充分的描述，而且可以施以正規(guī)化以使得分解是唯一的.
?
一些推論
\(LDU\) 分解
??推論 2： 設(shè)給定 \(A = [a_{ij}] \in M_n\).
??(a) 假設(shè) \(A\) 是非奇異的. 那么 \(A\) 有 \(LU\) 分解 \(A=LU\), 當(dāng)且僅當(dāng)對(duì)所有 \(i=1,\cdots,n\), \(A[\{1,\cdots, i \}]\) 都是非奇異的.
??(b) 假設(shè)對(duì)所有 \(i=1,\cdots,n\), \(A[\{1,\cdots, i \}]\) 都是非奇異的. 那么 \(A=LDU\), 其中 \(L,D,U \in M_n\), \(L\) 是單位下三角矩陣，\(U\) 是單位上三角矩陣， \(D=\mathrm{diag}(d_1,\cdots,d_n)\) 是對(duì)矩角陣， \(d_1=a_{11}\), 且
\begin{align}
d_i = \mathrm{det} \, A[{1,\cdots, i }] / \mathrm{det} \, A[{1,\cdots, i-1 }], \quad i=2,\cdots, n
\end{align}
因子 \(L,U,D\) 是唯一確定的.
?
\(PLU\) 分解
對(duì)于非奇異的線性方程組 \(Ax=b\) 的解，假設(shè) \(A \in M_n\) 不可能分解成 \(LU\)，其原因是前主子矩陣是奇異的，我們可以考慮對(duì)矩陣的行重新排序，使之滿足 \(LU\) 分解的條件，這就引入了 \(PLU\) 分解, 其中 \(P \in M_n\) 是置換矩陣，而 \(L\) 與 \(U\) 分別是下三角的和上三角的. 這就等同于在分解之前將線性方程組中的方程重新排序. 在此情形，通過 \(Ly=p^Tb\) 以及 \(Ux=y\), 求解 \(Ax=b\) 仍然是相當(dāng)簡(jiǎn)單的. 值得注意的是：任何 \(A \in M_n\) 都可以這樣分解且 \(L\) 可以取為非奇異的. \(Ax=b\) 的解與 \(Ux=L^{-1}P^Tb\) 的解是相同的.
?
??引理 2： 設(shè) \(A \in M_n\) 是非奇異的. 那么就存在一個(gè)置換矩陣 \(P \in M_k\), 使得 \(\mathrm{det}(P^TA)[\{1,\cdots,j\}] \neq 0\), \(j=1,\cdots, k\).
?
用歸納假設(shè)可以對(duì)引理 2 進(jìn)行說明，在此不再贅述. 下面給出 \(PLU\) 分解定理，其因子不一定是唯一的.
?
??定理 2（\(PLU\) 分解）： 對(duì)每個(gè) \(A \in M_n\), 存在一個(gè)置換矩陣 \(P \in M_n\), 一個(gè)單位下三角矩陣 \(L \in M_n\) 以及一個(gè)上三角矩陣 \(U \in M_n\), 使得 \(A = PLU\).
?
上個(gè)定理也可說為：每一個(gè) \(A \in M_n\), 可以分解成 \(A=LUP\), 其中 \(L\) 是下三角的，\(U\) 是單位上三角的，且 \(P \in M_n\) 是置換矩陣. 值得一提的是，\(PLU\) 分解對(duì)矩陣 \(A \in M_n\) 沒有任何限制.
?
\(LPU\) 分解
下面的定理描述了一種特殊的三角分解，它對(duì)每一個(gè)復(fù)方陣成立. 在非奇異的情形，因子 \(P\) 的唯一性有重要的推論.
?
??定理 3（\(LPU\) 分解）： 對(duì)每一個(gè) \(A \in M_n\), 存在一個(gè)置換矩陣 \(P \in M_n\), 一個(gè)單位下三角矩陣 \(L \in M_n\) 以及一個(gè)上三角矩陣 \(U \in M_n\), 使得 \(A = LPU\). 此外，如果 \(A\) 是非奇異的，那么 \(P\) 是唯一確定的.
?
上個(gè)定理可用歸納法證明.
?
\(LPDU\) 分解
首先給出一個(gè)等價(jià)關(guān)系的定義.
?
??定義 2：矩陣 \(A,B \in M_n\) 稱為三角等價(jià)的，如果存在非奇異的矩陣 \(L,U \in M_n\), 使得 \(L\) 是下三角的，\(U\) 是上三角的，且 \(A=LBU\).
?
最后一個(gè)定理與用單位三角矩陣來實(shí)現(xiàn)三角等價(jià)有關(guān). 它用到如下事實(shí)：(a) 單位下三角矩陣的逆是單位下三角的，以及 (b) 單位下三角矩陣的乘積是單位下三角的，關(guān)于單位上三角矩陣的逆有對(duì)應(yīng)的結(jié)論.
?
??定理 4（\(LPDU\) 分解）： 對(duì)每一個(gè)非奇異的 \(A \in M_n\), 存在一個(gè)唯一的置換矩陣 \(P \in M_n\), 一個(gè)唯一的非奇異的對(duì)角矩陣 \(D\), 一個(gè)單位下三角矩陣 \(L\) 以及一個(gè)上三角矩陣 \(U\), 使得 \(A = LPDU\).
?
應(yīng)該知道什么
- 如果矩陣 \(A\) 有 \(LU\) 分解，且 \(A\) 的每一個(gè)前主子矩陣都有 \(LU\) 分解，且分解式中的因子是 \(L\) 與 \(U\) 的對(duì)應(yīng)的前主子矩陣
- 由推論 1 知，若 \(\mathrm{rank}\,A=k\)，如果對(duì)所有 \(j=1,\cdots,k\), \(A[\{1,\cdots, j\}]\) 都是非奇異的，那么 \(A\) 有 \(LU\) 分解. 非奇異矩陣不一定有 \(LU\) 分解，比如反序矩陣.
- 奇異的前主子矩陣的非奇異的矩陣不可能有 \(LU\) 分解
- 給定矩陣的 \(LU\) 分解可能存在，也可能不存在，即使存在也不一定唯一
- 對(duì)所有 \(i=1,\cdots,n\), \(A[\{1,\cdots, i \}]\) 都是非奇異的. 那么 \(A=LDU\), 其中 \(L,D,U \in M_n\) 且各自唯一
- 對(duì)每個(gè) \(A \in M_n\), 存在 \(PLU\) 分解，其不唯一
- 對(duì)每個(gè) \(A \in M_n\), 存在 \(LPU\) 分解，如果 \(A\) 是非奇異的，那么 \(P\) 是唯一確定的
- 對(duì)每一個(gè)非奇異的 \(A \in M_n\), 存在一個(gè)唯一的置換矩陣 \(P \in M_n\), 一個(gè)唯一的非奇異的對(duì)角矩陣 \(D\), 一個(gè)單位下三角矩陣 \(L\) 以及一個(gè)上三角矩陣 \(U\), 使得 \(A = LPDU\)
轉(zhuǎn)載于:https://www.cnblogs.com/zhoukui/p/7865142.html
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
