步长小可能带来错觉
迭代解线性方程组会产生一连串近似值,并非经过指定次数运算便一定得到精确解。常见的停止准则是检查相邻两个存储向量是否接近。这很有用,却可能误导:即使距离解仍远,舍入也可能令计算值不再改变。要解读小步长,我们既需要理想迭代的收敛界,也需要计算单步误差的界。
令 T(x)=Bx+c 定义于 Rn,采用固定向量范数及其诱导矩阵范数。假设已知 ∥B∥≤q<1。唯一不动点 x∗ 满足 x∗=Bx∗+c。我们把存储的 B,c 视为精确数据;这些数据与原本物理或数学问题的差异须另行分析。计算机计算满足
yk+1=T(yk)+δk,∥δk∥≤εk.εk 必须涵盖整个更新的误差,包括所有舍入和任何不精确的内层求解,并可随 k 改变。以下结果适用于所有满足这个模型的计算序列,即使误差彼此相关或经刻意选取亦然;我们没有假设随机舍入。
压缩性还能给我们什么?
对任何 k≥1,
∥yk−x∗∥≤qk∥y0−x∗∥+j=0∑k−1qk−1−jεj.令 dk=∥yk−yk−1∥,则利用最近一次的误差界可得
∥yk−x∗∥≤1−qqdk+εk−1.另一方法是取任何经认证的 ∥T(yk)−yk∥ 上界 ρk,则
∥yk−x∗∥≤1−qρk.
从计算更新式减去不动点方程,再用三角不等式及诱导范数,得到
∥yk+1−x∗∥≤q∥yk−x∗∥+εk.反复代入便得第一个界。为得到步长判据,插入上一次计算更新式:
yk−x∗=B(yk−1−x∗)+δk−1=B(yk−x∗)−B(yk−yk−1)+δk−1.取范数并把 q∥yk−x∗∥ 移到左边,即得所述结果。最后,
yk−x∗=B(yk−x∗)−(T(yk)−yk),同样整理便得缺陷界。每次都必须使用 1−q>0。
证明透视
保留新的误差项
三个假设在不同位置进入证明。诱导范数对每个 v 给出 ∥Bv∥≤q∥v∥,每次更新用一次。单步误差界以加法进入,所以较早的误差 δj 会被之后每一次压缩削弱;这就是 εj 带有权重 qk−1−j、而不会被放大的原因。
步长判据中不显然的一步,是把 yk−1−x∗ 改写成 (yk−x∗)−(yk−yk−1)。未知误差于是出现在等式两边,右边的系数至多为 q,而 q<1 使它可以被吸收到左边,从而产生因子 1/(1−q);若 q≥1,整理时要除以非正数,什么也认证不了。缺陷界是同一种吸收,只是以精确更新 T(yk) 代替存储的 yk−1,所以没有 ε 项,但 ρk 必须是精确缺陷的上界。证明没有用到任何符号或概率假设:每一步都是对刻意选取的误差也成立的范数不等式。
因此,绝对容差 τ>0 的停止测试可只在 (qdk+εk−1)/(1−q) 的认证上界不超过 τ 时接受结果。实际机器运算中,计算 dk、q 及最后的式子也会产生误差。应使用精确运算、定向舍入或其他严格区间包围取得所需上界;屏幕上的舍入小数不会自动成为上界。若要认证相对误差,还需要 ∥x∗∥ 的正下界;当解为零时,绝对误差不能独自给出相对精度。
若所有 εk≤ε,则
∥yk−x∗∥≤qk∥y0−x∗∥+1−q1−qkε.若 εk→0,则 yk→x∗。
一致情形下,j=0∑k−1qk−1−jε≤εi=0∑k−1qi=ε(1−qk)/(1−q)。趋于零的情形下,固定 η>0,选 J 使所有 j≥J 都有 εj≤η(1−q)。当 k>J,早期项满足 j<J∑qk−1−jεj≤qk−Jj<J∑εj,它趋向零;尾项满足 J≤j<k∑qk−1−jεj≤η(1−q)/(1−q)=η。由于 qk∥y0−x∗∥→0,对每个 η>0 都有 klimsup∥yk−x∗∥≤η。
一致界趋向 ε/(1−q),未必趋向零。这是保证值的误差下限,并非声称每个实际序列的极限误差都非零。
如何取得单步误差界
对显式的矩阵与向量乘法,一个标准舍入模型可给出上界。本小节额外假设向量范数具有单调性:若逐分量有 ∣v∣≤∣w∣,则 ∥v∥≤∥w∥。常见的 ℓ1、ℓ2 和 ℓ∞ 范数均有此性质,任意向量范数则未必如此。假设标量乘法与加法各自以最接近值舍入,没有溢出或令模型失效的下溢,且 mu<1;其中 u 是单位舍入误差,m=n+1。令 γm=mu/(1−mu)。By+c 的每个分量先以顺序内积计算 n 个乘积,再加上 ci;标准舍入因子乘积估计给出保守的逐分量界
∣δ∣≤γm(∣B∣∣y∣+∣c∣),ε=γm∣B∣∣y∣+∣c∣.
这里 ∣B∣、∣y∣ 按分量取绝对值;右侧本身也须向上包围。对无穷范数,取该非负向量各分量的最大值。融合乘加、不同的求和次序、隐式三角更新、次正规数运算或溢出,都需要适合实际运算的界。特别是,不能把这个显式矩阵计数原封不动地套用于从未构造 B 的 Gauss–Seidel 实现。
对 Ax=b,常见形式为 T(x)=x+M−1(b−Ax),其中分裂矩阵 M 非奇异。其精确缺陷是 M−1(b−Ay),一般并非未经预处理的残差。因此,只有控制 M−1 的作用及其计算误差后,残差界才可转化成压缩判据。
算例与简单准则的失效
考虑标量理想映射 T(x)=21x+1,不动点为 x∗=2。假设 y0=0,第一次计算更新得到 y1=1.01,且已知单步误差满足 ε0≤0.01。存储步长 d1=1.01,定理给出
∣y1−2∣≤1/2(1/2)(1.01)+0.01=1.03.实际误差为 0.99。此界偏保守,但无须知道单步误差的符号便有效。同一点的精确缺陷是 ∣T(1.01)−1.01∣=0.495,因此得到更精确的界 0.99。
反例模式
零步长不能认证精度
再考虑同一映射;若从 y=1.9 出发的计算更新仍返回 1.9,步长为零,但误差为 0.1。此时计算误差为 −0.05,修正后步长界是 0.05/(1−1/2)=0.1。只有误差界也足够小,零步长才构成认证。反过来,若认证界大于目标,只表示此论证不能作结,并不能证明实际答案不准确。
令 B=(1/21/41/41/2)、c=(1,1)T,则 q=∥B∥∞=3/4。解 (I−B)x=c 得 x∗=(4,4)T;验算:每行 2+1+1=4。在 y=x∗,∣B∣∣y∣+∣c∣ 每个分量都是 2+1+1=4。这里 n=2,所以 m=3。二进制双精度中 u=2−53≈1.11×10−16,γ3≈3.33×10−16。因此单步误差界约为 ε=4γ3≈1.33×10−15,保证值的下限为 ε/(1−q)≈5.33×10−15。用于认证之前,这些小数必须向上舍入。
取 q=1/2、∥y0−x∗∥≤2 及 εj=0.01⋅2−j。加权和的每一项为 2−(k−1−j)⋅0.01⋅2−j=0.01⋅21−k,与 j 无关,所以
∥yk−x∗∥≤21−k+0.01k21−k.当 k=10,此界为 (2+0.2)/1024≈2.15×10−3。正如推论所说,界趋向零;但这个边界情形显示,误差恰以压缩速率递减时要付出额外的因子 k。
常见错误
对 T(x)=x+M−1(b−Ax),缺陷是 M−1(b−Ay)。取标量情形 A=0.1、M=0.2、b=1:则 T(x)=0.5x+5、q=0.5、x∗=10。在 y=9,残差为 0.1,缺陷却是 0.5。用残差会得到错误的判据 0.1/0.5=0.2;缺陷给出 0.5/0.5=1,正是实际误差。
假设 (qdk+εk−1)/(1−q) 的精确值是 0.0030004,容差为 τ=0.003。舍入到四位小数的显示是 0.0030,看似通过,实际上测试并不成立。只有向上舍入或精确计算的值才可与 τ 比较。
练习与解答
快速检查
(设 q=1/4、dk=0.006,且经认证的 εk−1=0.0003。步长判据能否确立绝对误差不大于 0.003?)
解答 · 答案
上界为 (0.25⋅0.006+0.0003)/0.75=0.0024,所以可以。实现时三个输入界和最后的运算均须认证。
快速检查
(设 q=0.9,每次单步误差均不大于 10−6。求一致误差公式的极限上界。这是否证明迭代不收敛?)
在一致误差公式中令 k→∞。
解答 · 答案
极限上界为 10−5。这不证明失败;例如所有 δk=0 时便正常收敛。此界容许极限误差非零,却不要求它非零。
快速检查
(标量映射 T(x)=0.8x+0.2 在某个候选值的精确缺陷是 0.02。求误差界。若计算出的缺陷为 0.02,其绝对计算误差最多为 0.001,又能确立什么界?)
这里 q=0.8,所以 1−q=0.2。
解答 · 答案
精确缺陷给出 0.02/0.2=0.1。第二种情况下缺陷的认证上界为 0.021,故 ∣y−x∗∣≤0.105。
快速检查
(给出一个具有固定非零单步误差的计算序列,使其渐近达到一致误差界。)
解答 · 答案
令 T(x)=qx、0<q<1、x∗=0、y0=0 及 δk=ε>0。直接求和得到 yk=ε(1−qk)/(1−q)。其极限等于上述界,故仅靠这些假设不能得到更小的一致保证。