递推需要的不只是候选值
解 可以猜测 的极限,但不能证明迭代收敛,甚至不能保证各项留在定义域中。压缩条件补上这些步骤,也提供定量误差界。
定义 5.1.1
(闭区间上的压缩映射)
设 为非空闭有界区间, 为映射。若存在常数 ,,使
则称 为 上的压缩映射。取 ,数列 称为 的迭代;满足 的点 称为不动点。
条件 保证每一项都有定义;同一个 控制区间内所有点对。
定理 5.1.2
(带误差界的压缩映射定理)
设 为 上以 为常数的压缩映射。则 在 中恰有一个不动点 ,且从任意 出发,迭代收敛到 。此外,对 ,
而对 ,
为何迭代收敛
证明
(Cauchy 迭代、不动的极限与尾和估计)
令 ,并约定 (包括 )。因 ,每个 都在 内。反复使用压缩不等式得 。当 ,三角不等式及等比求和给出
右边趋于零,所以迭代是 Cauchy 序列。实数完备性给出极限 , 的闭性保证 。压缩不等式也给出 的连续性,于是对 取极限,得到 。
若 都是不动点,则 。因 ,只能有 。在尾和估计中令 ,得先验界。
至于后验界,固定 ,对从 出发的迭代使用指标为 的先验界。其第一步是 ,第一个差是 ,所以 。其中的 是已为 证明的常数;若没有这样的界,单靠一步差小并不足够。
证明透视
压缩证明中各个假设的作用
这个证明有四步,每一步用到不同的假设。第一, 使每个迭代点都留在可以使用 的集合内。第二, 把望远镜式的差变成收敛的等比级数,从而使数列为 Cauchy。第三,实数完备性提供极限, 的闭性使极限留在定义域;之后才可用 的连续性(它本身由压缩不等式推出)确认极限是不动点。第四,唯一性是另一次比较 ,这里再次用 迫使 。误差界就是第二步中等比级数的尾和。若去掉 ,第二步与第四步同时失效。
严格不等式 不能换成 ,即使不动点是唯一的也一样。
反例模式
只有唯一不动点不保证收敛
断言:若 满足 且有唯一不动点,则迭代收敛到该点。这是错的。取 。解 得唯一不动点 。但从 出发,迭代为 永远交替,且对每个 都有 。这里 ,常数恰为 ,定理不适用。修正方法是要求严格的常数 。
例子
例题 5.1.3
(一个显式的压缩映射及其误差界)
在 上取 。对 有 ,所以区间不变。对 ,
因此可取 。由 开始得 、。不动点方程为 ,两根为 ;只有 在 内。存在与收敛已先证明,选根是在确定极限,而不是假设它存在。
在 的最新步差界为 。实际误差 ,远在界之内。
例题 5.1.4
(选取迭代次数)
对同一映射,,,,所以先验界为 。要保证误差小于 ,需要 。由于 ,而 ,能保证成立的最小选择是 。这个保证不需要事先知道 。
例题 5.1.5
(边界情形 )
设 上 。因为两边都是 ,不等式在 时成立。对任意 ,,此后每项都是 ,所以 。先验界在 时 ,故 ,与事实完全吻合。 时它写成 ,这也成立,因为 。
常见错误
常见错误
(从不变区间以外出发)
对 ,不动点方程有两个根: 与 。从 内出发时,只有第一个是极限。从 出发,迭代为 ,无界递增。压缩估计只在 上证明过,而根 在区间之外。
常见错误
(最后一步差小不等于误差小)
界 含有因子 ,当 接近 时这个因子很大。对 上的 及 ,有 、、。因此 ,因子 恰好取到。当步差小于容许值就停止,只能保证误差小于容许值的九倍。
练习与解答
快速检查
(对例子的映射 ,由 精确求 。)
把 作用于 一次。
解答 · 答案
。
快速检查
(若 、,估计 。)
使用后验界。
解答 · 答案
因子为 ,所以 。
快速检查
(若 定义在 上,为什么上面的闭区间定理不适用?)
看看迭代点趋向哪里。
解答 · 答案
定义域不闭。由正初值开始的迭代都趋于 ,而 在定义域之外,所以域内没有不动点。
快速检查
(若 ,一步之后会怎样?)
把 代入压缩不等式。
解答 · 答案
不等式迫使 在非空定义域上为常数。该值属于 且是不动点,所以从 起各项都等于它。