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}\in\mathbb{R}^{n\times n}$$

Gauss变换

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消元法的基础上的：它在每一次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消元，构建增广矩阵（即将两个矩阵拼起来）。