A3-数值线性代数

数值线性代数 #

这讲讲什么：把「解方程、最小二乘、求特征值」从纸上的精确推导，变成机器上真能跑完、并且知道误差有多大的算法。核心工具只有两类：矩阵分解（LU / QR / Cholesky）与迭代法（Jacobi / SOR / 幂法 / 共轭梯度）。
前置：09 讲（矩阵乘法与分块）、10 讲（可逆）、20 讲（特征值与可对角化）、22 讲（内积与范数）、23 讲（Gram–Schmidt）、27 讲（正算子）、29 讲（奇异值与条件数）。A1 篇的高斯消元是本文 LU 一节的前身，读过更顺。
一句话：理论问「解存不存在、唯不唯一」，数值计算问「用有限位浮点数、几步能算到几位有效数字」；后一个问题的答案由两个不同的量决定——矩阵的条件数（问题有多敏感）与算法的稳定性（方法会不会自己放大误差）。

---

一、为什么需要它 #

1.1 同一个方程组，两种算法差 10¹⁰ 年 #

取一个 $25\times25$ 的非奇异方程组 $Ax=b$。Cramer 法则写得漂亮：

$$x_i=\frac{\det A_i}{\det A},\qquad i=1,\dots,n$$

其中 $A_i$ 是把 $A$ 的第 $i$ 列换成 $b$。照定义硬算行列式（完全展开），一共要 $(n-1)(n+1)!$ 次乘法。$n=25$ 时这是

$$24\times 26!\approx 9.7\times10^{27}$$

次乘法。一台每秒 $10^{10}$ 次浮点运算的机器要跑 $3\times10^{10}$ 年——宇宙年龄的两倍多。而同一个方程组，高斯消去法的乘法数是

$$\sum_{i=1}^{n}(i-1)(i+1)=\frac{n(n+1)(2n+1)}{6}-n$$

$n=25$ 时等于 $5500$ 次，不到一秒。

1.2 机器里没有「精确」 #

双精度浮点数用 53 位二进制尾数，机器精度

$$\varepsilon=2^{-53}\approx 1.11\times10^{-16}$$

每一次四则运算的结果都被悄悄乘上一个 $1+\delta$，$|\delta|\le\varepsilon$。由此有三件事必须记住：

1. $1+10^{-17}$ 存不下来，它被存成 $1$。这个「差一点」在后面会要命（见 3.2 节的小主元）。
2. 相近的数相减会吃掉有效位。$1.000000001-1=10^{-9}$，两个 10 位数相减，结果只剩 1 位有效数字。
3. 误差会沿着运算链累积并放大，放大的倍数由矩阵决定，不由你写代码的习惯决定。

1.3 为什么「求逆矩阵」在实践里几乎没人用 #

理论上 $x=A^{-1}b$ 天经地义，$A$ 可逆时这就是唯一解。实践里没人这么干，三条原因，每条都能量化：

（一）求解这一步慢一个 $n$ 倍。 解一个右端项：先花 $O(2n^3/3)$ 做一次 LU 分解，再花 $O(2n^2)$ 前代加回代。求 $A^{-1}$：要么对 $e_1,\dots,e_n$ 解 $n$ 次，总代价约 $2n^3/3+2n^3\approx2.7n^3$；要么按伴随矩阵硬算，更贵。关键差距在三角形那一步：一次解是 $2n^2$，求逆是 $2n^3$，正好差 $n$ 倍。 $n=10^3$ 时前者约 $2\times10^{6}$ 次运算，后者约 $2\times10^{9}$。

真正要紧的不是这点常数：你通常只需要 $A^{-1}b$，不需要 $A^{-1}$。 付了 $n$ 倍的代价，换来一个你根本不会去看的矩阵。

（二）稀疏结构被毁掉。 三对角矩阵的逆通常是稠密的。你手上有一个 $10^6$ 阶、每条对角线都非零的矩阵，存它只要 $3\times10^6$ 个数；存它的逆要 $10^{12}$ 个数，8 TB。

（三）求逆不能改善条件数。 这一点最容易被误解：$\kappa(A^{-1})=\kappa(A)$。病态问题求了逆还是病态，只是多绕一道、多叠一层舍入。

$$\frac{\|b-H\hat x\|_\infty}{\|b\|_\infty}\approx 1.4\times10^{-16},\qquad \frac{\|\hat x-\mathbf{1}\|_\infty}{\|\mathbf 1\|_\infty}\approx 0.70$$

残差小到机器精度，解错了 70%。 残差衡量的是「$\hat x$ 是某个附近方程组的解」，不是「$\hat x$ 接近真解」。两者之间隔着一个 $\kappa(A)$。

1.4 两个必须分开的概念：病态与不稳定 #

这一节最重要的一句话：

概念	属于谁	判据	你能做什么
病态（ill-conditioned）	问题	$\kappa(A)$ 很大	换公式、换模型、加正则化；算法救不了
不稳定（unstable）	算法	误差被算法放大	换算法（例如加主元选取）

一个良态的矩阵可以被一个不稳定的算法算得面目全非——第三节的小主元例子就是：$\kappa_\infty(A)\approx16$，四位有效数字的算术，算出来的解第一位就错了。反过来，Hilbert 矩阵是病态的，换任何算法都救不回来。

---

二、定义与最小例子 #

2.1 范数与条件数 #

向量范数（22 讲）搬到矩阵上，最常用的四个：

$$\|A\|_1=\max_{1\le j\le n}\sum_{i=1}^{n}|a_{ij}|,\qquad \|A\|_\infty=\max_{1\le i\le n}\sum_{j=1}^{n}|a_{ij}|$$

$$\|A\|_2=\sqrt{\lambda_{\max}(A^{\mathsf T}A)},\qquad \|A\|_F=\Big(\sum_{i,j}|a_{ij}|^2\Big)^{1/2}$$

$\|A\|_1$ 是「绝对值最大的列和」，$\|A\|_\infty$ 是「绝对值最大的行和」，这两个能手算。$\|A\|_2$ 就是 29 讲的最大奇异值 $\sigma_{\max}=\sqrt{\lambda_{\max}(A^{\mathsf T}A)}$——注意它既不是最大特征值、也不是谱半径，除非 $A$ 半正定（那时 $\sigma_k=\lambda_k$ 且全非负）。对称只能保证 $|\lambda_k|$ 是奇异值，即 $\|A\|_2=\max|\lambda_k|=\rho(A)$，仍不等于 $\lambda_{\max}$——例如 $A=\operatorname{diag}(1,-3)$：$\|A\|_2=3$，而 $\lambda_{\max}=1$。

条件数定义为

$$\kappa(A)=\|A\|\cdot\|A^{-1}\|$$

它满足 $\kappa(A)\ge 1$（因为 $1=\|I\|=\|AA^{-1}\|\le\|A\|\|A^{-1}\|$）。$\kappa$ 小叫良态，大叫病态。注意 $\kappa$ 依赖你选哪个范数，$\kappa_2$ 与 $\kappa_\infty$ 可以差几倍，但「大不大」的结论通常一致。

条件数管什么？两个基本不等式：

