第2章：线性方程组与矩阵分解

消元与 LU

高斯消元通过行操作把方程组化为三角系统。记录消元乘子得到 LU 分解，再分别前代和回代。对一般稠密 n 阶矩阵，分解成本为 $O(n^3)$ ，每个新右端的三角求解为 $O(n^2)$ 。

因此同一 A 配多个 b 时应复用分解，而不是每次求逆。显式逆矩阵通常增加计算和存储，也不是求解方程组所必需的。

考虑

A=\begin{pmatrix}\epsilon&1\\1&1\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\end{pmatrix},\quad0<\epsilon\ll1.

若直接用 $\epsilon$ 作主元，消元乘子为 $1/\epsilon$ ，中间量放大，随后相减可能严重损失精度。交换两行可使用 1 作主元，避免该问题。

部分主元法每步选择当前列中绝对值较大的元素。它在实践中通常可靠，但稳定界还含增长因子，不能说对所有矩阵都具有不带条件的完美稳定性。

对称正定 A 可分解为 $LL^T$ ，利用对称性减少存储与运算。正定意味着 $x^TAx>0$ 对所有非零 x 成立，不等价于每个元素都为正。

Cholesky 不适用于任意对称不定矩阵。若因舍入或建模使理论正定矩阵失去数值正定性，应检查尺度、数据与算法，不能简单忽略失败。

求出 $\hat x$ 后，检查相对残差 $\|b-A\hat x\|/(\|A\|\|\hat x\|+\|b\|)$ 可提供一种归一化后向误差信息。若还知道条件数，可进一步估计前向准确性。

迭代改进用残差解修正方程 $Ad=r$ ，再更新 $\hat x\leftarrow\hat x+d$ 。高精度残差和适当稳定的原分解可以提高结果，但效果仍受条件数和舍入限制。