【数学】三分查找

这里写图片描述

三分法用于求解单峰函数极值

速度快,但结果并非准确值

 

如图先标4个点,其中mmid​是midR的中点​

现在任务是通过迭代缩小范围

1.如果f(mid)>f(mmid),则mmid一定在峰的右边

2.如果f(mid)<f(mmid),则mid一定在峰的右边

当最后当L=R-1 ​时,再比较小两个点的值,我们就找到了答案

精度控制:两种办法

控制迭代次数:设一个\lambda ​值,迭代了这么多次之后就退出。
直接控制精度:设一个精度限制\varepsilon​,如果R-L<\varepsilon就退出。

实现:凸函数

const double eps = 1e-6;

double trichotomy(double L,double R){
    double mid,mmid;

    while(R - L >= eps){
        mid = L + (R - L) / 3;
        mmid = R - (R - L) / 3;

        if(f(mid) <= f(mmid)){
            L = mid;
        }else{
            R = mmid;
        }
    }

    return (mid + mmid) / 2;
}

凹函数:

const double eps = 1e-6;

double trichotomy(double L,double R){
    double mid,mmid;

    while(R - L >= eps){
        mid = L + (R - L) / 3;
        mmid = R - (R - L) / 3;

        if(f(mid) <= f(mmid)){
            R = mmid;
        }else{
            L = mid;
        }
    }

    return (mid + mmid) / 2;
}