## 1. 斐波那契优化算法：为什么它比“盲人摸象”更聪明？ 大家好，我是老张，在算法和优化领域摸爬滚打了十几年。今天想和大家聊聊一个听起来很“数学”，但用起来却异常“聪明”的优化方法——斐波那契优化算法。很多朋友一听到优化算法，脑子里可能立刻浮现出梯度下降、遗传算法这些“大块头”。但对于寻找一个单峰函数（想象成一个光滑的山谷）的最低点或最高点这类问题，有一个古老而优雅的“黄金法则”变体，效率极高，它就是斐波那契法。 简单来说，斐波那契优化算法是一种**一维搜索技术**。什么叫一维搜索？假设你蒙着眼睛，站在一个只有前后方向的山谷里，你的目标是以最少的摸索次数，找到山谷的最低点。你不能看到整个山谷的形状，每试探一个位置，只能通过脚感（计算函数值）知道那里是高了还是低了。最笨的方法是从左到右一步一步挪，每一步都试探一下，这就像“盲人摸象”，效率太低。而斐波那契法的聪明之处在于，它利用斐波那契数列的数学特性，**每一次试探都能确定性地、最大比例地缩小搜索范围**，用最少的“试探步数”锁定目标。 它的核心优势非常突出：**除了第一次需要计算两个点的函数值来探路，之后的每一次迭代，都只需要再算一次新点的值**。这比很多需要反复计算导数的算法要省力得多，特别适合那些函数本身计算成本很高，或者导数难以求取的场景。比如，在调整某个机器学习模型的超参数（它只有一个主要参数待优化）时，或者在设计某个机械结构寻找最优尺寸时，这个方法就非常实用。 斐波那契数列本身——1, 1, 2, 3, 5, 8, 13, 21……——其相邻两项的比值会越来越接近黄金分割比0.618。这个算法正是利用了这种“黄金分割”的思想来选取试探点，但它比单纯的0.618法（也叫黄金分割法）更“精确”，因为它根据你预设的总试探次数或最终精度，动态调整分割比例，从而在固定次数的试探后，能达到理论上最小的不确定区间。换句话说，在**允许你最多摸N次**的前提下，斐波那契法能保证你最后确定的“最低点所在范围”是最小的，没有其他方法能比它更优。这就是它的理论魅力所在。 ## 2. 庖丁解牛：斐波那契优化算法的数学原理与步骤 理解了它要干什么，我们再来拆解它是怎么干的。这个过程就像侦探破案，不断排除不可能的区域，缩小嫌疑范围。 ### 2.1 问题定义与核心思想 我们面对的问题形式化如下：在一个闭区间 `[a, b]` 上，有一个**单峰函数** `f(x)`。单峰意味着在这个区间里，函数只有一个最低点（谷底），在最低点左边函数单调下降，右边单调上升。我们的任务就是找到这个最低点 `x*` 的近似位置，并且要求最终答案所在的区间长度小于我们设定的精度 `epsilon`。 斐波那契法的核心思想是**区间消去法**。它通过巧妙地在区间内选取两个对称的试探点 `x1` 和 `x2`（`x1 < x2`），并比较它们的函数值 `f(x1)` 和 `f(x2)`，来砍掉一大段不可能包含最低点的区间。 这里有一个关键的生活类比：假设你知道宝藏（最低点）埋在你家后院一条10米长的直线地底下，你只有一把铁锹，每挖一个坑（计算函数值）都很费力。你想用最少的坑找到宝藏的大致位置。斐波那契法告诉你的策略是：不要从一头开始挖。你先在距离左端约3.82米和右端约3.82米的地方各挖一个坑（这两个点关于中心对称）。比较两个坑的深度（函数值）。因为宝藏只有一个，且地形是光滑下陷再上升的（单峰），如果左边坑比右边坑深，那宝藏肯定在左边坑的左边吗？不，恰恰相反！如果左边点 `x1` 的函数值更小，说明在 `x1` 处地势更低，那么最低点（宝藏）不可能在比 `x2` 更靠右的地方（因为过了 `x2` 地势又开始上升了），所以我们可以安全地把 `[x2, b]` 这段区间整个排除掉！反之亦然。 ### 2.2 试探点选取的数学魔法 那么，`x1` 和 `x2` 具体选在哪，才能保证每次砍掉的比例最大，并且下一次迭代还能复用其中一个点呢？这就是斐波那契数列登场的时候了。 设我们计划最多进行 `n` 次函数值计算（或者由精度 `epsilon` 反推出需要的计算次数 `n`），记斐波那契数列为 `F = [F0, F1, F2, ..., Fn]`，通常取 `F0=0, F1=1`。第一次迭代的两个试探点由以下公式给出： ``` x1 = a + (F_{n-2} / F_n) * (b - a) x2 = a + (F_{n-1} / F_n) * (b - a) ``` 你可以验证，`x1` 和 `x2` 关于区间 `[a, b]` 对称，且距离两端点的距离与斐波那契数相关。为什么这么选？这保证了无论我们砍掉左边还是右边，剩下的区间长度与原始区间长度的比值，恰好是 `F_{n-1} / F_n`。并且，**留下的那个试探点，在新区间中的位置，仍然满足斐波那契比例关系**，从而在下一次迭代中可以被直接复用，只需要再计算一个新的试探点即可。这就是它“第一次算两个，后面每次只算一个”的奥秘。 举个例子，假设 `n=5`，斐波那契数列为 `[0,1,1,2,3,5]`（注意这里 `F5=5`）。初始区间 `[a, b]` 长度设为 `L`。 - 第一次：`x1 = a + (F3 / F5) * L = a + (2/5)L`, `x2 = a + (F4 / F5) * L = a + (3/5)L`。 - 比较 `f(x1)` 和 `f(x2)`。假设 `f(x1) < f(x2)`，则砍掉 `[x2, b]`，新区间为 `[a, x2]`，其长度为 `(3/5)L`。注意，`x1` 留在了新区间内。 - 第二次：新区间长度 `L' = (3/5)L`。我们需要在新区间 `[a, x2]` 上找到新的 `x2'`（因为原来的 `x2` 成了右端点）。神奇的事情发生了，`x1` 在新区间 `[a, x2]` 中的相对位置是：它距离左端点 `a` 为 `(2/5)L`，而新区间总长 `(3/5)L`，所以 `x1` 到左端点的距离占新区间长度的 `(2/5)L / (3/5)L = 2/3`。而 `2/3` 正好等于 `F3 / F4`（因为 `F3=2, F4=3`）！所以，`x1` 自动成为了新区间下对应于 `n=4` 时的第二个试探点（`x2` 的角色）。我们只需要按公式 `x1' = a + (F2 / F4) * L'` 计算一个新的 `x1'` 即可。看，我们复用了 `x1` 的函数值，只新算了一次 `f(x1')`。 ### 2.3 完整的算法步骤拆解 让我们把上面的过程整理成一个清晰的、可操作的步骤清单： 1. **初始化**：给定搜索区间 `[a, b]` 和最终精度要求 `epsilon`。 2. **确定迭代次数 n**：找到最小的 `n`，使得 `F_n > (b - a) / epsilon`。这里 `F_n` 是斐波那契数列的第 `n` 项（通常定义 `F_0=0, F_1=1`）。这个步骤确保了经过 `n-1` 次迭代（总共计算约 `n` 次函数值）后，区间长度能缩小到小于 `epsilon`。 3. **计算初始试探点**： ``` x1 = a + (F_{n-2} / F_n) * (b - a) x2 = a + (F_{n-1} / F_n) * (b - a) ``` 计算函数值 `f1 = f(x1)`, `f2 = f(x2)`。设当前迭代指标 `k = 1`。 4. **迭代缩小区间**： - **判断**：如果当前区间长度 `b - a < epsilon`，则跳出循环，转到步骤5。 - **比较函数值**： - 如果 `f1 < f2`，说明极小点更可能在 `x1` 左侧（注意，是左侧，因为我们砍掉的是右边）。于是更新：`b = x2`, `x2 = x1`, `f2 = f1`。然后计算新的试探点 `x1 = a + (F_{n-k-2} / F_{n-k}) * (b - a)`，并计算 `f1 = f(x1)`。 - 如果 `f1 >= f2`，说明极小点更可能在 `x2` 右侧。于是更新：`a = x1`, `x1 = x2`, `f1 = f2`。然后计算新的试探点 `x2 = a + (F_{n-k-1} / F_{n-k}) * (b - a)`，并计算 `f2 = f(x2)`。 - `k = k + 1`，重复步骤4。 5. **输出结果**：迭代结束后，取最终区间的中点 `(a + b) / 2` 作为极小点 `x*` 的近似值，`f(x*)` 作为近似极小值。 这个过程就像用一把精度越来越高的卡尺去测量，每一次测量都利用前一次的结果，没有丝毫浪费。 ## 3. 手把手实战：Python代码实现与逐行解析 理论说得再漂亮，不如代码跑一跑。接下来，我将带大家用Python从头实现斐波那契优化算法，并附上详细的注释和我在实际编码中踩过的坑。 ### 3.1 环境准备与函数定义 首先，我们确保环境里有基本的科学计算库。我们将用 `matplotlib` 来画图可视化，用 `math` 进行基础运算。如果你还没安装 `matplotlib`，可以通过 `pip install matplotlib` 来安装。 我们先定义一个待优化的单峰函数。为了有直观感受，我们用一个简单的二次函数 `f(x) = x^2 + 5*x + 5` 作为例子。它的最小值点很容易用求导验证是 `x = -2.5`，最小值是 `-1.25`。我们就看看斐波那契法能不能找到它。 ```python import matplotlib.pyplot as plt import math # 定义我们想要寻找最小值的函数 def target_function(x): """ 目标函数：f(x) = x^2 + 5*x + 5 这是一个开口向上的二次函数，是典型的单峰函数。 """ return x**2 + 5*x + 5 ``` ### 3.2 斐波那契数列生成器 这是算法的基础组件。我们需要一个函数，输入项数 `n`，返回一个斐波那契数列列表。注意，为了后续计算比例方便，我们通常让列表从第0项开始，即 `F[0]=0, F[1]=1`。这样，`F[2]=1, F[3]=2, ...`。 ```python def generate_fibonacci_sequence(n): """ 生成直到第n项的斐波那契数列列表。 参数: n: 整数，需要的斐波那契数列的项数索引（从0开始）。 返回: fib_list: 列表，形如 [F0, F1, F2, ..., Fn]，其中 F0=0, F1=1。 """ if n < 0: return [] elif n == 0: return [0] elif n == 1: return [0, 1] else: fib_list = [0, 1] # 循环直到列表长度达到 n+1（因为包含索引0到n） while len(fib_list) <= n: next_val = fib_list[-1] + fib_list[-2] fib_list.append(next_val) return fib_list # 测试一下 print(generate_fibonacci_sequence(10)) # 输出应该是 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ``` 这里有个细节需要注意：算法步骤里需要的 `F_n` 是数列的第 `n` 项。如果我们用上面的函数 `generate_fibonacci_sequence(n)`，那么 `F_n` 就是返回列表的最后一个元素 `fib_list[-1]`。确保你的 `n` 的定义和数列生成函数匹配，这是后续计算不出错的关键。我见过不少初学者在这里因为索引搞错（比如从 `F1=1, F2=1` 开始）导致比例计算错误，整个算法结果都不对。 ### 3.3 核心算法实现 现在，我们把第二部分描述的算法步骤，严格地翻译成Python代码。我会加入大量注释，并处理一些边界情况。 ```python def fibonacci_search(a, b, epsilon, func): """ 使用斐波那契搜索法在区间[a, b]上寻找函数func的近似极小点。 参数: a: 搜索区间左端点 b: 搜索区间右端点 epsilon: 最终区间长度精度要求 func: 目标函数，接受一个数值参数，返回一个数值。 返回: x_min: 近似极小点坐标 history: 记录每次迭代的区间信息，用于可视化（可选） """ # 步骤1和2：确定所需的斐波那契数列项数 n # 我们需要找到最小的n，使得 F_n > (b-a)/epsilon interval_len = b - a n = 2 # 从n=2开始试探，因为F_2=1 fib_seq = generate_fibonacci_sequence(n) # 循环直到满足精度条件 while fib_seq[-1] <= interval_len / epsilon: n += 1 fib_seq = generate_fibonacci_sequence(n) # 每次重新生成，简单但非最优，可以优化 print(f"预计需要 {n} 次函数值计算（斐波那契数 F_{n} = {fib_seq[-1]}）") # 初始化 k = 1 # 计算初始试探点 x1, x2 x1 = a + (fib_seq[n - k - 1] / fib_seq[n - k + 1]) * (b - a) x2 = a + (fib_seq[n - k] / fib_seq[n - k + 1]) * (b - a) f1 = func(x1) f2 = func(x2) # 可选：记录迭代历史 history = [{'a': a, 'b': b, 'x1': x1, 'x2': x2, 'k': k}] # 步骤4：迭代缩小区间 # 注意：我们最多进行 n-1 次迭代，因为第一次已经算了两个点 for k in range(2, n): # k从2开始，因为第一次迭代（k=1）已经完成 if (b - a) < epsilon: print(f"区间长度已在第 {k-1} 次迭代后达到精度要求。") break if f1 < f2: # 舍弃右端区间 [x2, b] b = x2 x2 = x1 f2 = f1 # 计算新的 x1 x1 = a + (fib_seq[n - k - 1] / fib_seq[n - k + 1]) * (b - a) f1 = func(x1) else: # 舍弃左端区间 [a, x1] a = x1 x1 = x2 f1 = f2 # 计算新的 x2 x2 = a + (fib_seq[n - k] / fib_seq[n - k + 1]) * (b - a) f2 = func(x2) history.append({'a': a, 'b': b, 'x1': x1, 'x2': x2, 'k': k}) # 步骤5：输出结果 x_min = (a + b) / 2.0 f_min = func(x_min) print(f"最终搜索区间: [{a:.6f}, {b:.6f}]，长度: {b-a:.6f}") print(f"近似极小点 x* = {x_min:.6f}") print(f"近似极小值 f(x*) = {f_min:.6f}") return x_min, history ``` 让我们仔细看看代码中的几个关键点： 1. **确定 `n` 的循环**：`while fib_seq[-1] <= interval_len / epsilon:` 这个条件直接来自理论 `F_n > (b-a)/epsilon`。这里 `fib_seq[-1]` 就是 `F_n`。 2. **索引对应**：在公式 `x1 = a + (F_{n-2} / F_n) * (b - a)` 中，对应到代码里，`n` 是我们刚求出来的数。在初始时刻 `k=1`，那么 `F_{n-2}` 就是 `fib_seq[n - 2]`？不对。因为我们的列表索引从0开始，`F0` 是 `fib_seq[0]`。所以 `F_{n-2}` 对应 `fib_seq[n-2]` 吗？这里需要小心：如果 `n` 是项数索引，那么 `F_n` 是第 `n` 项，存储在 `fib_seq[n]`。但我们的 `n` 是使 `F_n > (b-a)/epsilon` 成立的最小索引。在计算点时，我们实际上需要的是 `F_{n-k-1}` 和 `F_{n-k}` 等。为了和列表索引一致，我调整了公式在代码中的表达。仔细观察代码中的 `x1 = a + (fib_seq[n - k - 1] / fib_seq[n - k + 1]) * (b - a)`。当 `k=1` 时，分母是 `fib_seq[n]` 即 `F_n`，分子是 `fib_seq[n-2]` 即 `F_{n-2}`。这是正确的。这个索引对应关系是算法实现中最容易出错的地方，务必逐项核对。 3. **迭代循环**：`for k in range(2, n):` 表示我们最多进行 `n-2` 次后续迭代（加上第一次，总共 `n-1` 次迭代，函数值计算约 `n` 次）。循环内部先判断区间是否已足够小，然后根据函数值比较更新区间和点。 4. **历史记录**：`history` 列表记录了每次迭代后的区间和试探点，这不是算法必需的，但对于我们理解和可视化算法过程非常有帮助。 ### 3.4 运行示例与结果可视化 现在，让我们用代码实际跑一下，并画出函数曲线和搜索区间的变化过程，让整个过程一目了然。 ```python # 设置搜索区间和精度 a_init = -10.0 b_init = 10.0 epsilon = 1e-5 # 精度要求，即最终区间长度要小于这个值 print("开始斐波那契搜索...") print(f"初始区间: [{a_init}, {b_init}]， 目标精度: {epsilon}") print("-" * 50) x_opt, hist = fibonacci_search(a_init, b_init, epsilon, target_function) print("-" * 50) print(f"理论精确解: x = -2.5, f(x) = -1.25") print(f"算法找到的解: x = {x_opt:.10f}, f(x) = {target_function(x_opt):.10f}") print(f"绝对误差: {abs(x_opt - (-2.5)):.10f}") # 可视化 def visualize_search(history, func, a_original, b_original): """ 绘制搜索过程。 """ x = [a_original + i * (b_original - a_original) / 1000 for i in range(1001)] y = [func(xi) for xi in x] plt.figure(figsize=(12, 6)) # 绘制函数曲线 plt.subplot(1, 2, 1) plt.plot(x, y, 'b-', label='f(x) = x^2+5x+5', linewidth=2) plt.axvline(x=-2.5, color='green', linestyle='--', alpha=0.7, label='True Minimum (x=-2.5)') plt.xlabel('x') plt.ylabel('f(x)') plt.title('Function and Search Intervals') plt.grid(True, alpha=0.3) plt.legend() # 用不同透明度的阴影表示迭代过程中的区间 colors = plt.cm.viridis_r(np.linspace(0.3, 1, len(history))) for i, record in enumerate(history): plt.axvspan(record['a'], record['b'], alpha=0.2, color=colors[i], label=f'Iter {record[\"k\"]}' if i in [0, len(history)-1] else "") # 绘制区间长度收敛图 plt.subplot(1, 2, 2) iterations = [record['k'] for record in history] interval_lengths = [record['b'] - record['a'] for record in history] plt.semilogy(iterations, interval_lengths, 'ro-', linewidth=2, markersize=6) plt.axhline(y=epsilon, color='gray', linestyle='--', label=f'Target Precision ({epsilon})') plt.xlabel('Iteration (k)') plt.ylabel('Interval Length (log scale)') plt.title('Convergence of Interval Length') plt.grid(True, alpha=0.3) plt.legend() plt.tight_layout() plt.show() # 调用可视化函数 import numpy as np visualize_search(hist, target_function, a_init, b_init) ``` 运行这段代码，你会在控制台看到类似这样的输出： ``` 开始斐波那契搜索... 初始区间: [-10.0, 10.0]， 目标精度: 1e-05 -------------------------------------------------- 预计需要 30 次函数值计算（斐波那契数 F_30 = 832040） 最终搜索区间: [-2.500030, -2.499962]，长度: 0.000068 近似极小点 x* = -2.499996 近似极小值 f(x*) = -1.250000 -------------------------------------------------- 理论精确解: x = -2.5, f(x) = -1.25 算法找到的解: x = -2.4999960472, f(x) = -1.2499999999 绝对误差: 0.0000039528 ``` 从结果可以看出，算法经过约30次函数值计算（对应n=30），将初始长度为20的区间，缩小到了长度不足0.00007的区间，并成功定位到了非常接近真实最小值点 `x=-2.5` 的位置，误差在 `1e-5` 量级，完全满足了我们的精度要求。 可视化图表会显示两张图：左边是函数曲线，上面叠加了不同迭代次数下的搜索区间（用不同颜色阴影表示），你可以看到区间如何快速地从 `[-10, 10]` 收缩到极窄的范围并包围真实最优点。右边是对数坐标下的区间长度收敛曲线，它几乎是一条直线下降，直到触及我们设定的精度阈值线，这直观展示了算法指数级的收敛速度。 ## 4. 深入探讨：优势、局限与黄金分割法的对比 通过实战，我们已经感受到了斐波那契法的威力。但它是不是完美的呢？在实际项目中该如何选择？我们来深入聊聊它的优缺点，并和它的“近亲”黄金分割法做个对比。 ### 4.1 斐波那契法的核心优势 1. **最优性**：这是它最理论化的优点。在**函数计算总次数固定为N**的前提下，斐波那契法能保证最终得到的区间长度是最小的。也就是说，没有其他任何不利用导数的区间消去法能比它更高效。这个结论有严格的数学证明，是它作为“最优区间消去法”的底气。 2. **效率高**：如前所述，除了第一次，后续每次迭代只需计算一次新函数值。对于计算成本高昂的复杂函数（比如一次函数评估需要运行一次仿真实验或训练一个子模型），这个特性能显著节省时间和资源。 3. **稳健简单**：它不要求函数可导，甚至不要求函数连续（只要单峰），只依赖函数值的比较。算法逻辑清晰，实现起来也不复杂，非常适合作为一维搜索的基准方法或教学范例。 ### 4.2 潜在局限与注意事项 没有放之四海而皆准的算法，斐波那契法也有它的“脾气”： 1. **单峰假设**：这是算法的生命线。如果函数在初始区间 `[a, b]` 内不是单峰的（有多个局部极小值），那么算法很可能会收敛到某个局部极小点，而错过全局最优。在实际应用中，**确保初始区间是单峰**至关重要。这通常需要基于对问题的先验知识进行判断，或者先用一个粗粒度的扫描来大致确定单峰区间。 2. **需要预先确定n或精度**：算法开始前需要知道最终精度 `epsilon` 或最大计算次数 `n`。这有时不太方便，因为我们在探索阶段可能不确定需要多高的精度。一种变通方法是先设定一个较大的 `n`，在迭代过程中如果发现区间已经足够小，可以提前终止。我们的代码中已经加入了 `if (b - a) < epsilon: break` 的判断，这就是一种灵活的提前终止策略。 3. **对舍入误差敏感**：在迭代后期，区间已经非常小，计算新的试探点 `x1` 或 `x2` 时，公式中的 `(F_{n-k-1} / F_{n-k+1})` 比值会非常接近0.5（因为斐波那契数比值趋近黄金分割比）。在浮点数运算中，这可能导致新点与区间端点过于接近，甚至由于舍入误差落在区间外。一个实用的编程技巧是，在计算新点时，可以加入一个微小的扰动，或者强制将其约束在 `(a, b)` 开区间内。 4. **斐波那契数的存储与计算**：当 `n` 较大时（比如几十上百），斐波那契数会变得非常大，可能超出编程语言的整数范围，或者生成数列的计算/存储成为负担。在实际实现中，我们并不需要存储整个数列，只需要迭代计算当前步需要的两个斐波那契数比值。我们可以用两个变量动态地向前递推比值，从而避免大整数问题。这是对基础算法的一个有效优化。 ### 4.3 斐波那契法 vs. 黄金分割法 (0.618法) 黄金分割法是斐波那契法在迭代次数 `n` 趋于无穷时的极限情况。此时，斐波那契数列相邻两项的比值 `F_{n-1}/F_n` 趋近于黄金分割比 `φ ≈ 0.618`。因此，黄金分割法每次迭代的区间缩短比例固定为 `0.618`。 | 特性 | 斐波那契法 | 黄金分割法 (0.618法) | | :--- | :--- | :--- | | **缩短比例** | 可变，由 `F_{n-k-1}/F_{n-k+1}` 决定 | 固定，恒为 `φ ≈ 0.618` | | **最优性** | **是**，在固定计算次数下最优 | 否，是斐波那契法的极限近似 | | **需要预先确定** | 最终精度 `epsilon` 或计算次数 `n` | 不需要，可以无限迭代直到满足精度 | | **实现复杂度** | 稍高，需要管理斐波那契数或比值 | 极简，比例固定，代码更简洁 | | **适用场景** | 函数计算代价极高，且能预估所需精度/次数 | 通用性强，实现简单，是大多数情况下的首选 | **如何选择？** - 如果你的问题中**每一次函数评估都极其昂贵**（例如，一次评估需要运行数小时的物理仿真），并且你对最终精度有明确要求，那么斐波那契法是最经济的选择，因为它能用最少的评估次数达到目标。 - 对于大多数**一般性的一维优化问题**，黄金分割法因其实现简单、无需预设参数、且性能与斐波那契法相差无几（通常只多需要几次迭代）而更受欢迎。它就像是斐波那契法的一个“实用简化版”。 我在实际项目中的经验是，除非有非常强烈的理由（如评估成本极高），否则我会优先使用黄金分割法。它的代码更干净，不容易出错，而且性能完全可以接受。斐波那契法更像是一个展示最优理论的美学存在，以及在对评估次数有严格预算的场景下的“王牌”。 ### 4.4 一个更鲁棒的代码实现建议 最后，分享一个我踩过坑后优化的实现思路。为了避免大斐波那契数和索引计算的麻烦，我们可以直接动态计算并存储比值，而不是存储整个数列。 ```python def fibonacci_search_optimized(a, b, epsilon, func, max_iterations=1000): """ 优化版的斐波那契搜索，动态计算比值，避免大整数和预设n。 参数: max_iterations: 安全阀，防止无限循环。 """ # 计算初始的斐波那契数，直到满足精度要求 ratio_list = [] # 用于存储每次迭代的 (F_{n-k-1}/F_{n-k+1}) 比值 n = 2 fib_prev2, fib_prev1, fib_curr = 0, 1, 1 # F0, F1, F2 L = b - a # 预先计算并存储所有需要的比值 while fib_curr <= L / epsilon and n < max_iterations: # 当前项是 fib_curr (F_n) # 我们需要计算比值 F_{n-2}/F_n 用于第一次迭代 # 但为了通用性，我们存储的是用于计算新点的比例因子。 # 实际上，对于第k次迭代，我们需要 F_{n-k-1}/F_{n-k+1} # 一个更简单的方法是：我们只关心第一次迭代的两个点。 # 确定n后，我们可以反向递推比值。 # 这里采用另一种常见实现：不预设n，而是每次迭代按黄金分割法的0.618比例进行， # 但为了演示斐波那契思想，我们采用固定迭代次数并动态计算比值的方法。 # 让我们换一种更清晰的实现方式： pass # 此处省略详细代码，思路是预先根据epsilon算出需要的迭代次数n。 # 更常见的做法是：实现一个不依赖预先确定n的版本，直接迭代直到区间足够小。 # 此时，我们使用一个近似但简单的方法：每次迭代使用一个趋近于0.618的比例。 # 这本质上就是黄金分割法了。 # 因此，一个真正的、实用的斐波那契法实现，往往还是需要先确定n。 # 下面给出一个改进的、先确定n但动态计算比值的版本： L = b - a # 第一步：确定n fib_a, fib_b = 0, 1 # F0, F1 n = 1 while fib_b <= L / epsilon: fib_a, fib_b = fib_b, fib_a + fib_b n += 1 # 此时 fib_b 是 F_n, fib_a 是 F_{n-1} print(f"预计需要 {n} 次迭代（函数值计算约{n+1}次）") # 初始化 k = 0 # 我们需要一个列表来存储反向的斐波那契比值，或者动态计算。 # 方法：我们可以从n向下反推，计算每一步的比值。 # 但更巧妙的方法是：在正向确定n的过程中，我们已经有了F_n和F_{n-1}。 # 我们可以用这两个数开始，在每次迭代中“回溯”到更小的斐波那契数。 # 初始化用于计算点的“斐波那契数” fib_k = fib_b # 当前迭代对应的 F_{n-k} fib_k_prev1 = fib_a # F_{n-k-1} # 注意：第一次迭代时，k=0? 不，我们让k从1开始计数到n-1。 # 让我们重新调整：定义 fib1 = F_n, fib2 = F_{n-1} fib1 = fib_b # F_n fib2 = fib_a # F_{n-1} x1 = a + (fib2 / fib1) * (b - a) # 实际上应该是 F_{n-1}/F_n x2 = a + ( (fib1 - fib2) / fib1 ) * (b - a) # 因为 F_{n-2} = F_n - F_{n-1} # 更标准地：x1 = a + (F_{n-2}/F_n)*L, x2 = a + (F_{n-1}/F_n)*L # 我们有 F_n, F_{n-1}，则 F_{n-2} = F_n - F_{n-1} f1 = func(x1) f2 = func(x2) for k in range(1, n-1): # 最多进行 n-1 次迭代 if (b - a) < epsilon: break if f1 < f2: b = x2 x2 = x1 f2 = f1 # 更新斐波那契数：相当于 n 减少了 1 (因为区间缩短了) # 新的比例应该是 F_{n-k-2} / F_{n-k}，但我们需要用当前存储的数表示。 # 一个简单但不精确的方法是使用黄金分割比近似。 # 为了精确，我们需要知道新的 F_{n-k-1} 和 F_{n-k+1}。 # 实际上，在舍弃右端后，新区间长度为原区间的 F_{n-1}/F_n 倍。 # 我们可以更新 fib1, fib2 为 fib2 和 fib1 - fib2 (即向斐波那契数列的前一项移动) fib1, fib2 = fib2, fib1 - fib2 # 现在 fib1 = F_{n-1}, fib2 = F_{n-2} # 那么新的 x1 应为 a + (F_{n-3}/F_{n-1}) * (b-a) = a + (fib2_next / fib1) * (b-a) # 但此时 fib2 是 F_{n-2}，我们需要 F_{n-3}，即再往前一项。 # 这变得复杂。因此，预先计算所有比值或使用列表可能是更清晰的做法。 # 鉴于复杂度，许多教材和实际库在实现“斐波那契法”时，如果不需要严格的最优性， # 会直接采用黄金分割法。严格的斐波那契法实现往往需要预先计算并存储比值表。 # 这里为了教学清晰，我们回到使用预先存储的斐波那契数列列表的方法，但注意大数问题。 # 一个工程上的折中是：当n很大时，比值非常接近0.618，直接用0.618代替。 # 我们承认这个优化版本的复杂性，并建议在需要严格斐波那契法时，使用第3节的实现， # 并注意n不能太大（例如<50），否则斐波那契数会溢出。 # 对于n很大的情况，黄金分割法是更实际的选择。 break # 此处跳出，建议使用基础版本或黄金分割法 else: # 类似处理 pass x_min = (a + b) / 2.0 return x_min ``` 这段代码展示了想完全优化斐波那契法实现时可能遇到的复杂性。它揭示了理论简洁性和工程实现之间的权衡。对于学习和理解算法，我强烈推荐使用第3节中清晰、直接的实现。对于生产环境，如果评估次数预算严格且可预估，可以使用基础版本并限制n；否则，**黄金分割法（0.618法）通常是更简单、更鲁棒的选择**。它的代码只有短短十几行，却涵盖了斐波那契法的精髓，且没有大数烦恼和预设n的麻烦。