algorithm - 我怎样才能在我的 matlab 脚本中拦截这个近似错误？

Question

我正在尝试使用此算法找到函数的最小值。这不是最佳算法，但目前我不在乎。

此外，您不必知道算法的工作原理才能回复，但如果您好奇，我会在本文末尾讨论。这真的没有那么难。

牵连算法

function result = fmin(f,a,b,max_error)
if abs(b-a) < max_error
    result = (a+b)/2;
else
    r1 = a+(b-a)*rand(1,1); r2 = a+(b-a)*rand(1,1);
    c = min([r1,r2]); d = max([r1,r2]);
    fc = f(c); fd = f(d);  
    if fc <= fd
        b = d;
    else
        a = c;
    end
    result = fmin(f,a,b,max_error);
end

现在，问题是此算法返回的最小值与实际最小值(通过 matlab 预定义函数 fminbnd 计算)相去甚远，超过了 max_error。 ，如果我将它与 max_error <= 1e-10 的值一起使用.这种情况，从理论上讲是不可能的。

作为递归算法，如果条件 abs(b-a) < max_error 永远不会返回永远不会满足。

因此，我认为数字的近似值存在一些误差。起初，我以为r1或 r2哪里没有正确计算。在某些时候，这两个数字会超出 [a,b]。间隔，从而使算法所依据的假设无效。

为了证明这一点，我修改了上面的算法以包括对每次迭代计算的间隔的检查:

Incriminated 算法 2 [检查极端情况]

function result = fmin(f,a,b,max_error)
if abs(b-a) < max_error
    result = (a+b)/2;
else
    r1 = a+(b-a)*rand(1,1); r2 = a+(b-a)*rand(1,1);
    c = min([r1,r2]); d=max([r1,r2]);
    % check that c and d are actually inside [a,b]
    if ((c < a)||(d > b))
        disp('Max precision reached');
        result = (a+b)/2;
        return;
    end
    fc = f(c); fd = f(d);  
    if fc <= fd
        b = d;
    else
        a = c;
    end
    result = fmin(f,a,b,max_error);
end

但我没有从控制台获得任何额外的输出。

因此，我认为 f(c) 的计算存在一些错误或 f(d) , 但我不知道如何证明。

问题

最后，我的问题是

1. 在这一点上，我们是否可以确定在计算 f(c) 中的任何一个时都犯了错误？或 f(d) ？
2. 我们可以用一些代码来证明吗？或者更好的是，我们能否编写算法，使其按预期返回？

算法是如何工作的(严格来说不是问题固有的)

这是一个迭代算法。基本上，想法是生成包含解的区间序列，从初始区间 [a,b] 开始，其中给定函数 f是单峰的。在每一步，我们随机选择两个数字 c和 d这样a <= c <= d <= b .现在，如果我们发现 f(c) > f(d)这意味着我们确定我们可以丢弃函数在 c 之前假定的值由于单峰性，作为最低限度的有效候选人。所以我们限制区间并在区间 [c,b] 重复该过程.相反，如果是 f(c) < f(d) , 我们可以丢弃 d 中的值至 b , 所以我们在区间 [a,d] 重复这个过程.

在每次迭代中，间隔会变短。当其长度小于指定的 max_error 时值，算法返回最后一个区间的中间点作为最小值的近似值。

---

编辑

我看到有人想结束这个问题，因为它太宽泛了。请先生，您能在评论中详细说明吗？

Answer 1

这种分割方法仅适用于您的函数是(准)凸函数(一个局部最小值，单调向左下降，向右上升)的特殊情况。在有多个局部极小值的情况下，它通常会收敛到其中一个，但决不能保证算法会找到全局最小值。从 a 减少到 c resp。从b到d可以跳过几个局部最小值。