Ch1 线性方程组的直接解法(Ax=b)
1.1 三角形方程的解法
-
下三角形——前代法
- 因为第一行只有\(a_{11} \neq 0\)，所以先解出\(x_1\)；
- 再将\(x_1\)代入第二行，解出\(x_2\)。重复以上步骤直至解出\(x\)。
- 上三角形——回代法
- 因为最后一行只有\(a_{nn} \neq 0\)，所以先解出\(x_n\)；
- 再将\(x_n\)代入倒数第二行，解出\(x_{n-1}\)。重复以上步骤直至解出\(x\)。
1.2 Gauss变换与Gauss消元法
- Gauss变换的形式
\[
L_k = \begin{bmatrix}
1 & & &\\
& \ddots & &\\
& & 1 &\\
& & -l_{k+1, k}\;\;\;\; 1\\
& & \vdots & \ddots \\
& & -l_{n,k}& & 1
\end{bmatrix}
\]
其实Gauss变换可以看作一个算子，一个特殊的对应的Gauss变换作用于矩阵A，可以将A的第k列转化为\([x_1, x_2, \cdots, x_k, 0, \cdots, 0]^T\).
-
矩阵\(A\)的三角分解：
- 令\(L = (L_{n-1}L_{n-2}\cdots L_1)^{-1}, U = A^{(n-1)}\)，则\(A = LU\)；
- 其中\(L\)是下三角矩阵，\(U\)是上三角矩阵
- 三角分解之后，\(Ax= b \rightarrow LUx=b \rightarrow Ly=b,Ux=y\)
1.3 选主元三角分解
- 全主元消元法
- \(U = L_{n-1}P_{n-1}L_{n-2}P_{n-2} \cdots L_1P_1AQ_1 \cdots Q_{n-1}\)，其中\(P_i, Q_i\)均为置换矩阵，\(L_i\)为Gauss变换。
- 也就是说，从正式开始消元之前，就已经选过一轮全主元了。
- 列主元消元法
- 只在当前主元这一列的下方选，如现在主元是\(a_{kk}\)，那么就是从\(\{a_{ik}: k\leq i \leq n\}\)中选出绝对值最大的一个，然后进行行交换——也就是说，没有全主元方法中的右端的\(Q_i\)了。
- 也是从第一步消元前就先选了一轮了。
选主元消去是完全建立在Gauss消元法的基础上的，它只不过是在每一次消去之后，通过对比主元与其他元间的大小进而交换对应的行与列，来确保A的所有顺序主子式均非零。
1.4 平方根法(Cholesky分解)
- \(Ax=b \rightarrow A=LL^T \rightarrow LL^Tx=b \rightarrow Ly=b,L^Tx=y\)
- 改进的平方根法：\(A = LDL^T\)，不需要开方运算。
1.5 拓展
- 三对角矩阵\(\rightarrow\)带状矩阵
- 追赶法求解三对角矩阵
- Doolittle分解，Courant分解
- 求逆的方法：Gauss-Jordan消元，构建增广矩阵（将两个矩阵拼起来）。