$$\frac{\|x-\hat x\|}{\|x\|}\le \kappa(A)\,\frac{\|b-\hat b\|}{\|b\|}$$

右端项的相对扰动被放大最多 $\kappa$ 倍。若连 $A$ 本身有扰动 $E$，则

$$\frac{\|x-\hat x\|}{\|x\|}\le \frac{\kappa(A)}{1-\kappa(A)\|E\|/\|A\|}\left(\frac{\|E\|}{\|A\|}+\frac{\|\delta b\|}{\|b\|}\right)$$

这就是「有效数字会掉几位」的定量版本：$\kappa\approx10^k$ 意味着大约损失 $k$ 位十进制有效数字。 双精度有 16 位，所以 $\kappa\approx10^{16}$ 的矩阵在双精度下一位都不对（1.3 节的 Hilbert 例子正是如此）。

2.2 三种三角分解 #

LU 分解：把 $A$ 拆成一个单位下三角 $L$ 与一个上三角 $U$，

$$A=LU$$

于是 $Ax=b$ 变成两步三角形方程组：$Ly=b$（前代，$O(n^2)$）与 $Ux=y$（回代，$O(n^2)$）。

带主元的 LU：一般矩阵不保证 $A=LU$ 存在（某个顺序主子式为零就卡住）。引进置换矩阵 $P$（单位矩阵换行得到的矩阵，满足 $P^{-1}=P^{\mathsf T}$、$\det P=\pm1$），写成

$$PA=LU$$

$P$ 的作用是把「绝对值最大的元素」换到当前主元位置。部分主元（partial pivoting）只在当前列里挑最大；全主元（complete pivoting）在整个右下子块里挑最大，更稳但比较本身就要 $O(n^3)$，代价太高，实践中几乎只用部分主元。

Cholesky 分解：$A$ 对称正定时（27 讲），存在对角元为正的下三角 $L$ 使

$$A=LL^{\mathsf T}$$

它不需要选主元：Cholesky 只做「开平方 + 除法」，永远不构造需要互相比较的乘数，所以没有「小主元」这回事；而正定性保证每一步开方的数都为正，计算不会中断。乘法的另一半优势在运算量（见 3.4 节的对比）。

QR 分解：$A=QR$，$Q$ 正交（$Q^{\mathsf T}Q=I$），$R$ 上三角。$m\ge n$ 时写成 $A=Q\begin{pmatrix}R\\0\end{pmatrix}$。它的价值在于正交变换不改变 2 范数：$\|Ax-b\|_2=\|QRx-b\|_2=\|Rx-Q^{\mathsf T}b\|_2$，于是最小二乘问题（24 讲）直接化成解一个上三角方程组 $Rx=c_1$。

2.3 两种造 $Q$ 的办法 #

Householder 变换：取单位向量 $w$，令

$$H=I-2ww^{\mathsf T}$$

$H$ 对称、正交、$H^2=I$，几何上是「关于过原点且垂直于 $w$ 的平面的镜面反射」。给定 $x\ne0$，取

$$v=x+\operatorname{sign}(x_1)\|x\|_2e_1,\qquad H=I-\frac{2}{v^{\mathsf T}v}vv^{\mathsf T}$$

就有 $Hx=-\operatorname{sign}(x_1)\|x\|_2e_1$：一次反射把 $x$ 的后面所有分量清零。用 $n$ 次反射就把 $A$ 打成上三角。

Givens 旋转：只在第 $i,k$ 两个坐标上转一下，

$$G(i,k,\theta)=\begin{pmatrix}1&&&&\\&c&&s&\\&&\ddots&&\\&-s&&c&\\&&&&1\end{pmatrix},\qquad c^2+s^2=1$$

取 $c=x_i/\sqrt{x_i^2+x_k^2}$、$s=x_k/\sqrt{x_i^2+x_k^2}$，就只把 $x_k$ 一个分量清零。一次只杀一个元素，比 Householder 慢，但对带状、稀疏矩阵可以只转需要的地方，反而省。

2.4 迭代法的统一写法 #

把 $A$ 拆成 $A=D-L-U$（$D$ 是对角部分，$L,U$ 分别是严格下、上三角部分的相反数），任何定常迭代都写成

$$x_{k+1}=Bx_k+g$$

误差满足 $x-x_{k+1}=B(x-x_k)$，于是 $x-x_k=B^k(x-x_0)$。收敛 ⟺ $B^k\to0$ ⟺ 谱半径 $\rho(B)<1$。三种经典取法：

方法	迭代矩阵 $B$	一句话
Jacobi	$B_J=D^{-1}(L+U)$	全用旧值算新分量
Gauss–Seidel	$B_{GS}=(D-L)^{-1}U$	新算出的分量立刻用上
SOR	$L_\omega=(D-\omega L)^{-1}\big((1-\omega)D+\omega U\big)$	在旧值与 GS 值之间取加权平均，$\omega\in(0,2)$

$\omega=1$ 就是 GS，$\omega>1$ 叫超松弛（加速），$\omega<1$ 叫低松弛。$\omega\notin(0,2)$ 时必然发散，因为 $\det L_\omega=(1-\omega)^n$ 给出 $\rho(L_\omega)\ge|1-\omega|\ge1$。

2.5 一个贯穿全篇的矩阵 #

后面所有分解、所有迭代，都拿同一个矩阵算，你才能看出不同工具的视角差别。取

$$A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$$

它是一维 Poisson 矩阵：把 $u''=f$ 在等距网格上用二阶差分离散，就得到它（乘以 $-1/h^2$）。化学里的扩散方程、材料的稳态热传导，离散后都是它的高维推广。

先确认它是对称正定的，用手算顺序主子式：$2>0$，$\det\begin{pmatrix}2&-1\\-1&2\end{pmatrix}=3>0$，$\det A=4>0$。三个全正，由 27 讲的判据，$A$ 正定。

它的特征值有闭式：

$$\lambda_k=2-2\cos\frac{k\pi}{4},\qquad k=1,2,3\quad\Longrightarrow\quad \lambda=2-\sqrt2,\ 2,\ 2+\sqrt2$$

即约 $0.5858,\ 2,\ 3.4142$。于是

$$\kappa_2(A)=\frac{2+\sqrt2}{2-\sqrt2}=3+2\sqrt2\approx5.83$$

而 $\|A\|_\infty=4$，$\|A^{-1}\|_\infty=2$，所以 $\kappa_\infty(A)=8$。两个都是精确值，后面拿来对账。

它的逆也干净：

$$A^{-1}=\frac14\begin{pmatrix}3&2&1\\2&4&2\\1&2&3\end{pmatrix}$$

---

三、几个必须自己算一遍的结论 #

3.1 LU 手算：Doolittle 一遍到底 #

Doolittle 的规矩是「$L$ 对角元取 $1$」。按列推进，第 $k$ 步用 $U$ 的第 $k$ 行去消 $A$ 下面各行。

第一步，$u_{11}=a_{11}=2$，$u_{12}=-1$，$u_{13}=0$；乘数 $l_{21}=a_{21}/u_{11}=-1/2$，$l_{31}=0$。

