矩阵分解

三角分解

注：上角标用来标记变换次数，(1)^{(1)}表示没有发生变化。

若有A=[a11a12…a1na21a22…a2n⋮⋮⋱⋮an1an2…ann]n×nA = \left[\begin{array}{c} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{array}\right]_{n×n}，则第一步高斯消去的过程就是对矩阵AA做了(n−1)(n-1)次初等行变换，其效果就相当于左乘(n−1)(n-1)个初等矩阵，将这(n−1)(n-1)个初等矩阵相乘即得单位下三角矩阵L1L_1。
 

L1=[1−l211−l311⋮⋱−ln11]n×nL_1 = \left[\begin{array}{c} 1 & \\ -l_{21} & 1 & \\ -l_{31} & & 1 & \\ \vdots & & & \ddots & \\ -l_{n1} & & & & 1 \end{array}\right]_{n×n}，A(2)=L1A=[a11(1)a12(1)⋯a1n(1)0a22(2)⋯a2n(2)⋮⋮⋱⋮0an2(2)⋯ann(2)]A^{(2)} = L_1A = \left[\begin{array}{c} a_{11}^{(1)} & a_{12}^{(1)} & \cdots & a_{1n}^{(1)} \\ 0 & a_{22}^{(2)} & \cdots & a_{2n}^{(2)} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & a_{n2}^{(2)} & \cdots & a_{nn}^{(2)} \end{array}\right]
 

继续对矩阵A(2)A^{(2)}做初等行变换以得到A(3)A^{(3)}。

L2=[11−l321⋮⋱−ln21]n×nL_2 = \left[\begin{array}{c} 1 & \\ & 1 & \\ & -l_{32} & 1 & \\ & \vdots & & \ddots & \\ & -l_{n2} & & & 1 \end{array}\right]_{n×n}，A(3)=L2A(2)[a11(1)a12(1)a13(1)⋯a1n(1)0a22(2)a23(2)⋯a2n(2)00a33(3)⋯a3n(3)⋮⋮⋮⋱⋮00an3(3)⋯ann(3)]A^{(3)} = L_2A^{(2)} \left[\begin{array}{c} a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)} & \cdots & a_{1n}^{(1)} \\ 0 & a_{22}^{(2)} & a_{23}^{(2)} & \cdots & a_{2n}^{(2)} \\ 0 & 0 & a_{33}^{(3)} & \cdots & a_{3n}^{(3)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & a_{n3}^{(3)} & \cdots & a_{nn}^{(3)} \end{array}\right]
 

综上

A(n)=Ln−1Ln−2⋯L2L1AA^{(n)} = L_{n-1} L_{n-2} \cdots L_2 L_1 A

A=L1−1L2−1⋯Ln−2−1Ln−1−1A(n)A = L_1^{-1} L_2^{-1} \cdots L_{n-2}^{-1} L_{n-1}^{-1} A^{(n)}

LU分解

