本文介绍了矩阵的三角分解,如LU分解,LDR分解,Cholesky分解等。
为博主在学习过程中,总结或者思考的记录,用于加深印象,不作为知识讲解和科普,如果理解有误还请指出。
前言
对矩阵进行分解能够清晰反应出原矩阵的某些数字特征,在矩阵运算中可以起到化简的作用,其次在一些特定的场合将矩阵分解为合适的形式能够减少运算误差,在数值计算中有很重要的地位。
一、LR(LU)分解,也称Doolittle分解
若矩阵A可以表示为:
A = L·R
其中,L为单位下三角矩阵,R为上三角矩阵,则称A可三角分解(LR分解)。例如:
A=⎣⎢⎡24213241320⎦⎥⎤=⎣⎢⎡121111⎦⎥⎤⋅⎣⎢⎡2114511⎦⎥⎤=L⋅R
LR分解可以用于解线性方程组 Ax=b,若方阵A有LR分解,即A=L⋅R,令Rx=y,则方程组等价于:
{Ly=bRx=y,此处L.R.b均为已知量
由于L和R的特殊形式,Ly=b 很容易利用高斯消元迭代求出y,然后代入Rx=y,再次迭代求出x。
那么提出三个问题,什么矩阵可以分解?什么矩阵不可以分解?以及分解的形式是否唯一?
1. 什么矩阵可以分解
很容易找到矩阵[0110],此矩阵可逆但是没有三角分解。
定理1:
n阶方阵A具有唯一LR分解的充要条件是A的前 n - 1个顺序主子式不为零。
其中,
A=⎝⎜⎜⎜⎜⎛a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann⎠⎟⎟⎟⎟⎞,第k个顺序主子式
Δk=∣∣∣∣∣∣∣∣∣∣a11a21⋮ak1a12a22⋮ak2⋯⋯⋱⋯a1ka2k⋮akk∣∣∣∣∣∣∣∣∣∣
易知
a11=0,那么对A进行行初等变换,把除了第一行以外的所有行的第一个元素全部消除,相当于在A的左边乘以下三角矩阵
L1,其中:
L1=⎣⎢⎢⎢⎢⎢⎢⎡1−a21a11−1−a31a11−1⋮−an1a11−110⋮0⋱⋱⋯⋱01⎦⎥⎥⎥⎥⎥⎥⎤
此时有:
L1A≜⎣⎢⎢⎢⎢⎡a110⋮0a12a22(1)⋮an2(1)⋯⋯⋱⋯a1na2n(1)⋮am(1)⎦⎥⎥⎥⎥⎤
接着构造下一个下三角矩阵L2,将第二列对角线以下的元素全部消除,注意此时的条件Δ2=a11⋅a22(2)=0,a11=0,即a22(2)=0.
L2=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡1000⋮01−a32(1)/a22(1)−a42(1)/a22(1)⋮−an2(1)/a22(1)10⋮0⋱⋱⋯⋱01⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤
继续左乘在L1A处,有:
L2L1A=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡a11a12a22(1)⋮00a13a22(1)a33(2)⋮an3(2)⋯⋯⋯⋱⋯a1na2n(1)a3n(2)⋮am(2)⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
以此类推,最终可以化简得到:
Ln−1⋯L2L1A=⎣⎢⎢⎢⎢⎢⎢⎢⎡a11a12a22(1)a13a22(1)a33(2)⋯⋯⋯⋱a1na2n(1)a3n(2)⋮am(n−1)⎦⎥⎥⎥⎥⎥⎥⎥⎤≜R
记Ln−1⋯L2L1=L−1,则有L−1A=R,L也是下三角矩阵,且为单位下三角矩阵。(下三角矩阵的逆仍然为下三角矩阵)
2. 那什么情况下不能分解呢?
我们看看上面的过程,是不是每一次乘以 Li 矩阵时,都需要第 i 个主对角元素不为0,这样才能作为分母,把该列下面的元素全部通过初等行变换消掉,如果矩阵 Li⋯L1A 的第 i 个主对角元素为0,那么久不能再乘以 L 了,举个例子:
A=⎣⎢⎡24212241320⎦⎥⎤r2−2r1,r3−r1⎣⎢⎡2001014516⎦⎥⎤
此时就无法继续化成上三角了。
2. 什么情况分解唯一
上面也讲了,当顺序主子式不等于0时,具有唯一分解。那么什么情况下不唯一呢?当然是顺序主子式等于0的情况,但是同时要注意上面举例说过如果碰到主子式等于0很可能出现无法继续化简的情况,但是如果恰好碰到该列下面所有元素都为0时,那就不用乘这个L了。我们举例说明:
A=⎣⎢⎡2401204136⎦⎥⎤r2−2r1⎣⎢⎡200100456⎦⎥⎤
恰好第三行需要消除的元素本身就为0.
但是此时有一个问题就是,我可以当作看成第三行没有变,我也可以是将任意倍数的第二行加到第三行,那么此时的L2既可以是单位阵,也可以是其他下三角矩阵,即L2不唯一,那么所有L的乘积自然不唯一。
A=⎣⎢⎡2401204136⎦⎥⎤=⎣⎢⎡120101⎦⎥⎤⋅⎣⎢⎡200100456⎦⎥⎤=⎣⎢⎡120111⎦⎥⎤⋅⎣⎢⎡200100451⎦⎥⎤
二、带行变换的LU分解
之前说过,如果遇到某次变换后的主对角元素为0那么就不能继续进行变换,但是我们要是将下面的行移上来呢,那主对角元素不就非0了吗?
我们用增广矩阵的形式来描述上述过程:
[AInIn]→[PAInP]→[PAQQP]=[LQP]
整个过程的目的就是将A变成下三角矩阵,由于每次只会将右边的列换到左边,所以Q一定是上三角阵,P为置换阵(多个初等行变换相乘)。
PA=LQ−1=LR
三、LDR分解
若满秩方阵A有LR分解:
A=L⋅R
则R也是满秩矩阵,且对焦元素不为0,有:
R=⎣⎢⎢⎢⎡d1d2⋱dn⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎡1r121⋯⋱⋱r1n⋮r(n−1)n1⎦⎥⎥⎥⎥⎤
从而A=LDR,其中L为单位下三角阵,D为对角阵,R为单位上三角阵。
与LR分解对比,我们只需要知道如何分解得到:
R=DR,举例说明:
R=⎣⎢⎡2114511⎦⎥⎤=⎣⎢⎡2111⎦⎥⎤⋅⎣⎢⎡11/21251⎦⎥⎤
实际上就是除以该行的主对角元素,因为对角矩阵只是会缩放当前行(左乘时),将D分解出去相当于提出了一个系数。
四、Cholesky分解
若矩阵A是对称正定矩阵,其顺序主子式Δk>0,所以A具有唯一的LDR分解,即A=LDR,其中D为对角阵:
D=⎝⎛d1⋱dn⎠⎞
由于A是对称矩阵,则有A=AT=LDR=(LDR)T=RTDLT,同时LDR分解是唯一的,说明:L=RT,A也可以表示为:
A=LDR=LD21D21LT=LD21(LD21)T=GGT
这里需要说明,因为A是正定的,D作为对角阵所有元素都是大于零的 (理由我也讲不清楚,但是D的子行列式(d1⋅d2⋯dk)是等于A对应的顺序主子式Δk的),所以 D21 相当于所有元素di开方求得。
举例:
[AInIn]→[PAPTPTP]→[DGTG]
解释一下,这里对A同时进行行和列的变换,因为A是对称矩阵,那么行怎么化简消除,列也应该怎么化简消除,所以两边是转置的关系,又因为总是消除下面的行,消除右边的列,所以P是下三角矩阵,最后的G也是下三角矩阵。
本位最初发表于2021.11 @肆拾伍
Q.E.D.