[矩陣的三角分解系列五] 三角分解中的行列變換

三角分解中的行列變換

• 簡介
• 行變換分解
• • 置換矩陣
  • PLU分解
  • • 證明
• 例子
• 引用

矩陣的三角分解是求解線性方程組常用的方法，包括LU分解，LDU分解，杜利特(Doolittle)分解，克勞特(Crout)分解，LLT(喬累斯基Cholesky)分解，LDLT(不帶平方根喬累斯基)分解等，以及為了滿足分解條件又加入行列變換的LPU分解，PLU分解，LUP分解，LDPU分解等。這裡矩陣的三角分解系列教程主要是針對在學習三角分解時候的涉及到的一些細節，包括很多方法的來源和證明等，以及其中用到的一些矩陣操作的基礎知識，主要包括：

• [矩陣的三角分解系列一] 高斯消元法
• [矩陣的三角分解系列二] LDU基本定理
• [矩陣的三角分解系列三] 杜利特/克勞特分解公式
• [矩陣的三角分解系列四] 喬累斯基(Cholesky)分解公式
• [矩陣的三角分解系列五] 三角分解中的行列變換
• [矩陣的三角分解系列六] Eigen中的三角分解

這個系列後面文章會用到前面文章的理論和技術，是以建議按照順序檢視。

簡介

在之前文章的講解中，主要介紹 n n n階方陣 A \boldsymbol{A} A可以進行三角分解的充要條件為 A \boldsymbol{A} A的前 n − 1 n-1 n−1個順序主子式 Δ k ≠ 0 ( k = 1 , 2 , ⋯   , n − 1 ) \Delta_{k} \not = 0(k=1,2,\cdots,n-1) Δk​​=0(k=1,2,⋯,n−1)。但不是所有的 n n n階方陣 A \boldsymbol{A} A都滿足這個條件，但對于某些矩陣來說通過行變換可以滿足矩陣三角分解的條件。同時在[矩陣的三角分解系列二] LDU基本定理-穩定性中也介紹對于矩陣 L U \boldsymbol{LU} LU分解是不穩定的，會出現大數的問題。這裡主要介紹利用矩陣的行變換解決三角分解的這些問題。

行變換分解

置換矩陣

行變換矩陣是置換(permutation)矩陣的一種，是以一般叫做 P \boldsymbol{P} P矩陣。而且一個 n n n階方陣 P \boldsymbol{P} P為置換矩陣的充要條件是矩陣的每一行恰有一個1，每一列恰有一個1。具體定義為

設 e i e_i ei​是 n n n階機關矩陣的第 i ( i = 1 , 2 , ⋯   , n ) i(i=1,2,\cdots,n) i(i=1,2,⋯,n)，以 e 1 , e 2 , ⋯   , e n e_1,e_2,\cdots,e_n e1​,e2​,⋯,en​為列組成的矩陣 [ e k 1 , e k 2 , ⋯   , e k n ] [e_{k1},e_{k2},\cdots,e_{kn}] [ek1​,ek2​,⋯,ekn​]稱為 n n n階置換矩陣，其中 k 1 , k 2 , ⋯   , k n k1,k2,\cdots,kn k1,k2,⋯,kn變量是 1 , 2 , ⋯   , n 1,2,\cdots,n 1,2,⋯,n的一個排列。

令

P = [ e k 1 , e k 2 , ⋯   , e k n ] \boldsymbol{P}=[e_{k1},e_{k2},\cdots,e_{kn}] P=[ek1​,ek2​,⋯,ekn​]

那麼 P T A \boldsymbol{P^\mathrm{T}A} PTA就是将 A \boldsymbol{A} A的所有行按照 k 1 , k 2 , ⋯   , k n k1,k2,\cdots,kn k1,k2,⋯,kn的順序重新排列。左乘 P \boldsymbol{P} P就是行變換操作。

同理，那麼 A P \boldsymbol{AP} AP就是将 A \boldsymbol{A} A的所有列按照 k 1 , k 2 , ⋯   , k n k1,k2,\cdots,kn k1,k2,⋯,kn的順序重新排列。右乘 P \boldsymbol{P} P就是列變換操作。

同時需要注意置換矩陣還是正交矩陣，滿足 P P T = I \boldsymbol{PP^\mathrm{T}=I} PPT=I。

為了解決簡介中提到的利用行變換對矩陣 A \boldsymbol{A} A進行變換，以使得變換後的矩陣 A ′ \boldsymbol{A}^\prime A′滿足三角分解的條件。在三角分解中進行行變換的方式比較多，這裡僅僅介紹常用的幾個。

PLU分解

A \boldsymbol{A} A為 n n n階方陣，則存在分解

A = P L U \boldsymbol{A = P L U} A=PLU

其中 L \boldsymbol{L} L是機關下三角矩陣， U \boldsymbol{U} U是上三角矩陣， P \boldsymbol{P} P是置換矩陣。

證明

待續

例子

引用

【1】 矩陣論(第二版)