黄金分割搜索的终止标准

计算科学 优化
2021-12-01 14:46:47

阅读黄金分割搜索的实现,我遇到了以下终止测试:

|ad|<ε(|b|+|c|)

在哪里a<b<c<d是探测函数的四个点,并且ε是用户提供的容差。为什么这是一个好的终止标准?如果我采用一个函数和一个初始括号并沿横坐标平移它们,算法应该以相同的方式探测函数,但是这个测试将在不同的迭代中终止运行......

干杯!

1个回答

|b|+|c|具有与极值相同的数量级。因此,无论您有多少有效数字|b|+|c|尽可能准确地计算极值的位置。通过确保您的支架是其中的一小部分,您可以确保您有一个可到达的条件,同时仍然尽可能地获得尽可能高的准确性。

例如,假设您的极值在109并且您正在以单精度工作。有 7 个信号。无花果。在单精度中,你只能希望得到一个答案 within100的实际值(单精度根本没有精度做得更好)。在这种情况下,您必须将误差容限(不等式的 rhs)至少设置为100否则您的算法将永远不会收敛。在另一种情况下,您可以有一个具有极值的函数103. 如果你使用上次运行的参数,你会发现一个介于 -100 和 100 之间的数字,而且离你很远。

但是,如果您将 epsilon 设置为107,您将测量极值的准确度约为100在第一种情况下,准确度约为1010在收敛之前的第二种情况。这在两种情况下都使用完全相同的参数。

当您在浮点运算中存在未知的极值位置时,这是一种解决方法。如果您有任意精度,或者知道解决方案的大致位置,您可以设置一个固定的误差范围,并且该算法将运行良好。