c - 如果您已经知道输出，找到函数输入的最佳方法是什么？

Question

我正在处理一个相当复杂的程序，不幸的是我把自己逼到了一个角落。

我有一个函数(为简单起见，我们称它为 f(x))，我知道它的输出值，我需要找到生成该输出值的输入值(在特定阈值内)。

不幸的是，f(x) 背后的方程相当复杂，我没有我需要的所有信息来简单地反向运行它们 - 所以我不得不执行某种蛮力搜索以找到正确的输入变量代替。

f(x) 的输出保证有序，f(x - 1) < f(x) < f(x + 1) 始终为真。

找到 x 值的最有效方法是什么？我不完全确定这是否是一个“寻根”问题——它看起来非常接近，但又不完全是。我想这种算法应该有一些正式名称，但我在 Google 上找不到任何东西。

Answer 1

我假设 x是一个整数所以结果 f(x - 1) < f(x) < f(x + 1)意味着该函数是严格单调的。

我也假设你的功能不是病态的，比如

f(x) = x * cos(2 * pi * x)

它满足您的属性，但在 x 的整数值之间存在各种问题.

线性二分法 算法在这里是合适且易于处理的(并且您可以将其调整为对于非整数 x 表现不佳的函数)，Brent 可能会恢复解决方案更快。这样的算法很可能会返回一个非整数值 x ，但您始终可以检查它的任一侧的整数，并返回最好的一个(如果函数在 x 的 所有 实数值中是单调的，这将起作用)。此外，如果您有 f(x) 的解析一阶导数 ，那么 Newton Raphson 的改编可能会很好，约束 x是不可或缺的(这可能没有多大意义，具体取决于您的功能；将其应用于上面的病态示例将是灾难性的!)。 Newton Raphson 很可爱，因为您只需要一个起点，这与 Linear Bisection 和 Brent 不同，它们都需要 括号 的根。

用 Google 搜索我斜体的条款。

引用:Brent's Method - Wikipedia