一元函数，单峰函数；

<aside> 💡

目的在减少计算函数值点的个数。（相比三等分法直接抛弃一个三分点）

</aside>

黄金分割法：

将区间分成三份，恰好按黄金分割比划分。其划分思路是：

插入到两端点相同的$\lambda=1-\mu$，在抹去某段后，$\mu$同样可分相同比例的三段$\mu/1=\lambda/\mu,\frac{1-\lambda}{1}=\frac{1-\mu}{1-\lambda}$，这样$\mu$可以复用，每次抹去只需要增加一个划分。

其抹去思路是：

根据$[\lambda,\mu]$划分点区间端点的大小判断，已知目标函数$f$为单峰函数，若$f(a_{i+1})<f(b_{i+1})$，则抹去右边，保留$[a_i,b_{i+1}]$；若$f(a_{i+1})\ge f(b_{i+1})$，则抹去左边，保留$[a_{i+1},b_{i}]$。每次抹去，区间收缩$\frac{b_{i+1-a_{i}}}{b_{i+1-a_{i+1}}}=\frac{b_{i-a_{i+1}}}{b_{i+1-a_{i+1}}}=\mu\approx0.618$，经过$n$次迭代，区间收缩到原长度的$\mu^N$

Untitled

$$ \begin{cases}\lambda=\frac{3-\sqrt5}{2}\approx0.382\\\mu=\frac{\sqrt5-1}{2}\approx0.618\end{cases} $$

Untitled

改进：

<aside> 📹

抽出为三段法：每次迭代划分一次区间，比较抛弃一侧区间，保留另一划分点函数值。

</aside>

  1. 动态划分比例：以一个黄金分割比为极限的数列作划分比例序列。如“斐波那契数列”

    $$ F_{-1}=0,F_0=1,F_1=1,\cdots $$

    $$ \begin{aligned}&\rho_{1}&& =1-\frac{F_{N}}{F_{N+1}}  \\&\rho_{2}&& =1-\frac{F_{N-1}}{F_{N}}  \\&\cdots\\&\rho_{k}&&=1-{\frac{F_{N-k+1}}{F_{N-k+2}}}  \\&\cdots\\&\rho_{N}&& =1-\frac{F_{1}}{F_{2}} \end{aligned} $$

    $$ \frac{F_n}{F_{n+1}}\to\mu,1-\frac{F_n}{F_{n+1}}\to\lambda $$

    可以证明，【斐波那契数列法】的分法是所有动态划分方法的最优方法。

    $$ (1-\rho_{1})(1-\rho_{2})\cdots(1-\rho_{N})=\frac{F_{N}}{F_{N+1}}\frac{F_{N-1}}{F_{N}}\cdots\frac{F_{1}}{F_{2}}=\frac{F_{1}}{F_{N+1}}=\frac{1}{F_{N+1}} $$

    为避免重合：

    Untitled