一揽子矩阵变换

· · 个人记录

Gauss消去与矩阵的LU分解

1. Gauss消元

对于线性方程组 Ax=b ，使用高斯消元求解无疑是基础的。在这里我们不再过多赘述，以下给出一个相关的代码作为参考。

link

2. 矩阵的LU分解

而矩阵的LU分解的思路与Gauss消去的过程极为相似。在这里给出定义：

对于n阶方阵 A ，如果存在n阶单位下三角矩阵 L 和n阶上三角矩阵 U ，使得 A=LU ，则称其为矩阵 A 的LU分解，也称为 Doolittle 分解。

3. 判断LU分解是否存在

对于任意方阵 A ，LU分解不总是存在的。这里给出一个数学上判断矩阵是否能进行LU分解的办法。

如果 A 的各阶顺序主子式 D_k(k=1,2,3,...n-1) 均不为零，则 A 必能够进行LU分解。

更具体地，倘若我们设分解之后 U 矩阵主对角元上的各个元素分别为 a_1,a_2...a_n ，则通过对 L,U 做分块处理的办法，我们可以得到：

a_i=\frac{D_i}{D_{i-1}},i=1,2,3...n-1,D_0=1

那么在这里可以发现，当 D_k(k=1,2,3,...n-1) 均不为零时，a_1,a_2...a_{n-1} 对应地也均不为零。通过Gauss消元的过程大概可以想到，在这样的条件下一定存在一个LU分解。

4. LU分解是唯一的

在接下来的一段中，我们要大概证明：如果矩阵存在LU分解，那么它一定是唯一的。

情况一：|A| \not=0 时，倘若 A 有多个LU分解，那么一定有：

A=L_1U_1=L_2U_2

由于 L、U 均为上/下三角阵，能得到：

L_2^{-1}L_1=U_2U_1^{-1}=I

所以有： L_1=L_2,U_1=U_2

情况二：|A| =0 时,由上述LU分解的存在性可知，A的n-1阶顺序主子式一定行列式不为零，所以对于前n-1阶而言，我们之前讨论出的唯一性仍然成立。于是我们对 A,L,U 分别进行如下的分块。

A= \begin{bmatrix} L_1^* & 0 \\ \alpha^T & 1 \end{bmatrix} \begin{bmatrix} U_1^* & \beta \\ 0 & s \end{bmatrix}

考虑高斯消元的全过程，其中 \alpha,\beta,L_1^*,U_1^* 均是唯一的，而 s=0 也一定成立(等式两端行列式为零)。于是我们得出LU分解是唯一的。

5. 更多的LU分解

如： LDU分解，Crout分解

这样的分解同样满足唯一性，很多性质也和上述的类似。

6. LU分解与高斯消元

二者都是 O(n^3) 量级的复杂度，常数上LU分解会更好。

但LU分解在一些特定情况下会明显更优 (例如系数矩阵A不变而方程等式右边常数向量多次变化的时候，我们只需要对A做一次LU分解进而以O(n^2)的复杂度求解接下来的所有方程)

7. LU分解举例

8. 选定列主元的LU分解

- 关于Cholesky分解

1. 关于正定矩阵

link

在这里，我们主要关注的正定阵性质是：正定阵的所有特征值均为正数。

另外，在实数域的范围里，我们认为正定阵就是对称的(大概)。

2. Cholesky分解

对任意n阶对称正定矩阵 A ，均存在下三角阵 L 使得 A=LL^T 成立，称其为对称正定矩阵 A 的 Cholesky 分解。

接下来我们大概证明一下该定理的正确性：

由于 A 是n阶正定矩阵，则它的各阶顺序主子式均是正的。那么按照LU分解中的结论，存在唯一的单位下三角矩阵 L 、单位上三角矩阵 U 、对角阵 D ， 使得 A=LDU 。 又由于 A=A^T ，我们可以得到：

A=A^T=LDU=(LDU)^T=U^TDL^T

又由LU分解的唯一性，可以得到：

L=U^T U=L^T

于是有：

A=LDL^T

由于 A 是正定的，所以 D 是各对角元均为正数的对角阵，那么对于每个元素做开方操作一定可以得到 D=D_1D_1^T

A=(LD_1)(LD_1)^T

3. Cholesky分解是否唯一

我们知道 LU 分解一定是唯一的，那么对于Cholesky分解而言，只要 D_1 是被规定的，那么 A=LL^T 中的 L 就是确定的。

进一步综合考虑 D=D_1D_1^T 且 D 是各个元素均为正数的对角阵的性质，我们可以知道：当 L 各个对角元的正负被规定之后，L 就是唯一的。

4. Cholesky方法通常是数值稳定的