为什么不能直接套用常见定理?
牛顿(Newton)法以切线近似函数,并把切线的零点用作下一个近似值。对于单根 ,导数不为零使局部二次收敛定理成为可能;在重根处切线水平,因此不能直接套用该定理。方法仍可能收敛,但速度通常改变。以下公式都讨论精确实数运算;有限精度下的函数计算和停止判据需要另行分析。
定义 2.4.1
(重数为 的根)
若在包含 的开区间上
其中 是整数(此处 ), 在 附近属于 ,则称 是 的 重根。这个分解比单独知道 更具体:它指明了第一个不为零的因子。
以下假设有这样的分解,且 。记 ,普通迭代和重数修正迭代分别为
只在 且导数非零时使用这些式子。如果已知到达根,就应停止,而不是计算 。
误差恒等式与局部收敛
定理 2.4.2
(重数的影响)
在上述条件下,当 充分接近 且 时,两种迭代均有定义,而且
初值充分接近时,两种迭代都收敛到 。若普通迭代没有在有限步内到达根,则相继误差的绝对值满足
对某个常数 ,修正迭代在局部满足 。这是上界:特殊情况下修正法可能更快,甚至恰好终止。
证明
(约去误差的公共幂)
微分得到 。方括号趋向非零数 ,因此在足够小的邻域内不为零。对 约去 ,便得两个恒等式。普通迭代的误差乘数趋向 ,它严格介于零与一之间。由连续性,在更小邻域内,乘数的绝对值有固定上界 ;因此迭代点留在邻域内,且 。若误差从不为零,再取乘数极限即得所述比值。
对修正公式,连续性使 在局部有上界,而 有正的下界,所以 。进一步缩小初值邻域,使 且后续迭代点都留在邻域内,误差便趋于零。如果某一步等于 ,就停止。这个局部证明不保证任意初值都收敛。
证明透视
每个假设在哪里用到
证明包含一个代数步骤和两个分析步骤。代数步骤是导数的分解 :使 的同一个幂 也整除 ,所以即使 与 都在 处为零,牛顿商 仍是 的光滑倍数。条件 用了两次:它使方括号 远离零,因而两种更新在 附近都有定义;它也使普通乘数趋向 ,而不是不定式。
第一个分析步骤把极限化为一致上界。乘数只是趋向一个小于一的数,还不足以说明迭代点留在 附近;选取乘数绝对值不超过 的邻域,这个邻域便映入自身,之后才可反复使用上界得到 。第二个步骤针对修正更新:利用已知的 恰好消去分子的一阶部分,剩下 。 在 附近连续,因而分子有界,这就给出常数 。若所用因子不等于 ,消项便失败,线性项会保留下来。
定理预测的收敛速度,在实际观察迭代时很容易被误读。
常见错误
(在根附近收敛不等于二次收敛)
普通牛顿迭代收敛,并不表示它具有单根时的二次收敛速度。在二重根处,误差渐近地每步减半;要把误差再缩小 倍,约需 步,因为 。误差比稳定在 附近,是重根的征兆,而不是程序错误;它正是提示我们估计 的信号。
算例:修正后的第一步
例题 2.4.3
(二重根处的一步普通迭代与一步修正迭代)
令 ,从靠近 的 出发。这里 ,。因为 、,商为 ,于是
事实上,只要分母非零,修正迭代的精确误差映射为 ;在 处它给出 ,与上面的计算一致。在零附近新误差约为 。本例的第一步误差更小,说明了定理,但不意味着修正对任意初值都更好。此函数还有另一个单根 。
例题 2.4.4
(普通迭代的误差比趋向二分之一)
对同一函数,,所以当 且 时
因此 ,当 时趋向 ,与定理一致。在 处比值为 ,得 ,与前例相同。由于对 , 严格介于 与 之间,任何正初值都给出递减的正误差,而相继比值从上方趋向 。这是线性收敛:误差每步约减半,而不是平方。
重数选错与数据敏感性
如果改用整数或实数系数 ,更新 的局部误差乘数趋向 。因此错误系数通常留下线性项;以上论证只在 ,即 时给出局部收缩。区间外不能由此论证保证收缩,两个端点也须另行分析。
例题 2.4.5
(端点因子 产生二周期)
取 ,于是 、,并用 。对 ,,所以
从 出发,迭代值为 :误差的绝对值从不改变,序列不收敛。乘数恰为 ,位于收缩区间的边界,这正是端点情形必须排除的原因。若改用 ,则 ,序列正负交替但收敛,乘数为 。
常见错误
(猜测的重数可能损害单根)
因为根“可能是二重根”就把牛顿步长加倍,并非无害。对 的单根(),取 的更新给出 ,就是上例的二周期;而普通牛顿法一步便到达 。只有在重数已知或已被可靠估计时,修正才有依据。
反例模式
残差小不代表根误差同样小
对 ,在 处函数值仅为 ,但到根的距离是 。残差以函数值为单位,本身不能证明 有同样小的数值误差。另外,将方程改为 ,当 时根变为 ;改为 则没有实根。对未扰动方程快速收敛,并不能消除问题本身对变化的敏感性。
练习与解答
快速检查
(对 ,推导普通牛顿更新和修正更新。)
解答 · 答案
当 时,。普通牛顿法给出 ,所以误差恰好乘以 。使用 的修正法一步得到 。此时停止,因为下一次商没有定义。
快速检查
(根的重数为 ,若使用因子 ,极限误差乘数是多少?)
解答 · 答案
。其绝对值小于一,所以局部收缩论证适用,但收敛是线性的:这不是 时的二次消项。
快速检查
(对 ,从 计算一步修正迭代。)
解答 · 答案
由精确映射 ,。这一步误差由 降至 ,接近预测值 。
快速检查
(对 和 ,残差 能否证明 ?)
解答 · 答案
不能。对这个特定函数只能推出 ,而 达到上界。要由残差得到实用的误差界,还需要根附近函数的额外信息。