三分查找

三分查找用于求单峰函数的极值。
速度快,但是结果并非准确值。

方法

首先,在函数上标4个点:$x=le,rt,mid,mmid$。其中$mmid$$mid$$rt$的中点。

选点

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

  1. 如果$f(mid)>f(mmid)$,则$mmid$一定在峰的右边。
  2. 如果$f(mid)<f(mmid)$,则$mid$一定在峰的左边。

证明: 1. 我们假设存在$f(mid)>f(mmid)$$mmid$在峰的左边。
由于$f(x)$在峰的左边单调递增,且$f(mid)>f(mmid)$,所以$mid$$mmid$右边
然而$mmid = \frac{mid+rt}{2}$,显然$mid$$mmid$左边。矛盾。

2. 我们假设存在$f(mid)<f(mmid)$$mid$在峰的右边。
由于$f(x)$在峰的右边单调递减,且$f(mid)<f(mmid)$,所以$mid$$mmid$右边
然而$mmid = \frac{mid+rt}{2}$,显然$mid$$mmid$左边。矛盾。

食用姿势

首先我们要证明,需要三分的函数是个单峰函数
然后就可以写三分了。

如何控制精度?
两种办法。一种是控制迭代次数,一种是直接控制精度

控制迭代次数:设一个$lambda$值,迭代了这么多次之后就退出。
直接控制精度:设一个精度限制$eps$,如果$rt-le < eps$就退出。

具体用哪种方式由题目决定
一般来说,如果题目要求控制相对精度,控制迭代次数比较好;如果题目要求控制绝对精度,直接去控制精确到小数点后多少位比较好。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close