三分法求单峰(单谷)函数极值

时间：2021-10-06 19:06:35

what is 三分法

对于二分，相信你一定十分熟悉。就是在一个具有单调性序列上查找你所需要的数字。由于其单调性，你每一次在查找是就可以将规模缩小一半，大致就是：
1.假设这个数列单调递增
2.维护一个区间左端点\(l\)，区间右端点r和中间点\(mid\)
3.如果\(mid\)比想要的值小，则左边肯定不可以，那么\(l=mid\)
2.如果\(mid\)比想要的值大，则右边肯定不可以，那么\(r=mid\)
因此大致就可以这么写：

while (l+1<r)
{
    int mid=l+r>>1;
    if (v<a[mid) r=mid;
    else l=mid;
}

不保证代码正确，但是具体思想就是这样。
三分也一样啊：
对于一段抛物线（极值的一边单调递增，极值的一边单调递减）我们就可以把它分成三段，根据其图像特性来求解。

三分法求二次函数峰值

对于三分，我们用左端点\(lmid\)和\(rmid\)进行维护，将这个图像分成三段。并且图像区间的左右端点分别是\(l<r.\)则我们可以选择这么考虑：（以二次函数\(y=-5x^{2}+8x-1\)为例）
如图所示：
三分法求单峰(单谷)函数极值
当\(lmid\)处于\(A\)点,\(rmid\)处于\(B\)点时：可将左端点\(l\)缩到\(lmid\)，右端点不变以保证极值存在。
当\(lmid\)处于\(A\)点,\(rmid\)处于\(C\)点时：照样可以将\(l\)缩到\(lmid\)。
同理，
当\(lmid\)处于\(C\)点,\(rmid\)处于\(D\)点时：可将右端点\(r\)缩到\(rmid\)，左端点不变以保证极值存在。
当\(lmid\)处于\(B\)点,\(rmid\)处于\(B\)点时：照样可以将\(r\)缩到\(rmid\)。
故得到结论：
\[f(l)<f(r)→l=lmid\]
\[f(l)≥f(r)→r=rmid\]
然后就进行简单的代码实现：

#include<bits/stdc++.h>
using namespace std;
double a,b,c;
inline double f(double x) {
    return a*x*x+b*x+c;
}
int main(void)
{
    cin>>a>>b>>c;
    //形如y=ax^2+by+c的二次函数
    double l=-1e9,r=1e9;
    while (l+1e-9<r)
    {
        double lmid=l+(r-l)/3.0;
        //图像上位于1/3部分的靠左的mid值 
        double rmid=l+(r-l)/3.0*2.0;
        //图像上位于2/3部分的靠右的mid值
        if (f(lmid)<f(rmid)) l=lmid;
        else r=rmid;
        //求单峰极值 
    } 
    cout<<"X="<<l<<'\n';
    cout<<"Y="<<f(l); 
}

二次函数求单谷谷值 & 高次函数应用

通过画图和分类讨论\(a<0\)的情况，不难得出：
\[f(l)＞f(r)→l=lmid\]
\[f(l)≤f(r)→r=rmid\]
代码实现只要if内反一下即可：

#include<bits/stdc++.h>
using namespace std;
double a,b,c;
inline double f(double x) {
    return a*x*x+b*x+c;
}
int main(void)
{
    cin>>a>>b>>c;
    //形如y=ax^2+by+c的二次函数
    double l=-1e9,r=1e9;
    while (l+1e-9<r)
    {
        double lmid=l+(r-l)/3.0;
        //图像上位于1/3部分的靠左的mid值 
        double rmid=l+(r-l)/3.0*2.0;
        //图像上位于2/3部分的靠右的mid值
        if (f(lmid)>f(rmid)) l=lmid;
        else r=rmid;
        //求单峰极值 
    } 
    cout<<"X="<<l<<'\n';
    cout<<"Y="<<f(l); 
}

如果需要高次函数过其它图像，只要在f内稍作修改即可。
标签：

相关文章