函数迭代的应用

一句话

很多过程都是同一个映射一做再做：缩小地图、按递推式算下一项、把一个数换成它各位数字的平方和……把它写成 $x_{n+1}=f(x_n)$，问题就成了“$f$ 的轨道往哪里去”。三把钥匙：

• 不动点：轨道如果停下来，只能停在 $f(x)=x$ 的点上。
• 收缩：每做一次，到不动点的距离乘以一个小于 $1$ 的数，轨道就一定被吸过去。
• 有限：如果轨道只能落在有限个值里，迟早会重复，从此循环。

第 1 站 · 数列：轨道的极限

$a_1=0$，$a_{n+1}=\sqrt{2+a_n}$。这是 $f(x)=\sqrt{x+2}$ 从 $0$ 出发的轨道。

要说清楚“它趋向 $2$”，分两步：

1. 候选人：极限 $L$ 若存在，由 $L=\sqrt{L+2}$ 得 $L=2$（舍去负根）。
2. 真的会去：$2-a_{n+1}=2-\sqrt{2+a_n}=\frac{2-a_n}{2+\sqrt{2+a_n}}$，分母至少是 $2+\sqrt{2}>2$，所以到 $2$ 的距离每次至少缩小一半：$0\le 2-a_n\le \frac{2}{2^{n-1}}\to 0$。

第二步和地图的证明是同一个想法：收缩。

第 2 站 · 数论：有限必循环

把一个正整数换成它各位数字的平方和，记作 $S(n)$。例如 $S(32)=9+4=13$，$S(13)=10$，$S(10)=1$，$S(1)=1$——$32$ 的轨道停在了不动点 $1$ 上。可 $S(4)=16$，$S(16)=37$，……从 $4$ 出发永远到不了 $1$。

第 3 站 · 函数方程：在 $f(f(x))$ 里找不动点

例 $f:\mathbb{R}\to \mathbb{R}$ 满足 $f(f(x))=x^2-x+1$。求 $f(1)$。

注意 $x=1$ 是 $x^2-x+1$ 的不动点。迭代的想法：把 $f$ 再作用一次，$f(f(f(x)))$ 可以用两种方式计算——

令 $x=1$，记 $a=f(1)$：左边 $f(1)=a$，右边 $a^2-a+1$。于是 $a^2-2a+1=0$，$a=1$。

练一练