第二步，把第 $1$ 行乘 $-1/2$ 加到第 $2$ 行：新 $(2,2)$ 元 $=2-\frac12= \frac32$，新 $(2,3)$ 元 $=-1-0=-1$。故 $u_{22}=\frac32$，$u_{23}=-1$，$l_{32}=a^{(1)}_{32}/u_{22}=(-1)/(\frac32)=-\frac23$。

第三步，$u_{33}=2-\big(-\frac23\big)(-1)=2-\frac23=\frac43$。

于是

$$L=\begin{pmatrix}1&0&0\\-\tfrac12&1&0\\0&-\tfrac23&1\end{pmatrix},\qquad U=\begin{pmatrix}2&-1&0\\0&\tfrac32&-1\\0&0&\tfrac43\end{pmatrix}$$

乘回去验一遍：$(2,2)$ 元 $=(-\frac12)(-1)+\frac32=2$ ✓，$(3,3)$ 元 $=(-\frac23)(-1)+\frac43=2$ ✓。主元是 $2,\ \frac32,\ \frac43$，全为正。

解 $Ax=b$，取 $b=(1,0,1)^{\mathsf T}$（正好是 $A\mathbf 1$，所以真解是 $\mathbf 1$）。前代 $Ly=b$：

$$y_1=1,\qquad y_2=0-\Big(-\tfrac12\Big)(1)=\tfrac12,\qquad y_3=1-\Big(-\tfrac23\Big)\Big(\tfrac12\Big)=\tfrac43$$

回代 $Ux=y$：$x_3=\frac{4/3}{4/3}=1$，$x_2=\frac{\frac12+1}{\frac32}=1$，$x_1=\frac{1+1}{2}=1$。✓

3.2 小主元为什么必须换行（一个四位算术的完整验算） #

这是全篇最该亲手算一遍的例子。取

$$A=\begin{pmatrix}10^{-5}&1\\1&3\end{pmatrix},\qquad b=\begin{pmatrix}2\\7\end{pmatrix}$$

先看它有多良态：$\|A\|_\infty=4$，而

$$A^{-1}=\frac{1}{3\cdot10^{-5}-1}\begin{pmatrix}3&-1\\-1&10^{-5}\end{pmatrix}$$

其行和最大是 $\frac{4}{0.99997}\approx4.0001$，故 $\kappa_\infty(A)\approx16.0005$。这是相当好的矩阵——$\kappa\varepsilon$ 只有 $10^{-15}$ 量级，双精度下能保住十几位有效数字。

精确解是

$$x_1=\frac{2\cdot3-1\cdot7}{10^{-5}\cdot3-1}=\frac{-1}{-0.99997}=1.00003\ldots,\qquad x_2=2-10^{-5}x_1=1.99999\ldots$$

不换行，用四位十进制浮点：

• 乘数 $m=a_{21}/a_{11}=1/10^{-5}=10^{5}$（四位正好存下）
• $u_{22}=3-10^{5}\cdot1=3-100000=-99997\ \longrightarrow\ -1.000\times10^{5}$
• $y_2=7-10^{5}\cdot2=-199993\ \longrightarrow\ -2.000\times10^{5}$
• $x_2=(-2.000\times10^{5})/(-1.000\times10^{5})=2.000$
• $x_1=(2-1\cdot2.000)/10^{-5}=0$

得到 $x\approx(0,\ 2.000)$。真解 $x_1=1.00003$，相对误差 100%。

换行之后（交换两行，$b$ 也换）：

$$A'=\begin{pmatrix}1&3\\10^{-5}&1\end{pmatrix},\qquad b'=\begin{pmatrix}7\\2\end{pmatrix}$$

• $m=10^{-5}/1=10^{-5}$
• $u_{22}=1-10^{-5}\cdot3=0.99997\ \longrightarrow\ 1.000$
• $y_2=2-10^{-5}\cdot7=1.99993\ \longrightarrow\ 2.000$
• $x_2=2.000/1.000=2.000$，$x_1=(7-3\cdot2.000)/1=1.000$

得到 $(1.000,\ 2.000)$，四位全对。

一般结论：带部分主元的 LU 对任何非奇异 $A$ 都能进行到底，得到 $PA=LU$。代价只是选主元时多 $O(n^2)$ 次比较。

3.3 QR：Gram–Schmidt 与 Householder 的差别在哪 #

对 2.5 节的 $A$ 走一遍古典 Gram–Schmidt（23 讲的算法，作用在列向量上）。

$r_{11}=\|a_1\|=\sqrt{2^2+(-1)^2}=\sqrt5$，$q_1=\frac{1}{\sqrt5}(2,-1,0)^{\mathsf T}$。

$r_{12}=q_1^{\mathsf T}a_2=\frac{1}{\sqrt5}(2\cdot(-1)+(-1)\cdot2)=-\frac{4}{\sqrt5}$，

$$v_2=a_2-r_{12}q_1=\begin{pmatrix}-1\\2\\-1\end{pmatrix}+\frac45\begin{pmatrix}2\\-1\\0\end{pmatrix}=\begin{pmatrix}3/5\\6/5\\-1\end{pmatrix}$$

$r_{22}=\|v_2\|=\sqrt{\frac{9+36}{25}+1}=\frac{\sqrt{70}}{5}$，$q_2=\frac{1}{\sqrt{70}}(3,6,-5)^{\mathsf T}$。

$r_{13}=q_1^{\mathsf T}a_3=\frac{1}{\sqrt5}$，$r_{23}=q_2^{\mathsf T}a_3=-\frac{16}{\sqrt{70}}$，于是

$$v_3=a_3-r_{13}q_1-r_{23}q_2=\Big(\tfrac27,\tfrac47,\tfrac67\Big),\qquad r_{33}=\frac{\sqrt{56}}{7}$$

结果（检算：$R$ 对角元之积 $=\sqrt5\cdot\frac{\sqrt{70}}{5}\cdot\frac{\sqrt{56}}{7}=\sqrt{16}=4=\det A$ ✓）

$$R=\begin{pmatrix}\sqrt5&-\frac{4}{\sqrt5}&\frac{1}{\sqrt5}\\[2pt]0&\frac{\sqrt{70}}{5}&-\frac{16}{\sqrt{70}}\\[2pt]0&0&\frac{\sqrt{56}}{7}\end{pmatrix},\qquad Q=\begin{pmatrix}\frac{2}{\sqrt5}&\frac{3}{\sqrt{70}}&\frac{1}{\sqrt{14}}\\[2pt]-\frac{1}{\sqrt5}&\frac{6}{\sqrt{70}}&\frac{2}{\sqrt{14}}\\[2pt]0&-\frac{5}{\sqrt{70}}&\frac{3}{\sqrt{14}}\end{pmatrix}$$

检查一下：$R$ 的对角元平方是 $5,\ \frac{14}{5},\ \frac87$。这不是巧合——由 $A^{\mathsf T}A=R^{\mathsf T}Q^{\mathsf T}QR=R^{\mathsf T}R$（正交矩阵 $Q^{\mathsf T}Q=I$），$R^{\mathsf T}$ 正是 $A^{\mathsf T}A$ 的 Cholesky 因子（把 $R$ 的对角元取正号后逐个比对，二者完全相同）。

