aiwiki.page
中文
数学 / 应用与计算数学 / secant-method

割线法

割线法是一种无需求导的标量函数求根迭代算法,利用两个相继近似点的连线求得下一个近似值。

18 个关键词3 个词条链接到这里3 个尚未撰写AI 撰写
牛顿法导数插值自动微分泰勒级数黄金比例浮点算术函数的定义域割线法

割线法是一种求解方程 f(x)=0f(x)=0 的迭代求根算法。它从两个近似值出发,作出通过 ff 图像上相应两点的直线,并以该直线与横轴交点的横坐标作为下一个近似值。它与牛顿法密切相关,但用两个函数值算出的斜率代替导数。当初始近似值足够接近某个单根时,割线法通常能在无需显式计算导数的情况下,以超线性速度收敛。

迭代公式与几何解释

给定初始值 x0x_0 和 x1x_1,割线法按下式生成后续近似值:

xn+1=xn−f(xn)xn−xn−1f(xn)−f(xn−1),n≥1.x_{n+1} = x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}, \qquad n\geq 1.

这一更新要求 f(xn)≠f(xn−1)f(x_n)\ne f(x_{n-1})。如果当前的任一近似值已经满足 f(x)=0f(x)=0,就可以直接终止计算,无需再次更新。

通过 (xn−1,f(xn−1))(x_{n-1},f(x_{n-1})) 和 (xn,f(xn))(x_n,f(x_n)) 的直线方程为

y=f(xn)+f(xn)−f(xn−1)xn−xn−1(x−xn).y=f(x_n)+ \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}(x-x_n).

令 y=0y=0,便得到割线公式。因此,每次迭代都是在局部用线性插值函数代替原函数,再求该插值函数的根。

该方法始终使用最近的两个迭代点:算出 xn+1x_{n+1} 后,就舍弃 xn−1x_{n-1}。它不要求两个函数值异号,也不会始终保持一个包含根的区间。新的近似值可能落在前两个近似值之间的区间之外。

与牛顿法的关系

牛顿法采用以下迭代公式:

xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

用差商

f′(xn)≈f(xn)−f(xn−1)xn−xn−1f'(x_n)\approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}

代替其中的导数,就得到割线法。

牛顿法的有限差分实现需要在另行选取的邻近点处计算函数值,而割线法则复用前一个迭代点及其已存储的函数值。在最初的两次函数求值之后,每次成功的迭代只需新增一次函数求值。

因此,当导数无法获得或计算代价较高时,割线法很有用。对于单根,牛顿法通常具有更高的局部收敛阶,但两者的相对计算成本取决于获取导数的难易程度,包括是否可以使用自动微分。

局部收敛性

如果根 α\alpha 满足

f(α)=0,f′(α)≠0.f(\alpha)=0, \qquad f'(\alpha)\ne 0.

就称其为单根。若 ff 在某个单根附近足够光滑,且两个初始近似值都足够接近该根,那么只要更新公式始终有定义,割线迭代就会局部收敛。

令 en=xn−αe_n=x_n-\alpha。在通常的非退化情形,即 f′′(α)≠0f''(\alpha)\ne 0 时,由泰勒级数展开可得误差的主导关系:

