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

布伦特法

布伦特法是一种无需导数、结合根区间夹逼与插值的可靠快速求根算法,也指一种相关的极小化算法。

16 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
数值分析二分法割线法导数数学优化连续函数介值定理插值布伦特法

布伦特法是数值分析中用于求实值函数零点的一种算法,初始区间两端的函数值须异号。它结合了二分法的可靠性与割线法及逆二次插值的速度优势。插值用于提出可能快速逼近根的试探步;保障机制则会拒绝不合适的试探步,改用二分步骤。该方法需要计算函数值,但不需要导数。

这个名称也指一种不同但密切相关的一维数学优化算法,用于求极小值,将抛物线插值与黄金分割搜索相结合。除非上下文涉及优化,否则“布伦特法”通常指求根算法。

求根问题与假设

求根问题是确定一个数 rr,使其满足

f(r)=0.f(r)=0.

布伦特求根法从区间 [a,b][a,b] 出发,要求 ff 在该区间上是连续函数,且

f(a)f(b)<0.f(a)f(b)<0.

根据介值定理,该区间内至少存在一个根。如果某个端点已经满足 f(x)=0f(x)=0,则可以立即返回该端点。

这样的初始区间称为夹根区间。算法在推进过程中始终保持区间两端函数值异号,因此即使插值预测不佳,也能保证区间内至少包含一个根。该方法不要求函数单调,也不要求根唯一。不过,当夹根区间内有多个根时,该方法通常无法预先指定最终找到哪一个。

连续性是根存在性保证的必要条件。不连续函数可能变号却不取零值:例如,f(x)=1/xf(x)=1/x 在 −1-1 和 11 处的值异号,但两者之间没有零点,而且函数在原点处无定义。

组成方法

二分法

二分法计算中点

m=a+b−a2m=a+\frac{b-a}{2}

处的函数值,然后保留仍能夹住根的那个半区间。经过 nn 次二分后,宽度为 WW 的初始区间缩小为

W2n.\frac{W}{2^n}.

这种缩减是可预测的,不依赖于函数的局部形状。其局限在于,它不利用函数值的大小来加速收敛。

割线插值

给定函数值不相等的两点 x0,x1x_0,x_1,割线法提出试探点

s=x1−f(x1)x1−x0f(x1)−f(x0).s=x_1-f(x_1)\frac{x_1-x_0}{f(x_1)-f(x_0)}.

这是通过两个采样点的直线的零点。在足够光滑的单根附近,割线步骤的收敛速度可以快于二分法。然而,单独使用时,割线步骤不一定始终落在夹根区间内,也可能不收敛。

逆二次插值

给定三点 x0,x1,x2x_0,x_1,x_2,且其函数值 yi=f(xi)y_i=f(x_i) 两两不同,逆二次插值将 xx 视为 y=f(x)y=f(x) 的函数,并拟合一个二次近似。在 y=0y=0 处计算该近似,得到

s=x0y1y2(y0−y1)(y0−y2)+x1y0y2(y1−y0)(y1−y2)+x2y0y1(y2−y0)(y2−y1).s= x_0\frac{y_1y_2}{(y_0-y_1)(y_0-y_2)} + x_1\frac{y_0y_2}{(y_1-y_0)(y_1-y_2)} + x_2\frac{y_0y_1}{(y_2-y_0)(y_2-y_1)}.

这是插值的一种应用,其中自变量与函数值的角色互换。与对 f(x)f(x) 进行普通二次插值不同,它不需要在拟合所得二次函数的两个根之间作出选择。

在单根附近满足适当的光滑性和非退化条件时,单独使用逆二次插值的渐近收敛阶约为 1.8391.839。这描述的是插值过程良好的局部表现,并不意味着带有保障机制的布伦特算法每次运行都能无条件达到这一收敛阶。

求根算法的工作原理

不同实现采用的记号和状态管理方式有所差异,但核心结构一致。

算法维护以下信息:

  • 函数值异号的两个点;
  • 一个优先采用的近似点,通常是夹根区间中函数值绝对值较小的端点;
  • 一个先前的点,以及近期步长的信息。

从概念上说,每次迭代按以下步骤进行:

  1. 检查终止条件。 如果某个函数值为零,或剩余夹根区间已足够小,则停止。
  2. 构造插值试探点。 若有三个合适且互不相同的函数值,则使用逆二次插值;否则使用割线步骤。
  3. 执行保障检查。 如果试探点位于夹根区间允许的部分之外、相对于近期步长而言步子过大,或未通过算法的进展检验,则将其拒绝。
  4. 必要时二分。 当插值被拒绝时,改用夹根区间的中点。
  5. 计算新点的函数值。 更新两端函数值异号的夹根区间,并按需重新安排所存储的点。

保障条件比“试探点必须位于夹根区间内”更为严格。即使试探点位于区间内部,也可能几乎无法取得进展,例如反复落在非常靠近某个端点的位置。布伦特法的接受规则利用近期步长来防止这种停滞,并在必要时强制执行二分步骤。

因此,布伦特法并非只是在二分与插值之间任意交替。它的核心特征是在夹根框架内,有控制地接受快速逼近的步骤。

收敛性与停止准则

对于连续函数,只要初始夹根区间有效,带有保障机制的方法在精确算术下就会收敛,而不要求对某个特定根有良好的初始近似。这通常称为全局收敛性,其含义是从符合条件的夹根区间出发能够收敛,而不是能够找出所有根,或能够从任意一对数出发。

