[矩阵的三角分解系列五] 三角分解中的行列变换

三角分解中的行列变换

• 简介
• 行变换分解
• • 置换矩阵
  • 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】 矩阵论(第二版)