不动点迭代

形式陈述 ​

给定集合 $D$、映射 $g:D\to D$ 和初值 $x_0\in D$，不动点迭代依次计算

$$x_{k+1}=g(x_k),k=0,1,2,\dots ,$$

希望输出满足 $x_{\ast }=g(x_{\ast })$ 的点。若原问题写作 $f(x)=0$，选择 $g$ 就是算法设计的一部分；同一个方程可以有许多代数等价的重排，它们的迭代轨道却未必相同。一次迭代需要一次 $g$ 的求值并保存当前状态，因而执行 $k$ 步的成本通常是 $k$ 次函数求值、额外存储为常数规模；若 $g$ 内部还要求解子问题，则应把那部分成本另行计入。

全局保证直接来自Banach 不动点定理公理库Banach 不动点定理Banach fixed-point theorem · Contraction mapping theorem完备度量空间上的压缩映射具有唯一不动点，且迭代以几何速度收敛。。若 $(D,d)$ 完备、$g(D)\subseteq D$，并存在统一常数 $0\le q<1$ 使

$$d(g(x),g(y))\le qd(x,y)(x,y\in D),$$

则 $D$ 中有唯一不动点，任意 $x_0\in D$ 都收敛到它。除存在唯一性外，还得到先验界与后验界

$$d(x_k,x_{\ast })\le \frac{q^k}{1-q}d(x_1,x_0),d(x_k,x_{\ast })\le \frac{q}{1-q}d(x_k,x_{k-1}).$$

第二个不等式说明：只有已知收缩因子时，相邻两步的距离才能变成真误差证书。若目标误差为 $\tau$，可以在右端不超过 $\tau$ 时停止；实际实现还应检查定义域、非有限值、最大迭代数和舍入停滞，并按残差与误差估计公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。的尺度规则同时报告残差或更新量。

一维局部理论更弱，也更常用于分析具体公式。若 $g$ 在不动点 $x_{\ast }$ 附近连续可微且 $|g^{\prime }(x_{\ast })|<1$，则存在一个足够小的邻域，使从其中出发且不离开该邻域的迭代收敛。若 $g^{\prime }(x_{\ast })\ne 0$，误差 $e_k=x_k-x_{\ast }$ 满足

$$\underset{k\to \mathrm{\infty }}{lim}\frac{|e_{k+1}|}{|e_k|}=|g^{\prime }(x_{\ast })|,$$

所以它通常是线性收敛公理库迭代收敛阶Order of convergence · Q-convergence · R-convergence用相邻迭代误差的渐近幂律区分线性、超线性与二次收敛，并说明实验估阶的边界。；当 $g^{\prime }(x_{\ast })=0$ 时，速度可能更高，但仍要由更高阶展开确认。

直觉 ​

不动点迭代不是“把等号右边反复按计算器”这么简单。映射 $g$ 会在每一步重新塑造误差：若它把不动点附近的距离压短，轨道像被逐步拉向固定位置；若它把距离放大或把点送出定义域，形式上完全正确的重排也会成为失败算法。压缩常数 $q$ 描述最坏方向上的拉伸，$q$ 越接近 $1$，每一步看起来越安静，抵达目标却越慢。

这也解释了表示方式为何属于算法而不只是代数。方程 $f(x)=0$ 规定要找哪个对象，重排 $x=g(x)$ 则决定如何走向它。两个 $g$ 可以拥有同一个不动点，却分别产生快速收敛、缓慢收敛、周期振荡或定义域逃逸。

例子与边界 ​

方程 $x=\cos x$ 在 $[0,1]$ 上给出一个干净的全局例子。映射 $g(x)=\cos x$ 把该区间送回自身，且 $|g^{\prime }(x)|=|\sin x|\le \sin 1<1$。从 $x_0=1$ 出发，轨道

$$1,0.5403,0.8576,0.6543,\dots$$

在不动点两侧交替靠近，最终收敛到 $0.739085\dots$。振荡本身不表示发散；真正起作用的是误差幅度受到统一压缩。

同一方程 $x^2=2$ 展示了重排的决定性。取

$$g_1(x)=\frac{1}{2}(x+\frac{2}{x}),$$

从 $x_0=1$ 得到 $3/2,17/12,577/408,\dots$，并快速趋于 $\sqrt{2}$；在根处 $g_1^{\prime }(\sqrt{2})=0$，这正是速度高于线性的原因。若改成同样等价的 $g_2(x)=2/x$，则 $g_2(g_2(x))=x$，任意非根初值都会在两点间来回跳动，因为 $g_2^{\prime }(\sqrt{2})=-1$ 正落在局部收敛条件的边界上。

仅凭更新量很小也可能过早停机。对 $g(x)=qx+(1-q)x_{\ast }$，有 $|x_{k+1}-x_k|=(1-q)|x_k-x_{\ast }|$；当 $q$ 极接近 $1$ 时，步长可以很小，而真误差仍大。未知 $q$ 时，相邻差只能作为诊断信号，不能替代残差、问题尺度或后验误差界。

推论与应用 ​

Banach 定理负责回答“在什么统一条件下存在唯一不动点并从任意初值收敛”，本页则负责选择迭代映射、估算实际成本和设计停止条件。两者不应重复：定理页保留抽象证明与误差界，算法页展示不同重排为何改变数值行为。

Picard 迭代把常微分方程改写为函数空间中的积分不动点问题，主要用于证明局部存在唯一性；它并不等于把时间区间离散成步长的 ODE 时间步进算法。在线性方程、积分方程和带折扣动态规划中也会出现同样框架，但每个应用都必须重新说明所用空间、范数、自映射区域和收缩常数。

参考资料

• NIST Digital Library of Mathematical Functions, §3.8 Nonlinear Equations.
• J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, 2000, fixed-point iterations and local convergence.
• Richard L. Burden, J. Douglas Faires, and Annette M. Burden, Numerical Analysis, 10th ed., Cengage, 2016, fixed-point iteration and error bounds.