用斜率代替导数
牛顿(Newton)法使用切线。当导数不可得或代价高昂时,可以用经过前两个点的割线来提供近似。
定义 6.2.1
(割线迭代)
设 且 。割线迭代令
这是在这两点处对 作插值的直线的零点。它需要两个初始值以及一个非零的分母。它不是一种包围法:即使初始两点位于根的两侧,之后的点也不一定仍位于它们之间。
例题 6.2.2
(二次函数上的一步割线迭代)
取 ,,。则 ,,故 。用插值直线验算:其斜率为 ,零点为 ,结果一致。由于 ,新点位于根 的左侧,与根相距 ,比 (距离 )和 (距离 )近得多。
局部误差乘积
设 为一个根,并记 。关键的估计涉及两个相邻的误差。
引理 6.2.3
(一步割线迭代的误差乘积)
设 ,其中 是包含 的区间,,且在 上 ,。若互不相同的 都位于 中,则割线步的分母非零,且
证明
(插值误差与割线斜率)
设 为 在 和 处的线性插值。在 处带余项的插值( 恰为节点时公式同样成立)给出
其中 属于包含这三个点的区间。 的斜率是差商 ,由中值定理,其绝对值至少为 : 连续,且在 上不能变号。特别地它不为零,所以这一步有定义。由于 , 等于斜率的绝对值乘以 。综合这些事实即证明该界。若任一迭代点已经是 ,则停止;无需再进行迭代。
定义 6.2.4
(超线性收敛)
设序列 且 ,记 。若 ,则称它超线性收敛。
定理 6.2.5
(割线法的局部超线性收敛)
设 在单根 附近成立,即 且 。则存在一个邻域,使得其中任意两个互不相同的起始点都会产生一个良定义的割线序列并收敛到 ,除非某一步到达了根而算法停止。若它从未到达根,则
因此,在这种比值意义下,收敛是超线性的。
证明
(先得固定压缩因子,再得趋于零的比值)
将 周围的闭区间缩小,使得导数有正的下界 ,二阶导数有有限的上界 。选取足够小的 ,使得闭的 -邻域包含于该区间之内,并且 ,其中 。若当前两个误差都至多为 ,则乘积估计给出 。归纳法保证所有点都留在该邻域内,并使误差以几何速度趋于零。只要当前点不是根,下一个点就与之不同;于是 在该区间上的严格单调性保证下一个分母非零。最后 。
证明透视
超线性强于固定的几何因子
乘积估计首先给出固定的收缩因子 ,它使迭代保持在受控的邻域内。只有在两个误差都趋于零之后,我们才能把比值界改进为 。这一证明既不需要声称黄金比例的收敛阶,也不需要在每一步估计 。
例子与局限
例题 6.2.6
(割线迭代逼近二的平方根)
对于 ,取 ,,
误差为 ,,,比值 , 都很小。下一个迭代点是 ,,。这些迭代点逼近 ;局部定理保证:一旦两个相邻的迭代点位于足够小的邻域内,就会收敛,但它本身并不能证明任意起始点对都会到达该邻域。
常见错误
(割线法不保证根留在最新两点之间)
上例中, 与 位于 两侧, 与 也是。但 与 都小于 ,根并不在两者之间,下一步 便跳到另一侧,大于 (确实 )。与二分法不同,割线法并不维持变号的夹根区间,所以最新两点本身不提供误差保证。
反例模式
在到达根之前可能出现零分母
对于 ,互不相同的起始点 与 满足 。即使两点都不是根,割线的分母仍为零。稳健的实现必须检测这种情况;只涉及单个单根附近的局部定理,并不能支持在全局范围内忽略这一点。
这些假设在重根处同样重要。对于 ,取正的互异起始值,递推式化简为 。导数在根处为零,因此在零附近不存在正的下界 ,上述定理并不适用。
例题 6.2.7
(二重根使超线性收敛失效)
对 和正的互异 ,上面的递推式等价于 。记 ,得到 Fibonacci 递推 ,所以 以 的速度增长,其中 ,而 。误差比值 趋于 ,并不趋于 。例如 , 给出 ,即 :相继比值为 ,趋近 。序列确实收敛,但只是线性收敛。
练习与解答
快速检查
(对于 ,从 , 出发,计算一步割线迭代。)
先计算两点的函数值。
解答 · 答案
且 ,所以 。
快速检查
(为什么局部定理能确保差商不为零?)
把差商与 联系起来。
解答 · 答案
对所选区间中两个不同的点, 连续且远离零,因此由中值定理,差商的绝对值有下界 。
快速检查
(对于 ,局部定理是否保证从 , 出发会收敛?)
比较两点的函数值。
解答 · 答案
不保证:这两个点并不位于同一个受控的单根邻域内,而且它们的函数值相等,所以第一个分母为零。
快速检查
(若乘积界成立,且两个误差都趋于零而从未到达根,解释为什么误差比值趋于零。)
把乘积界除以 。
解答 · 答案
把 除以 ,得到比值至多为 。