一个循环之所以停止,可能是因为显示出的两个数看起来很接近,可能是因为迭代次数预算已经用完,也可能是因为某个误差界达到了所要求的容差。这些是不同的事件。一个数值方法应当报告发生的是哪一种事件,以及在哪些假设下它的停止准则才是有信息量的。
数学约定
定义 13.1.1
(不变区间上的压缩映射)
设 为闭区间。若 且
则称映射 是 上常数为 的压缩映射。包含关系 称为不变性:它使每个迭代值 都留在压缩估计已知成立的范围内。对 ,记 为观察到的步长。
定理 13.1.2
(不动点迭代的后验误差界)
设 是 上常数为 的压缩映射,且 。则所有迭代值都在 内,,其中 是唯一的不动点,并且对每个 都有
证明
(用几何级数界定尾项)
由不变性,用归纳法得所有 。对 ,把压缩不等式用于 ,得 ,因此 。对 ,裂项相消再用三角不等式,得
同一估计表明 是柯西(Cauchy)序列,故收敛到某个 ;因 是闭集,。 连续,所以 。若 是 中另一个不动点,则 ,因 而得 。最后在上面的不等式中令 :,即得所求。若 ,则 在 上为常数,第一次更新就已经得到不动点。
证明透视
每一行用了哪个假设
关键一步是裂项求和:未知的误差 被换成一串观察到的步长之和,而压缩不等式把这个和变成几何级数。不变性只用来保证每个阶段的 和 都在 内,使 每次都可使用;没有它,链条在第一个离开 的迭代值处就断了。条件 用了两次:求级数和,以及使不动点唯一。最后的极限 需要紧接之前证明的收敛性;仅凭很小的 ,没有压缩常数,根本得不出任何尾项估计。因子 是不知道后续步长所付的代价:恰在 接近一时它才很大。
这个界适用于新的迭代值 ,即在度量它与 的距离之后。仅凭差值很小并不是普遍适用的证书:这个界用到一个已证明的压缩常数以及区间的不变性。
计算示例
例题 13.1.3
(常数为二分之一的映射)
取 、 及 。其像为 ,且 ,故 。不动点满足 ,因此 。前几个迭代值为
在 时,,所以证书为 。这里实际误差也是 。等号成立是这个例子的性质,并不是一般地保证这个界是精确的。
下面的互动图在五个映射上运行这个循环,并比较每一步的步长 、证书 与真实误差,让你看出小步长在何时才有保证。
小步长能保证什么
在五个映射上运行本节的循环,比较步长 d_n、证书 (q/(1−q))·d_n 与真实误差,看停止准则在什么时候才有意义。
曲线为 y = g(x),虚线为 y = x,折线连接 (x_{n−1}, x_{n−1})、(x_{n−1}, x_n)、(x_n, x_n)。下表列出相同的迭代点。
| n | x_n | d_n = |x_n − x_{n−1}| | 证书 (q/(1−q))·d_n | 真实误差 |x_n − x*| | 真实误差 ÷ 证书 |
|---|---|---|---|---|---|
| 0 | 0 | 无 | 无 | 2 | 无 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3/2 | 1/2 | 1/2 | 1/2 | 1 |
| 3 | 7/4 | 1/4 | 1/4 | 1/4 | 1 |
| 4 | 15/8 | 1/8 | 1/8 | 1/8 | 1 |
| 5 | 31/16 | 1/16 | 1/16 | 1/16 | 1 |
开头的 ≈ 表示四舍五入的小数,其余各项均为精确值。
- 状态
- ok(达标)
- 已证明的压缩常数 q
- 1/2
- g 在 I 上的最佳利普希茨常数
- 1/2
- 不动点 x*
- 2
- 算术
- 精确有理数
- 停止的指标 n
- 5
- 首个 d_n ≤ tol 的 n
- 5
- 最后一行的证书
- 1/16
- 最后一行的真实误差
- 1/16
- 每一行的真实误差 ≤ 证书
- 是
状态 ok。循环在 n = 5 停止,因为证书 1/16 不大于 tol = 10⁻¹。在已证明的 q = 1/2 下,定理给出 |x* − x_n| ≤ 1/16;真实误差为 1/16。
只用步长的检验 d_n ≤ tol 会在 n = 5 停止,此时 d_n = 1/16。该处的真实误差为 1/16,是 d_n 的 1 倍。
证书为何成立,又在何时失效
若 g(I) ⊆ I,且 |g(x) − g(y)| ≤ q|x − y|,其中 0 ≤ q < 1,则 d_{n+1} ≤ q d_n,故 d_{n+j} ≤ qʲ d_n。因 x_m → x*,由三角不等式和几何级数的尾项得 |x* − x_n| ≤ d_{n+1} + d_{n+2} + … ≤ (q/(1−q)) d_n。
对 g(x) = 1 + x/2,由于每一步的方向相同,证书在每个 n 都等于真实误差;对 cos x,比值保持小于 1。等号成立是这些例子本身的性质,并不是对该界一般为精确界的承诺。
对 g(x) = 1 + 0.999(x − 1),常数 q = 999/1000,所以 q/(1−q) = 999,真实误差为 999 d_n:10⁻³ 的步长可以与接近 1 的误差同时存在。对 2 − x,迭代点在 x₀ 与 2 − x₀ 之间往复;对 x + 10⁻⁶,步长永远是 10⁻⁶,却根本没有不动点。
余弦预设使用 q = sin 1,即 |g′| 在 [0, 1] 上的最大值,而 g([0, 1]) = [cos 1, 1] ⊆ [0, 1]。它以双精度浮点数运算,因此其证书并不是严格的机器算术界;仿射预设则按精确数计算。
初始值为区间 I 内的 x₀ = k/8,容差为 10⁻ᵉ(e 取 1 到 8),最多运行 60 步。表格在首个证书不大于 tol 的 n 处结束。真实误差使用已知的不动点 2、1、1 和 0.7390851332151607。
例题 13.1.4
(容差需要多少步?)
对同一个映射及 ,有 ,故 ;又因 ,证书等于 。我们要它不超过 ,即 。由于 而 ,第一个合格的 是 ,证书为 ,真实误差 。若步数上限为 maxSteps = 10,循环便无法证明这个容差,状态必须如实报告。
例题 13.1.5
(由导数得出压缩常数)
设 ,。则 ,且在 上 ,所以由中值定理得到以此 为常数的压缩,并且 。由 出发:、、,所以 ,证书约为 。这个证书是有效的,因为真实误差为 ,但它比 的长度还大,没有提供有用的信息。常数接近一会使适中的步长成为缺乏说服力的证书;要把证书压小,需要多得多的迭代。
报告自身状态的有界循环
下面的 MATLAB 函数是针对这个特定的 和区间的简洁演示。它接受位于 [0,2] 中的有限实数标量 x0、正的有限值 tol,以及正整数 maxSteps。这里假定输入满足上述约定;用于实际生产的函数应在执行循环之前对输入进行验证。
function [x, ok, n, bound] = fixed_demo(x0, tol, maxSteps)
% Mathematical x_n is returned after n updates.
q = 1/2;
x = double(x0);
ok = false;
bound = Inf;
for n = 1:maxSteps
xnew = 1 + x/2;
bound = (q/(1-q))*abs(xnew-x);
x = xnew;
if bound <= tol
ok = true;
return
end
end
end
迭代计数器统计的是已完成的更新次数。如果没有任何一个界达到容差,ok 保持为 false,函数返回最后一个近似值,同时返回最后一个界以及已用尽的计数。maxSteps 为正的约定保证了即使循环从未提前返回,n 也会被赋值。在精确算术下,ok=true 在已证明的压缩假设下证明了所陈述的距离界。浮点舍入会带来该证明中未包含的影响,因此仅凭显示出的 bound 并不是严格的机器算术证书。
对于不同的 ,在没有证明相关区间上的有效界之前,不要沿用 q=1/2。特别地,若 在 上连续、在其内部可微,且在整个内部都有 ,则中值定理给出压缩不等式。不变性 仍需另行检查;只在单个点检查导数是不够的。
小步长可能造成误导
反例模式
步长很小而误差很大
断言:若 小于 ,则 与不动点相差约不超过 。取 上的 。其像为 ,故 ,,。由 得 ,所以 ,但真实误差是 ,即 。一般地,,而 。这与定理一致:证书 在此恰好等于真实误差。只有当 适中时,小步长才说明误差很小;当 时,这个因子至多为一。
常见错误
(约定不成立时仍把最后一个迭代值当作根)
映射 把 映入自身,并有不动点 ,但它不是常数小于一的压缩映射:。由 出发,序列为 ,每一步都是 ,所以步长测试从不触发,循环只会在最大步数处结束。最后的迭代值 或 并不是不动点 。最大步数上限可防止循环无休止地执行,但不会把这个输出变成已收敛的答案。同样, 的步长很小,但它没有不动点,也没有所需类型的不变有界区间。当假设不成立时,正确的做法是报告其局限,而不是把最后一个迭代值标为已证明的根。
小测
快速检查
(对 上的 及 ,在 时证书是多少?)
利用 和 。
解答 · 答案
,且 ,所以证书是 。真实误差为 。
快速检查
(某映射是压缩映射,,最后一步为 。定理给出什么误差界?)
计算 。
解答 · 答案
,故 。在步长为 时停止,只能证明约 ,而不是 。
快速检查
(当 取什么值时,停止测试 本身就是误差不超过 的证书?)
解 ,其中 。
解答 · 答案
,即 。 较大时,步长应与 比较。
快速检查
(对 上的 ,定理的哪一个假设不成立?)
取 、 检验压缩不等式。
解答 · 答案
不变性成立,但 ,所以不存在 。迭代 并不收敛。