Chapter2：解线性方程组的直接方法

概述#

这一章的核心是：

如何用有限次加、减、乘、除，把线性方程组
$Ax=b$
解出来，并尽量让计算过程稳定、可编程、可复用。

这一章和下一章都围绕线性方程组展开：

Chapter 2：直接方法
- 有限步内把方程组化成容易解的形式
- 代表方法：Gauss 消去法、主元素法、LU 分解、Cholesky 分解
Chapter 3：迭代方法
- 从初值开始逐步逼近真解
- 适合更大规模、更稀疏的问题

这章最重要的思想链条是：

1
线性方程组  →  消元  →  上三角方程组  →  回代
2
              ↓
3
          初等行变换
4
              ↓
5
          LU 分解 / PA = LU
6
              ↓
7
       多个右端项时可重复使用分解结果

直接方法的目标不只是“会手算”，更重要的是：

程序怎么写
运算量是多少
舍入误差会不会被放大
矩阵结构能不能利用
同一个 $A$ 、不同右端项 $b$ 时能不能复用已有计算

线性方程组与直接方法#

一般线性方程组写成：

\begin{cases} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1,\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2,\\ \cdots\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n. \end{cases}

矩阵形式为：

Ax=b,

其中

A=(a_{ij})_{n\times n},\qquad x=(x_1,x_2,\dots,x_n)^T,\qquad b=(b_1,b_2,\dots,b_n)^T.

如果 $\det(A)\ne 0$ ，方程组有唯一解。

为什么不用 Cramer 法则#

Cramer 法则给出了解析表达：

x_i=\frac{\det(A_i)}{\det(A)},

其中 $A_i$ 是把 $A$ 的第 $i$ 列替换成 $b$ 后得到的矩阵。

但它在数值计算中基本不可用，主要原因是：

行列式展开会产生阶乘级别的计算量
$n!$ 增长极快，远大于多项式复杂度
实际计算中还会伴随大量舍入误差

所以 Cramer 法则适合说明理论存在性，不适合真正写程序求解大规模线性方程组。

直接方法的基本想法#

直接方法的核心思路：

通过等价变换，把原方程组变成容易解的方程组
最典型的目标形式是上三角方程组
再用回代得到所有未知量

也就是：

1
Ax=b
2
  ↓ 消元
3
Ux=c
4
  ↓ 回代
5
x

其中 $U$ 是上三角矩阵。

TIP
消元过程不能改变方程组的解。
从方程组角度看，它是“某一行减去另一行的倍数”；从矩阵角度看，它是左乘初等行变换矩阵。

工程问题中的矩阵规模与稀疏性#

老师上课举了一个很重要的工程直观：

如果要计算一个飞行器、炮弹或流场周围每个网格点上的物理量，最终往往也会落到某种线性方程组：

Ax=b.

例如在 $1\text{m}\times1\text{m}\times1\text{m}$ 的区域内，如果空间步长取 $1\text{mm}$ ，单个标量未知量的网格点数量已经达到约

1000^3=10^9.

这意味着未知量可能达到十亿量级。若矩阵是满矩阵，存储和计算都很难承受。

但真实物理模型往往有局部性：

一个网格点通常只和附近网格点强相关
很远处的点对它的直接影响可忽略
于是矩阵中大量元素为 $0$

这种矩阵叫 稀疏矩阵（sparse matrix）。

在一维局部相邻作用模型中，矩阵常常呈现三对角结构；二维、三维中也会出现带状或稀疏结构。

配图占位：插入 lesson2 手写 PPT 中“网格点局部耦合导致稀疏矩阵 / 三对角矩阵”的示意图。

Gauss 消去法#

基本消元过程#

以第 $k$ 步为例，假设当前主元为 $a_{kk}^{(k)}$ ，希望消去第 $k$ 列中 $k$ 行以下的元素。

对 $i=k+1,k+2,\dots,n$ ，令

l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}.

然后做行变换：

\text{第 }i\text{ 行}\leftarrow \text{第 }i\text{ 行}-l_{ik}\cdot \text{第 }k\text{ 行}.

于是有

a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}a_{kj}^{(k)}, \qquad j=k+1,k+2,\dots,n,

以及右端项

b_i^{(k+1)}=b_i^{(k)}-l_{ik}b_k^{(k)}.

经过 $n-1$ 轮消元后，原方程组化为上三角方程组：

Ux=c.

回代#

上三角方程组形如：

