一个算出的向量可能几乎满足方程组,却仍与精确解相距甚远。这并不矛盾:矩阵可能把某个输入方向上的大变化映成输出的微小变化。残差衡量方程的偏差;前向误差衡量答案的偏差。后向误差提出另一个有用问题:输入数据需要改变多少,才能使算出的答案成为精确解?
本章使用实矩阵、欧氏向量范数 及其诱导矩阵范数,两者使用同一符号。对矩阵 ,,因此 且 。扰动证明只需要这些范数估计。本章所有等式和界限均针对精确数量;浮点计算在求这些数量时可能引入额外舍入误差。
残差与前向误差
定义 6.1.1
(残差与前向误差)
设 是非奇异实 矩阵,,且 。对给定的近似答案 ,定义残差及前向误差为
定理 6.1.2
(前向误差的残差界)
设 是非奇异实 矩阵,, 的残差为 、前向误差为 。则 。若 ,则还有 。
证明
(减去精确方程)
减去 得 ,所以 ,并有
若 ,则 。由 ,将上式相除得到
因此只有当条件数适中,小的相对残差才能有效控制相对前向误差。这是上界,并非预测误差必定达到它。若 ,除以 或 的相对表达式没有定义;绝对误差不等式仍然成立。右端为零时精确解为零,但算出的向量未必是零。
范数意义下的后向误差证明
定理 6.1.3
(计算解的范数后向误差)
令 、、,并在 时令 。则 恰是使下列条件成立的最小 :存在 满足 、 且 。
证明
(下界,以及达到下界的秩一扰动)
假设算出的答案要成为附近方程组 的解。令 、 和 。当 时,定义
这不只是方便的尺度。它恰好是使以下条件成立的最小 :存在扰动满足 、 及 。后一等式等价于 。三角不等式给出 ,所以每个容许的 至少是 。
要证明反向界限,若 ,取
则 。秩至多为一的矩阵 的二范数是 :Cauchy–Schwarz 不等式给出上界,单位向量 达到该上界。因此 且 。若 而 ,则 ;取 、,便达到 。若 ,非奇异性给出 ,故 ;此时原方程已成立,取 。
证明透视
后向误差证明的两个部分
下界 只用到对 的三角不等式。关键一步是构造:所需的修正量 按 的比例分给 与 ,使两个范数约束在同一个 下同时取等。选用秩一矩阵 ,是因为它把 恰好送到 的倍数,而且范数是完成此任务所需的最小者;由 Cauchy–Schwarz,其范数等于 。证明中要除以 与 ,所以 与 要分开处理。下界与构造在 处相遇,论证因而完结。
这是对两个数据对象同时施加相对界限的范数式证明。它不自动等于只容许改变 时的最小扰动,也不是逐项误差界限。若只容许改变 ,精确选择是 ,其范数为 。当各个项目的尺度差异很大时,这个分别尤其重要。
概念视角几何
后向误差是扰动空间中的一个球
固定 ,考虑由扰动对到 的线性映射 。在水平 下容许的扰动对构成球 、;而 恰为扰动系统的精确解,当且仅当 。上述证明表明,当 时, 把这个球映成以 为中心、半径为 的闭欧氏球。因此 是使像球到达 的最小 :它是以 为单位度量的 。
同时扰动矩阵与右端
定理 6.1.4
(同时扰动两项数据的扰动界)
假设 且 。记 、、。若 ,则 非奇异,且
证明
(相减、估界,并吸收误差项)
假设 ,且 满足 。定义
假设 。此条件亦保证 非奇异:因为 ,而 使第二个因子可由收敛的 Neumann 级数求逆。这是充分条件,并非必要条件。
令 。从扰动后方程减去 ,得 。因此
把最后一项移到左边,并除以 。因为 ,得
在所列充分条件下,分母为正。当分母接近零,界限会失去参考价值;这并不能证明实际误差很大。若只改变 ,令 ,便得到较简单的 界限。条件数描述数学问题的敏感度;后向误差描述某个答案对附近数据的吻合程度。
如何理解误差证明
上述范数式后向误差构造容许同时改变 和 。下界与明确构造的扰动恰好相等,故证明了最优性。换一个问题,答案也会改变:例如要求 的某些项保持为零,或要求保留对称性,都会限制容许的扰动。所构造的秩至多为一的矩阵未必满足这两种限制。称某个误差为小之前,应先说清楚容许什么改变。共同的相对容差把 和 视为两个对象;它不表示每个元素的改变都不超过同一百分比。
即使不知道真解,这个证明仍可能有用。计算 只需原始数据和给定答案;计算 则需要精确解。等式 解释两者差别,但实际应用它可能和解原方程一样困难。 的界限或估计可提供可用上界;结论的可靠程度也取决于该估计及残差计算本身。
亦要留意缩放。若同时以同一非零标量乘 和 ,精确解及有定义的两种相对量均不变。范数式后向误差也不变,因为其分子与分母以相同比例缩放。但只缩放其中一个方程,即使解集不变,范数式量度也可能改变,因为缩放后各方程在范数中的权重不同。在涉及物理单位或行尺度差距很大的应用中,可能需要合适缩放或逐项分析;上述范数式证明不能替我们决定这个选择。
扰动估计也是单向的。大的条件数表示某些方向可能敏感,并不迫使每个右端或每种扰动都达到最坏情况。同样,若界限大于一,它仍可能正确,但实际信息很少。检查真实残差及扰动方向,往往比只引用一个标量更有用。先前章节的奇异向量解释可找出伸长最多和最少的方向,但上述不等式不要求计算这些向量。
正规方程、QR 与尚未证明的事项
对实满列秩矩阵 , 的奇异值是 的奇异值平方,故 。若 是具有标准正交列的薄 QR 分解,对每个 都有 ,因此 和 有相同奇异值,。
这些都是精确的条件数恒等式。它们解释为何明确形成正规矩阵可能令待解方程的条件变差;它们没有证明每一种 QR 实现都后向稳定,也没有量化其浮点误差。这类结论需要指定算法及另外的舍入误差分析。实际上,乘积 本身也要计算,故在求解之前其元素可能已有舍入误差。我们不单凭条件数平方就预言普遍适用的数字损失。
例题
例题 6.1.5
(小残差与显著前向误差)
取 、 及 。求精确解、相对残差、相对前向误差和范数式后向误差。
解答。 精确解为 。残差为 ,而 。所以
前者约为 ,后者约为 。此处 、 及 ,故残差界限容许所见的误差。由于 ,精确范数式后向误差为
它约为 :尽管给定向量与原数据的精确答案相距甚远,它是适当附近数据的精确解。小的第二奇异值解释了放大现象。
例题 6.1.6
(扰动界限与两种分解)
设 、、 及 。求扰动后的解,将实际相对误差与界限比较,并比较正规方程及 QR 的相关条件数。
解答。 原解为 。 的第二个对角项是 ,故 。因此 。由范数得 、、 及 。界限为
确实大于实际相对误差。此外, 的条件数为 400。精确 QR 分解 、 的 。这些精确比较没有量度某个具体软件实现的舍入误差。
例题 6.1.7
(零候选解:边界情形)
令 、、。精确解为 ,残差 ,前向误差 ,所以相对前向误差为 。这里 、、,故 。对 的构造取 、:确实 。由于 ,需要对 作百分之百的相对改变;对 和 作任何更小的相对改变,都不能使 成为精确解。
反例模式
相对残差很小并不保证误差很小
断言:若 ,则相对前向误差也小于 。这是假的。取 、、。精确解是 ,残差为 ,所以 ;但 ,。修正后的说法是残差界:,而 ,容许所观察到的误差。
常见错误与细节
常见错误
(把条件数界当作预测)
第二个例题中,界是 ,实际相对误差是 。这个界是“至多”形式的保证,并非误差的估计值; 很大也不表示每个右端项都会出现最坏情形。
常见错误
(除以零范数)
若 ,精确解为零,分母含 或 的相对量没有定义,只剩绝对界 。同样, 需要 ,而 须按上面的方式另行处理。
习题
快速检查
(对 、、,求 与 ,并比较 与 。)
精确解很容易读出。
解答 · 答案
精确解是 。于是 ,,所以 。又 、,故界 取等号。
快速检查
(若只允许扰动 ,要使 成为 的精确解,最小的 是多少?)
解出 。
解答 · 答案
方程迫使 ,所以唯一的选择,也就是最小的选择,其范数为 。
快速检查
(设 、、。扰动定理是否适用?它给出什么?)
先检查 。
解答 · 答案
,所以 非奇异,界为 。