对近似解提出另一种问题
假设计算得到的向量 用来求解 。前向误差 需要知道精确解 。残差 通常更容易计算,但其大小依赖单位和尺度。后向误差提出的问题是:数据需要改变多少,才能让 成为精确解?
定义 2.5.1
(范数意义的后向误差)
先考虑实矩阵、欧氏(Euclidean)向量范数和其诱导矩阵范数。定义
这里 与 都可以改变。如果其中一个恰为零,其相对界也强制对应扰动为零。
这个定义是给定近似向量和数据的性质,并不声称产生它的某个算法是稳定的。
精确的范数意义公式
定理 2.5.2
(范数意义后向误差的精确公式)
令 。当 时,
若 ,则 且 或 ,所以 ;零扰动达到 。
证明
(残差恒等式与秩一扰动)
扰动后方程精确成立等价于 。因此任何允许的扰动都满足
这证明了下界。若 ,零扰动达到它。否则令 、。当 时,令 并取
秩一矩阵 的诱导 2-范数为一,而且 。当 时取 , 保持相同定义;此时 ,等式仍然成立。因此所有情况都能达到这个下确界。
证明透视
下界与构造是两个独立的部分
证明分成两个独立的部分。下界只用残差恒等式 和三角不等式,所以对每个允许的扰动都成立。与之匹配的构造才是不显然的一步:两个扰动都取成与残差方向 平行, 通过 起作用,使 且 。符号( 取 , 取 )使两部分贡献叠加成 而不是相互抵消,共同的 用尽了全部预算 。 的情形要单独处理,因为此时 没有定义;那时预算只有 。没有这个构造,我们只知道 。
更严格的逐分量问题
范数意义的扰动可能在尺度差异很大的元素之间转移数据。
定义 2.5.3
(逐分量后向误差)
逐分量后向误差 是使得存在 满足 并且
的最小 。
定理 2.5.4
(逐分量后向误差的精确公式)
记 。满足条件的最小 是
其中将 项解释为零。
证明
(逐行的残差恒等式)
这个约定是自洽的: 蕴含 且每个 ,所以 。
残差恒等式逐行给出 ,从而得到下界。对每个 的行,取
对于 的行,取零扰动。因为 ,这些选择满足 ,并在 时满足逐分量界。因此公式给出精确最小值。这个模型保持 和 的零元素;不同的扰动模型可能产生不同的后向误差。
例题 2.5.5
(同时计算两个后向误差)
设 、、。则 ,、、,所以 ,。逐分量公式中 ,故 。最优的逐分量扰动只改动第 行:、。验算:,而第 行本来就精确。
例题 2.5.6
(零近似解)
设 、、。则 ,,所以 。 的构造取 、,得 :整个右端项都必须被去掉。逐分量地,,,两个比值为 和 ,所以 。第二行 、,用到了 的约定。
范数意义误差很小,某个分量仍可能很差
例题 2.5.7
(范数意义误差很小而逐分量误差很大)
取 ,令
精确解为 ,残差为 。由于 、,
当 时,范数意义的后向误差趋于零,但第二个方程的逐分量后向误差为 100%,相对前向误差仍然很大。 的 2-范数条件数为 ;该问题会放大小奇异值方向上的误差(此处也是特征值 的特征向量方向)。
反例模式
残差小并不决定前向精度
一个诱人的说法是:范数意义的后向误差小,就保证相对前向误差小。取上面的对角例子并令 。则 ,,但 。修正见下面的界:因子 乘在残差上,所以要得出前向误差的结论,除了 之外还需要 和精确解尺度的信息。
当 非奇异时,基本恒等式 给出 。结合 ,还得到 。所以前向误差结论会涉及条件性;这是独立于两个后向误差公式的另一个界。实际浮点计算中,残差本身也经过舍入;如果要对精确数据给出严格证书,也必须控制残差的计算误差。
常见错误
(范数意义的扰动不一定保持零元素)
范数意义的极小扰动是 ,这是一个一般为稠密的秩一矩阵。在对角例子中 、,所以 在 为零的 位置放入了非零元素。若零结构有实际意义, 就不是在度量合法的扰动;这正是 的作用。
常见错误
(残差除以 b 的范数并不是后向误差)
比值 只是单独扰动 时最小的相对扰动。由于 也可以改变, 可以更小。取 、、,则 ,;但 ,,由 、 达到:此时 。
练习与解答
快速检查
(对 、、,计算 和 。)
先求 。
解答 · 答案
,。又 ,所以 。每个 ,所以 。
快速检查
(在上面的对角例子中,求逐分量公式的两个分母 。)
使用 。
解答 · 答案
、;残差分量为 和 ,因此最大比值为 。
快速检查
(若 精确求解 ,两个后向误差分别是多少?)
此时 。
解答 · 答案
两者都为零,由零扰动达到。
快速检查
(为什么逐分量扰动模型保持 的零元素?)
看对 的约束。
解答 · 答案
约束 强制 时 。