\begin{cases} u_{11}x_1+u_{12}x_2+\cdots+u_{1n}x_n=c_1,\\ u_{22}x_2+\cdots+u_{2n}x_n=c_2,\\ \cdots\\ u_{nn}x_n=c_n. \end{cases}

先由最后一行得到

x_n=\frac{c_n}{u_{nn}},

再依次向上求：

x_k=\frac{c_k-\sum_{j=k+1}^n u_{kj}x_j}{u_{kk}}, \qquad k=n-1,n-2,\dots,1.

这一步叫 回代（back substitution）。

运算量#

Gauss 消去的主要计算量来自消元。

粗略看：

(n-1)^2+(n-2)^2+\cdots+1^2=O(n^3).

回代的计算量为

1+2+\cdots+(n-1)=O(n^2).

因此整体复杂度为

O(n^3).

TIP
Gauss 消去法比 Cramer 法则实用得多：
Cramer 法则接近阶乘级复杂度，Gauss 消去法是三次多项式复杂度。

例：三元线性方程组的消元#

课本例子：

\begin{cases} x_1+x_2+x_3=6,\\ 12x_1-3x_2+3x_3=15,\\ -18x_1+3x_2-x_3=-15. \end{cases}

写成增广矩阵：

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 12&-3&3&15\\ -18&3&-1&-15 \end{array} \right].

第一步，用第 1 行消去第 1 列下面的元素：

R_2\leftarrow R_2-12R_1, \qquad R_3\leftarrow R_3+18R_1.

得到

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&-15&-9&-57\\ 0&21&17&93 \end{array} \right].

第二步，用第 2 行消去第 2 列下面的元素：

R_3\leftarrow R_3+\frac{7}{5}R_2.

得到上三角方程组：

\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&-15&-9&-57\\ 0&0&\frac{22}{5}&\frac{22}{5} \end{array} \right].

回代：

x_3=1,

-15x_2-9= -57\quad\Rightarrow\quad x_2=3,

x_1+x_2+x_3=6\quad\Rightarrow\quad x_1=2.

所以

x=(2,3,1)^T.

主元素法#

小主元为什么危险#

Gauss 消去法中，每一步都要除以主元 $a_{kk}^{(k)}$ 。

如果主元很小，形如

l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}

中的分母很小，舍入误差会被放大。

这会导致：

理论上等价的行变换，在浮点数计算中产生严重误差
后续步骤继续使用带误差的数据，误差不断传播
最终结果可能偏离真解很多

所以数值计算里不能只看“代数上能不能消”，还要看“消元顺序是否稳定”。

列主元素 Gauss 消去法#

列主元素法的规则：

第 $k$ 步消元前，在第 $k$ 列的第 $k$ 行到第 $n$ 行中，选绝对值最大的元素作为主元，并把它所在行交换到第 $k$ 行。

数学写法：

p=\arg\max_{k\le i\le n}|a_{ik}^{(k)}|.

若 $p\ne k$ ，先交换第 $p$ 行和第 $k$ 行，再继续消元。

这样做的目的：

避免用很小的数作分母
降低舍入误差被放大的风险
不改变未知量 $x_1,x_2,\dots,x_n$ 的顺序

TIP
只交换行，未知量编号不变。
如果交换列， $x$ 的分量顺序也会变化，程序实现更麻烦。

例：例 2.1 的数值不稳定#

课本例 2.1：

\begin{cases} 0.50x_1+1.1x_2+3.1x_3=6.0,\\ 2.0x_1+4.5x_2+0.36x_3=0.02,\\ 5.0x_1+0.96x_2+6.5x_3=0.96. \end{cases}

若按原顺序直接用普通 Gauss 消去法，在有限位数计算下会得到近似结果：

x_1\approx -5.80, \qquad x_2\approx 2.40, \qquad x_3\approx 2.00.

真解应为：

x_1=-2.60, \qquad x_2=1.00, \qquad x_3=2.00.

误差的关键原因在于：第一次消元后，第二步主元附近出现了类似 $0.1$ 的小数。下一轮消元要除以它，舍入误差被大幅放大。

列主元素法的做法：第一列中绝对值最大的元素是 $5.0$ ，先把第 3 行换到第 1 行：

\begin{cases} 5.0x_1+0.96x_2+6.5x_3=0.96,\\ 2.0x_1+4.5x_2+0.36x_3=0.02,\\ 0.50x_1+1.1x_2+3.1x_3=6.0. \end{cases}

接下来再消元，主元分母从 $0.50$ 换成 $5.0$ ，误差不会被小分母放大。最终可得到正确近似：