为什么 Householder 更稳？ 关键不在「公式更复杂」，而在误差的传播方式：

• Gram–Schmidt 算 $q_j$ 时，是把已经算出的 $\hat q_1,\dots,\hat q_{j-1}$ 拿来减。这些 $\hat q_i$ 本身已经带误差，而且它们不严格正交。第 $j$ 步的误差里有一份正比于 $\kappa(A)^2$ 的项——条件数被平方了。
• Householder 从不显式造 $Q$：它对 $A$ 连续左乘正交矩阵，每步只算 $v$ 与 $\beta=2/v^{\mathsf T}v$。正交矩阵在 2 范数下保距（$\|HA\|_2=\|A\|_2$），误差不会被放大，总误差只正比于 $\kappa(A)$。

用 Läuchli 矩阵 $A=\begin{pmatrix}1&1&1\\ \epsilon&0&0\\0&\epsilon&0\\0&0&\epsilon\end{pmatrix}$ 实测（$\epsilon=10^{-8}$，$\kappa_2(A)\approx1.7\times10^{8}$），比较算出的 $Q$ 有多正交：

算法	$\|Q^{\mathsf T}Q-I\|_{\max}$
古典 Gram–Schmidt	$5.0\times10^{-1}$
修正 Gram–Schmidt（逐个减）	$7.1\times10^{-9}$
Householder	$1.1\times10^{-15}$

古典 GS 的 $Q$ 已经完全不正交（误差 $0.5$），Householder 稳在机器精度。这就是「$\kappa$ 被平方」的具体样子。

Givens 什么时候赢？ 对 2.5 节的 $A$，要清掉 $a_{21}=-1$：取 $c=2/\sqrt5$、$s=-1/\sqrt5$，旋转后第一行变成 $(\sqrt5,\ -4/\sqrt5,\ 1/\sqrt5)$——和上面 $R$ 的第一行一模一样。但 Givens 每次只动两行，做完整三角化要 $\sim n^2/2$ 次旋转；Householder 只要 $n$ 次反射。所以稠密矩阵用 Householder，带状或只需要局部清零（比如把某个元素单独打掉）时才用 Givens。

3.4 Cholesky：为什么它比 LU 便宜一半，而且不用选主元 #

对 2.5 节的 $A$ 逐元比较 $A=LL^{\mathsf T}$。记 $L=(l_{ij})$ 下三角。

$(1,1)$：$l_{11}^2=2\Rightarrow l_{11}=\sqrt2$。
$(2,1)$：$l_{21}l_{11}=-1\Rightarrow l_{21}=-1/\sqrt2$。
$(2,2)$：$l_{21}^2+l_{22}^2=2\Rightarrow l_{22}=\sqrt{2-\frac12}=\sqrt{3/2}$。
$(3,2)$：$l_{31}l_{21}+l_{32}l_{22}=-1$，而 $l_{31}=0$，故 $l_{32}=-1/\sqrt{3/2}=-\sqrt{2/3}$。
$(3,3)$：$l_{32}^2+l_{33}^2=2\Rightarrow l_{33}=\sqrt{2-\frac23}=\frac{2}{\sqrt3}$。

$$L=\begin{pmatrix}\sqrt2&0&0\\-\frac{1}{\sqrt2}&\sqrt{\frac32}&0\\0&-\sqrt{\frac23}&\frac{2}{\sqrt3}\end{pmatrix}$$

把它的对角元平方，和 3.1 节的 LU 主元逐个对照：

$$\underbrace{2,\ \tfrac32,\ \tfrac43}_{\text{LU 主元}}\qquad\Longleftrightarrow\qquad\underbrace{2,\ \tfrac32,\ \tfrac43}_{l_{11}^2,\ l_{22}^2,\ l_{33}^2}$$

完全一致。 这不是巧合：Cholesky 就是「$LDL^{\mathsf T}$ 分解里把对角元开方塞进 $L$」，而 $LDL^{\mathsf T}$ 的 $D$ 正是 LU 的主元。$A$ 正定时每个主元恒正，开方永远合法——所以不需要选主元。

代价对比：LU 约 $\frac23n^3$ 次乘法，Cholesky 约 $\frac13n^3$，省一半，还省一半存储（只存一个三角）。

3.5 条件数：两个具体矩阵，一个良态一个病态 #

良态的那一个。 2.5 节的 $A$ 有 $\kappa_2=3+2\sqrt2\approx5.83$。这个数很实在：右端项相对扰动 $10^{-3}$，解的相对误差不超过 $5.83\times10^{-3}$——大约掉半位有效数字。

病态的那一个：Hilbert 矩阵。 $H_n=\big(\frac{1}{i+j-1}\big)$，经典病态样本：

$n$	3	6	9	12
$\kappa_2(H_n)$	$5.2\times10^{2}$	$1.5\times10^{7}$	$4.9\times10^{11}$	$1.8\times10^{16}$

$n=12$ 时 $\kappa\cdot\varepsilon\approx1.8\times10^{16}\times1.1\times10^{-16}\approx2>1$。双精度下一位有效数字都不剩——这就是 1.3 节那个「残差 $10^{-16}$、误差 $0.70$」的来源。

拿 $3\times3$ 做一次能手算的放大实验。$H_3=\begin{pmatrix}1&\frac12&\frac13\\ \frac12&\frac13&\frac14\\ \frac13&\frac14&\frac15\end{pmatrix}$，$\kappa_2(H_3)\approx524$，$\kappa_\infty(H_3)=748$。取 $x=\mathbf 1$，$b=H_3\mathbf 1=\big(\frac{11}{6},\frac{13}{12},\frac{47}{60}\big)$。把 $b_1$ 改动 $1\%$：

$$\frac{\|\delta b\|_\infty}{\|b\|_\infty}=0.01\qquad\Longrightarrow\qquad \frac{\|\delta x\|_\infty}{\|x\|_\infty}=0.66$$

输入动 $1\%$，输出动 $66\%$，放大约 $66$ 倍。 这个 66 落在 $\kappa$ 的界内（$\kappa_\infty=748$ 是上界，不是等号），方向完全正确。手算可以验：$\hat x=(1.165,\ 0.34,\ 1.55)$。

3.6 迭代法：三种方法的谱半径，一次算清 #

对 2.5 节的 $A=D-L-U$，$D=2I$，

$$B_J=D^{-1}(L+U)=\begin{pmatrix}0&\frac12&0\\ \frac12&0&\frac12\\ 0&\frac12&0\end{pmatrix}$$

它的特征多项式由三对角行列式直接展开：$B_J$ 的第一、三行只有第 2 个位置非零，故

$$\det(\lambda I-B_J)=\lambda\cdot\lambda\cdot\lambda-\lambda\Big(\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12\Big)=\lambda^3-\tfrac12\lambda=\lambda\Big(\lambda^2-\tfrac12\Big)$$

（消去法是：第一行与第三行的非零元只通过中间行耦合，两项 $\frac14+\frac14$ 就是走「上行—中行—下行」这两条路径的贡献。）于是

$$\rho(B_J)=\frac{1}{\sqrt2}=\frac{\sqrt2}{2}\approx0.7071$$

