从方程到迭代
用迭代法求解 ,首先要作一个选择:把方程改写成 ,再计算 。同一个方程的两种等价改写,迭代效果可能截然不同。开始之前,要在所讨论的定义域上检查两个方向:所求的零点是否都是不动点?考虑范围内的不动点是否都是原方程的零点?如果把 乘上一个可能为零的因子,就可能引入多余的不动点。
即使改写等价,迭代也未必收敛。设计方法时可以问:能否找到一个包含目标零点的闭区间,使 把区间映回自身,并使区间内任意两点的距离缩小?两个条件作用不同:映回自身使所有迭代点留在估计有效的区域;压缩条件则控制误差。
定理 2.3.1
(可计算的不动点误差上界)
设 是非空有界闭区间,,并且存在已知常数 ,使得
对任意 ,迭代 收敛到 内唯一的不动点 。当 时(在上界中约定 时 ),
当 时,
知道第一步后,前者便可用于先验估计;后者利用最近一次算出的步长。若 ,则 在 上为常数,且 。
上界从何而来
证明
(几何级数的尾项控制其后每个迭代点)
记 ()。压缩条件给出 ,因此 。对 ,由三角不等式和等比数列求和,
因为 ,当 增大时右边一致趋于零,所以迭代点构成Cauchy 序列。实数的完备性和 的闭性保证极限 在 内。压缩不等式保证 连续,于是在 中取极限得到 。若 是另一个不动点,则 迫使 。令上式中的 即得后验上界;从 起对步长求和则得先验上界。这些估计假设精确运算,并要求 有可靠依据,不能只凭几步观察猜测。
证明透视
映回自身、闭性与压缩各用在哪里
证明只依赖一个估计 ,而它同时需要两个假设:压缩不等式之所以可以用于 与 ,是因为映回自身使每个迭代点都留在 内。关键一步是用几何级数的尾项控制两个迭代点之间的距离:。令 ,这个 Cauchy 估计就成为误差界。这就是后验上界是最近一步乘以 、而非最近一步本身的原因:这个因子计入了其后所有步长,而 接近一时它很大。
的闭性与实数的完备性把极限放在 内。没有闭性,结论就不成立: 以 把 映到自身,但其不动点 不在区间内。条件 另外还用了两次:保证几何级数收敛,以及证明唯一性。
若 在 上连续、在内部可微,且内部满足 ,中值定理便给出压缩不等式。导数检验不能代替另外检查 。
常见错误
(只检查导数而不检查值域)
在 上取 ,处处有 ,导数检验通过。但 与 不相交,而 在实数上唯一的不动点是 ,不在 内。从 出发得到 ,收敛到 。由于映回自身不成立,定理关于 内不动点的结论无从谈起。
完整算例
例题 2.3.2
(求正根的不动点迭代)
在 上求 ,取 。当 时,,而且
定理保证 内有唯一不动点。由于区间上 , 与原方程等价。从 出发,得到
最近一步的大小为 。取 ,便得到 的可计算误差上界:
这个保证不需要先知道精确根 或其小数值。上界可能偏保守,但区间和导数界都已事先证明,因此它是有效的。
例题 2.3.3
( 的保守先验步数)
在 上取 。由于 在此递减,,且 。从 得 ,所以先验上界为 。要保证误差不超过 ,需要
因此 获得保证(上界约为 ), 则否(约 )。事实上,迭代点在 时首次与不动点 相距不超过 ,因为在 附近局部因子是 ,而非 。先验步数有效但偏保守;后验上界 更贴近实际进展。
局部收敛是另一种结论
设 在不动点 附近连续可微。若 ,连续性保证存在一个充分小的、以 为中心的闭区间,使其上 。中值定理又给出 ,因此该区间映回自身。从这个充分小的区间出发便会收敛。这一结论没有给出区间半径,也不保证任意初值都成功。
反例模式
映回自身与局部导数各自都不够
在 上, 把区间映回自身,但序列 并不收敛。此时 ,缺少严格压缩。反过来, 有不动点 ,且 ;但从 出发得到 ,反而远离零。局部条件不能保护远处的初值。
常见错误
(步长小不等于误差小)
仅凭步长小不能保证误差小: 的不动点是零,从 出发,步长只有 ,但 的误差为 。它的压缩因子 ,定理恰好要求把该步长乘以 。
如何选择松弛参数
常用的一族迭代是 ,其中 是非零常数。在其有定义的区间内,不动点恰好是 的零点。若区间 上已知 ,选取
便有 :线性表达式 的绝对值在 或 处达到最大。这只证明压缩;仍须另外验证 。如果已知零点 存在,且 关于 对称,导数界可以保证映回自身;实际中区间可能不对称,根的位置也可能未知。参数选得不好,即使方程很简单也可能发散:对 取 ,得到 。
例题 2.3.4
(用松弛法解 )
在 上取 。这里 落在 ,故 、、、。映射 满足 。映回自身须另外检查: 是凹函数,最大值为 ,而 ,所以 。从 出发,
最近一步为 ,所以 。实际误差约为 ,落在保证范围之内。
练习与解答
快速检查
(在 上取 ,。验证定理条件,求不动点,并用最近一步估计 的误差。)
映射递增,所以值域由端点决定。
解答 · 答案
值域为 ,且 。不动点 。算得 、,故后验上界为 ;本例中它恰等于真实误差。
快速检查
(对 ,考虑 。解释为何其不动点不全是 的零点。)
直接解 。
解答 · 答案
不动点满足 ,所以 是多余的不动点,而 。所求零点 仍是不动点。乘上的因子在 处为零,因而破坏了等价性。
快速检查
(已验证某压缩映射的 ,且 。求一个足够大的整数 ,使先验上界保证 。)
使用 。
解答 · 答案
上界为 。当 时为 ,仍过大;当 时为 。因此 足够。这里从 开始计迭代次数;这是充分保证,并不一定是实际误差首次达到要求的步数。
上述公式针对精确迭代。函数求值和算术中的舍入可能破坏不等式;严格的机器计算保证须另行控制这些误差。因此,因停滞或迭代次数上限而退出,应与证明达到误差容限的情况分开报告。