03 Higher-order Functions & Env Diagrams 1

update(x) = 1 + 1/x 能收敛到黄金比例，不是所有方程随便写成 \(x=f(x)\) 迭代就会收敛；不动点迭代有严格收敛条件。

1. 回顾：我们在做不动点迭代

我们的方程：

\(\phi^2=\phi+1 \implies \phi = 1+\frac1\phi\) 定义迭代函数

\(f(x)=1+\frac1x\) 迭代：\(x_{n+1}=f(x_n)\) 求不动点：\(x=f(x)\)

不动点：输入 x，经过 f 变换后输出仍然等于 x。

2. 不动点收敛定理（Banach 不动点 / 导数判据，一维简单版）

设 \(x^*\) 是不动点 \(x^*=f(x^*)\)。 如果在不动点附近满足：

\(\boldsymbol{|f'(x^*)| < 1}\) 那么从足够靠近 \(x^*\) 的初始值出发，迭代 \(x_{n+1}=f(x_n)\) 局部收敛； 如果 \(|f'(x^*)|>1\)，局部发散。

直观理解：导数绝对值小于 1，每次迭代误差会被 “压缩”；大于 1，误差被放大，越迭代越远。

套入黄金比例例子

\(f(x)=1+\frac1x\) 求导：

\(f'(x) = -\frac{1}{x^2}\) 不动点 \(x^*=\phi=\frac{1+\sqrt5}{2}\approx1.618\)

\(|f'(\phi)|=\left|-\frac{1}{\phi^2}\right|=\frac{1}{\phi^2}\) 我们知道 \(\phi^2=\phi+1\approx2.618\)

\(\frac{1}{\phi^2}\approx0.382<1\) ✅ 满足 \(|f'(\phi)|<1\) → 局部收敛。 这就是为什么 golden_update 能不断逼近 phi。 负号代表：迭代值会在 phi 上下震荡，慢慢靠近（你前面看到的序列：1 →2→1.5→1.6667→1.6→1.625… 来回跳，振幅越来越小）。

3. 换成别的方程，还成立吗？

不成立！随便改写方程得到的 \(x=f(x)\) 很容易发散。

举同一个二次方程 \(\boldsymbol{x^2-x-1=0}\)，我们换一种变形，构造另一个 update： 原方程：\(x^2 = x+1\) 变形方案 2：\(x=x^2-1\) 此时迭代函数 \(f(x)=x^2-1\)，不动点同样满足 \(x=x^2-1\)，解依然是\(\phi\)。

求导：\(f'(x)=2x\)，在不动点\(\phi\approx1.618\)处

\(f'(\phi)=2\times1.618\approx3.236\)

\(|f'(\phi)|>1\) 👉 迭代会发散！ 试一下，初始 guess=1： \(x_0=1\) \(x_1=1^2-1=0\) \(x_2=0^2-1=-1\) \(x_3=(-1)^2-1=0\) 陷入循环震荡，永远到不了 1.618。

同一个方程，不同代数变形得到不同迭代函数，有的收敛、有的不收敛。能不能收敛看不动点处导数绝对值。

4. 更多例子对比

1. \(f(x)=\cos x\)，不动点 \(x=\cos x\)。 \(f'(x)=-\sin x\)，不动点附近\(|f'(x)|<1\)，迭代收敛。
2. \(f(x)=2x+1\)，不动点 \(x=2x+1 \Rightarrow x=-1\)。 \(f'(x)=2, |f'|>1\)，迭代发散。

5. 两个重要局限

1. 局部收敛：只保证起点离根不远时收敛；如果初始 guess 离太远，依然可能发散。黄金比例这个迭代还好，正数起点基本都能收敛。
2. 条件 \(|f'(x^*)|<1\) 是充分条件不是必要条件；少数情况导数 = 1 也可能收敛，但非常特殊。

6. 回到代码的结构

improve(update, close, guess=1)

improve 本身是通用迭代模板，它不管 update 会不会收敛！ improve 只是机械循环：不断执行update直到close返回 True。

• 如果 update 收敛：正常拿到解；
• 如果 update 发散：死循环，永远不满足 close，程序卡住。

模板是中立工具；收敛性完全由你传入的 update 函数决定。

7. 补充：和牛顿法对比（拓展）

不动点迭代收敛速度一般比较慢；牛顿法是一种构造特殊 update 的不动点，保证更快收敛。

小结

1. golden_update 收敛根源：迭代函数 \(f(x)=1+1/x\) 在不动点\(\phi\)处导数绝对值\(<1\)，误差逐轮压缩。
2. 同一个代数方程，可以写成多种 \(x=f(x)\) 形式；只有满足导数判据的那个 update 才能收敛。
3. improve只是高阶函数循环框架，没有内置收敛保证，给它一个发散的 update 就会死循环。