Gauss–Seidel 的迭代矩阵是

$$B_{GS}=(D-L)^{-1}U=\begin{pmatrix}\frac12&0&0\\[2pt]\frac14&\frac12&0\\[2pt]\frac18&\frac14&\frac12\end{pmatrix}\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}=\begin{pmatrix}0&\frac12&0\\[2pt]0&\frac14&\frac12\\[2pt]0&\frac18&\frac14\end{pmatrix}$$

其特征多项式是 $\lambda^2\big(\lambda-\frac12\big)$（直接展开可得，也可由 $B_{GS}$ 秩为 $2$ 预判至少有一个零特征值），于是 $\rho(B_{GS})=\frac12$。这个结果不用硬算也能预判：$A$ 是三对角的，具有「性质 A」（存在置换把它化成分块二循环形式 $PAP^{\mathsf T}=\begin{pmatrix}D_{11}&M_{12}\\M_{21}&D_{22}\end{pmatrix}$，其中 $D_{11},D_{22}$ 是对角块、$M_{12},M_{21}$ 一般非零——注意这不是分块对角），而相容次序保证

$$\rho(B_{GS})=\rho(B_J)^2=\Big(\frac{1}{\sqrt2}\Big)^2=\frac12$$

GS 的收敛因子正好是 Jacobi 的平方——每步 GS 相当于走了两步 Jacobi，因为新算出的分量立刻被下游用了。

SOR 的最优松弛因子（同样由相容次序理论给出，$\mu=\rho(B_J)$）

$$\omega_{\text{opt}}=\frac{2}{1+\sqrt{1-\mu^2}}=\frac{2}{1+\frac{1}{\sqrt2}}\approx1.1716,\qquad \rho(L_{\omega_{\text{opt}}})=\omega_{\text{opt}}-1\approx0.1716$$

三个数放在一起看：$0.7071\to0.5\to0.1716$。要把误差压到 $10^{-6}$，大致需要 $\ln(10^{-6})/\ln\rho$ 步：

方法	$\rho$	约需步数（误差 $10^{-6}$）
Jacobi	$0.7071$	$40$
Gauss–Seidel	$0.5$	$20$
SOR（$\omega=1.1716$）	$0.1716$	$8$

SOR 用对了 $\omega$，比 Jacobi 快 5 倍。

收敛的充分条件（不用算谱半径就能用的判据）：

• 严格对角占优（$|a_{ii}|>\sum_{j\ne i}|a_{ij}|$ 对每行成立）⟹ Jacobi 与 GS 都收敛，因为 $\|B_J\|_\infty<1$。
• 不可约 + 弱对角占优（允许等号，但至少一处严格）⟹ 也收敛。注意：此时不能推出 $\rho(B_{GS})<\rho(B_J)$；要得到这条比较，还需要 $a_{ij}\le0\ (i\ne j)$（即 $A$ 是 M-矩阵，Stein–Rosenberg 定理）。缺这个前提有反例：$A=\begin{pmatrix}8&3&-3\\2&6&3\\-2&-3&6\end{pmatrix}$ 三行都严格对角占优，$B_J$ 幂零故 $\rho(B_J)=0$，而 $\rho(B_{GS})\approx0.283>\rho(B_J)$。所以「GS 比 Jacobi 快」不是普遍结论。
• $A$ 对称正定 ⟹ GS 一定收敛；SOR 对一切 $\omega\in(0,2)$ 收敛。

注意 2.5 节的 $A$ 只是弱对角占优（中间行 $2=1+1$），严格判据用不上，但它不可约，所以仍然收敛——这解释了为什么它是个好例子而不是反例。

3.7 幂法与反幂法：收敛速度是可以算出来的 #

幂法的迭代格式是：取 $\|u_0\|_\infty=1$，反复做

$$y_k=Au_{k-1},\qquad \mu_k=\text{$y_k$ 中绝对值最大的分量},\qquad u_k=y_k/\mu_k$$

理由很直白：若 $A$ 可对角化、$|\lambda_1|>|\lambda_2|\ge\cdots$，把 $u_0=\sum\alpha_jx_j$ 展开，

$$A^ku_0=\lambda_1^k\Big(\alpha_1x_1+\sum_{j\ge2}\alpha_j\Big(\frac{\lambda_j}{\lambda_1}\Big)^kx_j\Big)$$

括号里第二项按 $|\lambda_2/\lambda_1|^k$ 衰减，所以方向收敛到 $x_1$，$\mu_k\to\lambda_1$。收敛速度就是 $|\lambda_2/\lambda_1|$。

对 2.5 节的 $A$，$\lambda_1=2+\sqrt2$、$\lambda_2=2$，故理论上

$$\Big|\frac{\lambda_2}{\lambda_1}\Big|=\frac{2}{2+\sqrt2}=2-\sqrt2\approx0.5858$$

取 $u_0=(1,1,1)^{\mathsf T}$，手算前几步（$\mu_k$ 是 $y_k$ 绝对值最大的分量，会带符号）：

$k$	1	2	3	4	5	6	7
$\mu_k$	$1$	$2$	$-4$	$3.5$	$3.4286$	$3.4167$	$3.4146$

趋向 $3.4142$。要误差到 $10^{-6}$，按理论比值需 $\ln(10^{-6})/\ln(0.5858)\approx26$ 步。

$$\frac{\lambda_3}{\lambda_1}=\frac{2-\sqrt2}{2+\sqrt2}=(\sqrt2-1)^2\approx0.1716$$

接管。（$\lambda_3=2-\sqrt2$ 对应的是两端同号的「慢变」模态，$\lambda_1$ 对应正负交替的「快变」模态。）

这是特例，不是普遍规律。把同一个谱换一个朝向（例如取 $A=Q\Lambda Q^{\mathsf T}$、$Q$ 是一个随机的正交矩阵），$\alpha_2\ne0$，实测比值立刻回到 $0.5858$。所以：
理论界 $|\lambda_2/\lambda_1|$ 是「最坏情况」，实际速度取决于初值在各特征方向上的投影。 幂法的收敛速度不能只看矩阵，还要看初值。
若把比值真的做成 $0.99$（两个特征值几乎一样大），则需要约 $\ln(10^{-6})/\ln(0.99)\approx1375$ 步——这才是幂法「慢」的定量含义。

反幂法：对 $A^{-1}$ 用幂法，收敛到 $|\lambda|$ 最小的特征值，速度由 $|\lambda_n/\lambda_{n-1}|$ 决定。每步要解 $Ay=z$，但 LU 只分解一次，之后每步两个三角形方程组，$O(n^2)$。

带位移的反幂法：对 $A-\mu I$ 用反幂法。若 $\mu$ 接近某个特征值 $\lambda_i$，则

$$\frac{|\lambda_i-\mu|}{|\lambda_j-\mu|}\ \text{极小}\quad\Longrightarrow\quad\text{一两步就收敛}$$

代价是 $A-\mu I$ 接近奇异，每步解的是病态方程组——但病态不影响特征向量的收敛，这是反幂法最反直觉、也最有用的一条性质。

3.8 Krylov 子空间：为什么大规模稀疏问题必须用迭代法 #

直接法在大矩阵上会撞两堵墙。

