矩阵的分解

矩阵的分解

怎么计算矩阵又快又准——矩阵的分解

• 先判断Doolittle分解是否唯一，再进行Doolittle分解

各阶顺序主子式均不为0，Doolittle分解唯一；

特殊的：正定/负定矩阵，Doolittle分解唯一；严格行(列)对角占优矩阵，Doolittle分解唯一；

Doolittle分解的算法

一共 5 种分解

一、Doolittle分解（三角分解 或称 LR分解）

【定义】Doolittle分解

设 $A\in {\mathbb{C}}^{n\times n}$，若存在一个下三角矩阵 $L$ 和一个上三角矩阵 $R$，使得 $A=LR$，则称 $A=LR$ 为 $A$ 的三角分解

特别的，当 $L$ 为单位（主对角元全为1）下三角矩阵时，称 $A=LR$ 为 $A$ 的 Doolittle 分解

【注】

• 上(下)三角矩阵的逆矩阵是上(下)三角矩阵
• 单位下三角矩阵的逆矩阵是单位下三角矩阵

【定理】Doolittle分解唯一⇔各阶顺序主子式均不为0

设 $A\in {\mathbb{C}}^{n\times n}$，为可逆矩阵，则存在唯一的 Doolittle分解 $⟺$ 各阶顺序主子式均不为0

【定理】若A为正定或负定Hermite矩阵，则A存在唯一的Doolittle分解

【定义】行(列)对角占优矩阵

设 $A\in {\mathbb{C}}^{n\times n}$，若 $A$ 的元满足：
$$|a_{ii}|\ge \sum _{i\ne j}|a_{ij}|,i=1,2,\cdots ,n$$
则称 $A$ 为行对角占优矩阵；

若 $A$ 的元满足：
$$|a_{ii}|>\sum _{i\ne j}|a_{ij}|,i=1,2,\cdots ,n$$
则称 $A$ 为严格行对角占优矩阵；

若 $A^T$ 为(严格)行对角占优矩阵，则称 $A$ 为(严格)列对角占优矩阵

【定理】 (严格)行(列)对角占优矩阵的各阶顺序主子阵也是 (严格)行(列)对角占优矩阵

【定理】严格行(列)对角占优矩阵A是可逆矩阵，且A有唯一的Doolittle分解

【算法】Doolittle分解算法

设 $A\in {\mathbb{C}}^{n\times n}$ 的各阶顺序主子式不为0，$A$ 的 Doolittle分解为 $A=LR$，用 $l_{ij}$ 和 $r_{ij}$ 分别表示矩阵 $L,R$ 的元，由于
$$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]=\left[\begin{array}{cccc}1& & & \\ l_{21}& 1& & \\ ⋮& & \ddots & \\ l_{n1}& \cdots & l_{n,n-1}& 1\end{array}\right]\left[\begin{array}{cccc}{r}_{11}& r_{12}& \cdots & r_{1n}\\ & r_{22}& \cdots & r_{2n}\\ & & \ddots & ⋮\\ & & & r_{nn}\end{array}\right]$$
则 $a_{1j}=r_{1j}$，并且
$$a_{ij}=\{\begin{array}{ll}{\sum }_{t=1}^j{l}_{it}{r}_{tj},& j<i\\ & \\ {\sum }_{t=1}^{i-1}{l}_{it}{r}_{tj}+r_{ij},& j\ge i\end{array}(i=2,3,\cdots ,n)$$
利用上式可以得到如下递归式：
$$r_{ij}=a_{kj}-\sum _{t=1}^{k-1}{l}_{kt}{r}_{tj},j=k,k+1,\cdots ,n$$

$$l_{ik}=\frac{1}{r_{kk}}\left(a_{ik}-\sum _{t=1}^{k-1}{l}_{it}{r}_{tk}\right),i=k+1,\cdots ,n$$

按照上述递归式，可以顺次求出第一行、第一列、第二行、第二列……，直到解出全部的元

例题：

最后将该紧凑形式拆分，得到：
$$A=\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 3& 1& 0\\ 1& 7& 6& 1\end{array}\right]\left[\begin{array}{cccc}1& 2& 3& 4\\ 0& 2& 6& 12\\ 0& 0& 6& 24\\ 0& 0& 0& 24\end{array}\right]$$

二、QR分解（施密特正交化）

【定理】满秩方阵QR分解存在

设 $A\in {\mathbb{R}}^{n\times n}$ 满秩，则存在正交矩阵 $Q$ 和 正线实上三角矩阵 $R$，使得 $A=QR$

【定理】列满秩矩阵QR分解存在

设 $A\in {\mathbb{R}}^{m\times n}$ 列满秩，则有 $A=QR$ ，其中 $Q\in {\mathbb{C}}^{m\times n}$ 列满秩，$Q^{H}Q=E_n$， $R\in {\mathbb{C}}^{n\times n}$ 为正线上三角矩阵

【定理】矩阵的QR分解存在

