LU手算方法#

1. 将矩阵$A$进行高斯消元，得到一个上三角矩阵$U$，消元时$R_i - k R_j$(第$i$行减去第$j$行的$k$倍)的系数$k$就是下三角矩阵$L$中元素$l_{ij}$的值

e.g.:

NOTE

定型文：直接解$Ax = b$和先LU分解再解方程，复杂度都是$O(n^3)$，为什么还要分解？

1. LU分解可以复用：如果要解多个方程$Ax = b_i$，只需要一次LU分解，后续每个方程的求解复杂度是$O(n^2)$，比直接解每个方程的$O(n^3)$更高效
2. 空间复杂度低：LU分解为”原地”操作，可用原A的空间存储L和U
3. 行列式计算简单：$\det(A) = \det(L) \cdot \det(U)$，其中$\det(L) = 1$，所以$\det(A) = \prod_{i=1}^n u_{ii}$，只需要计算上三角矩阵$U$的对角线元素的乘积即可
4. 数值稳定性：LU分解可以通过部分选主元来提高数值稳定性，避免除以小数导致的误差放大
5. 求逆更快

QR手算方法#

1. 使用格拉姆-施密特正交化方法将矩阵$A$的列向量正交化，得到一个正交矩阵$Q$，正交化过程中每个列向量的长度就是上三角矩阵$R$中的元素

e.g.:

先算$\mathbf{q_1}$：

然后算$\mathbf{a_2}$在$\mathbf{q_1}$上的投影：

得垂直向量$\mathbf{v_2}$：

最后算$\mathbf{q_2}$：

得到：

SVD手算#

这你要考手算那我还说啥了，分不要了呗

EVD手算#

1. 计算矩阵$A$的特征值$\lambda$，通过求解特征多项式$\det(A - \lambda I) = 0$得到
2. 对于每个特征值$\lambda$，求解特征向量$\mathbf{v}$，通过求解线性方程组$(A - \lambda I)\mathbf{v} = 0$得到
3. 把特征值摆在$D$的对角线上，把对应的特征向量摆在$P$的列向量上
4. 还要求$P^{-1}$，如果是对称矩阵，特征向量相互正交，$P$是正交矩阵，$P^{-1} = P^T$，否则需要通过其他方法求逆

Cholesky手算#

LU分解升级版

1. 对角线元素：$l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2}$
2. 非对角线元素：$l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk} \right)$，其中$i > j$

e.g.:

先算第一列：

然后算第二列：

最后算第三列：