第一堵是运算量。LU 是 $O(n^3)$。$n=10^6$ 时 $2n^3/3\approx6.7\times10^{17}$ 次乘法，按每秒 $10^{10}$ 次算要两年多。

第二堵更致命：稀疏性会在消元中丢失（fill-in）。用二维 Laplacian（$N\times N$ 网格，$n=N^2$）实测非零元个数：

网格 $N$	$n=N^2$	$A$ 的非零元	LU 因子的非零元	倍数
4	16	64	118	1.8×
8	64	288	974	3.4×
12	144	672	3334	5.0×

非零元随 $N$ 稳定增长，倍数一路往上。$N=1000$（$n=10^6$）时，即使用带宽优化，分解也要约 $2\times10^{12}$ 次运算、存 $10^9$ 个双精度数——8 GB 只为了存因子。

迭代法只做一件事：矩阵乘向量。 每步 $O(\text{nnz}(A))$，稀疏时是 $O(n)$。它从不修改 $A$，所以稀疏性永远不会丢。

共轭梯度（CG） 用在对称正定情形。它不是「沿负梯度走」（那是最速下降，很慢），而是让每一步的搜索方向关于 $A$ 共轭（$p_i^{\mathsf T}Ap_j=0$，$i\ne j$），从而每一步都在一个新的维度上取到最优。迭代格式：

$$\alpha_k=\frac{r_k^{\mathsf T}r_k}{p_k^{\mathsf T}Ap_k},\quad x_{k+1}=x_k+\alpha_kp_k,\quad r_{k+1}=r_k-\alpha_kAp_k,\quad \beta_k=\frac{r_{k+1}^{\mathsf T}r_{k+1}}{r_k^{\mathsf T}r_k},\quad p_{k+1}=r_{k+1}+\beta_kp_k$$

三个性质必须记住：

1. 理论上 $n$ 步必到精确解（Krylov 子空间维数不超过 $n$）。所以 CG 严格说是直接法。
2. 实际上把它当迭代法用，残差小于阈值就停，通常远早于 $n$ 步。
3. 误差界是

$$\|x_k-x^*\|_A\le 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\|x_0-x^*\|_A$$

其中 $\|v\|_A=\sqrt{v^{\mathsf T}Av}$。收敛速度只由 $\sqrt\kappa$ 决定——这是 CG 相对别的迭代法最大的优势：条件数被开了一次方。

对 2.5 节的 $A$，$\kappa=3+2\sqrt2$，$\sqrt\kappa=1+\sqrt2$，于是

$$\frac{\sqrt\kappa-1}{\sqrt\kappa+1}=\frac{\sqrt2}{2+\sqrt2}=\sqrt2-1\approx0.4142$$

界说每步误差缩到 $0.4142$ 倍。实测更快：取 $b=A\mathbf 1=(1,0,1)^{\mathsf T}$，CG 两步就到精确解（残差历史 $1.41\to1.00\to0$）。界是悲观的，这很正常——它只用了 $\kappa$ 一个数，丢掉了谱分布的全部信息。

GMRES 处理非对称情形。它不做「误差在 $A$ 范数下最小」，而做残差最小：

$$x_k=\arg\min_{x\in x_0+\mathcal K_k(A,r_0)}\|b-Ax\|_2,\qquad \mathcal K_k=\operatorname{span}\{r_0,Ar_0,\dots,A^{k-1}r_0\}$$

同样 $n$ 步必到精确解（用 Cayley–Hamilton：特征多项式给出一个零化多项式）。实践中靠 Arnoldi 过程逐步构造正交基，每步存一个向量，存储随步数线性增长，所以要「重启」（每 $m$ 步清空重来）。

代价对比一句话：CG 每步一个矩阵乘向量 + 常数存储；GMRES 每步一个矩阵乘向量 + 一步正交化 + 线性增长的存储。 能用 CG 就别用 GMRES。

---

四、几何直观 / 记忆钩子 #

四种分解，四个动作 #

分解	几何动作	一句话记忆
$A=LU$	把「消元的账本」留下来	L 记账，U 是结果
$PA=LU$	消元前先「挑个大的站台」	先换行，再开算
$A=QR$	把列向量一支一支掰成互相垂直	正交化 = 换一组直角坐标
$A=LL^{\mathsf T}$	对称正定时，掰一次就够（另一半自动对称）	开方版的 LU，省一半

三个镜像式的对照 #

• Householder = 照镜子：一次反射把整列后面全打成零。Givens = 拧螺丝：一次只转掉一个元素。前者大刀阔斧，后者精雕细刻。
• 条件数 = 椭圆的轴比（29 讲）：球被压成扁椭圆，$\kappa=\sigma_{\max}/\sigma_{\min}$ 就是长轴比短轴。椭圆越扁，反解时短轴方向被放大得越狠。
• 谱半径 = 每步误差的缩小比例：$\rho=0.9$ 意味着每步只掉一成，要掉到 $10^{-6}$ 得 $130$ 步；$\rho=0.17$ 只要 $8$ 步。迭代法的全部性能都在这个数里。

一句口诀 #

分解看结构（对称正定用 Cholesky，一般方阵用 LU，最小二乘用 QR），
求解看规模（小稠密直接法，大稀疏迭代法），
信不信看条件数（$\kappa\varepsilon$ 就是你能信几位）。

幂法为什么「自然会」收敛 #

把 $A$ 想成一台「按方向拉伸」的机器，拉伸倍数就是特征值。反复作用，倍数最大的那个方向每次都赢一点点，比值 $|\lambda_2/\lambda_1|$ 就是「赢的速率」。所以幂法的速度不是技巧问题，是谱的分布问题：想让幂法快，就得让 $\lambda_1$ 与 $\lambda_2$ 拉开距离——这正是「位移」技巧的出发点（把谱整体平移，人为造出差距）。

---

五、常见误区 #

---

六、拓展（可选，可跳过） #

6.1 预处理：把条件数压下去 #

迭代法的步数由 $\kappa$ 决定，那就想办法把 $\kappa$ 变小。做法是解等价的

$$M^{-1}Ax=M^{-1}b$$

其中 $M$ 是 $A$ 的一个「好求逆的近似」。理想情形 $\kappa(M^{-1}A)\ll\kappa(A)$。常见选择：对角预处理（$M=\operatorname{diag}A$，几乎免费）、不完全 Cholesky（$A\approx\tilde L\tilde L^{\mathsf T}$，故意把 fill-in 丢掉）、以及针对具体结构的块预处理。3.8 节末尾那句「网格加密一倍步数翻倍」，正是靠预处理才被消掉的。

6.2 稀疏直接法不是不存在 #

「大规模必须用迭代」是粗略说法。带带宽优化的直接法（只在对角带内消元）对带状矩阵非常有效：$n=10^6$、带宽 $b=10^3$ 时约 $2nb^2=2\times10^{12}$ 次运算，虽然大但可做，而且结果精确、不依赖收敛。真正的分界线是「fill-in 会不会把存储吃光」，不是「$n$ 大不大」。

6.3 化学与材料里的三个落点 #

