根查找

工作正在进行中。尚未准备好用于生产！

Rust中实现的根查找算法。

该包旨在提供适合生产使用的稳健数值方法。它包括广泛的文档和测试覆盖。

当前特性

• 区间生成
• 二分法
• 不动点法，Illinois方法

一些额外的方法目前只能以它们的“原始”形式提供。这些方法适用于重现学术文献中的结果，但不适合生产使用

• 牛顿-拉夫森
• 哈雷方法

正在开发适合生产使用的变体，这些变体将这些高阶方法与二分法混合，以确保收敛。

可以通过IsConverged特性行供自定义收敛标准。提供了一些合理的预定义实现。

与大多数数值方法一样，根查找算法需要您了解您试图实现什么，输入函数的性质，所使用的算法的特性等等。

欢迎反馈。

使用方法

请参阅rustdocs以获取详细文档。

以下示例摘自tests/integration.rs。

extern crate rootfind;

use rootfind::bracket::{Bounds, BracketGenerator};
use rootfind::solver::bisection;
use rootfind::wrap::RealFn;

// roots at 0, pi, 2pi, ...
let f_inner = |x: f64| x.sin();

// rootfind determines via traits what is f(x), df(x), d2f(x), etc.
// the RealFn wrapper annotates our closure accordingly.
let f = RealFn::new(&f_inner);

// search for root-holding brackets
let window_size = 0.1;
let bounds = Bounds::new(-0.1, 6.3);

for (i, b) in BracketGenerator::new(&f, bounds, window_size)
    .into_iter()
    .enumerate()
{
    // find root using bisection method
    let max_iterations = 100;
    let computed_root = bisection(&f, &b, max_iterations).expect("found root");

    // demonstrate that we found root
    let pi = std::f64::consts::PI;
    let expected_root = (i as f64) * pi;

    assert!(
        (computed_root - expected_root).abs() < 1e-9,
        format!("got={}, wanted={}", computed_root, expected_root)
    );
}

剩余工作

算法

1. 与区间方法混合以确保全局收敛的牛顿-拉夫森和哈雷方法的“安全”变体。

2. 没有解析导数时的TOMS-748实现，用于寻找根。（这提供了具有二分法和不动点法作为后备选项的良好默认选择）。

3. 用于寻找多项式根的专用例程。

设计

1. 在运行过程中提供对求解器状态的可见性。

2. 允许优化的牛顿-拉夫森，其中直接提供分数f(x)/f'(x)，而不是在运行时计算。项的消除提供了性能优化的机会。

3. 区间方法的收敛标准。

4. 检查收敛区间实际上是否关闭在根上，而不是跳跃不连续。

交叉验证

我想将设计和实现与C++ Boost、SciPy和GSL的根查找实现进行交叉验证。

通往1.0.0的道路

该项目使用语义版本控制（主要.次要.补丁）。剩余工作大多属于“次要”增量。当所有这些都完成时，我想要一些外部审查或反馈，然后才能发布正式的1.0.0版本。

参考文献

《数值算法》这本书深入探讨了根查找的实现和方法。

William H. Press, Saul A. Teukolsky, William T. Vetterling, 和 Brian P. Flannery. 2007. 《数值算法》第三版：科学计算的技巧（第3版）. 剑桥大学出版社，纽约，纽约，美国。

这是实践者的顶级资源。然而，由于版权问题，Rust rootfind 库避免了 NR 的实现。

关于根查找的另一个合理介绍可以在以下找到：

Recktenwald, G. W. (2000). 使用 MATLAB 的数值方法：实现和应用. Upper Saddle River, NJ: Prentice Hall.

维基百科的“根查找算法”页面提供了对根查找技术的概述，但它缺乏对实践者的指导和细节。特定算法的页面值得一读。

我还发现 Boost、SciPy 和 Gnu Scientific Library 的根查找实现和文档很有帮助。

作者

本文由 Niek Sanders 撰写（[email protected]）。

无许可

这是一个免费且不受限制的软件，已发布到公共领域。

任何人都可以自由复制、修改、发布、使用、编译、出售或分发此软件，无论是源代码形式还是编译后的二进制形式，出于任何目的，商业或非商业，以及任何手段。

在承认版权法的司法管辖区，本软件的作者或作者将软件的所有版权利益捐赠给公共领域。我们做出这一捐赠是为了公众利益，损害我们的继承人后继者的利益。我们打算将此捐赠视为一项永久放弃在版权法下所有现有和未来权利的明确行为。

本软件按“原样”提供，不提供任何保证，无论是明示的还是暗示的，包括但不限于适销性、适用于特定目的和非侵权的保证。在任何情况下，作者不对任何索赔、损害或其他责任承担责任，无论该责任是基于合同、侵权或其他原因，是否由于、从或与软件或软件的使用或其他处置有关。

如需更多信息，请参阅 http://unlicense.org/