Chapter6：Direct Methods for Solving Linear Systems
Target : Solve \(A\vec{x} = \vec{b}\)
6.1 Linear Systems of Equations
最简单的方法：高斯消元法：变成上三角后一个一个解出来。
容易理解，就是一个不断将对应k列消去为0的情况，这个判断\(=0\)用来判断是否是奇异矩阵。总共有\(n-1\)个step。
回代。
如果我们发现了\(a_{ii}^{(i)}=0\)的情况，我们可以进行一个方程行的交换。
然后就是这个令人迷惑的数步数，除法\(n-k\)(就是计算\(m_{ik}\)的那一步)，然后下面的高斯消元，\(a\)是\((n-k)^2\)次，\(b\)是\(n-k\)次，加起来取和是一个\(n^3\)量级。
回代开始是1次，分别计算的是\(n-i+1\)(\(n-i\)次乘法加一次除法)，加起来是\(n^2\)的量级。
6.5 Matrix Factorization
那么我们仿照上面的方式，构造我们的矩阵\(L_n\)系列。
那求逆很舒服了：
\(L\)是一个下三角阵。
那么我们再把消元后得到的一个上三角阵作为\(U\)，我们得到\(A=LU\)，这就是我们的"LU分解"。
这个LU分解的好处在哪？如果直接去解\(A\vec{x}=\vec{b}\)，我们需要解\(n^3\)量级，但是如果我们先解\(Ly=\vec{b}\)，再解\(Ux=y\)，我们只需要解\(2n^2\)即\(n^2\)量级(仅要回代)，这复杂度更低且可以应付不同\(\vec{b}\)的变换(因为是可以所谓提前做好的)，这很舒服了。(高斯消元：六百六十六吃到预制菜了)。
定理：L是唯一的，那么分解是唯一的。
6.6 Special Types of Matrices
-
严格对角占优阵
满足\(|a_{ii}| > \sum_{j\neq i} |a_{ij}|\)
- 非奇异的(即满秩的):反证法
- 高斯消元法不会出现行或列交换
- 舍入误差是稳定的
-
正定
满足矩阵\(A\)为对称的，且对于任意非零向量\(\vec{x}\)，都有\(\vec{x}^TA\vec{x} > 0\)
- \(A^{-1}\)也是正定的(易证)，且\(a_{ii}>0\)(因为这里乘到了\(x^2\))
- max|\(a_{ij}\)| < max|\(a_{kk}\)|，即对角占优，因此(\(a_{ij}^2 < a_{ii}a_{jj}\))
- \(A_k\)的每一个主子式都有正的行列式
对于正定矩阵A的LU分解，我们考虑以下变化过程：
\(U = D\tilde{U}\)
这一转换需要理解\(L = \tilde{U}^T\)(正定矩阵是对称的)，那么\(A = LDL^T\)，这样我们得到了\(\tilde{L} = LD^{\frac{1}{2}}\)即\(A = \tilde{L} \tilde{L}^T\)
-
三对角矩阵(即对角线及其上下两条共三条对角线不为0，其余为0)
注意所说的\(\alpha_i\)为0时无法继续。
定理：如果\(A\)是三对角占优的，且\(|b_1|>|c_1|>0,|b_n|>|a_n|>0\)，\(a_i,c_i\neq 0\)，那么\(A\)是非奇异且可用上述方法解的(即\(\alpha_i \neq 0\))。