x_1\approx -2.60, \qquad x_2\approx 1.00, \qquad x_3\approx 2.00.

配图占位：插入 lesson2 手写 PPT 中“例 2.1 小主元导致误差放大，以及交换行后主元变大”的推导截图。

全主元素法#

全主元素法在每一步中，从剩余子矩阵中选绝对值最大的元素作为主元。

它比列主元素法更稳定，但会带来列交换。

列交换意味着未知量顺序变化，例如 $x_1$ 和 $x_2$ 的位置可能被交换，程序中需要额外记录变量顺序。

实际工程计算中，常用列主元素法；全主元素法用得较少。

初等行变换与 LU 分解#

初等行变换矩阵#

交换矩阵左乘一个矩阵，就等价于交换它的行。

例如

A=\begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9 \end{bmatrix}.

若要交换第 1 行和第 3 行，可以构造

P_{13}=\begin{bmatrix} 0&0&1\\ 0&1&0\\ 1&0&0 \end{bmatrix}.

于是

P_{13}A= \begin{bmatrix} 7&8&9\\ 4&5&6\\ 1&2&3 \end{bmatrix}.

这一点说明：

对矩阵做初等行变换，可以理解为左乘某个初等矩阵。

消元也是初等行变换。比如

R_i\leftarrow R_i-l_{i1}R_1

对应的初等矩阵是在单位矩阵的 $(i,1)$ 位置放入 $-l_{i1}$ 。

Gauss 消去与 LU 分解的关系#

不选主元时，Gauss 消去可以写成一串初等矩阵左乘：

L_{n-1}\cdots L_2L_1A=U,

其中 $U$ 是上三角矩阵。

于是

A=(L_{n-1}\cdots L_2L_1)^{-1}U.

把左边这一串逆矩阵记为 $L$ ，得到

A=LU.

这里通常取：

$L$ ：单位下三角矩阵
$U$ ：上三角矩阵

这种形式也叫 Doolittle 分解。

TIP
Gauss 消去过程中的乘子 $l_{ik}$ ，最后会出现在 $L$ 的下三角部分。
$U$ 则是消元后的上三角矩阵。

压缩存储格式#

在普通消元中，被消掉的位置本来会变成 $0$ 。

例如第一列中 $a_{21},a_{31},\dots,a_{n1}$ 被消成 $0$ ，但这些位置可以拿来存放对应的消元乘子：

l_{21},l_{31},\dots,l_{n1}.

因此可以把 $L$ 和 $U$ 存在同一个二维数组中：