• 分子轨道：Roothaan–Hall 方程 $HC=\varepsilon SC$ 是广义特征值问题，$S$ 是重叠矩阵（对称正定）。标准做法是先做 $S=LL^{\mathsf T}$ 的 Cholesky，化成 $L^{-1}HL^{-\mathsf T}y=\varepsilon y$ 的标准对称特征值问题——正是 3.4 节的分解。
• 力场与几何优化：Hessian 必须正定才说明处在极小点，判据就是 Cholesky 能不能做完（3.4 节的注）。做不了就加位移或换优化器。
• 反应–扩散与传热：离散后就是 2.5 节那个矩阵的高维版本，$\kappa\sim O(n^{2/d})$，这就是为什么三维问题比一维难那么多。

6.4 与奇异值分解的关系 #

$\kappa_2(A)=\sigma_{\max}/\sigma_{\min}$（29 讲）。伪逆 $A^\dagger=V\Sigma^\dagger U^{\mathsf T}$ 把所有「小奇异值」的倒数写得明明白白：$\sigma_{\min}$ 小，$1/\sigma_{\min}$ 大，误差就在这个方向炸开。截断 SVD（把小于阈值的 $\sigma$ 直接置零）本质上是用「改问题」换「稳定」，与 Tikhonov 正则化是同一件事的两种说法。

---

七、自测（先做，再看答案） #

1. 对 $A=\begin{pmatrix}4&2\\2&3\end{pmatrix}$ 分别做 LU 与 Cholesky，验证「Cholesky 对角元的平方 = LU 的主元」这条关系。

2. 对三对角矩阵 $A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$，算 $\rho(B_J)$ 与 $\rho(B_{GS})$，并说明为什么这里「$\rho(B_{GS})=\rho(B_J)^2$」成立。

3. 用四位十进制算术，对 $A=\begin{pmatrix}10^{-5}&1\\1&3\end{pmatrix}$、$b=(2,7)^{\mathsf T}$，分别用「不换行」与「换行」的 LU 求 $x$，并解释误差来源。

4. $H_3$ 的 $\kappa_\infty=748$。若右端项有 $0.1\%$ 的相对扰动，解的相对误差最坏可能是多少？实测大约是多少？

5. 设 $A$ 的特征值是 $10,\ 9.9,\ -9.9$，用幂法求主特征值。误差要降到 $10^{-6}$ 需要多少步？如果改用带位移 $\mu=9.9$ 的反幂法呢？

答案（点开）

1. LU：$u_{11}=4$，$l_{21}=\frac12$，$u_{22}=3-\frac12\cdot2=2$。故主元是 $4,\ 2$。
Cholesky：$l_{11}=\sqrt4=2$，$l_{21}=2/2=1$，$l_{22}=\sqrt{3-1}=\sqrt2$。对角元平方是 $4,\ 2$。完全一致 ✓
原因：Cholesky 就是 $LDL^{\mathsf T}$ 里把 $\sqrt{D}$ 塞进 $L$，而 $D$ 正是 LU 的主元。

2. $D=2I$，$B_J=\frac12\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$，特征多项式 $\lambda^3-\frac12\lambda=0$，故 $\rho(B_J)=1/\sqrt2\approx0.7071$。
三对角矩阵具有性质 A（相容次序），由定理 $\rho(B_{GS})=\rho(B_J)^2=\frac12$；数值验算 $B_{GS}$ 的特征值是 $0,0,\frac12$，一致 ✓
物理意义：GS 每步用的信息比 Jacobi 多一倍（新值立刻用），等价于「两步 Jacobi 的效果」。

3. 不换行：$m=10^5$，$u_{22}=3-10^5\to-1.000\times10^5$，$y_2=7-2\times10^5\to-2.000\times10^5$，$x_2=2.000$，$x_1=(2-2.000)/10^{-5}=0$。得 $(0,\ 2.000)$，真解 $(1.00003,\ 1.99999)$，第一位就错。
换行后 $m=10^{-5}$，$u_{22}=0.99997\to1.000$，$y_2=1.99993\to2.000$，$x=(1.000,\ 2.000)$，四位全对。
误差来源不是矩阵病态（$\kappa_\infty\approx16$），而是 $u_{22}=3-10^5$ 这一步的相消：小数减大数，$3$ 的有效位被吞掉。

4. 最坏 $\kappa_\infty\times0.1\%=748\times10^{-3}\approx0.75$，即误差可能达到 75%——界允许解完全失真。
实测：把 $b_1$ 改动 $0.1\%$，解变化 $6.6\%$（放大约 $66$ 倍，与改动 $1\%$ 时的放大倍数相同——线性放大，倍数与扰动大小无关）。
所以界给 $75\%$、实测 $6.6\%$：界远大于实测，但方向与量级都对。工程上宁可按界估，因为界不依赖具体扰动长什么样（扰动落在「坏方向」上就会接近界）。

5. $|\lambda_2/\lambda_1|=9.9/10=0.99$。步数 $\approx\ln(10^{-6})/\ln(0.99)\approx1375$ 步。慢得没法用。
带位移 $\mu=9.9$ 的反幂法：$A-\mu I$ 的特征值是 $0.1,\ 0,\ -19.8$，最小的两个是 $0$ 与 $0.1$，比值趋于 $0$，一两步就收敛到 $\lambda=9.9$ 对应的特征向量。
注意：实际算时 $\mu$ 只有近似值，比值变成 $|\lambda_i-\mu|/|\lambda_j-\mu|$，仍然远小于 $0.99$，仍然是几步的事。

---

八、复习卡 #

