w wyl123ly 的博客
MD

11-1-数值稳定性与LU

111 KB 2026.10.11 原文件

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 的步骤

  1. 初始化 ,,,置换向量 。
  2. 对 :
  3. 选主元:找 。
  4. 若 小于给定阈值(如 ),判定矩阵数值奇异并停止。
  5. 换行:交换 的第 行;交换 的第 项;交换 第 行的前 个元素(只换已算出的部分)。
  6. 消元:对 计算乘子

  1. 得到 , 的上三角部分即消元结果, 的严格下三角部分存乘子。

4.2 用 解

  1. 求 (一次分解,可复用)。
  2. 置换右端项:(按 重排 )。
  3. 前代解 :

  1. 回代解 :

4.3 Cholesky 的步骤( 对称正定)

  1. 检验对称性:np.allclose(A, A.T)。
  2. 对 :

  1. 若某步根号内 ,说明矩阵不是正定(或已被舍入误差破坏),报错。
  2. 解方程:前代 ,回代 。

4.4 解完之后的数值体检(养成习惯)

  1. 算残差:,看 是否在 量级。
  2. 估条件数:np.linalg.cond(A)(双精度下若 ,结果基本不可信)。
  3. 看是否选主元:如果用的是手写代码,确认每步都做了行交换。
  4. 必要时迭代改进(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 倍

第二本账:精度。 这是更重要的理由。

  1. 解方程只经过一次向后稳定过程:LU 分解(带选主元)与两次三角形回代的向后误差都是 ,于是前向误差 。
  2. 显式求逆的误差要放大两次:求 时,每个元素都带着 的相对误差,而 (见 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. 1 + 1e-16 == 1:,预测 True。
  2. 1 + 1.2e-16 == 1:,加数超过了"半个间隔"的判定阈值,预测 False(结果约为 )。
  3. (1e16 + 1.0) - 1e16: 附近的间隔是 ,加 落在正中间,遇中取偶 被存成 ,再减 得 0.0。
  4. 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 步:从输出里读出的六条结论

  1. 机器精度:eps = 2.220446049250313e-16、u = eps/2 = 1.1102230246251565e-16、log10(1/u) = 15.95。np.spacing 的三个值(、、)与补 1.1 的手算完全一致。
  2. 的"遇中取偶":float(253) + 1.0 == float(253) 是 True,而 +2.0 有效。这是" 加不上去"的根源。
  3. 小主元:不选主元得到 (相对误差 ,),部分选主元得到 (误差 ,,)。中间矩阵里 与 的出现位置与题目 3 的手算逐行一致。
  4. 阈值效应(补 1.2 的定量判据): 时相对误差只有 (无害); 时恶化到 (约 的量级); 时 直接变成 (相对误差 )。注意 这一列:它与实际误差同步增长,这就是"正确的尺度"。
  5. 向后误差可以用一个数表达:不选主元的 ()与 (),选主元为 。check = True 说明构造的 确实让 成为扰动问题的精确解。
  6. solve 完胜 inv:前向误差 vs (差 25 倍),相对残差 vs (差 9 个数量级),flop 比 。最后一段还演示了第 5 条结论:残差始终在 量级,而前向误差随 从 涨到 ——"残差小 ≠ 解准",两者的比值始终不超过 。

复现这段代码时的两个坑

1. 不要把 换成 之类的"更小但看着更自然"的值再期待同样结论: 与 的精确性会变(实测 精确成立,但 )。手算例子要选"乘子可以精确表示"的 。

2. inv@b 的误差不是每次都大:它依赖随机种子与矩阵结构(本例固定种子 2026)。要下结论必须重复实验,而不是看一次结果。


六、应用

  1. 结构力学与有限元:刚度矩阵 对称正定,解 直接用 Cholesky,运算量与存储都省一半。这是有限元软件(ANSYS、Abaqus)内部的标准路径。
  2. 电路仿真(SPICE 类):修正节点分析(modified nodal analysis)得到的矩阵通常不对称,需要带部分选主元的 LU,并把 记录下来做稀疏重排(如 AMD、METIS 排序)以减少填充。
  3. 最小二乘与统计:正规方程 的系数矩阵对称正定,可用 Cholesky;但 ,所以条件数差时应该改用 QR(4-3-最小二乘逼近、11-2-范数与条件数)。
  4. 卡尔曼滤波:协方差矩阵 对称正定,更新步要做 Cholesky 或平方根滤波(square-root filter),以保证数值上始终保持正定。
  5. 机器学习:高斯过程回归要解 ,核矩阵 常常接近奇异( 可达 ),标准做法是加"抖动" 或改用 Cholesky + 迭代改进。
  6. 计算流体力学:流场离散后的稀疏矩阵送入直接求解器(如 MUMPS、SuperLU),核心就是带选主元的稀疏 LU;更大规模则改用迭代法(11-3-迭代方法与预条件)。
  7. 作为诊断工具: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:向后误差分析听起来很抽象,它对我的日常编程有什么实际影响?

三个直接用处:

  1. 诊断方向:残差小 + 结果错 ⟹ 去查条件数;残差大 ⟹ 去查算法/实现。
  2. 选择算法:向后稳定性是可以比较的算法属性。QR 向后稳定,正规方程不(它把条件数平方);LU 带主元向后稳定,不带主元不。所以选择顺序是"先看稳定性,再看速度"。
  3. 解释"为什么迭代改进有效":迭代改进能在 时把前向误差降到 量级,正是因为它把"前向"问题转成了"向后"问题——用高精度算残差,再解一次修正方程。

本篇小结

一、核心结论(十句话)

  1. 计算机里没有实数。双精度浮点数在 上等间距分布,间隔 ,一次运算的相对误差不超过 ,十进制有效数字约 位。所有 的整数精确可表示——这是" 加不上去"的根源。
  2. 误差分两类:舍入误差(与 同量级,不可消除,只能控制放大倍数)与截断误差(来自"有限过程替代无穷过程",与硬件无关)。数值分析的任务是让两者平衡,而不是消灭误差。
  3. 误差要相对地看: 的大小本身没有意义, 才有意义。本库默认"误差"指相对误差。
  4. 小主元的危险尺度是 (等价地是乘子 与 之比),不是 是否为零。 危害的准确位置是回代中"从 的数里榨出 的信息"那一步:浮点相减的绝对误差 被除以 ,放大成 。
  5. 部分选主元把乘子强制压到 :代价只有 次比较(相比 的消元可忽略),收益是让算法向后稳定。 中的 是"消元顺序"的完整记录,解方程时必须先置换右端项。
  6. 增长因子 是算法自己的放大器读数:分解中的元素被放大的倍数。不选主元时 无界;部分选主元理论界 、实践中常 ;Cholesky 天然 。误差界里的关键组合是 ——一旦 ,界彻底失效。
  7. 向后误差分析把"算法"与"问题"分开:算出的 是 的精确解,其中最小扰动满足 ()。好算法给 ,不选主元的消元可以给 (解的是差 22% 的问题)。
  8. 前向误差 条件数 向后误差。 由问题决定, 由算法决定。"病态"是问题的属性,"不稳定"是算法的属性——本篇的 与 反例中 只有 与 ,错的全是算法。
  9. Cholesky 是 SPD 情形的特权:不需要选主元、运算量与存储都减半( vs ),而且分解失败就是"不正定"的判定。对称但不定时改用 。
  10. 永远用 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,不报错就用它

三、动手清单(学完这一篇应该能独立完成)

  1. 用 np.finfo(float).eps 与 np.spacing(x) 手算并验证任意量级的 ulp。
  2. 写出一个"不选主元就错、选主元就对"的 例子,并逐行列出两种做法的中间矩阵、乘子、增长因子。
  3. 给定 ,用 算出相对向后误差,并据此判断"是算法烂还是问题难"。
  4. 用 估算一条 solve 语句能给出几位有效数字,并说明为什么 inv 路线更差。
  5. 判断一个给定矩阵该用 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(条件数)