为什么停止准则需要误差界?
迭代求解器输出的是向量,不是未知的误差。残差看似细小,要先说明尺度,以及矩阵如何把误差转成残差,才可判断它有多大意义。有限元问题常关心能量范数;相对于未加权的欧几里得(Euclid)范数,预处理矩阵可提供更合适的残差尺度。以下推导适用于任何近似解,不限于共轭梯度法产生的向量。
设 对称正定(SPD),, 是近似解。记 、,并定义 和 。无须显式求逆:解 后即可用 求后者的平方。
定义 1.6.1
(谱等价)
假设已知常数 ,对所有 均有
这等价于 的特征值都在 内。界不必最紧,但必须确实适用于所用矩阵。
定理 1.6.2
(由残差控制误差)
在 (1) 下,对任意 ,
若 ,相对能量误差亦满足
证明
(把预处理矩阵对角化)
令 。由 ,误差平方为 ,预处理残差平方为 。把对称正定矩阵对角化为 ,并令 ,则 ,。每个特征值 都满足 ;对各坐标求和得 ,即 (2)。
把 (2) 用于近似解 (其残差为 ),可知 介于 与 之间。用分子的上界除以分母的下界,反之亦然,即得 (3); 保证分母非零。
证明透视
平方根从何而来?
证明只用到谱包含条件 (1),而且只通过 的特征值使用它。决定性的一步是变量代换 :它把误差与预处理残差放进 的同一组标准正交特征基,在相同的平方坐标上分别配上权 与 。逐个坐标比较 与 ,便在平方范数上得到介于 与 之间的因子,因而范数本身出现平方根。
相对界 (3) 需要另一个独立的想法: 本身就是一个残差为 的近似解,所以同一不等式也控制分母 。常数合成 ,是因为分子的上界与分母的下界配对。没有任何一步涉及 是如何得到的,所以这些界对任何方法的任何迭代值都成立。
所以在精确算术下, 是保证相对能量误差不超过 的充分停止条件。未通过这条充分条件并不代表实际误差一定超标:保守的谱界可能使区间很宽。若 ,唯一解为零,(3) 的相对误差分母为零,应改用绝对误差界。
考虑两种偏差的可实施证书
计算机可能存储近似残差 ,以及方程 的近似解 。在 Krylov 法的递推更新中,存储的残差可能偏离 。重新计算可以减少偏差,却不能自动消除浮点误差。因此,我们明确假设已提供有效界,而非把存储值当成精确残差:
此处 是所表示数据与迭代向量的数学残差。两个偏差界须由其他方法提供,例如经验证的误差分析或验证算术;浮点输出本身不自动成为有效界。设
定理 1.6.3
(包含偏差的绝对误差证书)
在 (1)、(4) 下,若 (5) 中的量精确计算或向外取界,则
特别是,若上界不大于指定的绝对容差,便证明误差符合容差。
证明
(预处理范数中的两次三角不等式)
范数的反三角不等式给出
由 ,对角化可得 。又 ,因此 。代入 (2) 即得结论。此结果包括 ,不要求 为正。实际计算时,对 、 和常数取外界亦须考虑舍入;普通浮点计算的显示值不能直接当作证明。
内层求解偏差与残差偏差作用不同:前者量度 解得多准,后者比较存储残差与 。只有其中一项细小,不能取代另一项的界。若要相对误差证书,可同样独立地为分母 求一个严格正的下界;不要除以可能为零的下界。
例题 1.6.4
(明确计算两项偏差)
设 、、,以及 。广义特征值为 和 ,可取 、、。真实残差为 。假设计算存储了 和 ,则
故 ,由 (6) 可知能量误差介于 与 。已知精确解 ,因此 ,确在区间内。实际求解时通常不能用真实残差和精确误差作这种比较,须另外取得有效的偏差界。
例题 1.6.5
(共轭梯度迭代值的相对界)
沿用 、、 及 ,但改用精确算术,故 、。此时 ,,所以比值为 。不等式 (3) 给出
由于 ,实际值为 。若要用充分准则证明相对误差不超过 ,比值必须降到 。
例题 1.6.6
(精确预处理消除差距)
在边界情形 中,条件 (1) 以 成立,(2) 变成恒等式 。对 及 ,残差 给出 ,恰好等于 。此界是精确的,但计算 需要解一次与 相关的方程,而那正是原问题。
常见错误
(估计的特征值不是有效的界)
(2) 的上界需要一个真正是 的谱下界的常数 。由少数 Lanczos 步或粗略模型得到的估计可能把它高估。在第一个例子中,真值是 ;若改用 ,会得到 ,小于实际误差 ,所得证书便是错误的。
反例模式
残差小,误差却可以大
取 、、。此时 ,且 ,但 。矩阵在第二特征方向压小了误差所产生的残差。这不违反 (2):相关的谱下界很小,而且必须指明范数及尺度。
练习与解答
快速检查
(精细度:设 、,其中 。什么样的误差使 (2) 的两边分别取等号?)
试考虑沿单个特征向量的误差。
解答 · 答案
若 位于 的特征空间,则 ,而 ,误差上界取等号。位于 特征空间的误差则使下界取等号。所以只用这两个端点界时,两个常数都不能改进。
快速检查
(容差:设 、、。(6) 是否证明能量误差不超过 ?)
计算 (6) 的上端点。
解答 · 答案
上界为 ,所以可以,前提是所有列出的界都有效,而且所显示的算术已被安全地计算。
快速检查
(遗漏偏差:设 、、、、。内层求解精确,是否足以证明误差为零?)
比较存储的残差与 。
解答 · 答案
不足以。内层偏差为零,但 ,所以残差偏差 。实际误差为一,而 (6) 正确地给出区间 ;忽略 会得到错误的零误差证书。
快速检查
(下界:为什么上界证书很小,并不意味着 (6) 的下界为正?)
考虑 的情形。
解答 · 答案
若 ,证书的下端点为零。这时已有信息既与精确解相容,也与非零误差相容;它并没有说明实际误差是否为零。
这些界针对固定的 SPD 系统,并假设已给定确定性的有效包围界。它们不会自动提供谱界或验证浮点计算,也不分析可变或不定预处理矩阵,更不保证线性系统对原微分方程的离散化误差。