黄金分割搜索算法原理与C++实现

1. 黄金分割搜索算法原理与实现

黄金分割搜索是一种基于黄金分割比例(φ≈1.618)的一维优化算法，用于在给定区间内寻找单峰函数的极值点。与二分查找类似，它通过不断缩小搜索区间来逼近最优解，但采用了更高效的区间划分策略。

1.1 数学基础与算法原理

黄金分割比φ=(1+√5)/2≈1.6180339887具有独特的数学性质：φ²=φ+1。这个特性使得算法可以保持每次迭代的区间划分比例不变。

算法工作流程：

1. 初始化搜索区间[a,b]
2. 计算两个内点：c = b - (b-a)/φ，d = a + (b-a)/φ
3. 比较f(c)和f(d)的值：
   • 若f(c) < f(d)，则极值在[a,d]区间，更新b=d
   • 否则极值在[c,b]区间，更新a=c
4. 重复步骤2-3直到区间长度小于容差tol

关键点：每次迭代后搜索区间会缩小为原区间的1/φ≈0.618倍，这使得算法具有线性收敛速度。

1.2 C++实现详解

cpp复制double GoldenSectionSearch(const std::function<double(double)> &func,
                          const double lower_bound, const double upper_bound,
                          const double tol) {
  static constexpr double gr = 1.618033989;  // 黄金分割比例
  
  double a = lower_bound;
  double b = upper_bound;

  double t = (b - a) / gr;
  double c = b - t;
  double d = a + t;

  while (std::abs(c - d) > tol) {
    if (func(c) < func(d)) {
      b = d;
    } else {
      a = c;
    }
    t = (b - a) / gr;
    c = b - t;
    d = a + t;
  }
  return (a