项	内容
机器精度	双精度 $\varepsilon=2^{-53}\approx1.11\times10^{-16}$；每次运算带 $(1+\delta)$，$|\delta|\le\varepsilon$
有效位数	约 $16-\log_{10}\kappa$ 位；$\kappa\varepsilon\gtrsim1$ 时一位不剩
Cramer 代价	$(n-1)(n+1)!$ 次乘法，$n=25$ 要 $3\times10^{10}$ 年
高斯消去代价	$\approx n^3/3$；LU 分解 $\approx2n^3/3$；Cholesky $\approx n^3/3$
为什么不用求逆	运算量差 $n$ 倍；毁稀疏；$\kappa(A^{-1})=\kappa(A)$ 救不了病态
LU	$A=LU$，$L$ 单位下三角；$Ly=b$ 前代、$Ux=y$ 回代，各 $O(n^2)$
置换矩阵	$P^{-1}=P^{\mathsf T}$，$\det P=\pm1$；$PX$ 换行、$XP$ 换列
部分主元	每步在当前列取 $\max$，保证 $|l_{ij}|\le1$；得 $PA=LU$；比较代价 $O(n^2)$
全主元	在整个右下子块取 $\max$，更稳但比较本身 $O(n^3)$
小主元反例	$\begin{pmatrix}10^{-5}&1\\1&3\end{pmatrix}$，$\kappa_\infty\approx16$，四位算术下 $x_1$ 全错；换行后全对
Householder	$H=I-2ww^{\mathsf T}$，对称正交，$H^2=I$，镜面反射；$v=x+\operatorname{sign}(x_1)\|x\|_2e_1$
Givens	只转 $(i,k)$ 两行，$c=x_i/r$、$s=x_k/r$；带状/局部清零时用
QR	$A=QR$，$Q$ 正交、$R$ 上三角；正交变换保 2 范数，最小二乘化归 $Rx=c_1$
$\kappa$ 被平方	$\kappa_2(A^{\mathsf T}A)=\kappa_2(A)^2$；正规方程的致命伤
CGS vs MGS vs HH	$\kappa\approx1.7\times10^8$ 时正交性误差：$0.5$ / $7\times10^{-9}$ / $10^{-15}$
Cholesky	$A=LL^{\mathsf T}$，要求对称正定；不用选主元；$l_{jj}^2$ = LU 第 $j$ 个主元
条件数	$\kappa(A)=\|A\|\|A^{-1}\|\ge1$；$\kappa_2=\sigma_{\max}/\sigma_{\min}$
误差放大	$\dfrac{\|\delta x\|}{\|x\|}\le\kappa\dfrac{\|\delta b\|}{\|b\|}$；$\kappa$ 是上界不是等号
Hilbert	$\kappa_2$：$n=3$ 为 $524$，$n=6$ 为 $1.5\times10^{7}$，$n=12$ 为 $1.8\times10^{16}$
残差 ≠ 误差	残差小只说明是邻近问题的解；两者差一个 $\kappa$
迭代收敛判据	$x_{k+1}=Bx_k+g$ 对任意初值收敛 $\iff\rho(B)<1$
三种迭代矩阵	$B_J=D^{-1}(L+U)$；$B_{GS}=(D-L)^{-1}U$；$L_\omega=(D-\omega L)^{-1}((1-\omega)D+\omega U)$
充分条件	严格对角占优 ⟹ 两者都收敛；对称正定 ⟹ GS 收敛、SOR 对 $\omega\in(0,2)$ 收敛
相容次序	$\rho(B_{GS})=\rho(B_J)^2$；$\omega_{\text{opt}}=\frac{2}{1+\sqrt{1-\mu^2}}$，$\rho=\omega_{\text{opt}}-1$
SOR 的 $\omega$	$\omega\notin(0,2)$ 必发散（$\det L_\omega=(1-\omega)^n$）；超过 $\omega_{\text{opt}}$ 后 $\rho=\omega-1$ 上升
幂法	$u_k=Au_{k-1}/\mu_k$；$\mu_k\to\lambda_1$；速度 $=|\lambda_2/\lambda_1|$；$\rho\to1$ 时极慢（$0.99$ 需 $\sim1375$ 步）
反幂法	对 $A^{-1}$ 用幂法得 $|\lambda|$ 最小者；带位移 $\mu$ 可求任意特征值，一两步收敛
CG	对称正定；$p_i^{\mathsf T}Ap_j=0$；理论 $n$ 步精确；界 $2\big(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\big)^k$
GMRES	一般方阵；在 $x_0+\mathcal K_k$ 上最小化 $\|b-Ax\|_2$；存储线性增长，需重启
为什么用迭代	直接法 $O(n^3)$ + fill-in（二维 Laplacian 实测 $5\times$）+ 存储爆；迭代只做矩阵乘向量
Laplacian 条件数	一维 $\kappa\approx\frac{4}{\pi^2}(n+1)^2$；故 CG 步数 $\sim n$，需预处理

---

九、出处与延伸（可选，不影响阅读） #

• 主源：《数值线性代数及其应用》（金小庆、魏益民、赵志 著，科学出版社，2015，第 2 版中译本）。各节对应关系如下，页码为该书的印刷页码：
  • 第 1 章「绪论」p1–5：数值线性代数的三大问题（方程组、最小二乘、特征值）、Cramer 法则的运算量对比、病态（问题属性）与不稳定（算法属性）的区分、直接法与迭代法、线性/超线性收敛。
  • 第 2 章「高斯消去法」p7–16：三角方程组的前代与回代、高斯变换矩阵、LU 分解的存在唯一性（顺序主子式全非奇异）、置换矩阵的四条性质、部分主元与全主元、Cholesky 分解与算法。
  • 第 3 章「扰动与误差分析」p19–28：向量 $p$ 范数与矩阵范数、诱导范数、$\|A\|_1$ 与 $\|A\|_\infty$ 的显式公式、$\|A\|_2=\sqrt{\lambda_{\max}(A^{\mathsf T}A)}$、Frobenius 范数、谱半径、条件数的定义与两个扰动定理、$2.0001$ 型病态例子（$20000$ 倍放大）。
  • 第 4 章「最小二乘问题」p37–46：最小二乘的定义与正规方程、$A^{\mathsf T}A$ 丢失信息的例子、Householder 变换与 house 算法、Givens 旋转、QR 分解的存在唯一性、用 QR 解最小二乘。
  • 第 5 章「经典迭代法」p49–61：$A=D-L-U$ 的拆法、Jacobi 与 Gauss–Seidel、收敛定理（$\rho(B)<1$）、严格/弱对角占优、对称正定情形的收敛性、收敛速度的定义 $R_k(M)=-\ln\|M^k\|^{1/k}$、SOR 的迭代形式与 $0<\omega<2$ 的必要性、性质 A 与相容次序、最优 $\omega$。
  • 第 6 章「Krylov 子空间方法」p63–73：最速下降法、CG 的推导与四条正交性质、实用 CG 算法、CG 的收敛界（含 Chebyshev 多项式）、特征值聚簇时的加速、GMRES 的定义与终止性。
  • 第 7 章「非对称特征值问题」p85–93：Schur 分解、幂法及其收敛定理（速度由 $|\lambda_2/\lambda_1|$ 决定）、反幂法与带位移反幂法、QR 方法、上 Hessenberg 化。
• 范数与内积的抽象背景：《高等线性代数》（GTM 135 中译本）讲范数等价性与算子范数的部分，可对照 22 讲。
• 数值表与公式核对：Bronstein《数学手册》俄文第 10 版与英文第 6 版均收录常用矩阵范数、条件数与 Hilbert 矩阵逆的显式公式（$H_n^{-1}$ 的元素是整数，$H_3^{-1}=\begin{pmatrix}9&-36&30\\-36&192&-180\\30&-180&180\end{pmatrix}$，可直接用来验算 3.5 节）。
• 术语别名：部分主元选取 = partial pivoting = 列主元消去；全主元 = complete pivoting；置换矩阵 = permutation matrix；条件数 = condition number，记法 $\kappa$、$\operatorname{cond}$；谱半径 = spectral radius，$\rho$；Gauss–Seidel 也译「塞德尔迭代」；SOR = 逐次超松弛 = successive overrelaxation；CG = 共轭梯度 = conjugate gradient；GMRES = 广义极小残量 = generalized minimum residual。
• 一个提醒：不同教材对 $\|A\|_2$ 的定义统一（最大奇异值），但对「条件数」默认用哪个范数并不统一——数值分析书多用 $\kappa_2$，偏微分方程书常报 $\kappa_\infty$（因为行和好算）。看到「条件数」三个字，先确认是哪个范数，本例中 $\kappa_2=5.83$ 而 $\kappa_\infty=8$，差 37%，不影响结论但会影响你估的有效位数。