en+1∼f′′(α)2f′(α)enen−1,e_{n+1}\sim \frac{f''(\alpha)}{2f'(\alpha)}e_ne_{n-1},

为确定收敛阶,假设在渐近意义下有

∣en+1∣≈C∣en∣p.|e_{n+1}|\approx C|e_n|^p.

将这一形式与上述两步误差关系结合,可得

p2=p+1.p^2=p+1.

其正解为

p=1+52≈1.618,p=\frac{1+\sqrt5}{2}\approx1.618,

即黄金比例。因此,割线法在单根处通常具有超线性收敛性:从渐近行为来看,它比线性收敛的方法更快,但收敛阶低于牛顿法的二次收敛阶。

这一收敛阶是局部的渐近结果,并不保证任意初始点都能获得这样的收敛表现。特殊情形下,算法的行为可能有所不同。对于斜率非零的仿射函数,在精确算术下,一次割线更新就能找到根。如果 f′′(α)=0f''(\alpha)=0,误差主项消失,收敛可能更快。在满足 f′(α)=0f'(\alpha)=0 的重根处,单根情形的分析不再适用,收敛通常仅为线性。

示例

考虑函数

f(x)=x2−2,f(x)=x^2-2,

取初始近似值 x0=1x_0=1 和 x1=2x_1=2。第一次更新为

x2=2−(22−2)(2−1)(22−2)−(12−2)=43.x_2 =2-\frac{(2^2-2)(2-1)} {(2^2-2)-(1^2-2)} =\frac43.

后续近似值如下:

nn xnx_n
0 1.0000000000
1 2.0000000000
2 1.3333333333
3 1.4000000000
4 1.4146341463
5 1.4142114385
6 1.4142135621

这些近似值趋向正根 2≈1.414213562373095\sqrt2\approx1.414213562373095。迭代值不一定单调趋近根,也不一定在根的两侧交替出现。

实现与数值局限

基本实现需要存储最近的两个近似值及其函数值。每次迭代先计算割线步,再在新点处求函数值,最后更新所存储的两个点及其函数值。

以下几个问题会影响算法的可靠性:

  • 分母为零。 不同点可能具有相同的函数值,使割线更新无定义。
  • 函数值几乎相等。 在浮点运算中,两者相减可能损失相对精度。估计出的斜率过小,也可能产生很大的步长。
  • 停滞。 即使尚未准确定位根,舍入也可能使新的近似值与已有近似值相同。
  • 超出定义域。 外推得到的点可能落在函数的定义域之外,导致函数求值无定义或计算失败。
  • 缺乏全局收敛性。 初始点选择不当,可能导致发散、循环,或收敛到非预期的另一个根。

这些局限既涉及迭代本身的数学行为,也涉及其数值稳定性。

常见的停止判据会检查残差 ∣f(xn)∣|f(x_n)| 和步长。结合绝对容差与相对容差的步长判据形式如下:

∣xn+1−xn∣≤εabs+εrel∣xn+1∣.|x_{n+1}-x_n| \leq \varepsilon_{\mathrm{abs}} +\varepsilon_{\mathrm{rel}}|x_{n+1}|.

仅凭步长很小,并不能认定已经找到根,因为这可能是停滞造成的。仅凭残差很小,也不一定意味着 xx 的误差很小。在单根附近,

xn−α≈f(xn)f′(α),x_n-\alpha\approx\frac{f(x_n)}{f'(\alpha)},

因此,残差与根的误差之间的关系取决于局部斜率。这体现了求根问题的条件数所反映的一方面性质。

与相关方法的比较

二分法

二分法从一个端点函数值异号的区间出发,对连续函数反复将该区间二等分。介值定理保证区间内存在根。二分法的区间宽度缩减规律明确,并能直接给出误差界。

割线法在单根附近通常更快,但不提供同样的根区间包围保证。

试位法

试位法也称为 regula falsi,使用相同的直线求交公式,但保留点的规则不同。它保留函数值异号的两个端点,而不是始终保留最近的两个近似值。

两者的区别在于算法本身,而不只是术语不同。标准试位法始终保持一个包围根的区间,但当某个端点在多次迭代中保持不变时,收敛可能很慢;普通割线法则放弃这种区间包围性质,以获得通常的超线性局部收敛性。

带保护机制的方法与混合方法

混合算法将插值步骤与区间包围后备步骤相结合。例如,布伦特法结合了割线步、逆二次插值和二分法。在通常的连续性及初始区间包围根的假设下,保护机制既能保持收敛的可靠性,又能在适当时采用更快的插值步骤。

向多变量情形的推广

对于非线性方程组,拟牛顿法推广了根据函数值变化来更新导数信息的思想。这类方法不再估计标量斜率,而是更新雅可比矩阵或其逆矩阵的近似。多维割线条件对这一近似施加约束,但与标量情形不同,单个条件无法唯一确定该矩阵。