引子：怎么找一个单峰函数的极值

给定一个在区间 \([a,b]\) 上先降后升的单峰函数，怎么又快又稳地找到它的极小点？这是数值优化里最基础的一维问题，也是各种高维优化里"线搜索"（line search）步骤的内核。方法有一大把：三分查找、黄金分割、Fibonacci 查找、抛物线插值、Brent、二分/牛顿……

这篇文章把它们放在一起做个综述，全部用同一套基准诚实地量：同样的测试函数、同样的精度、数每种方法花了多少次函数求值，并检查是否都收敛到了正确答案。核心的一条主线是：一个方法用了函数的多少信息，决定了它能有多快，也决定了它的适用范围。

黄金分割"快"在哪：复用点

先从最经典的黄金分割查找（golden section search）说起。很多人以为它的精髓是那个神奇的比率 \(\varphi=0.618\dots\)，其实不是——精髓是"复用点"。

在区间 \([a,b]\) 放两个内点 \(c = b - \varphi(b-a)\)、\(d = a + \varphi(b-a)\)，比较 \(f(c)\) 和 \(f(d)\)，丢掉更差的一端。黄金比率满足自相似性质 \(\varphi^2 = 1-\varphi\)，使得收缩后的新区间里，旧的一个内点恰好落在新的黄金分割位置。下一轮只需算一个新点，另一个直接复用。

一句话：黄金分割每轮区间收缩到 0.618，但只花 1 次函数求值。 对比之下，三分查找每轮把区间缩到 2/3，看起来比 0.618 更狠，可它两个内点每轮都要重算，每轮花 2 次求值，摊下来反而更亏。这说明衡量快慢不能只看单轮收缩幅度，要看"每次求值能换来多少收缩"。

有限轮数下的最优：Fibonacci 查找

黄金分割的比率是恒定的。有没有可能让比率逐轮变化，既缩得更聪明、又保持复用？

有。用 Fibonacci 数列 \(F_n = 1,1,2,3,5,8,13,\dots\) 来定分点。给定精度需要的轮数 \(n\)，每轮的保留比率取 \(F_{n-k}/F_{n-k+1}\)。因为 Fibonacci 有递推 \(F_{n} = F_{n-1}+F_{n-2}\)，这个结构恰好也能复用一个旧点，每轮只算一个新点——和黄金分割一样省，但比率是逐轮变化的：

有意思的是：黄金分割查找其实就是 Fibonacci 查找在 \(n\to\infty\) 时的极限——比率不再变化、恒为 \(\varphi\)。而对有限轮数，Fibonacci 是理论最优的：在"只能比较函数值大小"的框架下，给定固定的求值次数，Fibonacci 能把最终区间压到最小（Kiefer 1953 证明）。

import math
phi = (math.sqrt(5) - 1) / 2

def fibonacci_search(f, a, b, tol=1e-6):
    calls = 0
    def F(x):
        nonlocal calls; calls += 1; return f(x)
    fib = [1, 1]
    while fib[-1] < (b - a) / tol:
        fib.append(fib[-1] + fib[-2])
    n = len(fib) - 1
    c = a + fib[n-2]/fib[n]*(b-a)
    d = a + fib[n-1]/fib[n]*(b-a)
    fc, fd = F(c), F(d)
    for k in range(1, n-1):
        if fc < fd:
            b, d, fd = d, c, fc
            c = a + fib[n-k-2]/fib[n-k]*(b-a)   # 比率逐轮变
            fc = F(c)                            # 但只算 1 个新点
        else:
            a, c, fc = c, d, fd
            d = a + fib[n-k-1]/fib[n-k]*(b-a)
            fd = F(d)
    return (a + b) / 2, calls

上代码，诚实地量所有方法

同一套 8 个单峰测试函数（二次、四次、尖谷、非对称指数、平底等），统一收敛到 \(10^{-6}\)，数每种方法的函数求值次数，并检查是否收敛正确：

（*二分需要导数，仅在 6 个可导函数上统计）

几个结论一目了然：

• 三分查找最慢：它不复用，每轮 2 次求值，虽然区间每轮缩到 2/3，但摊下来最亏。
• Fibonacci 略胜黄金分割（240 vs 248）：因为它在有限轮数下是最优的，黄金分割只是它的极限近似。
• 黄金分割是"够用且简单"的选择：不用预先算轮数，实现最短，性能只比最优差一点点。

真正的加速：利用更多信息

黄金分割和 Fibonacci 都只用了 \(f(c)<f(d)\) 这一个比较（一个比特），太浪费。想更快，就得用函数值里更多的信息。

抛物线插值（successive parabolic interpolation）用最近三点拟合抛物线，取顶点作为下一个试点：

在光滑函数附近超线性收敛，二次函数上一步到位（表中"二次"只用 5 次）。但它对尖谷、平底会失灵（"平底四次"用了 54 次，比黄金分割还慢）。

Brent 方法是工程上的标准答案：能抛物线插值就插值，插值越界或不老实就退回黄金分割兜底。既拿到插值的快，又保住黄金分割的稳，8 个函数只用 136 次，全部收敛正确。这也是 scipy.optimize.minimize_scalar 默认用的方法。

如果能拿到导数，那就更快：极值点等价于导数的零点，直接对导数做二分（120 次），甚至用牛顿法，但代价是必须有梯度。

方法家族全景

把这些方法按"用了多少信息"排一下，脉络就清楚了：信息用得越多，收敛越快，但对函数的要求也越高。

• 只比函数值大小（最通用，连不可导、有噪声都能用）：三分 → 黄金分割 → Fibonacci（最优）。
• 还用函数值的具体数值（曲率）：抛物线插值 → Brent（插值+兜底）。
• 还能用导数：二分（导数符号）→ 牛顿法（导数值），最快但要求最苛刻。

三种区间法同屏对比

最后放一个动画，让三分、黄金分割、Fibonacci 在同一个函数上同屏收缩。三分的区间每轮缩得多但费两次求值；黄金分割和 Fibonacci 缩得稳，且每轮只花一次。

小结

• 黄金分割查找的精髓是复用点：每轮收缩到 0.618，只花 1 次求值；三分不复用，所以更慢。
• 想在保持复用的同时让比率变得更聪明，正确做法是 Fibonacci 查找：比率逐轮变化（0.5→0.667→0.6→…→φ）却仍复用一点，且在有限轮数下理论最优。黄金分割正是它 \(n\to\infty\) 的极限。
• 真想更快，方向是用函数值里更多的信息：抛物线插值（用曲率）→ Brent（插值+黄金兜底，工程首选）；若有导数，二分/牛顿更快，但要求更高。
• 选型口诀：通用稳妥用 Brent，纯比较场景用黄金分割/Fibonacci，有梯度就上牛顿。