11-1-数值稳定性与LU
一句话概括
计算机里没有实数,只有浮点数; 的解之所以会算错,一半怪问题本身(条件数),一半怪算法(稳定性)。本篇讲清浮点数的本质、误差的两个来源、小主元如何毁掉消元、部分选主元(partial pivoting)为什么能救回来、 中 的数值意义、增长因子、Cholesky 为何快一倍且不用选主元,以及 Wilkinson 的向后误差分析这一理解数值稳定性的关键视角。
读完你应该能:手工算出一个"不选主元就全错、选主元就全对"的 例子;说清
inv(A) @ b与solve(A, b)在运算量与精度上的双重差别;用np.finfo(float).eps解释0.1 + 0.2 != 0.3。
一、定义
1.1 浮点数的本质:IEEE 754 双精度
计算机用有限位二进制表示实数。IEEE 754 的双精度浮点数(double precision,float64)用 64 位:1 位符号、11 位阶码、52 位尾数。
定义 11.1(规格化浮点数) 一个非零的双精度浮点数写作
其中 是 53 位有效二进制数字(首位 隐含不存)。能表示的实数总共只有 个左右,它们在实数轴上不均匀分布:越靠近 越密,量级越大越稀。
定义 11.2(机器精度 machine epsilon) 记 为 与"下一个比 大的可表示浮点数"之差:
在 numpy 中它就是 np.finfo(float).eps。与之等价的常用量是单位舍入误差(unit roundoff)
是"一次四舍五入最多引入的相对误差"的界。
定义 11.3(十进制有效数字) 双精度的十进制有效位数
所以双精度大约有 16 位十进制有效数字(保守地说是 15 位;np.finfo(float).precision 返回 15)。
这条结论是本章所有"丢失几位有效数字"讨论的基准:双精度下你最多只有约 16 位十进制数字可以花。
1.2 三个必须亲手验证的浮点现象
现象 A:。 因为 , 到 的距离小于"舍入到最近"的判定阈值的一半,于是被舍入回 。更一般地,只要 就有 。
现象 B:。 十进制小数 在二进制下是无限循环小数
必须舍入到 53 位,得到
两者相加得 ,再舍入得到
而 ,两者相差约 。所以 Python 里 0.1 + 0.2 打印出 0.30000000000000004。这不是 bug,是二进制表示的必然结果。
现象 C:浮点加法不满足结合律(associativity)。 取 ,,:
同一个式子,换个括号结果差 —— 相对差 100%。这就是为什么并行求和、快速求和、方程组消元的行序都会影响最终结果。
1.3 误差的两个来源
定义 11.4(舍入误差 rounding error) 由于用有限位浮点数表示实数、以及每一步浮点运算都要舍入而产生的误差。它不可避免,量级由 控制。
定义 11.5(截断误差 truncation error) 由于用有限过程替代无穷过程而产生的误差。典型来源:迭代法在有限步后停止、Taylor 级数截断、用有限差分替代导数。它与浮点数无关,即使有无限精度的计算机也存在。
| 对比项 | 舍入误差(rounding error) | 截断误差(truncation error) |
|---|---|---|
| 来源 | 浮点表示与浮点运算的舍入 | 用有限过程替代无穷过程 |
| 是否与硬件有关 | 有关,量级 | 无关,由算法与步长决定 |
| 增大迭代次数/减小步长 | 几乎不变(有随机游走式增长) | 单调减小 |
| 可否消除 | 不可,只能控制放大倍数 | 可以,代价是计算量 |
| 典型例子 | 0.1 + 0.2 != 0.3 | 迭代法在第 步停止;CG 只跑 100 步 |
| 本章关注点 | 消元中的放大 | 第 11-3 篇迭代法的精度 |
关键认识
数值分析的核心任务不是"消灭误差",而是分别控制这两类误差并让它们平衡。迭代法跑得越久截断误差越小,但舍入误差会累积——所以"迭代到机器精度"往往反而更差。
1.4 绝对误差与相对误差
定义 11.6 设 是精确值, 是近似值。
为什么相对误差才是有意义的指标? 看两组数据:
| 情形 | 精确值 | 近似值 | 绝对误差 | 相对误差 | 谁更好 |
|---|---|---|---|---|---|
| 测量星系距离 | 光年 | 相对误差小,很好 | |||
| 测量原子半径 | m | 绝对误差小,其实很差 |
第一行绝对误差大得吓人(1 光年),但相对误差只有亿分之一;第二行绝对误差只有纳米级,相对误差却高达 10%。"算得准不准"永远要相对地看。 本库此后约定:不特别说明时,"误差"都指相对误差,并且用某个范数来衡量向量的相对误差(详见 11-2-范数与条件数)。
1.5 向后误差分析:Wilkinson 的视角
定义 11.7(前向误差 forward error) 算法输出的解与真解之差:
定义 11.8(向后误差 backward error) 若存在扰动矩阵 与扰动向量 使得算出的 精确地满足扰动后的方程
且 、,则称该算法的向后误差不超过 。若 ( 为单位舍入误差,与 只差低次多项式因子),则称算法是向后稳定(backward stable)的。
这个视角的威力在哪里? 它把"算法好不好"与"问题难不难"彻底分开了:
- 向后误差由算法决定:一个好的算法(如带部分选主元的高斯消元)给出的 是"某个微小扰动后问题的精确解",。
- 条件数 由问题本身决定:它衡量"输入的小扰动会被放大成输出多大的扰动"。
- 两者相乘才是你实际看到的前向误差。
Wilkinson(James Hardy Wilkinson,1919–1986,图灵奖 1970)正是用这套框架证明了高斯消元是向后稳定的,从而终结了"消元法不稳定"的早期误解。一句话记住:好算法保证"解的是几乎同一个问题",但它不能保证"答案接近真答案"——后者取决于条件数。
为什么这个分解如此重要
当你发现结果不对时,向后误差分析告诉你该去查哪里:
- 残差 很小 ⟹ 向后误差小 ⟹ 算法没问题,问题出在 大。
- 残差很大 ⟹ 算法或实现有问题(例如忘了选主元、用了
inv、尺度失衡)。
二、几何直观
2.1 行图像:两条直线的交点
方程组 的行图像是平面上两条直线,解是它们的交点。
消元的几何意义:用第 1 个方程消去第 2 个方程里的 ,等于把第 2 条直线沿第 1 条直线的方向平移到竖直位置(系数变成 )。整个过程中交点不动——因为"把一条方程换成两条方程的线性组合"不改变解集。
选主元的几何意义:交换两行只是交换两条直线的标签,交点当然不变。但"用哪条方程去消元"决定了这个平移操作是否稳定。
2.2 小主元为什么危险:一次"大数相减"
取 ,考虑(本篇最核心的例子)
两条直线是
当 时第一条直线趋于水平线 ,第二条是斜率 的直线,交点在 附近。两条直线的夹角接近 ,交点非常"结实"——这说明问题本身是良态的(后文会算出 ,非常小)。
危险出在算法上:不选主元时第一步主元是 ,乘子 。消元后的第 2 个方程系数是
右端项是
两个"相差 1 和 2"的大数在做减法时把那点差别彻底扔掉了——这就是灾难性抵消(catastrophic cancellation)。几何上,消元后第 2 条直线变成了 (因为 ),它不再包含任何关于 的信息。然后回代要除以 :
在浮点里精确等于 0,于是 被算成 ,而真值是 。相对误差 100%。
2.3 换一个方向做消元:选主元的几何图像
如果先把两行交换,用 (系数为 的方程)做主元,乘子变成 ,是个很小的数:
然后 ,,完全正确。
几何图像:消元相当于"用一个方程当尺子去量另一个方程"。当尺子的刻度(主元 )极小时,量出来的读数被放大 倍,浮点噪声也同比放大。选主元就是每次都挑刻度最大的那把尺子。
2.4 列图像:条件数的几何预演
的列图像是问" 能否由 的两列组合出来"。此例中
当 时两列几乎就是 与 ,夹角约 ,不接近平行,所以组合系数对 的扰动不敏感——这再次说明问题良态。
对比之下,Hilbert 矩阵的两列几乎平行,组合系数极度敏感,那才是真正的病态(见 11-2-范数与条件数)。
本篇最重要的一句话
"病态"(ill-conditioned)是问题的属性,"不稳定"(unstable)是算法的属性。 上面这个 例子条件数只有约 (非常好的问题),但不选主元的消元算法依然给出 100% 的错误。不要用"问题难"来解释"算法烂"。
三、性质与定理
定理 11.1(浮点表示的基本模型) 对任意实数 (在浮点范围内),存在 使得
证明思路:IEEE 754 规定"舍入到最近、遇中取偶"(round to nearest, ties to even)。此时绝对误差不超过相邻两个浮点数间距的一半,即 (对规格化数 ),取 即得。
适用条件: 不溢出()也不下溢到次正规数区间()。次正规数的相对精度会显著退化。
定理 11.2(浮点运算模型) 对 与浮点数 (),
证明思路: 的精确值(在 已经是浮点数时,加减乘的精确结果就是实数运算结果)再舍入一次,套用定理 11.1。
推论 11.2.1 浮点加减乘除不满足结合律,也不满足分配律。反例见 1.2 节现象 C。
适用条件:这是逐次运算的模型,不能简单地叠加使用—— 次运算的误差按 (随机游走)或 (最坏情形)增长,而不是 倍的 直接相加。做误差分析时必须逐项追踪。
定理 11.3(消元中乘子的误差放大作用) 高斯消元第 步的乘子(multiplier)为
第 行的更新为 。若第 行(含其右端项)已带有绝对误差 ,则这个误差以 的规模传递到第 行。
证明思路: 的误差 = 的误差 + 的误差 + 一次舍入。
适用条件:这是启发式判断,不是严格的误差上界——它说明" 大是危险信号",但不排除某些大乘子的问题恰好结果不错。严格的结论要靠定理 11.9。
定理 11.4(部分选主元的规则与效果) 部分选主元(partial pivoting)的高斯消元:在第 步,先在当前列的主元以下部分中找绝对值最大者
交换第 行与第 行(同时交换右端项),然后消元。于是所有乘子满足
证明:交换后 对一切 成立,立得。
代价:每步 次比较,总共 ,与 的消元相比可忽略。
适用条件(重要): 只保证乘子不放大误差,不保证消元过程中元素本身不放大——后者由增长因子(定理 11.6)刻画。此外,如果矩阵各行量级相差悬殊(例如第一行元素是 量级、第二行是 量级),"绝对值最大"这个准则会偏向大尺度行,此时应先做行平衡(row scaling),或改用隐式选主元(implicit pivoting,按每行的最大元素归一化后再比较)。
定理 11.5( 分解) 设 非奇异。则存在置换矩阵 、单位下三角矩阵 (对角元全为 ,且 )、上三角矩阵 ,使得
证明思路:每一步选主元对应左乘一个置换矩阵 ,消元对应左乘单位下三角的初等矩阵 。逐步累乘得 ,把置换矩阵搬到右边并利用" 的乘子在被置换后会互换位置"这一事实,整理成 。
数值意义(本节要强调的): 不是装饰,它是"用什么顺序消元"的完整记录。解 的流程是
即三步:(1) 置换 ;(2) 前代解 ;(3) 回代解 。顺序错了(忘记置换右端项)是初学者最常见的实现错误。
定理 11.6(增长因子 growth factor) 定义
其中 是消元过程中第 步产生的元素。则
- 不选主元: 可以任意大(本篇的 例子中 )。
- 部分选主元:Wilkinson 给出了理论界 。
- 完全选主元(complete pivoting,在剩余子矩阵中找最大元素):理论界小得多,但代价是 次比较,实践中几乎不用。
- 实践中:对部分选主元,几乎总是 ,规模上千的矩阵实测 通常小于 。 这个上界事实上从来取不到,且需要刻意构造。
适用条件: 是最坏情形界,不是期望值。用"存在坏矩阵"来否定部分选主元是不对的;但用"实践中很安全"来忽视机制理解也是不对的。
定理 11.7(Cholesky 分解) 设 对称。则 正定当且仅当存在唯一的对角元全为正的下三角矩阵 使
证明思路:比较 两边元素得递推
"":对任意 ,( 可逆)。"": 正定 ⟹ 的所有顺序主子式为正(6-4-对称矩阵与正定矩阵)⟹ 归纳可知每个 的根号内为正,递推可以一直做下去。
数值意义:Cholesky 不需要选主元,因为 就是第 个顺序主子式之比(Schur 补的对角元),正定性保证它恒为正。这直接省掉了整个选主元逻辑。
| 对比项 | (带部分选主元) | (Cholesky) |
|---|---|---|
| 适用矩阵 | 任意非奇异方阵 | 对称正定(SPD) |
| 是否必须选主元 | 是(否则可能全错) | 否,正定性保证主元恒正 |
| 分解的浮点运算量 | (一半) | |
| 存储量 | ( 与 ) | 约 (只存 ) |
| 解方程总运算量 | ||
| 增长因子 | 需关注 | 天然受控( 量级) |
| 额外信息 | 无 | 分解失败即判定矩阵不正定 |
| numpy 函数 | np.linalg.cholesky(numpy 无 LU) | np.linalg.cholesky |
定理 11.8(条件数与误差放大) 设 非奇异,,。若右端项有扰动 ,则
证明:由 得 ,故 ;又 ,即 。两式相乘即得。
完整推导与 的全部性质见 11-2-范数与条件数。
定理 11.9(高斯消元的向后稳定性 / Wilkinson) 设 是用带部分选主元的高斯消元在浮点算术下解 得到的结果。则存在 使得
其中 是增长因子, 是一个不大的常数(与 无关)。
证明思路(三步):(1) 每一步消元的浮点运算可以用定理 11.2 的模型写成"精确运算 + 相对误差 ";(2) 把所有反向累积的舍入误差等价地解释为对原矩阵 的扰动 ,扰动的每一项量级为 乘以该步涉及的元素;(3) 用增长因子 把元素量级统一放大到 ,并用 步数求和。
意义:因为 实践中小、 在双精度下通常远小于 ,所以高斯消元实际算的是"几乎同一个问题"的精确解。于是由定理 11.8,
适用条件:这些结论只在选了主元时成立。不选主元的高斯消元不是向后稳定的(本篇 §2.2 的反例中 ,此时 ,界完全失效)。
定理 11.10(solve 优于 inv) 设 。用 LU 分解解一个右端项需要约 次浮点运算;显式求出 再乘 需要约 次——约 4 倍。精度上,前者误差界为 量级,后者约放大到 量级。
证明思路(误差部分):解方程经过一次 LU 分解(向后误差 );而显式求逆要解 个右端项,每个都带 的向后误差,逆矩阵的条件数又与 同阶,误差在"求逆 + 相乘"两步中被放大两次,累积出 。
结论:除了一类特殊场合(需要对很多个不断变化的右端项反复求解,或确实需要 的元素本身),永远用 solve,不要用 inv。 数值线性代数的第一戒律。
四、计算方法与步骤
4.1 手工/程序实现部分选主元 LU 的步骤
- 初始化 ,,,置换向量 。
- 对 :
- 选主元:找 。
- 若 小于给定阈值(如 ),判定矩阵数值奇异并停止。
- 换行:交换 的第 行;交换 的第 项;交换 第 行的前 个元素(只换已算出的部分)。
- 消元:对 计算乘子
- 得到 , 的上三角部分即消元结果, 的严格下三角部分存乘子。
4.2 用 解
- 求 (一次分解,可复用)。
- 置换右端项:(按 重排 )。
- 前代解 :
- 回代解 :
4.3 Cholesky 的步骤( 对称正定)
- 检验对称性:
np.allclose(A, A.T)。 - 对 :
- 若某步根号内 ,说明矩阵不是正定(或已被舍入误差破坏),报错。
- 解方程:前代 ,回代 。
4.4 解完之后的数值体检(养成习惯)
- 算残差:,看 是否在 量级。
- 估条件数:
np.linalg.cond(A)(双精度下若 ,结果基本不可信)。 - 看是否选主元:如果用的是手写代码,确认每步都做了行交换。
- 必要时迭代改进(iterative refinement):算 (用更高精度算残差),解 ,更新 。当 时它可以显著改善前向误差。
五、例题
例题 1(本篇核心):小主元的危害与选主元的拯救
设
在双精度浮点下分别用「不选主元」与「部分选主元」的高斯消元求解,并给出误差与增长因子。
第 0 步:求真解(精确算术)
方程组
用第 2 式减第 1 式:
所以在双精度下真解的两个分量都四舍五入为 (到 16 位有效数字):
第 1 步:不选主元的消元(手工逐步)
主元 。乘子
行变换 :
- 位置 :。
- 位置 :。
现在看双精度的表现。 且 ,所以 恰好可精确表示。在 这个量级上,相邻浮点数的间隔是
加 远小于间隔的一半,于是 被舍入回 。
- 右端项:,同样舍入为 。
- 右端项 不变:。
消元后的上三角系统是
回代:
得到
相对误差(2-范数)
正确解是 ,算法给出 —— 第一个分量完全错误。
第 2 步:部分选主元的消元(手工逐步)
第 1 步:当前列主元以下的最大绝对值元素是 ,位于第 2 行。交换第 1、2 行:
注意右端项必须一起交换——忘记这一步会得到完全错误的答案。
乘子
行变换 :
- :。
- :。因为 ,所以
- 右端项:,同样舍入为 。
消元后的系统
回代:
与真解完全一致(在双精度意义下)。
第 3 步:两种做法的对比
| 对比项 | 不选主元 | 部分选主元 |
|---|---|---|
| 第 1 步主元 | ||
| 乘子 | ||
| 是否满足 | 否 | 是 |
| 消元后 | ||
| 增长因子 | ||
| 计算出的解 | ||
| 相对误差(2-范数) | (机器精度) | |
| 结论 | 完全失败 | 完全正确 |
第 4 步:这个例子的"问题"到底好不好?
算一下条件数。,且
用 -范数:
条件数只有 4 —— 这是一个非常好的问题(对比:双精度能处理到 )。所以 71% 的误差完全归咎于算法:不选主元的高斯消元在这里不是向后稳定的。
这就是本章想让你记住的分工
说"问题很简单", 说"算法很糟糕"。前向误差 条件数 向后误差,而这里的向后误差被 放大到远超 ,界彻底失效。
例题 2:手工做一次 Cholesky 分解并与 LU 对照
设
先验证对称正定: 对称;顺序主子式
三个顺序主子式全正,故 对称正定(6-4-对称矩阵与正定矩阵)。
Cholesky 逐步计算
:
:
:
所以
验证:
与 LU 对照:不带主元的消元给出
即 ,其中 。于是
与上面一致。注意 ,即 Cholesky 的上三角因子就是 的缩放——这是"对称正定矩阵只需存一半"的根本原因。
五之补一、知识点补强:浮点、小主元、增长因子与向后误差
为什么要单独补这一节
§一~§四 已经把定义与定理给全了,但"数值稳定性"是一门必须自己算过一遍的学问。下面把这几个最容易含混的知识点摊开,每条都给出"手算就能验证"的形式,再用六道新增例题把它们串成一条线:浮点 → 小主元 → 增长因子 → 向后误差 → 条件数 → 算法选择。
补 1.1 机器精度不是神秘常数,而是一个可以手算的间隔
(1)ulp 公式。 双精度浮点数在区间 上是等间距的,间距(unit in the last place)为
由此立刻得到三个可以当场手算的数:
| 位置 | 阶码 | 手算过程 | numpy 实测 | |
|---|---|---|---|---|
np.spacing(1.0) = 2.220446049250313e-16 | ||||
np.spacing(1e16) = 2.0 | ||||
np.spacing(1e20) = 16384.0 |
这张表就是""的全部内容: 附近的间隔是 ,而任意更大的数 ,其间隔按 成比例放大。所以机器精度不是"绝对误差上限",而是相对误差上限。
(2)为什么误差界用 而不是 ? 因为 IEEE 754 采用"舍入到最近":最大绝对误差是半个间隔,
是"间隔", 是"半个间隔"。本库统一约定:估计误差时用 ,讨论"相邻浮点数间隔"时用 。 二者差 2 倍,混用会让误差界虚高或虚低一倍——这是文献里最常见的口径不一致。
(3)十进制有效数字的手算。
即双精度约有 15.95 位十进制有效数字(np.finfo(float).precision 保守返回 15,官方文档口径是"至少 15 位")。工程上常说"16 位",是把它向上取整了;做误差估计时用 更安全。
(4)能精确表示的整数上界是 。 尾数 53 位意味着所有绝对值不超过 的整数都能精确表示(整数没有"小数位"要舍),而 不行:它与 、 等距,按"遇中取偶"舍入回 :
这条结论马上要用:当 逼近 时, 与 在浮点里就无法区分了,而 恰好是高斯消元的乘子。
三个手算基准(建议背下来)
1. :一次浮点运算的相对误差上限(定理 11.1、11.2)。
2. : 附近两个相邻浮点数的间隔。
3. :"加不上去"的判据(例:)。
补 1.2 小主元为什么危险:危害的正确尺度是 而不是
§2.2 用 例子定性说明了灾难性抵消。现在把它写成定量公式,这样你才能判断"多大的主元算小"。
设 的左上角元素是 (其余元素是 量级),不选主元时第 1 步乘子是 。回代的最后一步(算 )是
其中分子 的真值是 (否则 就不是 了)。但 是若干个 的数相减得来的,而浮点相减的误差是绝对的 ,于是
结论:判断小主元是否致命,要看 (等价地看乘子 与 的比值),而不是看 是否等于 。
| 乘子 | 的相对误差量级 | 双精度下的实际表现 | ||
|---|---|---|---|---|
| 与正常舍入无异,看不出问题 | ||||
| (题目 8 实测 ) | 开始丢 2~3 位有效数字 | |||
| 有效数字全丢 | ||||
| 分子被舍成 | 直接算成 | |||
| 分子被舍成 | 直接算成 (本篇反例) |
"主元不为 就安全"是错的,"主元大于 就安全"也是错的
正确的判据有两条,任选其一:
1. 看乘子: 是否远大于 (部分选主元把这一项强制压到 );
2. 看比值: 是否可与 相比(一旦 ,误差界彻底失效)。
实践中永远选主元最省心:额外代价只有 次比较,相比 的消元可以忽略。
补 1.3 增长因子 :算法自己的"放大器读数"
定义(与定理 11.6 一致,这里给出读法)
它是消元过程中出现过的最大元素与原始最大元素之比,只由算法与矩阵共同决定。三个必须记住的读数:
| 情形 | 的理论界 | 实践中的典型值 | 该怎么理解 |
|---|---|---|---|
| 不选主元 | 无界(可以任意大) | 多数矩阵仍很小,但存在致命反例 | 本篇 例子 、 例子 |
| 部分选主元 | (Wilkinson) | 几乎总是 , 上千时实测常 | 是最坏情形,需要刻意构造才取到 |
| 完全选主元 | 小得多( 量级) | 极小 | 代价是 次比较,实践中不用 |
| Cholesky(对称正定) | 根本不需要选主元,这是它快一倍的隐藏红利 |
为什么 出现在误差界里? 因为定理 11.9 的向后误差界是
来自"消元一共做了 次行变换", 来自"每次变换舍入一次",而 是元素量级在这个过程中被放大的倍数——没有它就说不清" 被放大了多少倍"。当 (本例 )时,界彻底失效,算法给出的解可以是任意糟糕的。
补 1.4 向后误差的"动手版":算出的解到底是哪个问题的精确解?
§1.5 讲了向后误差的思想。这里给出可直接手算的构造,它把"算出的解是某个微小扰动问题的精确解"这句话变成一行公式。
定理(向后误差的标准构造) 设 非奇异, 是任意一个"候选解", 是它的残差。取
则 精确地满足 ,并且在这个"秩 1 扰动"的范围内, 是最小的,其值为
证明:直接代入即可:
范数部分: 是秩 1 矩阵 除以标量 ;秩 1 矩阵 的 2-范数是 (唯一非零奇异值是 ),故
最小性:若要求 ,则 是硬性约束,于是 ,上面的 恰好取到等号。
怎么用它? 把算法给出的 代进去,算出相对向后误差
- 若 :算法向后稳定,"它解的是几乎同一个问题",剩下的误差全是条件数的锅。
- 若 (本例题 7 会算出这个数):算法解的是一个差 20% 的问题,无论条件数多好都救不回来。
这个构造为什么是"数值稳定性的显微镜"
它把"算法好不好"这个模糊问题,变成了一个可以算出来的数 。于是你可以对同一个矩阵、同一个 ,比较不同算法的 :
solve的 ,inv@b的 大一个量级,不选主元的消元可以给出 。这是把"稳定性"量化、可比较、可测试的关键一步。
补 1.5 为什么 solve 优于 inv:运算量与精度两本账
第一本账:运算量(flop 计数)。
高斯消元第 步要对 的子矩阵做一次秩 1 修正,每步约 次"乘加"(乘加算 2 flops),故分解的总量是
| 任务 | flop 数 | 时的量级 | 说明 |
|---|---|---|---|
| (含选主元) | 选主元只加 ,可忽略 | ||
| 前代 + 回代(一个右端项) | 只占分解的 | ||
solve(A, b) 合计 | 一次分解 + 两次三角形求解 | ||
| 显式求 | 分解后再解 个右端项() | ||
inv(A) @ b 合计 | 再多一次矩阵乘向量 | ||
| 比值 | 求逆比解一个方程组贵约 4 倍 |
第二本账:精度。 这是更重要的理由。
- 解方程只经过一次向后稳定过程:LU 分解(带选主元)与两次三角形回代的向后误差都是 ,于是前向误差 。
- 显式求逆的误差要放大两次:求 时,每个元素都带着 的相对误差,而 (见 11-2-范数与条件数 的 (P7)),所以 自身的相对误差已经是 ;再做一次矩阵乘法,误差界乘上 :
差一个 因子。 当 时,这就是 8 位有效数字的差别(例题 8 的实验里实测到约 25 倍的误差差、残差差 倍)。
三个例外场合(可以正当地求逆)
1. 你确实需要 的元素本身(例如要读协方差矩阵、要算 );
2. 需要对大量不断变化的右端项反复求解(此时一次性求逆反而省时间,但精度仍差);
3. 矩阵很小()且你只想写一行代码。
除这三种情况,永远用
solve(或cholesky+ 两次三角求解)。数值线性代数的第一戒律。相关背景见 2-4-矩阵运算与逆矩阵:那里讲的是 的代数定义与 Gauss–Jordan 求逆,本篇讲的是它的数值代价;两者合起来才说明"为什么教科书里满页 ,而生产代码里几乎见不到它"。
五之补二、新增例题(六道)
题目 3(手算数字题): 小主元——不选主元 vs 部分选主元,中间结果全部写出
设 ,
(提示:双精度下 被存成 ,所以实际送入求解器的是 。)
请在双精度下分别用「不选主元」与「部分选主元」的高斯消元求解,逐步写出每一步的主元、乘子、中间矩阵与右端项,最后给出两种做法的解、相对误差、增长因子与向后误差,并解释差别。
这个矩阵是本篇 反例的"升级版":它的条件数很小,但不选主元依然会算错。
第 1 步:真解与问题的条件数(判断"问题难不难")
先求真解。取 ,直接验证
所以真解 ,而 在双精度里被存成 (因为 )。
再算条件数(判断问题是否良态):
(伴随矩阵由代数余子式矩阵转置得到; 项可以忽略。)于是
条件数只有 ( 只有 )——这是一个非常好的问题。 所以下面的任何错误都只能归咎于算法。与此对照,双精度能可靠处理到 。
第 2 步:不选主元的消元(逐步手算,全部中间结果)
第 1 步的主元是 (没有选主元,所以只能用它)。乘子
先看 的量级:在 附近相邻浮点数的间隔是 (补 1.1 的第 3 行),也就是说任何 的加数都会被扔掉。逐项做行变换 :
- 位置 :(消元成功)。
- 位置 :。因为 ,舍入得
- 位置 :(这一项完好无损,因为 ,乘子乘上去还是 )。
- 右端项:。
第 3 行不变()。消元一步后的系统是
第 2 步的主元 ,乘子
行变换 :
- 位置 :。
- 位置 :(,加不上去)。
- 右端项:。
于是
注意 是个"好乘子"(),所以第 2 步的消元是干净的: 位置上的 被保住了。危险全部来自第 1 步那个 。
第 3 步:不选主元的回代——错误发生的准确位置
(分子里的 在 的量级上被舍掉了,但因为分子分母同量级, 恰好仍然正确。)
这里就是错误的源头:分子 的真值应当只有 量级(因为 是 ,而分母是 ),具体地 。但 是三个 的数相减得到的,浮点相减的绝对误差是 ——误差比真值大 4 个数量级,于是 (连 本身都已经被存成 了),
答案:
第 4 步:部分选主元的消元(逐步手算)
第 1 步:看第一列主元以下的部分 ,绝对值最大的是 ,位于第 2 行。交换第 1、2 行(右端项必须一起交换):
新主元 ,乘子
行变换 :
- :。
- :()。
- :(保留下来了,而且是"乘子上不去"的正确量级)。
- 右端项:。
第 3 行不变。第 2 步主元:第 2 列主元以下部分为 ,取第一个( 取首个最大者),:
于是
回代:
关键对比:不选主元时算 的那一步,分子里出现的是 (两个 的数,真值 );选主元后,同一个位置的分子变成了 (三个 的数,真值 )。选主元的真正作用,是让回代时不再需要"从 的数里榨出 的信息"。
第 5 步:两种做法的对照表
| 对比项 | 不选主元 | 部分选主元 |
|---|---|---|
| 第 1 步主元 | ||
| 乘子 | ||
| 是否满足 | 否 | 是 |
| 消元后 | ( 被舍掉) | ( 被舍掉,无害) |
| 消元后 | ||
| 增长因子 | ||
| 计算的解 | ||
| 相对误差(2-范数) | ||
| 相对向后误差 | ||
| 结论 | 算法失败(问题本身 很好) | 完全正确 |
第 6 步:为什么这个例子的诊断结论是"算法烂"而不是"问题难"
- 条件数 、:问题是良态的,哪怕丢 1 位有效数字都算多。
- 增长因子 :算法把元素放大了 20 个数量级。
- 由定理 11.9 的界 ,这里 ,界彻底失效——这正是"不选主元的高斯消元不是向后稳定的"的具体含义。
- 用补 1.4 的公式实测:不选主元的相对向后误差 (解的是差 的问题),选主元为 。
题目 4(手算数字题):机器精度、ulp 与浮点误差的手算
不借助任何计算机,回答下列问题,然后与 numpy 的实测对照。
(1) 双精度下 附近相邻两个浮点数的间隔是多少? 附近呢? 附近呢?
(2) 最大的"所有整数都能精确表示"的整数是多少? 等于多少?
(3) 双精度大约有几位十进制有效数字?请写出推导。
(4) 预测下列式子的输出:
1 + 1e-16 == 1、1 + 1.2e-16 == 1、(1e16 + 1.0) - 1e16、1e16 - 1e16 + 1.0。
第 1 步:用 ulp 公式手算三个间隔
补 1.1 的公式: 时 。
- :,。
- :,故 ,。
- :,故 ,。
第 2 步: 与"遇中取偶"
尾数 53 位 的整数全部精确。而
落在 与 的正中间,按"舍入到最近、遇中取偶"规则取尾数为偶数的那一侧,即 。这就是"大整数加 1 没有反应"的原因,也是补 1.2 里" 判据"的物理来源。
第 3 步:十进制有效数字
即约 位。取 位是保守口径(np.finfo(float).precision 返回 15),说"16 位"是乐观口径。做误差估计时按 位算,留出的余量正好覆盖"舍入到最近"以外的额外消耗。
第 4 步:四个式子的预测
1 + 1e-16 == 1:,预测True。1 + 1.2e-16 == 1:,加数超过了"半个间隔"的判定阈值,预测False(结果约为 )。(1e16 + 1.0) - 1e16: 附近的间隔是 ,加 落在正中间,遇中取偶 被存成 ,再减 得0.0。1e16 - 1e16 + 1.0:先算减法得 ,再加 得1.0。
第 4 步的结论(浮点加法不满足结合律的极简例子):
第 5 步:numpy 实测对照
import numpy as np
print(np.spacing(1.0)) # 2.220446049250313e-16
print(np.spacing(1e16)) # 2.0
print(np.spacing(1e20)) # 16384.0
print(float(2**53) + 1.0 == float(2**53)) # True
print(float(2**53) + 2.0) # 9007199254740994.0
print(np.log10(1 / (np.finfo(float).eps / 2))) # 15.954589770191003
print(1 + 1e-16 == 1) # True
print(1 + 1.2e-16 == 1) # False
print((1e16 + 1.0) - 1e16) # 0.0
print(1e16 - 1e16 + 1.0) # 1.0
四项预测全部命中。注意第 3、4 式的教训:同一个数学表达式的不同加括号顺序,可以给出 与 两个完全不同的事实——这就是并行求和、快速求和、消元行序都会影响结果的原因(10-1-图与网络 里 PageRank 的并行求和也要注意同样的坑)。
题目 5(手算数字题):条件数与误差放大的定量关系,以及 solve/inv 的运算量账本
(1) 设 ,双精度下向后误差约为 。手算:相对前向误差的量级是多少?大约损失几位十进制有效数字?
(2) 取 ,。手算 、真解 ;再取扰动 (),手算 、两侧的相对误差,并验证它用掉了误差界的百分之多少。
(3) 设 ,手算
solve与inv(A) @ b的 flop 数之比(写出求和推导)。(4) 若 ,比较两条路线的相对误差量级。
第 1 步:由"条件数 × 向后误差"估前向误差
Wilkinson 账本(§1.5)说
十进制有效数字从 位降到
"条件数 就损失 位有效数字"这条经验法则的来源就是这一步,它的严格版本是相对前向误差 ,把 与 一起折算才得到"损失 位"。
第 2 步:一个可以完全手算的 例子
取 ,则
现在扰动第二个分量:,。
两侧的相对误差:
定理 11.8 给出的界:
界的利用率 。 这不是巧合:把界逐项算一遍会发现
(第一个因子为 因为 正好在最大奇异方向;第二个因子为 因为 的两个分量相等。)界是最优的,但只有当 落在最小奇异方向、 落在最大奇异方向时才取到等号——这就是 11-2-范数与条件数 里"误差放大有方向性"的定量版。
第 3 步:运算量的手算推导
消元第 步()要对剩下的 子矩阵做一次秩 1 修正,每个元素一次乘加(乘 加 flops):
(用了 。)
solve:一次分解 + 前代 + 回代 :
inv:分解一次 ,再解 个右端项(每个 ,即 ),最后乘 再加 :
- 比值:
代入 :
比值 ,约 4 倍(与例题 8 的实测一致)。
第 4 步: 时两条路线的精度
| 路线 | 误差界来源 | 相对误差量级 | 相当于还剩几位有效数字 |
|---|---|---|---|
solve(A, b) | 位 | ||
inv(A) @ b | 负的,结果毫无意义 |
也就是说:当 时,inv 路线的理论界已经彻底失效(界 表示"连符号都可能错"),而 solve 还能给你 6 位有效数字。这与例题 8 的实测趋势一致(实测中 inv@b 的前向误差是 solve 的约 25 倍,残差则差了 倍)。
"求逆的误差界是 "这句话的适用条件
它是最坏情形的一阶界,实践中常常达不到(因为误差有抵消、每个右端项的条件数还可能小于 )。所以:
- 不要用它预测"一定错多少位",只能用它判断"哪条路线更危险";
- 实测残差与实测前向误差才是最终依据(例题 8 的做法)。
题目 6(证明题):严格对角占优 不选主元的高斯消元也安全,且
设 严格对角占优:对每个 ,
证明:不选主元的高斯消元
(1) 每一步的主元都非零;
(2) 所有乘子满足 ;
(3) 增长因子 。
并说明去掉"严格"两个字之后,哪一条会失效。
第 1 步:把命题变成一个可以归纳的引理
关键引理:严格对角占优矩阵做一步高斯消元(不选主元)后,其 的 Schur 补仍然严格对角占优。
只要这个引理成立,归纳法立刻给出 (1)(2)(3):每一步的主元都是某个严格对角占优矩阵的对角元,而严格对角占优 对角元非零(因为 )。
第 2 步:证明引理(核心的三角不等式估计)
记号: 是主元(严格对角占优保证 ),乘子 ,消元后的新元素()
要证:对每个 ,。
下界方向(对 用反向三角不等式):
上界方向(对 用正向三角不等式,并提取公因子):
对第 1 行用严格对角占优:。代入:
对第 行用严格对角占优:。于是
引理得证。(注意两个不等号:第一个是严格的,来自"严格对角占优",这一步的严格性正是整个论证的支点。)
第 3 步:推出 (1)(2)(3)
- (1) 主元非零:归纳假设当前矩阵严格对角占优,则 ,故 。
- (2) 乘子:,而 ,故 。每一步同理。
- (3) 增长因子:由第 2 步的上界
对每一步的每个元素成立,于是 。
第 4 步:去掉"严格"会怎样(条件为什么不能省)
| 条件 | 结论 | 反例 |
|---|---|---|
| 严格对角占优() | 主元非零、、,可以不选主元 | —— |
| 弱对角占优(允许等号,即 ) | 可能遇到 (如 的两个行和都等于对角元的绝对值 ),必须选主元 | |
| 一般矩阵 | 主元可以为 或极小, 无界 | 本篇 、 反例(、) |
这条定理的实用价值
差分法 / 有限元离散椭圆型方程(Poisson 方程等)得到的矩阵天然严格对角占优(对角元来自"自身"项的系数,非对角元来自"邻居"项,符号相反且和更小)。所以在这类问题上:
- 不选主元也安全,、,误差界完美成立;
- 这也是 Jacobi / Gauss–Seidel 迭代一定收敛的原因(11-3-迭代方法与预条件 定理 11.3.3 用的是同一个对角占优条件)。
反过来说:"要不要选主元"不该凭感觉,而该看矩阵的结构——严格对角占优、对称正定(用 Cholesky)这两类可以不选;其余一律选。
题目 7(证明题+构造):算出的解是哪个扰动问题的精确解——把向后误差算成一个数
(1) 证明:对任意 ,取 ()就有 ,且 ,并且这个 在满足约束 的所有 中范数最小。
(2) 把它用到本篇两个反例上: 的 与 的 ,各自算出相对向后误差。
(3) 用这个数说明:"不选主元的高斯消元不是向后稳定的"到底是什么意思。
第 1 步:验证方程(直接代入)
第 2 步:范数公式
是秩 1 矩阵的标量倍。秩 1 矩阵 只有一个非零奇异值 ,所以
第 3 步:最小性(为什么它是"最小的扰动")
任何满足 的 必须满足 。由诱导范数的基本不等式
而 恰好取到等号,故它是最小的。 这个最小的 就叫相对向后误差。
第 4 步:代入两个反例
反例(,,):
反例(题目 3 的数据,):
(这一组数在例题 8 的实验中会逐字复现。)
第 5 步:结论——"不稳定"的定量含义
| 解 | 相对残差 | 相对向后误差 | 读法 |
|---|---|---|---|
| 选主元() | 扰动为零,"解的就是原问题" | ||
| 不选主元() | 解的是一个差了 22% 的问题 | ||
| 不选主元() | 解的是一个差了 62% 的问题 |
"算法向后稳定"的意思是:。 上面两个 分别比它大 与 个数量级——这就是"不选主元的高斯消元不是向后稳定的"这句话的全部内容。同时也验证了 §1.5 的诊断流程:这里的残差不小(、),所以按"残差大 ⟹ 查算法"的原则,应当先去查算法,而不是去怪条件数( 的条件数只有 )。这个"残差大就查算法"的判据,在 11-3-迭代方法与预条件 里判断迭代法是否收敛到正确解时同样适用。
题目 8(numpy 数值实验):从机器精度到 solve/inv 的六组实验
用一段 numpy 代码,把本篇的核心结论全部实测一遍:机器精度与 ulp、、 小主元的两种解法与增长因子、小主元危害的阈值效应、向后误差的构造、
solve与inv的精度对比、条件数与前向误差的关系。要求代码只用 numpy,并且输出与下表一致。
第 1 步:代码
import numpy as np
# ---------- (a) machine epsilon and ulp ----------
eps_mach = np.finfo(float).eps
u = eps_mach / 2
print("np.finfo(float).eps =", eps_mach)
print("u = eps/2 =", u)
print("np.finfo(float).precision =", np.finfo(float).precision)
print("log10(1/u) = %.6f" % np.log10(1.0 / u))
print("1 + 1e-16 == 1 :", 1.0 + 1e-16 == 1.0)
print("1 + 1.2e-16 == 1 :", 1.0 + 1.2e-16 == 1.0)
print("np.spacing(1.0) =", np.spacing(1.0))
print("np.spacing(1e16) =", np.spacing(1e16))
print("np.spacing(1e20) =", np.spacing(1e20))
print("float(2**53) + 1.0 == float(2**53) :", float(2**53) + 1.0 == float(2**53))
print("float(2**53) + 2.0 :", float(2**53) + 2.0)
print("(1e16 + 1.0) - 1e16 =", (1e16 + 1.0) - 1e16)
print("1e16 - 1e16 + 1.0 =", 1e16 - 1e16 + 1.0)
# ---------- (b) 3x3 tiny pivot: no pivot vs partial pivot ----------
def gauss_elim(A, b, pivot=True, verbose=False):
"""Solve A x = b by Gaussian elimination. pivot=False: no row exchange."""
A = np.array(A, dtype=float, copy=True)
b = np.array(b, dtype=float, copy=True)
n = b.size
for k in range(n - 1):
if pivot:
p = k + int(np.argmax(np.abs(A[k:, k]))) # partial pivoting
if p != k:
A[[k, p], :] = A[[p, k], :]
b[[k, p]] = b[[p, k]]
if verbose:
print(" step %d: swap row %d <-> %d, b = %s" % (k + 1, k + 1, p + 1, b))
if A[k, k] == 0.0:
raise ZeroDivisionError("zero pivot, pivoting is required")
m = A[k + 1:, k] / A[k, k] # multipliers
A[k + 1:, k:] -= np.outer(m, A[k, k:]) # elimination
b[k + 1:] -= m * b[k]
if verbose:
print(" step %d: pivot = %r, multipliers = %s" % (k + 1, A[k, k], m))
print(" A =\n%s" % np.array2string(A, precision=6))
print(" b = %s" % b)
x = np.zeros(n) # back substitution
for i in range(n - 1, -1, -1):
x[i] = (b[i] - A[i, i + 1:] @ x[i + 1:]) / A[i, i]
return x, A, b
eps3 = 1e-20
A3 = np.array([[eps3, 1.0, 0.0],
[1.0, 2.0, 1.0],
[0.0, 1.0, 2.0]])
b3 = np.array([1.0 + eps3, 4.0, 3.0])
x3_true = np.ones(3)
print()
print("A =\n", A3)
print("b =", b3, " (1 + 1e-20 == 1.0 in double)")
print("exact x* =", x3_true)
print("cond_inf(A) = %.4f cond_2(A) = %.4f" % (np.linalg.cond(A3, np.inf), np.linalg.cond(A3, 2)))
print("1/1e-20 == 1e20 :", 1.0 / 1e-20 == 1e20, " 1/(-1e20) == -1e-20 :", 1.0 / (-1e20) == -1e-20)
print("-1e20 - 1.0 == -1e20 :", -1e20 - 1.0 == -1e20, " 2 - 1e20 == -1e20 :", 2.0 - 1e20 == -1e20)
print("\n--- no pivoting ---")
x_no, U_no, c_no = gauss_elim(A3, b3, pivot=False, verbose=True)
print(" x_hat =", x_no)
print(" relative error (2-norm) = %.6f" % (np.linalg.norm(x_no - x3_true) / np.linalg.norm(x3_true)))
print(" growth factor rho = %.4e" % (np.abs(U_no).max() / np.abs(A3).max()))
print("\n--- partial pivoting ---")
x_pi, U_pi, c_pi = gauss_elim(A3, b3, pivot=True, verbose=True)
print(" x_hat =", x_pi)
print(" relative error (2-norm) = %.4e" % (np.linalg.norm(x_pi - x3_true) / np.linalg.norm(x3_true)))
print(" growth factor rho = %.4f" % (np.abs(U_pi).max() / np.abs(A3).max()))
print(" max |multiplier| = %.4f" % max(abs(eps3 / 1.0), abs(1.0 / 1.0)))
print("\n--- threshold effect: eps -> 1e-8 ... 1e-20 (no pivoting) ---")
for e in (1e-8, 1e-14, 1e-18, 1e-20):
Ae = np.array([[e, 1.0, 0.0], [1.0, 2.0, 1.0], [0.0, 1.0, 2.0]])
be = np.array([1.0 + e, 4.0, 3.0])
xe, _, _ = gauss_elim(Ae, be, pivot=False)
print(" eps=%-7.0e 1/eps=%-9.3e x=%s rel.err=%.3e u/eps=%.3e"
% (e, 1.0 / e, np.array2string(xe, precision=6),
np.linalg.norm(xe - x3_true) / np.linalg.norm(x3_true), u / e))
# ---------- (c) backward error: construct delta A with (A + delta A) x_hat = b ----------
print("\n--- backward error: delta A = r x_hat^T / (x_hat^T x_hat) ---")
for tag, xh in (("no pivot x_hat=(0,1,1)", x_no), ("pivoting x_hat=(1,1,1)", x_pi)):
r = b3 - A3 @ xh
dA = np.outer(r, xh) / (xh @ xh)
print("%s : ||r||_2 = %.4e ||dA||_2 = %.4e ||dA||_2/||A||_2 = %.4e check = %s"
% (tag, np.linalg.norm(r), np.linalg.norm(dA, 2),
np.linalg.norm(dA, 2) / np.linalg.norm(A3, 2),
np.allclose((A3 + dA) @ xh, b3)))
A2 = np.array([[1e-20, 1.0], [1.0, 1.0]])
b2 = np.array([1.0, 2.0])
xh2 = np.array([0.0, 1.0])
r2 = b2 - A2 @ xh2
dA2 = np.outer(r2, xh2) / (xh2 @ xh2)
print("2x2 example, no pivot x_hat=(0,1): ||r||_2 = %.4e ||dA||_2/||A||_2 = %.6f"
% (np.linalg.norm(r2), np.linalg.norm(dA2, 2) / np.linalg.norm(A2, 2)))
# ---------- (d) solve vs inv ----------
print("\n--- solve vs inv (kappa_2 = 1e10, fixed seed) ---")
rng = np.random.default_rng(2026)
n = 300
Q, _ = np.linalg.qr(rng.standard_normal((n, n)))
A = (Q * np.logspace(0, -10, n)) @ Q.T
A = (A + A.T) / 2
x_exact = np.ones(n)
b = A @ x_exact
x_solve = np.linalg.solve(A, b)
x_inv = np.linalg.inv(A) @ b
rel = lambda v: np.linalg.norm(v - x_exact) / np.linalg.norm(x_exact)
print("n = %d, cond_2(A) = %.4e" % (n, np.linalg.cond(A)))
print("solve : fwd err = %.4e rel residual = %.4e" % (rel(x_solve), np.linalg.norm(b - A @ x_solve) / np.linalg.norm(b)))
print("inv@b : fwd err = %.4e rel residual = %.4e" % (rel(x_inv), np.linalg.norm(b - A @ x_inv) / np.linalg.norm(b)))
print("difference of the two solutions = %.4e" % np.linalg.norm(x_solve - x_inv))
print("kappa*u = %.4e" % (np.linalg.cond(A) * u))
print("flops: solve = 2/3 n^3 + 2 n^2 = %.4e ; inv = 8/3 n^3 + 2 n^2 = %.4e ; ratio = %.2f"
% (2 / 3 * n**3 + 2 * n**2, 8 / 3 * n**3 + 2 * n**2,
(8 / 3 * n**3 + 2 * n**2) / (2 / 3 * n**3 + 2 * n**2)))
# ---------- (e) condition number vs error amplification ----------
print("\n--- residual is tiny while the error grows with kappa ---")
for k in (4, 8, 12, 14):
Q, _ = np.linalg.qr(rng.standard_normal((40, 40)))
Ak = (Q * np.logspace(0, -k, 40)) @ Q.T
Ak = (Ak + Ak.T) / 2
xb = np.ones(40)
bb = Ak @ xb
xh = np.linalg.solve(Ak, bb)
fwd = np.linalg.norm(xh - xb) / np.linalg.norm(xb)
print("kappa=1e%-2d fwd err = %.4e rel residual = %.4e fwd/(kappa*u) = %.3f"
% (k, fwd, np.linalg.norm(bb - Ak @ xh) / np.linalg.norm(bb), fwd / (np.linalg.cond(Ak) * u)))
第 2 步:实测输出
np.finfo(float).eps = 2.220446049250313e-16
u = eps/2 = 1.1102230246251565e-16
np.finfo(float).precision = 15
log10(1/u) = 15.954590
1 + 1e-16 == 1 : True
1 + 1.2e-16 == 1 : False
np.spacing(1.0) = 2.220446049250313e-16
np.spacing(1e16) = 2.0
np.spacing(1e20) = 16384.0
float(2**53) + 1.0 == float(2**53) : True
float(2**53) + 2.0 : 9007199254740994.0
(1e16 + 1.0) - 1e16 = 0.0
1e16 - 1e16 + 1.0 = 1.0
A =
[[1.e-20 1.e+00 0.e+00]
[1.e+00 2.e+00 1.e+00]
[0.e+00 1.e+00 2.e+00]]
b = [1. 4. 3.] (1 + 1e-20 == 1.0 in double)
exact x* = [1. 1. 1.]
cond_inf(A) = 12.0000 cond_2(A) = 6.5880
1/1e-20 == 1e20 : True 1/(-1e20) == -1e-20 : True
-1e20 - 1.0 == -1e20 : True 2 - 1e20 == -1e20 : True
--- no pivoting ---
step 1: pivot = np.float64(1e-20), multipliers = [1.e+20 0.e+00]
A =
[[ 1.e-20 1.e+00 0.e+00]
[ 0.e+00 -1.e+20 1.e+00]
[ 0.e+00 1.e+00 2.e+00]]
b = [ 1.e+00 -1.e+20 3.e+00]
step 2: pivot = np.float64(-1.e+20), multipliers = [-1.e-20]
A =
[[ 1.e-20 1.e+00 0.e+00]
[ 0.e+00 -1.e+20 1.e+00]
[ 0.e+00 0.e+00 2.e+00]]
b = [ 1.e+00 -1.e+20 2.e+00]
x_hat = [0. 1. 1.]
relative error (2-norm) = 0.577350
growth factor rho = 5.0000e+19
--- partial pivoting ---
step 1: swap row 1 <-> 2, b = [4. 1. 3.]
step 1: pivot = np.float64(1.0), multipliers = [1.e-20 0.e+00]
A =
[[ 1.e+00 2.e+00 1.e+00]
[ 0.e+00 1.e+00 -1.e-20]
[ 0.e+00 1.e+00 2.e+00]]
b = [4. 1. 3.]
step 2: pivot = np.float64(1.0), multipliers = [1.]
A =
[[ 1.e+00 2.e+00 1.e+00]
[ 0.e+00 1.e+00 -1.e-20]
[ 0.e+00 0.e+00 2.e+00]]
b = [4. 1. 2.]
x_hat = [1. 1. 1.]
relative error (2-norm) = 0.0000e+00
growth factor rho = 1.0000
max |multiplier| = 1.0000
--- threshold effect: eps -> 1e-8 ... 1e-20 (no pivoting) ---
eps=1e-08 1/eps=1.000e+08 x=[1. 1. 1.] rel.err=3.509e-09 u/eps=1.110e-08
eps=1e-14 1/eps=1.000e+14 x=[0.999201 1. 1. ] rel.err=4.615e-04 u/eps=1.110e-02
eps=1e-18 1/eps=1.000e+18 x=[0. 1. 1.] rel.err=5.774e-01 u/eps=1.110e+02
eps=1e-20 1/eps=1.000e+20 x=[0. 1. 1.] rel.err=5.774e-01 u/eps=1.110e+04
--- backward error: delta A = r x_hat^T / (x_hat^T x_hat) ---
no pivot x_hat=(0,1,1) : ||r||_2 = 1.0000e+00 ||dA||_2 = 7.0711e-01 ||dA||_2/||A||_2 = 2.2306e-01 check = True
pivoting x_hat=(1,1,1) : ||r||_2 = 0.0000e+00 ||dA||_2 = 0.0000e+00 ||dA||_2/||A||_2 = 0.0000e+00 check = True
2x2 example, no pivot x_hat=(0,1): ||r||_2 = 1.0000e+00 ||dA||_2/||A||_2 = 0.618034
--- solve vs inv (kappa_2 = 1e10, fixed seed) ---
n = 300, cond_2(A) = 1.0000e+10
solve : fwd err = 9.3123e-08 rel residual = 5.3255e-16
inv@b : fwd err = 2.2999e-06 rel residual = 1.0401e-07
difference of the two solutions = 3.9976e-05
kappa*u = 1.1102e-06
flops: solve = 2/3 n^3 + 2 n^2 = 1.8180e+07 ; inv = 8/3 n^3 + 2 n^2 = 7.2180e+07 ; ratio = 3.97
--- residual is tiny while the error grows with kappa ---
kappa=1e4 fwd err = 1.8589e-13 rel residual = 3.1138e-16 fwd/(kappa*u) = 0.167
kappa=1e8 fwd err = 5.4856e-10 rel residual = 2.5498e-16 fwd/(kappa*u) = 0.049
kappa=1e12 fwd err = 2.4775e-06 rel residual = 4.6707e-16 fwd/(kappa*u) = 0.022
kappa=1e14 fwd err = 7.6507e-04 rel residual = 2.1805e-16 fwd/(kappa*u) = 0.069
第 3 步:从输出里读出的六条结论
- 机器精度:
eps = 2.220446049250313e-16、u = eps/2 = 1.1102230246251565e-16、log10(1/u) = 15.95。np.spacing的三个值(、、)与补 1.1 的手算完全一致。 - 的"遇中取偶":
float(253) + 1.0 == float(253)是True,而+2.0有效。这是" 加不上去"的根源。 - 小主元:不选主元得到 (相对误差 ,),部分选主元得到 (误差 ,,)。中间矩阵里 与 的出现位置与题目 3 的手算逐行一致。
- 阈值效应(补 1.2 的定量判据): 时相对误差只有 (无害); 时恶化到 (约 的量级); 时 直接变成 (相对误差 )。注意 这一列:它与实际误差同步增长,这就是"正确的尺度"。
- 向后误差可以用一个数表达:不选主元的 ()与 (),选主元为 。
check = True说明构造的 确实让 成为扰动问题的精确解。 solve完胜inv:前向误差 vs (差 25 倍),相对残差 vs (差 9 个数量级),flop 比 。最后一段还演示了第 5 条结论:残差始终在 量级,而前向误差随 从 涨到 ——"残差小 ≠ 解准",两者的比值始终不超过 。
复现这段代码时的两个坑
1. 不要把 换成 之类的"更小但看着更自然"的值再期待同样结论: 与 的精确性会变(实测 精确成立,但 )。手算例子要选"乘子可以精确表示"的 。
2.
inv@b的误差不是每次都大:它依赖随机种子与矩阵结构(本例固定种子2026)。要下结论必须重复实验,而不是看一次结果。
六、应用
- 结构力学与有限元:刚度矩阵 对称正定,解 直接用 Cholesky,运算量与存储都省一半。这是有限元软件(ANSYS、Abaqus)内部的标准路径。
- 电路仿真(SPICE 类):修正节点分析(modified nodal analysis)得到的矩阵通常不对称,需要带部分选主元的 LU,并把 记录下来做稀疏重排(如 AMD、METIS 排序)以减少填充。
- 最小二乘与统计:正规方程 的系数矩阵对称正定,可用 Cholesky;但 ,所以条件数差时应该改用 QR(4-3-最小二乘逼近、11-2-范数与条件数)。
- 卡尔曼滤波:协方差矩阵 对称正定,更新步要做 Cholesky 或平方根滤波(square-root filter),以保证数值上始终保持正定。
- 机器学习:高斯过程回归要解 ,核矩阵 常常接近奇异( 可达 ),标准做法是加"抖动" 或改用 Cholesky + 迭代改进。
- 计算流体力学:流场离散后的稀疏矩阵送入直接求解器(如 MUMPS、SuperLU),核心就是带选主元的稀疏 LU;更大规模则改用迭代法(11-3-迭代方法与预条件)。
- 作为诊断工具:
np.linalg.cholesky抛LinAlgError是判定"矩阵是否正定"最可靠的数值方法——比检查特征值便宜,比检查行列式正确。
七、可运行代码示例
依赖
本节只用 numpy(
np.linalg已覆盖solve、inv、cond、cholesky、norm、matrix_rank)。仅在第 (6) 段用到 scipy 的lu,代码块前已注明。
(1) 浮点数的三个现象
import numpy as np
eps = np.finfo(float).eps
print("machine epsilon np.finfo(float).eps =", eps) # 2.220446049250313e-16
print("precision (decimal digits) =", np.finfo(float).precision) # 15
print("smallest normal =", np.finfo(float).tiny)
# 现象 A:1 + 1e-16 == 1
print("1 + 1e-16 == 1 :", 1.0 + 1e-16 == 1.0) # True
print("1 + 1e-15 == 1 :", 1.0 + 1e-15 == 1.0) # False
# 现象 B:0.1 + 0.2 != 0.3
print("0.1 + 0.2 =", repr(0.1 + 0.2)) # 0.30000000000000004
print("0.1 + 0.2 - 0.3 =", 0.1 + 0.2 - 0.3) # 5.551115123125783e-17
print("(0.1+0.2) == 0.3 :", (0.1 + 0.2) == 0.3) # False
# 现象 C:加法不满足结合律
a, b, c = 1e-16, 1.0, -1.0
print("(a+b)+c =", (a + b) + c, " a+(b+c) =", a + (b + c))
# 正确比较浮点数:np.isclose / np.allclose
print("np.isclose(0.1+0.2, 0.3) =", np.isclose(0.1 + 0.2, 0.3))
(2) 小主元的危害与部分选主元的作用
import numpy as np
def gauss_elim(A, b, pivot=True):
"""高斯消元解 A x = b。pivot=False 时不做任何行交换。"""
A = np.array(A, dtype=float, copy=True)
b = np.array(b, dtype=float, copy=True)
n = b.size
for k in range(n - 1):
if pivot: # 部分选主元
p = k + int(np.argmax(np.abs(A[k:, k])))
if p != k:
A[[k, p], :] = A[[p, k], :]
b[[k, p]] = b[[p, k]]
if A[k, k] == 0.0:
raise ZeroDivisionError("主元为 0,必须选主元")
m = A[k + 1:, k] / A[k, k] # 乘子
A[k + 1:, k:] -= np.outer(m, A[k, k:]) # 消元
b[k + 1:] -= m * b[k]
x = np.zeros(n) # 回代
for i in range(n - 1, -1, -1):
x[i] = (b[i] - A[i, i + 1:] @ x[i + 1:]) / A[i, i]
return x, A
eps_small = 1e-20
A = np.array([[eps_small, 1.0], [1.0, 1.0]])
b = np.array([1.0, 2.0])
x_true = np.array([1.0 / (1 - eps_small), 1.0 - eps_small / (1 - eps_small)])
x_no, U_no = gauss_elim(A, b, pivot=False)
x_pi, U_pi = gauss_elim(A, b, pivot=True)
x_np = np.linalg.solve(A, b)
print("不选主元 x =", x_no, " 误差 =", np.linalg.norm(x_no - x_true))
print("部分选主元 x =", x_pi, " 误差 =", np.linalg.norm(x_pi - x_true))
print("np.linalg.solve x =", x_np, " 误差 =", np.linalg.norm(x_np - x_true))
print("不选主元的 U =\n", U_no, "\n -> 增长因子约", np.abs(U_no).max() / np.abs(A).max())
print("选主元的 U =\n", U_pi, "\n -> 增长因子约", np.abs(U_pi).max() / np.abs(A).max())
print("cond(A, inf) =", np.linalg.cond(A, np.inf), " <- 问题本身良态,错在算法")
(3) inv(A) @ b 与 solve(A, b) 的对比
import numpy as np, time
rng = np.random.default_rng(2026)
n = 400
Q, _ = np.linalg.qr(rng.standard_normal((n, n))) # 随机正交矩阵
sig = np.logspace(0, -10, n) # 奇异值 1 ... 1e-10
A = (Q * sig) @ Q.T # 对称正定,kappa_2 = 1e10
A = (A + A.T) / 2
x_exact = np.ones(n)
b = A @ x_exact
t0 = time.perf_counter(); x_solve = np.linalg.solve(A, b); t1 = time.perf_counter()
x_inv = np.linalg.inv(A) @ b; t2 = time.perf_counter()
rel = lambda v: np.linalg.norm(v - x_exact) / np.linalg.norm(x_exact)
print("cond_2(A) =", np.linalg.cond(A))
print("solve : 相对误差 = %.3e 用时 %.4f s" % (rel(x_solve), t1 - t0))
print("inv@b : 相对误差 = %.3e 用时 %.4f s" % (rel(x_inv), t2 - t1))
print("残差 solve = %.3e inv = %.3e"
% (np.linalg.norm(b - A @ x_solve), np.linalg.norm(b - A @ x_inv)))
# 典型输出:solve 误差 ~1e-6,inv@b 误差大一个量级;两者残差都很小
(4) 判断病态:det 与 cond 的区别
import numpy as np
# det 极小但完全良态
A1 = 1e-20 * np.eye(4)
print("det(A1) =", np.linalg.det(A1), " cond(A1) =", np.linalg.cond(A1)) # 1e-80, 1.0
# det = 1 但极度病态
A2 = np.diag([1e8, 1.0, 1e-8])
print("det(A2) =", np.linalg.det(A2), " cond(A2) =", np.linalg.cond(A2)) # 1.0, 1e16
# Hilbert 矩阵:det 小、cond 大
for k in (3, 5, 8, 10):
H = np.array([[1.0 / (i + j + 1) for j in range(k)] for i in range(k)])
print("n=%2d det=%9.3e cond_2=%9.3e rank=%d"
% (k, np.linalg.det(H), np.linalg.cond(H), np.linalg.matrix_rank(H)))
(5) Cholesky 与 LU 的运算量对照
import numpy as np, time
rng = np.random.default_rng(7)
n = 800
B = rng.standard_normal((n, n))
A = B @ B.T + n * np.eye(n) # 对称正定
t0 = time.perf_counter(); L = np.linalg.cholesky(A); t1 = time.perf_counter()
print("Cholesky 用时 %.4f s, 分解正确性检查: %s" % (t1 - t0, np.allclose(L @ L.T, A)))
b = np.ones(n)
t2 = time.perf_counter(); x1 = np.linalg.solve(A, b); t3 = time.perf_counter()
y = np.linalg.solve(L, b); x2 = np.linalg.solve(L.T, y); t4 = time.perf_counter()
print("solve(A,b) 用时 %.4f s" % (t3 - t2))
print("Cholesky 两步骤 用时 %.4f s,与 solve 解之差 %.2e"
% (t4 - t3, np.linalg.norm(x1 - x2)))
print("A 是否正定(分解不报错即视为正定):", np.all(np.linalg.eigvalsh(A) > 0))
(6) 用 scipy 观察 的 (本示例需要 scipy:pip install scipy,因为 numpy 没有 LU 分解)
import numpy as np
from scipy.linalg import lu
A = np.array([[0.0, 1.0, 2.0],
[1.0, 1.0, 1.0],
[2.0, 1.0, 3.0]])
P, L, U = lu(A)
print("P =\n", P)
print("L =\n", L)
print("U =\n", U)
print("P @ L @ U 还原 A :", np.allclose(P @ L @ U, A))
print("L 下三角且对角为 1 :", np.allclose(L, np.tril(L)) and np.allclose(np.diag(L), 1))
print("L 的非平凡元素都 <= 1(乘子不放大):", np.all(np.abs(L[np.tril_indices(3, -1)]) <= 1))
print("A 的第一列主元为 0 -> 不选主元时的第一步行交换是必需的")
八、易错点
五个高频错误
1. 用
==比较浮点数。
0.1 + 0.2 == 0.3是False。这不是 Python 的错,是二进制的必然而已。正确做法:```python
np.isclose(a, b) # 默认 rtol=1e-5, atol=1e-8
np.allclose(A, B) # 矩阵版本
np.isclose(a, b, rtol=1e-12, atol=0) # 按需要收紧
```
注意
np.isclose的默认rtol=1e-5对数值线性代数来说过松,做算法验证时要显式收紧到 。2. 用
det判断矩阵是否奇异/病态。
np.linalg.det完全没有尺度不变性:。1e-20 * np.eye(4)的行列式是 (在双精度里已经下溢到 0 附近),但它是最良态的矩阵之一()。请用np.linalg.matrix_rank(基于 SVD 的数值秩)、np.linalg.cond(条件数)、或np.linalg.svd的奇异值比值。3. 以为"主元不为 就安全"。
本篇例题里主元是 ,不是 ,但消元结果完全错误。判据不是"是否为零",而是"是否小到让乘子 远大于 "。实践中最省事的办法是永远选主元——它的额外代价只有 。
4. 只看残差,忽略条件数。
残差小只说明向后误差小("解的是几乎同一个问题"),不说明前向误差小。若 ,残差可以小到 而解的相对误差高达 。看到"残差很小但结果明显不对"时,先算
np.linalg.cond(A)。5. 用
inv(A) @ b解方程。运算量约为
solve的 4 倍,误差界还要多一个 因子。inv只在真正需要逆矩阵元素时使用。顺带提醒:np.linalg.inv在矩阵"接近奇异但没有触发LinAlgError"时会静默返回垃圾(numpy 官方文档明确说明了这一点),必须自行用cond检查。
补充两个实现层面的坑:
- 忘记置换右端项:用
scipy.linalg.lu得到 后必须解 (即先算Pb = P @ b,再前代回代),忘了这一步会得到"看起来合理但其实错误"的结果。 - 在表格里写
\|A\|:Obsidian 的 Markdown 表格会把|当列分隔符,导致表格错乱。表格单元格内请改用\lVert A \rVert(见 11-2-范数与条件数 的对比表)。
九、练习题
练习 1(基础) (a) 用双精度手算下列各式的输出,并用 Python 验证,解释它们与"数学上应该的值"的差别:
1e16 + 1.0 - 1e16;(1e16 + 1.0) - 1e16;1e-16 + 1e-16 == 2e-16。
(b) 设 ,,,不选主元时的第一个乘子是多少?会不会出问题?
(c) 若改成 ,不选主元会怎样?请给出消元后的 与解,并总结"是否需要选主元"的正确判据。
练习 2(进阶) 对
手工完成带部分选主元的 LU 分解,写出 、、,并验证 。提示:第一步主元为 ,必须先换行。
练习 3(进阶) 证明:若 对称正定,则 的 Cholesky 分解中的每个 满足
其中 是 的 阶顺序主子矩阵(约定 )。并据此解释:Cholesky 分解失败(根号内为负)等价于矩阵不正定,因此它同时是正定性的一个数值判定算法。
练习 4(思考) 有人提出:"我的矩阵 ,条件数肯定没问题。"请构造一个 矩阵反驳他(要求 而 ),并说明"行列式为什么不是衡量奇异性的好指标"。(提示:从对角矩阵入手。)
练习 5(思考) 用定理 11.9 的界 回答:双精度下(),若 、、,向后误差的相对量级是多少?要使前向误差不超过 ,条件数最多能到多少?这与"双精度损失约 位有效数字"的经验法则是否一致?
十、常见问题 FAQ
Q1:既然浮点数这么不可靠,为什么工程上还敢用它算飞机和桥梁?
因为误差是可控的,关键在于把"问题的难度"(条件数)与"算法的质量"(向后误差)分开管理。工程问题的刚度矩阵条件数通常在 ,双精度有 16 位数字,减去 6~10 位还剩 6~10 位——足够工程精度。真正的危险来自三处:(a) 问题本身病态();(b) 用了不稳定的算法(不选主元、正规方程、inv);(c) 量纲混乱导致矩阵元素尺度差异极大。这三处都有标准对策:换算法(QR、SVD)、预条件、行平衡。
Q2:np.linalg.solve 内部到底用了什么算法?和手写消元有什么区别?
numpy 的 solve 调用 LAPACK 的 _gesv,即带部分选主元的 LU 分解 + 前代回代,和本篇讲的算法在数学上完全一致。区别在于工程实现:分块(blocked)算法以提升缓存命中率、BLAS 3 级调用、更细致的下溢/上溢处理。所以"手写一版用来理解原理"和"生产环境调用 LAPACK"并不矛盾——理解原理才知道什么时候 LAPACK 也救不了你(比如 太大)。
Q3:什么时候必须用 Cholesky 而不能用 LU?反过来呢?
用 Cholesky 的条件是对称正定且你要的是解方程或需要判定正定性。它的优势是运算量与存储都减半,且不需要选主元逻辑。若矩阵对称但不定(有正也有负特征值),Cholesky 会失败,此时可用 分解(对称但带选主元);若矩阵不对称,只能 LU。判断方法:先 np.allclose(A, A.T),再用 np.linalg.cholesky 试一下——分解成功即正定,这是最便宜的判定。
Q4:向后误差分析听起来很抽象,它对我的日常编程有什么实际影响?
三个直接用处:
- 诊断方向:残差小 + 结果错 ⟹ 去查条件数;残差大 ⟹ 去查算法/实现。
- 选择算法:向后稳定性是可以比较的算法属性。QR 向后稳定,正规方程不(它把条件数平方);LU 带主元向后稳定,不带主元不。所以选择顺序是"先看稳定性,再看速度"。
- 解释"为什么迭代改进有效":迭代改进能在 时把前向误差降到 量级,正是因为它把"前向"问题转成了"向后"问题——用高精度算残差,再解一次修正方程。
本篇小结
一、核心结论(十句话)
- 计算机里没有实数。双精度浮点数在 上等间距分布,间隔 ,一次运算的相对误差不超过 ,十进制有效数字约 位。所有 的整数精确可表示——这是" 加不上去"的根源。
- 误差分两类:舍入误差(与 同量级,不可消除,只能控制放大倍数)与截断误差(来自"有限过程替代无穷过程",与硬件无关)。数值分析的任务是让两者平衡,而不是消灭误差。
- 误差要相对地看: 的大小本身没有意义, 才有意义。本库默认"误差"指相对误差。
- 小主元的危险尺度是 (等价地是乘子 与 之比),不是 是否为零。 危害的准确位置是回代中"从 的数里榨出 的信息"那一步:浮点相减的绝对误差 被除以 ,放大成 。
- 部分选主元把乘子强制压到 :代价只有 次比较(相比 的消元可忽略),收益是让算法向后稳定。 中的 是"消元顺序"的完整记录,解方程时必须先置换右端项。
- 增长因子 是算法自己的放大器读数:分解中的元素被放大的倍数。不选主元时 无界;部分选主元理论界 、实践中常 ;Cholesky 天然 。误差界里的关键组合是 ——一旦 ,界彻底失效。
- 向后误差分析把"算法"与"问题"分开:算出的 是 的精确解,其中最小扰动满足 ()。好算法给 ,不选主元的消元可以给 (解的是差 22% 的问题)。
- 前向误差 条件数 向后误差。 由问题决定, 由算法决定。"病态"是问题的属性,"不稳定"是算法的属性——本篇的 与 反例中 只有 与 ,错的全是算法。
- Cholesky 是 SPD 情形的特权:不需要选主元、运算量与存储都减半( vs ),而且分解失败就是"不正定"的判定。对称但不定时改用 。
- 永远用
solve,不要用inv:运算量差约 4 倍( vs ),误差界还差一个 因子( vs )。inv只在"需要逆矩阵元素本身"或"大量变化的右端项"时使用。
二、易混概念对照表
| 容易混淆的一对 | 区别要点 | 一句话判别 |
|---|---|---|
| vs | 前者是相邻浮点数的间隔,后者是半个间隔(舍入到最近的最大绝对误差系数) | 估误差用 ,说间隔用 |
| 舍入误差(rounding) vs 截断误差(truncation) | 前者来自浮点表示与运算,量级 ;后者来自有限过程替代无穷过程 | 增大迭代次数:前者不变,后者变小 |
| 绝对误差 vs 相对误差 | 量纲不同;相对误差才与"准不准"相关 | " 损失 位数字"说的是相对误差 |
| 前向误差 vs 向后误差 | 前者 解与真解之差;后者 "解的是差多少的另一个问题" | 小残差只能保证向后误差小 |
| 条件数 (问题) vs 增长因子 (算法) | 只看矩阵; 还取决于消元顺序(选不选主元) | 结果错了先分清:查 cond 还是查选主元 |
| 病态(ill-conditioned) vs 不稳定(unstable) | 前者是问题属性,后者是算法属性 | 同一个良态问题可以被不稳定算法算错(本篇反例) |
| vs | 是椭球体积、受尺度影响(); 是扁度、尺度不变 | 判病态用 cond,永远不要用 det |
| 残差小 vs 解准确 | 小只说明向后误差小; 还要乘 | 残差 而误差 是完全正常的 |
| (不选主元) vs (部分选主元) | 前者在 不成立时会崩;后者永远可用 | 生产代码里没有"不选主元的 LU" |
| 部分选主元 vs 完全选主元 | 前者只在当前列里找最大( 次比较);后者在整个剩余子矩阵里找( 次) | 完全选主元理论上更稳,实践中不值得 |
solve vs inv | 前者一次分解直接求解;后者先求逆再乘(4 倍运算量 + 倍误差) | 除非要 A^{-1} 的元素,否则 solve |
| LU vs Cholesky | 适用条件:LU 对任意非奇异矩阵,Cholesky 只对对称正定;运算量 vs | 先试 cholesky,不报错就用它 |
三、动手清单(学完这一篇应该能独立完成)
- 用
np.finfo(float).eps与np.spacing(x)手算并验证任意量级的 ulp。 - 写出一个"不选主元就错、选主元就对"的 例子,并逐行列出两种做法的中间矩阵、乘子、增长因子。
- 给定 ,用 算出相对向后误差,并据此判断"是算法烂还是问题难"。
- 用 估算一条
solve语句能给出几位有效数字,并说明为什么inv路线更差。 - 判断一个给定矩阵该用 LU 还是 Cholesky,并说明能不能省掉选主元(提示:看严格对角占优或对称正定)。
这一篇与后面几篇的接口
- 向后误差的思想(本篇 §1.5、题目 7)是把"算法质量"量化的工具,在 11-3-迭代方法与预条件 里用来判断"迭代到残差 到底算不算收敛"。
- 条件数(本篇定理 11.8 只用到了它的定义)在 11-2-范数与条件数 里被彻底展开:三个范数公式、 的几何含义、Hilbert 矩阵这个经典病态例子。
- 选主元与消元顺序的代数背景在 2-2-消元法的思想(主元与解集的代数性质)与 5-2-排列与代数余子式(置换与符号)里,本篇补的是它们在浮点世界里的行为。
- 稀疏矩阵中"填充"与消元顺序的关系是 10-1-图与网络 的主题(图的填充分解),也是11-3-迭代方法与预条件 存在的原因。
相关笔记
- 11-2-范数与条件数:本篇反复用到 与 ,下一篇给出完整定义、三个矩阵范数公式、误差放大定理的严格证明,以及 Hilbert 矩阵这个经典病态例子。
- 11-3-迭代方法与预条件:当 是 的稀疏矩阵时,LU 分解产生的填充(fill-in)会吃掉全部内存,必须改用 Jacobi / Gauss–Seidel / 共轭梯度。
- 2-5-LU分解与转置置换: 与 的代数推导、置换矩阵的性质,本篇只讲它们的数值含义。
- 6-4-对称矩阵与正定矩阵:Cholesky 分解的适用条件;正定的等价条件与顺序主子式判据。
- 5-1-行列式的性质:为什么 受缩放影响这么大,以及 。
- 附录-矩阵分解总览:、、、 的适用条件与代价统一对照。
- 2-2-消元法的思想:主元、消元与解集的代数性质("把一行换成两行的线性组合不改变解集"),本篇补的是同一套操作在浮点下何时失效;想彻底理解"为什么选主元不改变答案却改变结果",两篇要连起来读。
- 2-4-矩阵运算与逆矩阵: 的代数定义与 Gauss–Jordan 求逆。那边教你怎么求逆,本篇告诉你为什么生产代码里几乎不求逆(4 倍运算量 + 多一个 因子)。
- 5-3-克莱姆法则与体积: 的体积意义。本篇反复强调" 小 病态",那篇给出 的几何解释(椭球的体积),合起来才能说清"体积小"与"扁"是两件事。
- 7-1-SVD的构造与几何意义:奇异值与"离奇异有多远"。本篇题目 7 中那个最小的扰动 正是由 给出的,完整的几何解释与 的推导在 11-2-范数与条件数。
- 12-3-多元高斯与加权最小二乘:多元高斯与加权最小二乘里频繁出现对称正定矩阵,"Cholesky 失败 不正定"是那里最常用的数值诊断手段(协方差矩阵不正定通常意味着样本不足或需要加抖动 )。
参考来源
- MIT OpenCourseWare 18.335J Introduction to Numerical Methods(Steven G. Johnson):浮点算术、向后误差分析、条件数与稳定性 —— https://ocw.mit.edu/courses/18-335j-introduction-to-numerical-methods-spring-2019/
- MIT OpenCourseWare 18.06 Linear Algebra(Gilbert Strang):消元、主元、 的课程视角 —— https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/
- numpy 官方文档
numpy.linalg.solve(LAPACK_gesv、满秩要求、与lstsq的分工) —— https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html - numpy 官方文档
numpy.linalg.inv(接近奇异时不报错、用cond检测病态、10**k损失 k 位有效数字的经验法则) —— https://numpy.org/doc/stable/reference/generated/numpy.linalg.inv.html - numpy 官方文档
numpy.finfo(eps = 2**-52 ≈ 2.22e-16、precision、smallest_normal) —— https://numpy.org/doc/stable/reference/generated/numpy.finfo.html - SciPy 官方文档
scipy.linalg.lu("Compute LU decomposition of a matrix with partial pivoting",) —— https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.lu.html - 教材(文字来源):Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley–Cambridge Press, 2016, §2.6(Elimination = Factorization: )与 §11.1;Gene H. Golub & Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §3.3(小主元与部分选主元)、§4.2(Cholesky);Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, 第 9 章(LU 的增长因子与向后误差);Lloyd N. Trefethen & David Bau, Numerical Linear Algebra, SIAM, 1997, Lecture 20(小主元示例)、Lecture 15(条件数)