三分法
举一反三,二分法是将区间一分为二,那么三分法就是将区间一分为三。
那么有了二分,为什么还要有三分呢?
原因是:二分算法解决的是单调函数求极值的问题,而三分算法解决的是单峰函数求极值的问题。
具体来讲,二分法可以解决一次函数的极值,而二次函数就要交给三分法解决了。
三分法具体怎么使用呢?让我们来看一个例子:
在图中,三分我们将获得m1,m2两个点的值,
因为m2<m1,所以m2相较于m1更靠近极值点,于是我们让l=m1。
等等,如果m1,m2都处于极值点的一侧呢?
我们发现,上面的结论依然成立,m1依旧会被无情地抛弃。
多次进行上面的操作,便可以找到单峰函数的极值点了。