算法的速度取决于函数本身:

  • 在光滑的单根附近,被接受的插值步骤往往能带来超线性收敛。
  • 当插值不可靠时,二分法可恢复可靠的区间缩减。
  • 函数平坦、不光滑,或其变化难以被数值计算充分分辨时,可能更频繁地退回二分步骤。

因此,布伦特法兼具夹根保证与良好的局部加速能力。这并不意味着每次迭代都会将夹根区间减半,也不意味着所有实现的函数计算次数总是不多于纯二分法。

一种常见的停止规则结合了绝对容差和相对容差,其示意形式为

∣b−a∣≤εabs+εrelmax⁡(∣a∣,∣b∣).|b-a| \leq \varepsilon_{\mathrm{abs}} + \varepsilon_{\mathrm{rel}}\max(|a|,|b|).

具体常数及其解释因软件库而异。只要根仍被夹在区间内,区间宽度就直接给出了位置不确定性的界限:区间内任意一点到其中至少一个根的距离不超过整个区间宽度,而中点到该根的距离不超过区间宽度的一半。

残差 ∣f(x)∣|f(x)| 很小,本身并不能普遍保证根的误差也很小。在可微的单根 rr 附近,

x−r≈f(x)f′(r).x-r\approx \frac{f(x)}{f'(r)}.

因此,当导数很小时,即使残差很小,根的位置也可能非常敏感。这使停止准则与求根问题的条件数联系起来。

数值实现

在浮点运算中,有几项细节十分重要:

  • 符号比较: 显式计算 f(a)f(b)f(a)f(b) 可能发生上溢或下溢。实现时可以先处理零值,再直接比较符号。
  • 插值分母: 相等或几乎相等的函数值可能使插值无定义,或在数值上不可靠。
  • 可表示的移动: 提出的增量可能小到无法改变当前浮点数。实现时需要规定能够产生实际变化的最小步长,或采用适当的终止检验。
  • 非有限值: 无穷大及未定义的数值结果需要显式处理;通常的收敛假设并不涵盖这些情况。
  • 复用函数值: 保存已经计算的函数值可避免不必要的函数调用,而函数调用可能占据计算成本的主要部分。

稳定的实现通常会计算经过代数重排的插值表达式,而不是直接使用上面展示的逆二次插值公式。数学上的等价并不意味着数值稳定性相同。

示例

考虑

f(x)=x3−x−2.f(x)=x^3-x-2.

由于

f(1)=−2,f(2)=4,f(1)=-2,\qquad f(2)=4,

区间 [1,2][1,2] 夹住了一个根。由这两个端点得到的割线试探点为

s=2−42−14−(−2)=43.s=2-4\frac{2-1}{4-(-2)} =\frac{4}{3}.

在该点处,

f(43)=−2627,f\left(\frac{4}{3}\right)=-\frac{26}{27},

因此,计算这个试探点的函数值后,可得到更窄的、两端函数值异号的夹根区间:

[43,2].\left[\frac{4}{3},2\right].

随着更多点可供使用,逆二次插值可以提出更准确的估计。如果这些试探点不合适,保障机制仍可改用二分法。原始区间内的根约为

r≈1.5213797068.r\approx 1.5213797068.

具体的试探点及迭代次数取决于实现方式和停止容差。

布伦特极小化法

同样称为布伦特法的优化算法,无需导数即可寻找标量目标函数的局部极小值。它结合了:

  • 抛物线插值:通过采样点拟合一个二次函数,并将其极小点作为试探点;
  • 黄金分割搜索:不依赖精确的抛物线模型即可缩小区间。

典型的极小值夹逼区间由三个有序点 a<x<ba<x<b 构成,满足

f(x)<f(a),f(x)<f(b).f(x)<f(a),\qquad f(x)<f(b).

只有当抛物线步骤的几何位置和步长满足适当的保障条件时,才会接受该步骤。否则,算法执行黄金分割步骤。

这与求根有根本区别:函数值是否异号在这里不起作用。夹住一个极小值,也不能证明它是更大定义域上的全局最小值。单峰性,即搜索区间内只有一个极小值,为可靠地缩小区间、逼近目标极小点提供了标准条件。

布伦特极小化法用于一维搜索,也用于更大型优化算法中的线搜索。噪声、多个局部极小值以及近乎平坦的目标函数,都可能降低抛物线插值的效用。

历史、用途与局限

理查德·P. 布伦特在西奥多勒斯·德克尔等人早期结合夹根与插值的混合方法基础上,发展出了这一求根算法。布伦特在1971年的一篇论文中介绍了改进后的算法,并在1973年出版的专著《无导数极小化算法》(Algorithms for Minimization Without Derivatives)中论述了求根与无导数极小化这两类问题。

布伦特求根法广泛用于科学计算软件,例如 SciPy 的 brentq 和 GNU 科学库的布伦特求解器。相关例程可能采用不同的插值公式或接受规则,因此仅凭名称,无法断定它们会产生相同的函数求值序列。

典型应用包括求解标量非线性方程、对单调函数求逆、确定阈值穿越点,以及根据累积概率求取分布的分位数。与牛顿法相比,布伦特法不需要计算导数,并且始终保留夹根区间;而在能够获得精确导数和合适初始近似时,牛顿法的局部收敛速度可能更快。

主要局限包括:

  • 必须先找到合适的、两端函数值异号的夹根区间。
  • 偶重根两侧的函数通常不变号,因此一般无法仅通过符号夹逼来检测这类根。
  • 包含多个根的夹根区间不能指定其中某一个根。
  • 不连续性可能使根存在性的保证失效。
  • 带有噪声或不准确的函数值可能同时干扰符号判断与插值。
  • 标准方法处理的是标量实数问题,而不是非线性方程组或一般的复数求根问题。