技术摘要：一种基于均匀间距收缩的随机区间套求根方法

1. 问题陈述

本文研究了在有界区间内求解非线性方程 $f(x) = 0$ 的数值问题，特别是在无导数黑盒设置下的问题。在这种环境下，函数评估可能非常昂贵、存在轻微噪声，或者具有天然的可并行性，且无法获取导数信息。

作者识别了经典确定性方法之间的差距：

• 区间套法（Bracketing methods）（如二分法）：具有鲁棒性并能保证产生有效的含根区间，但在收敛速度上往往过于保守。
• 开放法（Open methods）（如割线法、牛顿法）：可以实现快速收敛，但缺乏保证区间保存的能力，且对初始化或局部几何结构较为敏感。

其目标是开发一个既能保持经典方法保证区间保存特性，又能引入随机收缩机制的框架，从而利用批量或并行的函数评估来减少更新阶段的数量。

2. 方法论：随机区间收缩 (RIC) 框架

所提出的方法被称为 RIC-m，是一种随机的保持区间性质的区间收缩算法。该算法在假设 $f$ 在初始区间 $[a_0, b_0]$ 上连续且严格单调，且满足 $f(a_0)f(b_0) < 0$ 的前提下运行。

算法工作流

1. 初始化： 从包含唯一根 $x^*$ 的有效区间 $I_n = [a_n, b_n]$ 开始。
2. 采样： 在每次迭代 $n$ 中，从当前区间 $(a_n, b_n)$ 中独立且均匀地抽取 $m$ 个内部点 $X_{n,1}, \dots, X_{n,m}$。
3. 排序： 对采样点进行排序，得到顺序统计量 $X_{n,(1)} \le \dots \le X_{n,(m)}$。
4. 候选构造： 这些点与端点结合，将当前区间划分为 $m+1$ 个随机子区间（间距）。由此形成一个候选子区间族。
5. 选择： 算法识别出最短的可容许子区间。如果子区间端点的函数值符号相反（或其中一个为零），则称该区间为“可容许”的，这确保了它包含根。
6. 更新： 将当前区间更新为这个最短的可容许区间 $I_{n+1}$。
7. 终止： 重复此过程，直到区间长度低于容差 $\epsilon$。

与二分法的关键区别

不同于确定性的二分法（其将区间精确平分为两半，固定收缩因子为 $1/2$），RIC 方法的收缩是随机的，并受由均匀采样诱导的随机间距几何结构所支配。下一个区间是由包含根的局部间距配置决定的。

3. 理论贡献与分析

论文通过将算法性能与顺序统计量和最大间距理论联系起来，提供了严谨的概率分析。

收缩界限

核心理论见解在于，期望收缩因子受限于 $[0,1]$ 上 $m$ 个均匀点生成的最大间距（$B_m$）的期望值。

• 令 $S_0, \dots, S_m$ 为归一化间距。
• 收缩基准为 $B_m = E[\max_{0 \le j \le m} S_j]$。
• 论文证明了期望区间长度满足 $E[L_{n+1}] \le B_m L_n$ 几乎处处成立。
• 关于 $B_m$ 的显式公式推导为：$B_m = \frac{1}{m+1} \sum_{k=1}^{m+1} \frac{1}{k}$。
• 关键发现： 当 $m \ge 4$ 时，基准 $B_m$ 会降至二分法因子 $0.5$以下（例如，$B_4 \approx 0.457$）。

收敛保证

在精确函数评估且严格单调的假设下：

1. 根保存： 算法在每次迭代中都维持一个包含 $x^*$ 的有效区间。
2. 依概率收敛： 区间长度 $L_n$ 依概率收敛于 0，这意味着中点估计量 $\hat{x}_n$ 依概率收敛于 $x^*$。
3. 几乎处处收敛： 在满足轻微的对数矩条件（这在均匀间距下自动满足）的情况下，区间长度几乎处处收敛于 0。

复杂度与权衡

论文分析了样本量 $m$ 与计算成本之间的权衡，涵盖两种模型：

• 串行模型： 成本与总函数评估次数成正比（$N_{serial} \approx m \times \text{迭代次数}$）。较大的 $m$ 虽然能提高每步的收缩率，但会增加每步的成本。论文指出，随着 $m$ 的增大，串行效率存在收益递减现象。
• 批量/并行模型： 成本与更新阶段（迭代次数）的数量成正比。在此模式下，较大的 $m$ 能显著减少达到目标精度所需的阶段数量，因为收缩因子 $B_m$ 随之减小。

4. 数值实验结果

作者在五个单调测试函数和一个非单调探索性案例上进行了数值实验。

• 收缩行为： 观察到的经验收缩因子（$\hat{\rho}_m$）始终低于理论上限 $B_m$，证实了最大间距分析的保守性。
• 样本量影响： 将 $m$ 从 2 增加到 10，使平均迭代次数减少了一半以上（例如，对于 $m=10$，从约 23 次减少到约 9.75 次），但增加了总的函数评估次数。
• 与确定性求解器的比较：
  • 与二分法相比，当 $m \ge 3$ 时，RIC-m 需要更少的迭代次数，但在串行设置下需要更多的总函数评估次数。
  • 与割线法和 Brent 法相比，在平滑、串行、无噪声的环境中，RIC-m 的效率较低。论文明确指出，在这些环境下，它并不旨在取代这些成熟的求解器。
• 噪声环境： 在一项带有加性高斯噪声的探索性研究中，RIC 方法保持了 100% 的区间收缩成功率，优于因符号误判而导致失败的割线法和 Brent 法。

5. 重要性与主张

本文将自身的贡献定位为一个基础框架，而非通用的求解器替代品。

• 新颖性： 本文被呈现为第一个将收敛分析显式通过均匀顺序统计量的最大间距理论（而非确定性细分规则）进行构建的保持区间性质的求根框架。
• 利基应用： 该方法专为以下无导数黑盒机制设计：
  • 保证区间保存至关重要。
  • 函数评估昂贵或具有天然的可并行性（批量处理）。
  • 需要对评估不规则性（噪声）具有鲁棒性。
• 可调参数： 参数 $m$ 提供了一种透明的机制，用于在收缩强度与单次迭代成本之间进行权衡。
• 限定范围： 作者承认其理论保证依赖于严格单调性和精确的符号信息。针对非单调函数、多根情况或噪声 Oracle 的扩展被列为未来的研究方向，而非当前的声明。

综上所述，本文建立了随机采样、顺序统计量与区间收缩之间的概率联系，为那些并行评估和区间安全性高于纯串行效率的特定计算环境，提供了一种鲁棒的替代方案。