记{L=L1−1L2−1⋯Ln−2−1Ln−1−1U=A(n)\begin{cases} L = L_1^{-1}L_2^{-1} \cdots L_{n-2}^{-1} L_{n-1}^{-1} \\ U=A^{(n)} \end{cases}，则A=LUA=LU，称为方阵AA的LULU三角分解。

性质

求解

已知Ax=bAx=b，则LUx=bLUx=b，将线性方程组的求解转换为

{Ux=yLy=b\begin{cases} Ux=y \\ Ly=b \end{cases}

即两个三角方程组的求解。

LDU分解

如果AA能分解为LDULDU，则A=LDUA=LDU，称为方阵AA的LDULDU三角分解。

性质

Doolittle分解

对于LU分解，如果LL是一个单位下三角矩阵，则称它为Doolittle分解。

[a11a12…a1na21a22…a2n⋮⋮⋱⋮an1an2…ann]=[1l211⋮⋮⋱ln1ln2…1][u11u12…u1nu22…u2n⋱⋮unn]\left[\begin{array}{c} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{array}\right] = \left[\begin{array}{c} 1 & \\ l_{21} & 1 & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \dots & 1 \end{array}\right] \left[\begin{array}{c} u_{11} & u_{12} & \dots & u_{1n} \\ & u_{22} & \dots & u_{2n} \\ & & \ddots & \vdots \\ & & & u_{nn} \end{array}\right]

性质

分解法

变换法

直接分解法

Crout分解

对于LU分解，如果UU是一个单位上三角矩阵，则称它为Crout分解。

[a11a12…a1na21a22…a2n⋮⋮⋱⋮an1an2…ann]=[l11l21l22⋮⋮⋱ln1ln2…lnn][1u12…u1n1…u2n⋱⋮1]\left[\begin{array}{c} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{array}\right] = \left[\begin{array}{c} l_{11} & \\ l_{21} & l_{22} & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \dots & l_{nn} \end{array}\right] \left[\begin{array}{c} 1 & u_{12} & \dots & u_{1n} \\ & 1 & \dots & u_{2n} \\ & & \ddots & \vdots \\ & & & 1 \end{array}\right]

小结

对于LDU分解、Doolittle分解、Crout分解

例

已知{x1+2x2−3x3=12x1−x2+3x3=53x1−2x2+2x3=1\begin{cases} x_1 + 2x_2 - 3x_3 = 1 \\ 2x_1 - x_2 + 3x_3 = 5 \\ 3x_1 - 2x_2 + 2x_3 = 1 \end{cases}

解

则A=[12−32−133−22]A= \left[\begin{array}{c} 1 & 2 & -3 \\ 2 & -1 & 3 \\ 3 & -2 & 2 \end{array}\right]

使用Doolittle分解法，直接分解该矩阵。

L\U=[12−3  ]L{\backslash}U= \left[\begin{array}{c} 1 & 2 & -3 \\ \, \\ \, \end{array}\right]

L\U=[12−323]L{\backslash}U= \left[\begin{array}{c} 1 & 2 & -3 \\ 2 & \\ 3 & \end{array}\right]

L\U=[12−32−593]L{\backslash}U= \left[\begin{array}{c} 1 & 2 & -3 \\ 2 & -5 & 9 \\ 3 & \end{array}\right]

L\U=[12−32−59385]L{\backslash}U= \left[\begin{array}{c} 1 & 2 & -3 \\ 2 & -5 & 9 \\ 3 & \frac{8}{5} & \end{array}\right]

L\U=[12−32−59385−175]L{\backslash}U= \left[\begin{array}{c} 1 & 2 & -3 \\ 2 & -5 & 9 \\ 3 & \frac{8}{5} & -\frac{17}{5} \end{array}\right]

故A=[1213851][12−3−59−175]A= \left[\begin{array}{c} 1 & \\ 2 & 1 & \\ 3 & \frac{8}{5} & 1 \end{array}\right] \left[\begin{array}{c} 1 & 2 & -3 \\ & -5 & 9 \\ & & -\frac{17}{5} \end{array}\right]

Cholesky分解

当矩阵AA实对称（AT=AA^T=A）且正定（xTAx>0x^TAx>0）时，LULU分解的UU可以进一步分解为DMDM

[u11u12…u1nu22…u2n⋱⋮unn]=[u11u22⋱unn][1u12u11…u1nu111…u2nu22⋱⋮1]\left[\begin{array}{c} u_{11} & u_{12} & \dots & u_{1n} \\ & u_{22} & \dots & u_{2n} \\ & & \ddots & \vdots \\ & & & u_{nn} \end{array}\right] = \left[\begin{array}{c} u_{11} & \\ & u_{22} & \\ & & \ddots & \\ & & & u_{nn} \end{array}\right] \left[\begin{array}{c} 1 & \frac{u_{12}}{u_{11}} & \dots & \frac{u_{1n}}{u_{11}} \\ & 1 & \dots & \frac{u_{2n}}{u_{22}} \\ & & \ddots & \vdots \\ & & & 1 \end{array}\right]

A=LDMA=LDM，AT=AA^T=A

⇒AT=(LDM)T=MTDLT=A=LDM⇒MTDLT=LDM⇒M=LT⇒A=LDLT\begin{array}{l} ⇒ A^T = (LDM)^T = M^TDL^T = A = LDM \\ ⇒ M^TDL^T = LDM \\ ⇒ M = L^T \\ ⇒ A = LDL^T \end{array}

令D=D12⋅D12=[u11u22⋱unn][u11u22⋱unn]D = D^{\frac{1}{2}} ⋅ D^{\frac{1}{2}} = \left[\begin{array}{c} \sqrt{u_{11}} & \\ & \sqrt{u_{22}} & \\ & & \ddots & \\ & & & \sqrt{u_{nn}} \end{array}\right] \left[\begin{array}{c} \sqrt{u_{11}} & \\ & \sqrt{u_{22}} & \\ & & \ddots & \\ & & & \sqrt{u_{nn}} \end{array}\right]

则A=LD12D12LT=(LD12)(LD12)TA = L D^{\frac{1}{2}} D^{\frac{1}{2}} L^T = (LD^{\frac{1}{2}}) (LD^{\frac{1}{2}})^T

令G=LD12=[g11g21g22g31g32g33⋮⋮⋮⋱gn1gn2gn3⋯gnn]G = L D^{\frac{1}{2}} = \left[\begin{array}{c} g_{11} & \\ g_{21} & g_{22} & \\ g_{31} & g_{32} & g_{33} & \\ \vdots & \vdots & \vdots & \ddots & \\ g_{n1} & g_{n2} & g_{n3} & \cdots & g_{nn} \end{array}\right]，GT=[g11g21g31⋯gn1g22g32⋯gn1g33⋯gn3⋱gnn]G^T = \left[\begin{array}{c} g_{11} & g_{21} & g_{31} & \cdots & g_{n1} \\ & g_{22} & g_{32} & \cdots & g_{n1} \\ & & g_{33} & \cdots & g_{n3} \\ & & & \ddots & \\ & & & & g_{nn} \end{array}\right]

综上

A=GGTA = GG^T

称为对称正定矩阵的Cholesky分解或平方根分解。

满秩分解

将矩阵Am×nA_{m×n}化为行最简HH有

Am×n=P−1m×mHm×n=[Bm×rSm×(m−r)][Cr×n0(m−r)×n]=BCA_{m×n} = {P^{-1}}_{m×m} H_{m×n} = \left[\begin{array}{c} B_{m×r} & S_{m×(m-r)} \end{array}\right] \left[\begin{array}{c} C_{r×n} \\ 0_{(m-r)×n} \end{array}\right] = BC

[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn]m×n=[b11b12⋯b1rb21b22⋯b2r⋮⋮⋱⋮bm1bm2⋯bmr]m×r[c11c12⋯c1nc21c22⋯c2n⋮⋮⋱⋮cr1cr2⋯crn]r×n\left[\begin{array}{c} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array}\right]_{m×n} = \left[\begin{array}{c} b_{11} & b_{12} & \cdots & b_{1r} \\ b_{21} & b_{22} & \cdots & b_{2r} \\ \vdots & \vdots & \ddots & \vdots \\ b_{m1} & b_{m2} & \cdots & b_{mr} \end{array}\right]_{m×r} \left[\begin{array}{c} c_{11} & c_{12} & \cdots & c_{1n} \\ c_{21} & c_{22} & \cdots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{r1} & c_{r2} & \cdots & c_{rn} \end{array}\right]_{r×n}

对HH施列变换，使得HQ=[Er∗00]m×nHQ = \left[\begin{array}{c} E_r & * \\ 0 & 0 \end{array}\right]_{m×n}

AQ=P−1HQ=[BS]HQ=[BS][Er∗00]=[BB∗]AQ = P^{-1}HQ = \left[\begin{array}{c} B & S \end{array}\right] HQ =\left[\begin{array}{c} B & S \end{array}\right] \left[\begin{array}{c} E_r & * \\ 0 & 0 \end{array}\right] = \left[\begin{array}{c} B & B^* \end{array}\right]

性质

求解思路

例

求矩阵A=[204321−24031111021321]A = \left[\begin{array}{c} 2 & 0 & 4 & 3 & 2 \\ 1 & −2 & 4 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 \\ 2 & 1 & 3 & 2 & 1 \end{array}\right]的满秩分解。

解

A=[204321−24031111021321]→初等行变换[1111001−1010001000000]→初等行变换[1020101−10−10001000000]A = \left[\begin{array}{c} 2 & 0 & 4 & 3 & 2 \\ 1 & −2 & 4 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 \\ 2 & 1 & 3 & 2 & 1 \end{array}\right] \xrightarrow[]{初等行变换} \left[\begin{array}{c} 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & −1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \xrightarrow[]{初等行变换} \left[\begin{array}{c} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & −1 & 0 & −1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]

明显r=3r=3（前3行不为0）

C=[1020101−10−100010]C = \left[\begin{array}{c} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & −1 & 0 & −1 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right]

由AQ=[BB∗]AQ = \left[\begin{array}{c} B & B^* \end{array}\right]（即3、4列互换）

B=[2031−20111212]B = \left[\begin{array}{c} 2 & 0 & 3 \\ 1 & −2 & 0 \\ 1 & 1 & 1 \\ 2 & 1 & 2 \end{array}\right]

综上

A=[2031−20111212][1020101−10−100010]A = \left[\begin{array}{c} 2 & 0 & 3 \\ 1 & −2 & 0 \\ 1 & 1 & 1 \\ 2 & 1 & 2 \end{array}\right] \left[\begin{array}{c} 1 & 0 & 2 & 0 & 1 \\ 0 & 1 & −1 & 0 & −1 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right]

QR分解

Am×n=Qm×rRr×nA_{m×n} = Q_{m×r} R_{r×n}

其中QQ满足QTQ=ErQ^TQ=E_r，可对满秩分解的BB矩阵做Schmidt正交化得到QQ矩阵。

性质

奇异值分解

略