\begin{bmatrix} u_{11}&u_{12}&u_{13}&\cdots&u_{1n}\\ l_{21}&u_{22}&u_{23}&\cdots&u_{2n}\\ l_{31}&l_{32}&u_{33}&\cdots&u_{3n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ l_{n1}&l_{n2}&l_{n3}&\cdots&u_{nn} \end{bmatrix}.

这就是老师反复强调的 压缩存储格式。

它的好处：

不额外开一个矩阵存 $L$
原来应为 $0$ 的位置被有效利用
更接近真实程序中的 LU 分解实现

为什么 LU 分解有用#

如果只解一个方程组，Gauss 消去和 LU 分解的计算量接近，都是 $O(n^3)$ 。

但如果同一个 $A$ 对应多个右端项：

Ax=b^{(1)},\quad Ax=b^{(2)},\quad Ax=b^{(3)},\dots

LU 分解就非常有用。

先做一次

A=LU.

每次解

Ax=b

时，只需解两个三角方程组：

Ly=b,

Ux=y.

其中：

$Ly=b$ ：前代， $O(n^2)$
$Ux=y$ ：回代， $O(n^2)$

所以：

1
一次 LU 分解：O(n^3)
2
每换一个 b：O(n^2)

这就是 LU 分解在工程计算中的核心意义。

WARNING
工程计算中通常不会真的求 $A^{-1}$ 。
如果需要 $A^{-1}$ 对某个向量的作用，例如 $q=A^{-1}p$ ，实际做法是解
$Aq=p.$
若已经有 $A=LU$ ，就通过前代和回代得到 $q$ 。

带列主元素的三角分解：PA = LU#

如果消元过程中发生了行交换，分解形式要写成

PA=LU,

而不能只写 $A=LU$ 。

其中 $P$ 是置换矩阵，记录行交换。

理解方式：

$P$ 把 $A$ 的行重新排列
对重新排列后的矩阵做普通 LU 分解
列主元素法对应的分解结果就是 $PA=LU$

例：带列主元素的 LU 分解#

老师课上重新演示了课本例 2.5。设

A=\begin{bmatrix} 0&2&0&1\\ 2&2&3&2\\ 4&-3&0&1\\ 6&1&-6&-5 \end{bmatrix}, \qquad b=\begin{bmatrix}0\\-2\\-7\\6\end{bmatrix}.

第一列主元选绝对值最大的 $6$ ，所以第 4 行换到最上面。

第一轮消元后，压缩存储形式为：

\left[ \begin{array}{rrrr|r} 6&1&-6&-5&6\\ \frac13&\frac53&5&\frac{11}{3}&-4\\ \frac23&-\frac{11}{3}&4&\frac{13}{3}&-11\\ 0&2&0&1&0 \end{array} \right].

第二列主元在剩余行中选 $-\dfrac{11}{3}$ ，所以当前第 2 行和第 3 行交换。继续消元后得到：

\left[ \begin{array}{rrrr|r} 6&1&-6&-5&6\\ \frac23&-\frac{11}{3}&4&\frac{13}{3}&-11\\ \frac13&-\frac5{11}&\frac{75}{11}&\frac{62}{11}&-9\\ 0&-\frac6{11}&\frac{24}{11}&\frac{37}{11}&-6 \end{array} \right].

第三列不用换主元，消元乘子为

\frac{\frac{24}{11}}{\frac{75}{11}}=\frac{8}{25}.

最终得到

P=\begin{bmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{bmatrix},

L=\begin{bmatrix} 1&0&0&0\\ \frac23&1&0&0\\ \frac13&-\frac5{11}&1&0\\ 0&-\frac6{11}&\frac8{25}&1 \end{bmatrix},

U=\begin{bmatrix} 6&1&-6&-5\\ 0&-\frac{11}{3}&4&\frac{13}{3}\\ 0&0&\frac{75}{11}&\frac{62}{11}\\ 0&0&0&\frac{39}{25} \end{bmatrix}.

它们满足

PA=LU.

如果继续求解方程组，最终得到

x=\left(-\frac12,\;1,\;\frac13,\;-2\right)^T.

配图占位：插入 lesson3 手写 PPT 中“例 2.5 带列主元素 LU 分解的压缩存储表格”截图。

TIP
这个例子的重点是理解结构：
行交换通过 $P$ 记录，消元乘子进入 $L$ ，剩下的上三角部分构成 $U$ 。

三对角方程组与追赶法#

三对角矩阵从哪里来#

三对角方程组形如：

\begin{bmatrix} b_1&c_1&&&0\\ a_2&b_2&c_2&&\\ & a_3&b_3&c_3&\\ &&\ddots&\ddots&\ddots\\ 0&&&a_n&b_n \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3\\\vdots\\x_n \end{bmatrix} = \begin{bmatrix} d_1\\d_2\\d_3\\\vdots\\d_n \end{bmatrix}.

也就是只有三条对角线上可能非零：

主对角线 $b_i$
上副对角线 $c_i$
下副对角线 $a_i$

这种结构常来自一维网格上的局部耦合。

例如：某点 $x_i$ 的方程只考虑相邻点 $x_{i-1}$ 、 $x_i$ 、 $x_{i+1}$ 的影响，远处点影响忽略，于是每一行只有三个非零元素。

如果网格等距、材料均匀，还常常得到对称三对角矩阵。

三对角矩阵的 LU 分解#

设

A=LU,

其中

L=\begin{bmatrix} 1&&&&0\\ l_2&1&&&\\ &l_3&1&&\\ &&\ddots&\ddots&\\ 0&&&l_n&1 \end{bmatrix},

U=\begin{bmatrix} u_1&c_1&&&0\\ &u_2&c_2&&\\ &&u_3&c_3&\\ &&&\ddots&\ddots\\ 0&&&&u_n \end{bmatrix}.

把 $L$ 和 $U$ 相乘并对比 $A$ ，可得：

u_1=b_1,

对 $i=2,3,\dots,n$ ，有

l_i=\frac{a_i}{u_{i-1}},

u_i=b_i-l_ic_{i-1}.

注意：上副对角线 $c_i$ 不变。

追赶法求解步骤#

追赶法分三步。

第一步：分解

u_1=b_1,

l_i=\frac{a_i}{u_{i-1}},\qquad u_i=b_i-l_ic_{i-1},\qquad i=2,3,\dots,n.

第二步：前代解 $Ly=d$

y_1=d_1,

y_i=d_i-l_iy_{i-1},\qquad i=2,3,\dots,n.

第三步：回代解 $Ux=y$

x_n=\frac{y_n}{u_n},

x_i=\frac{y_i-c_ix_{i+1}}{u_i},\qquad i=n-1,n-2,\dots,1.

所以追赶法只需要三个循环，计算量为

O(n).

这比普通 LU 分解的 $O(n^3)$ 低很多。

WARNING
三对角结构非常宝贵。
如果直接把它当作一般满矩阵处理，会浪费大量计算和存储。

配图占位：插入 lesson3 手写 PPT 中“三对角矩阵结构与追赶法三个循环”的截图。

对称正定矩阵与平方根法#

对称正定的直观来源#

对称正定矩阵在工程建模中非常常见。

对称性常来自物理作用的互易性：

点 $i$ 对点 $j$ 的影响
点 $j$ 对点 $i$ 的影响

在均匀材料、对称几何或对称相互作用下，这两者常常对应同一系数。

正定性可理解为能量意义上的“稳定”：

x^TAx>0,\qquad x\ne0.

在很多弹性、热传导、扩散等问题中，系统能量为正，离散后得到的矩阵也常为对称正定矩阵。

TIP
当你在工程建模中断言 $A$ 是对称正定矩阵时，背后通常包含物理假设：局部作用、能量稳定、材料或几何的对称性。

Cholesky 分解#

定理：若 $A$ 是对称正定矩阵，则存在唯一的下三角矩阵 $L$ ，且 $L$ 的对角元全为正，使得

A=LL^T.

这叫 Cholesky 分解，也叫平方根法。

对于

A=(a_{ij})_{n\times n},

算法为：

l_{kk}=\sqrt{a_{kk}-\sum_{j=1}^{k-1}l_{kj}^2}, \qquad k=1,2,\dots,n.

对 $i=k+1,k+2,\dots,n$ ，

l_{ik}=\frac{a_{ik}-\sum_{j=1}^{k-1}l_{ij}l_{kj}}{l_{kk}}.

正定性保证根号内为正，因此算法能继续做下去。

若要求解

Ax=b,

由于

A=LL^T,

可分两步：

Ly=b,

L^Tx=y.

第一步前代，第二步回代。

改进平方根法：LDL^T 分解#

Cholesky 分解需要开平方。开平方在计算上比加减乘除更贵。

为了避免开平方，可以把分解写成

A=LDL^T,

其中：

$L$ 是单位下三角矩阵
$D$ 是对角矩阵

设

D=\operatorname{diag}(d_1,d_2,\dots,d_n).

算法为：

d_k=a_{kk}-\sum_{j=1}^{k-1}l_{kj}^2d_j, \qquad k=1,2,\dots,n.

对 $i=k+1,k+2,\dots,n$ ，

l_{ik}=\frac{a_{ik}-\sum_{j=1}^{k-1}l_{ij}l_{kj}d_j}{d_k}.

求解时分三步：

Ly=b,

Dz=y,

L^Tx=z.

TIP
$LDL^T$ 分解保留了对称正定结构，又避开了开平方运算，在程序实现中很实用。

配图占位：插入 lesson3 手写 PPT 中“Cholesky 与 LDL^T 待定系数推导”的截图。

向量范数、矩阵范数与条件数#

前面的算法都在处理误差与稳定性。要严格讨论“误差多大”，需要先定义向量和矩阵的大小，这就是范数。

向量范数#

向量范数是从 $\mathbb{R}^n$ 到 $\mathbb{R}$ 的映射：

x\mapsto \|x\|.

它要满足：

非负性与正定性

\|x\|\ge0, \qquad \|x\|=0\Longleftrightarrow x=0.

齐次性

\|\alpha x\|=|\alpha|\|x\|.

三角不等式

\|x+y\|\le \|x\|+\|y\|.

常用向量范数有：

1 范数

\|x\|_1=\sum_{i=1}^n|x_i|.

2 范数

\|x\|_2=\left(\sum_{i=1}^n x_i^2\right)^{1/2}.

它就是欧氏长度。

无穷范数

\|x\|_\infty=\max_{1\le i\le n}|x_i|.

在 $\mathbb{R}^2$ 中，不同范数下的“单位圆”形状不同：

2 范数：圆
1 范数：菱形
无穷范数：正方形

这说明范数改变后，几何意义也会改变。

配图占位：插入 lesson3 手写 PPT 中“2 范数圆与无穷范数正方形单位圆”的示意图。

矩阵范数#

矩阵范数给矩阵定义大小。对 $A,B\in\mathbb{R}^{n\times n}$ ，矩阵范数满足：

非负性与正定性

\|A\|\ge0, \qquad \|A\|=0\Longleftrightarrow A=0.

齐次性

\|\alpha A\|=|\alpha|\|A\|.

三角不等式

\|A+B\|\le \|A\|+\|B\|.

相容性 / 次乘性

\|AB\|\le \|A\|\|B\|.

相容性非常重要，因为矩阵代表线性算子。它允许我们估计多次线性作用带来的放大效果。

例如：

\|A^m\|\le \|A\|^m.

若 $\|A\|<1$ ，则 $\|A^m\|\to0$ 。

向量诱导的矩阵范数#

给定一个向量范数，可以定义对应的矩阵范数：

\|A\|=\max_{x\ne0}\frac{\|Ax\|}{\|x\|}.

由于

\frac{\|Ax\|}{\|x\|}=\left\|A\frac{x}{\|x\|}\right\|,

所以也可以理解为：

在所有单位向量上，找出 $A$ 对向量长度的最大放大倍数。

常用诱导矩阵范数：

矩阵 1 范数

\|A\|_1=\max_{1\le j\le n}\sum_{i=1}^n |a_{ij}|.

即最大列和。

矩阵无穷范数

\|A\|_\infty=\max_{1\le i\le n}\sum_{j=1}^n |a_{ij}|.

即最大行和。

矩阵 2 范数

\|A\|_2=\sqrt{\lambda_{\max}(A^TA)}.

其中 $\lambda_{\max}(A^TA)$ 是 $A^TA$ 的最大特征值。

还有一个常用但非诱导的矩阵范数：Frobenius 范数

\|A\|_F=\left(\sum_{i=1}^n\sum_{j=1}^n a_{ij}^2\right)^{1/2}.

它计算方便，性质也很好，很多场合可作为 2 范数的替代估计。

条件数#

考虑

Ax=b.

若右端项有扰动：

A(x+\delta x)=b+\delta b.

因为 $Ax=b$ ，相减得

A\delta x=\delta b.

若 $A$ 非奇异，则

\delta x=A^{-1}\delta b.

于是

\|\delta x\|\le \|A^{-1}\|\,\|\delta b\|.

另一方面

\|b\|=\|Ax\|\le \|A\|\,\|x\|,

所以

\frac{\|\delta x\|}{\|x\|} \le \|A\|\,\|A^{-1}\| \frac{\|\delta b\|}{\|b\|}.

定义矩阵 $A$ 的条件数：

\kappa(A)=\|A\|\,\|A^{-1}\|.

因此

\frac{\|\delta x\|}{\|x\|} \le \kappa(A)\frac{\|\delta b\|}{\|b\|}.

条件数的意义：

它衡量输入相对误差可能被放大多少倍后传到解中。

$\kappa(A)$ 小：问题条件好
$\kappa(A)$ 大：问题病态，右端项中的小误差可能造成解的大误差

工程直观：

如果测量得到的 $b$ 本身有 $10\%$ 误差，那么解 $x$ 的误差可能被 $\kappa(A)$ 放大。模型建得好不好，不只看方程形式，也要看条件数是否可接受。

WARNING
条件数描述的是问题本身对扰动的敏感性。
算法稳定性描述的是计算方法在有限精度下是否额外放大误差。二者都重要。

本章总结#

这一章的主线可以压缩成几句话：

线性方程组 $Ax=b$ 是工程计算的核心问题之一。
Cramer 法则有理论意义，但运算量过大。
Gauss 消去法通过消元把方程组化为上三角方程组，再回代求解。
普通 Gauss 消去可能遇到小主元，导致舍入误差被放大。
列主元素法通过行交换选较大主元，提高数值稳定性。
从初等行变换角度看，Gauss 消去本质上产生了 LU 分解。
不换行时 $A=LU$ ，带列主元素时 $PA=LU$ 。
LU 分解适合同一个 $A$ 、多个 $b$ 的问题：一次分解，多次前代回代。
三对角矩阵可用追赶法，计算量从 $O(n^3)$ 降到 $O(n)$ 。
对称正定矩阵可用 Cholesky 分解 $A=LL^T$ ，也可用无需开根号的 $A=LDL^T$ 。
范数提供“误差大小”的度量，条件数刻画误差放大能力。

本章真正要掌握的是：

方程组怎么解、为什么这样解、计算量是多少、误差在哪里被放大、矩阵结构如何帮助我们更快更稳地解。