设 $A\in {\mathbb{C}}^{m\times n}$，rank$A$=$r$，则存在 $B\in {\mathbb{C}}^{m\times r}$，$C\in {\mathbb{C}}^{r\times n}$，rank$B$=rank$C$=$r$，使得 $A=BC$，这里的 $A=BC$ 称为 $A$ 的满秩分解

设 $A\in {\mathbb{C}}^{m\times n}$，rank$A$=$r$，则存在 $Q\in {\mathbb{R}}^{m\times r}$，$C\in {\mathbb{C}}^{r\times n}$，rank$Q$=rank$R$=$r$，$Q^{H}Q=E_r$ 使得 $A=QR$，这里的 $A=QR$ 称为 $A$ 的QR分解

【算法】QR分解算法

先将矩阵进行施密特正交化，过程如图所示，将矩阵的所有列向量化为标准正交基

可以得到
$$A=[{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_n]=[{\eta }_1,{\eta }_2,\cdots ,{\eta }_n]\left[\begin{array}{ccccc}{l}_{11}& l_{21}& \cdots & l_{n1}& \\ 0& l_{22}& \cdots & l_{n2}& \\ ⋮& ⋮& & ⋮& \\ 0& 0& \cdots & l_{nn}& \end{array}\right]=UR$$
其中 $U$ 为酉矩阵，$R$ 为正线上三角矩阵

三、谱分解

【定义】谱分解

$$A=P\Lambda P^{-1}=[{\xi }_1,{\xi }_2,\cdots ,{\xi }_n]\left[\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right]\left[\begin{array}{c}{\eta }_1^T\\ {\eta }_2^T\\ ⋮\\ {\eta }_n^T\end{array}\right]={\lambda }_1{\xi }_1{\eta }_1^T+{\lambda }_2{\xi }_2{\eta }_2^T+\cdots +{\lambda }_n{\xi }_n{\eta }_n^T$$

令 $G_i={\xi }_i{\eta }_i^T$，则 $A=\sum {\lambda }_i{G}_i$ 为矩阵的谱分解

【定理】谱分解唯一性

设 $A\in {\mathbb{C}}^{n\times n}$，$A$ 存在 n 个线性无关的特征向量，${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r$，为 $A$ 的全部相异特征值，则 $A$ 可以进行满足下列性质的谱分解：

• $A={\sum }_{j=1}^r{\lambda }_j{E}_j$
• $E_j^2=E_j$，$(j=1,2,\cdots ,r)$
• $E_i{E}_j=0$，$(i\ne j,i,j=1,2,\cdots ,r)$
• ${\sum }_{j=1}^r{E}_j=E$
• rank$E_j=n_j$，这里 $n_j$ 为 ${\lambda }_j$ 的代数重数

满足上述性质的 $E_j$ 唯一确定

注：$E_i={\xi }_{i1}{\eta }_{i1}^T+{\xi }_{i2}{\eta }_{i2}^T+\cdots +{\xi }_{ir}{\eta }_{ir}^T$

【算法】谱分解算法

求谱分解方法1

求谱分解方法2

四、奇异值分解

【定理】AA^H、A^HA与特征值

设 $A\in {\mathbb{C}}^{m\times n}$，则

1. $rank(A{A}^H)=rank(A^{H}A)=rankA$
2. $A^{H}A$ 与 $A{A}^H$ 均为半正定 Hermite 矩阵
3. $rankA=r$，${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_r$ 为 $A{A}^H$ 的全部正特征值
4. $rankA=r$，${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_r$ 为 $A^{H}A$ 的全部正特征值
5. 3、4 中 ${\lambda }_i={\mu }_i$，$i=1,2,\cdots ,r$。$A{A}^H$ 与 $A^{H}A$ 的正特征值一样，只是 0 特征值的数量不一样

【定义】奇异值

设 $A\in {\mathbb{C}}^{m\times n}$，rank$A=r$，${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r$ 为 $A{A}^H$ 的正特征值

称 ${\sigma }_i={\sqrt{\lambda }}_i$（$i=1,2,\cdots ,r$）为 $A$ 的奇异值

注：

• $A$ 与 $A^H$ 具有相同的奇异值
• 若 $A$ 为 Hermite 矩阵，则 $A$ 的奇异值等于 $A$ 的非零特征值的绝对值

【定义】奇异值分解

设 $A\in {\mathbb{C}}^{m\times n}$，rank$A=r$，${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r$ 为 $A$ 的奇异值，则

存在 m 阶酉矩阵 $U$ 和 n 阶酉矩阵 $V$ 使得：
$$U^{H}AV=D={\left[\begin{array}{cc}\Delta & 0\\ 0& 0\end{array}\right]}_{m\times n}$$
其中 $\Delta =diag({\sigma }_1,{\sigma }_2,\cdots ,{\sigma }_r)$ ，称 $A=U^{H}AV$ 为 $A$ 的奇异值分解

【算法】奇异值分解算法