Cha*_*les 5 language-agnostic algorithm math
假设您被赋予单个变量和参数a和b的函数,并被要求查找函数在区间[a,b]上采用的最小值.(您可以假设参数是双精度的,但在我的应用程序中,我可能需要使用任意精度库.)
一般来说,这是一个难题,因为功能可能很奇怪.这个问题的一个简单版本是最小化函数,假设它是连续的(无间隙或跳跃)和单峰值(有一个唯一的最小值;在最小值的左边,函数正在减小,在右边它是增加).有没有一种好方法可以解决这个问题(但也许并不容易!)？
假设函数可能难以计算,但存储您计算的答案并不是特别昂贵.(显然,如果你不必制作巨大的键/值对数组,那就更好了.)
关于在幸运案例中改进算法的好主意的好处(例如:导数存在,函数是平滑/解析,导数可以以封闭形式计算,导数可以在评估函数时免费计算) .
您描述的版本具有一个最小值，很容易解决。
想法是这样的。假设我有 3 个点a < b < c和f(b) < f(a)。f(b) < f(c)那么真正的最小值在a和之间c。此外，如果我d在区间中的某个位置选择另一个点，那么我可以丢弃其中一个a或d，并且仍然有一个区间，其中真正的最小值位于中间。随着我进行更多的迭代，我的近似值将呈指数级快速提高。
我们还没有完全从这个开始。a我们从 2 点和开始b，并且知道答案在中间的某个位置。取中点。如果f低于终点，我们就进入了我上面讨论的情况。否则，它必须低于其中一个端点，并高于另一个端点。我们可以丢弃较高的端点并重复。