割线法是一种求解方程 的迭代求根算法。它从两个近似值出发,作出通过 图像上相应两点的直线,并以该直线与横轴交点的横坐标作为下一个近似值。它与牛顿法密切相关,但用两个函数值算出的斜率代替导数。当初始近似值足够接近某个单根时,割线法通常能在无需显式计算导数的情况下,以超线性速度收敛。
迭代公式与几何解释
给定初始值 和 ,割线法按下式生成后续近似值:
这一更新要求 。如果当前的任一近似值已经满足 ,就可以直接终止计算,无需再次更新。
通过 和 的直线方程为
令 ,便得到割线公式。因此,每次迭代都是在局部用线性插值函数代替原函数,再求该插值函数的根。
该方法始终使用最近的两个迭代点:算出 后,就舍弃 。它不要求两个函数值异号,也不会始终保持一个包含根的区间。新的近似值可能落在前两个近似值之间的区间之外。
与牛顿法的关系
牛顿法采用以下迭代公式:
用差商
代替其中的导数,就得到割线法。
牛顿法的有限差分实现需要在另行选取的邻近点处计算函数值,而割线法则复用前一个迭代点及其已存储的函数值。在最初的两次函数求值之后,每次成功的迭代只需新增一次函数求值。
因此,当导数无法获得或计算代价较高时,割线法很有用。对于单根,牛顿法通常具有更高的局部收敛阶,但两者的相对计算成本取决于获取导数的难易程度,包括是否可以使用自动微分。
局部收敛性
如果根 满足
就称其为单根。若 在某个单根附近足够光滑,且两个初始近似值都足够接近该根,那么只要更新公式始终有定义,割线迭代就会局部收敛。
令 。在通常的非退化情形,即 时,由泰勒级数展开可得误差的主导关系:
为确定收敛阶,假设在渐近意义下有
将这一形式与上述两步误差关系结合,可得
其正解为
即黄金比例。因此,割线法在单根处通常具有超线性收敛性:从渐近行为来看,它比线性收敛的方法更快,但收敛阶低于牛顿法的二次收敛阶。
这一收敛阶是局部的渐近结果,并不保证任意初始点都能获得这样的收敛表现。特殊情形下,算法的行为可能有所不同。对于斜率非零的仿射函数,在精确算术下,一次割线更新就能找到根。如果 ,误差主项消失,收敛可能更快。在满足 的重根处,单根情形的分析不再适用,收敛通常仅为线性。
示例
考虑函数
取初始近似值 和 。第一次更新为
后续近似值如下:
| 0 | 1.0000000000 |
| 1 | 2.0000000000 |
| 2 | 1.3333333333 |
| 3 | 1.4000000000 |
| 4 | 1.4146341463 |
| 5 | 1.4142114385 |
| 6 | 1.4142135621 |
这些近似值趋向正根 。迭代值不一定单调趋近根,也不一定在根的两侧交替出现。
实现与数值局限
基本实现需要存储最近的两个近似值及其函数值。每次迭代先计算割线步,再在新点处求函数值,最后更新所存储的两个点及其函数值。
以下几个问题会影响算法的可靠性:
- 分母为零。 不同点可能具有相同的函数值,使割线更新无定义。
- 函数值几乎相等。 在浮点运算中,两者相减可能损失相对精度。估计出的斜率过小,也可能产生很大的步长。
- 停滞。 即使尚未准确定位根,舍入也可能使新的近似值与已有近似值相同。
- 超出定义域。 外推得到的点可能落在函数的定义域之外,导致函数求值无定义或计算失败。
- 缺乏全局收敛性。 初始点选择不当,可能导致发散、循环,或收敛到非预期的另一个根。
这些局限既涉及迭代本身的数学行为,也涉及其数值稳定性。
常见的停止判据会检查残差 和步长。结合绝对容差与相对容差的步长判据形式如下:
仅凭步长很小,并不能认定已经找到根,因为这可能是停滞造成的。仅凭残差很小,也不一定意味着 的误差很小。在单根附近,
因此,残差与根的误差之间的关系取决于局部斜率。这体现了求根问题的条件数所反映的一方面性质。
与相关方法的比较
二分法
二分法从一个端点函数值异号的区间出发,对连续函数反复将该区间二等分。介值定理保证区间内存在根。二分法的区间宽度缩减规律明确,并能直接给出误差界。
割线法在单根附近通常更快,但不提供同样的根区间包围保证。
试位法
试位法也称为 regula falsi,使用相同的直线求交公式,但保留点的规则不同。它保留函数值异号的两个端点,而不是始终保留最近的两个近似值。
两者的区别在于算法本身,而不只是术语不同。标准试位法始终保持一个包围根的区间,但当某个端点在多次迭代中保持不变时,收敛可能很慢;普通割线法则放弃这种区间包围性质,以获得通常的超线性局部收敛性。
带保护机制的方法与混合方法
混合算法将插值步骤与区间包围后备步骤相结合。例如,布伦特法结合了割线步、逆二次插值和二分法。在通常的连续性及初始区间包围根的假设下,保护机制既能保持收敛的可靠性,又能在适当时采用更快的插值步骤。
向多变量情形的推广
对于非线性方程组,拟牛顿法推广了根据函数值变化来更新导数信息的思想。这类方法不再估计标量斜率,而是更新雅可比矩阵或其逆矩阵的近似。多维割线条件对这一近似施加约束,但与标量情形不同,单个条件无法唯一确定该矩阵。