不动点迭代是数值分析中用于逼近映射的不动点的方法;不动点即满足 g(x∗)=x∗ 的点 x∗。从初始近似值 x0 出发,该方法生成序列
xn+1=g(xn),n=0,1,2,….
如果该序列收敛于 x∗,且 g 在该点连续,那么 x∗ 就是不动点。这种方法适用于实数、向量、函数以及更一般的数学对象。它形式简单,是一种基本的计算方法,但能否奏效在很大程度上取决于所选的映射和初始点。
表述与解释
求根问题
通常可以改写为
例如,对任意非零常数 λ,原方程都等价于
x=x−λf(x).
由此得到迭代格式
xn+1=xn−λf(xn).
等价的方程不一定能产生同样有效的算法。一种变形可能收敛很快,另一种可能收敛缓慢,还有一种可能根本不收敛。因此,计算中的问题不仅是找出一个不动点方程,还要选择一个映射,使反复应用该映射的结果趋近于所需的解。
用函数复合表示,
xn=g∘n(x0),
其中 g∘n 表示连续应用 g 共 n 次。同样的构造也定义了一个离散动力系统,其中的不动点可能吸引或排斥附近的轨道。
对于实值映射,可以借助曲线 y=g(x) 和 y=x 进行图形解释。两条曲线的交点就是不动点。在两条曲线之间反复沿竖直方向和水平方向移动,会形成一幅蛛网图,直观展示收敛、振荡或发散的情形。
压缩条件下的收敛性
最主要的一般性收敛结论是巴拿赫不动点定理。设 (X,d) 是非空的完备度量空间,并假设 g:X→X 是压缩映射:存在常数 q,满足 0≤q<1,使得对所有 x,y∈X,都有
d(g(x),g(y))≤qd(x,y)
则:
完备性保证迭代生成的柯西序列在该空间内有极限。条件 g(X)⊆X 则保证每一步都停留在压缩估计适用的区域内。
两个有用的误差界为
d(xn,x∗)≤1−qqnd(x1,x0)
以及对 n≥1,
d(xn,x∗)≤1−qqd(xn,xn−1).
前者是基于初始一步的先验误差界;后者是基于已算出的迭代值的后验误差界。
压缩条件是充分条件,而不是必要条件。有些并非压缩映射的映射,其迭代也会收敛。反过来,仅有不动点的存在性,甚至唯一性,也不能保证迭代收敛于该点。
实值迭代
对于闭区间 [a,b] 上的连续可微映射 g,一个便于使用的充分条件是
g([a,b])⊆[a,b],x∈[a,b]max∣g′(x)∣≤q<1.
由中值定理,上述导数界使 g 成为该区间上的压缩映射。自映射条件则防止迭代值离开这个区间。
局部吸引与排斥
设 x∗ 是不动点,且 g 在其附近连续可微。由泰勒级数展开可得
xn+1−x∗=g′(x∗)(xn−x∗)+o(∣xn−x∗∣).
因此:
- 若 ∣g′(x∗)∣<1,则该不动点具有局部吸引性:从足够接近它的初始点出发,迭代会收敛于它。
- 若 ∣g′(x∗)∣>1,则该不动点具有局部排斥性。
- 若 ∣g′(x∗)∣=1,则导数判别法无法给出结论。
当 0<g′(x∗)<1 时,附近的误差通常保持同号。当 −1<g′(x∗)<0 时,误差通常正负交替。
在临界情形下,不同映射的表现可能大不相同。在零点附近,g(x)=x−x3 会吸引绝对值足够小的初始值,而 g(x)=x+x3 会排斥附近的非零初始值。两者都满足 g′(0)=1。
示例:求解 x=cosx
考虑
xn+1=cosxn.
在 [0,1] 上,余弦函数将该区间映射到自身,且满足
∣g′(x)∣=∣sinx∣≤sin1<1.
因此,从该区间内的任意初始值出发,迭代都会收敛到区间内唯一的不动点,
x∗≈0.7390851332.
相比之下,通过
xn+1=xn2
求解 x2=2 通常无法收敛。对任意非零的 x0,都有
因此,除非初始值本身就是不动点,否则序列会形成二周期循环。另一种迭代
xn+1=21(xn+xn2)
则从任意正初始值出发都收敛于 2。
收敛速度
设 en=xn−x∗。在通常的误差非零假设下,如果收敛的迭代满足
n→∞lim∣en∣p∣en+1∣=C,0<C<∞.
则称其收敛阶为 p。
对于光滑的标量映射:
- 若 0<∣g′(x∗)∣<1,则为线性收敛,渐近收敛因子为 ∣g′(x∗)∣。
- 若 g′(x∗)=0 且 g′′(x∗)=0,则为二次收敛。
- 更一般地,若不动点处第一个非零导数为 p 阶导数,且 p≥2,则只要迭代没有在有限步内达到解,其局部收敛阶就为 p。
线性收敛因子接近 1 时,收敛速度很慢。因此,一种迭代即使满足严格的收敛定理,在计算上也可能仍然效率低下。
牛顿法是一个重要特例:
g(x)=x−f′(x)f(x).
对于充分光滑的函数,在其单根处有 g′(x∗)=0,这解释了牛顿法的局部二次收敛性。但这种局部优势并不意味着从任意初始值出发都能收敛。
向量迭代与线性迭代
对于映射 g:Rm→Rm,更新公式仍为
xn+1=g(xn).
压缩估计可以用范数表示为
∥g(x)−g(y)∥≤q∥x−y∥,q<1.
如果 g 在不动点附近连续可微,则其雅可比矩阵决定局部行为:
en+1=Dg(x∗)en+o(∥en∥).
局部收敛的一个充分条件是
ρ(Dg(x∗))<1,
其中谱半径 ρ 是矩阵各特征值绝对值的最大值。如果谱半径大于 1,则不动点不稳定;等于 1 时则需要进一步分析。
对于仿射迭代
xn+1=Bxn+c,
误差严格满足
en+1=Ben.
从任意初始向量出发都收敛于唯一不动点,当且仅当
这一框架涵盖了求解线性方程组的定常迭代法。给定 Ax=b,选取分裂
其中 M 可逆。于是
xn+1=M−1Nxn+M−1b.
不同的分裂方式会得到雅可比迭代、高斯–赛德尔迭代等方法。在实际实现中,应用 M−1 通常意味着求解一个更简单的线性方程组,而不是显式构造逆矩阵。
松弛与加速
松弛迭代将直接更新替换为
xn+1=(1−ω)xn+ωg(xn).
当 ω=0 时,它与 g 具有相同的不动点。取值 0<ω<1 称为欠松弛*;取值 ω>1 称为超松弛*。
在标量不动点处,松弛后映射的导数为
1−ω+ωg′(x∗).
选择适当的 ω 可以加快收敛,或使某些振荡迭代稳定下来,但也可能导致发散。欠松弛并非万能的补救措施:如果 g′(x∗)>1,那么任意正的 ω 都会使上述导数仍大于 1。
加速方法利用多个迭代值所包含的信息。对于标量序列,艾特肯 Δ² 加速法在分母非零时构造
xn=xn−xn+2−2xn+1+xn(xn+1−xn)2,
它可以消除线性收敛序列中占主导的几何型误差,但分母过小时,计算可能对舍入误差十分敏感。
对于向量问题,安德森加速法通过求解一个小规模最小二乘问题,将先前的迭代值和残差组合起来。其效果取决于映射、保存的历史信息以及实现中的保护措施。
应用
不动点迭代既可用于构造算法,也可用于证明解的存在性。
微分方程。 对于初值问题
y′(t)=F(t,y(t)),y(t0)=y0,
皮卡迭代应用积分算子
yn+1(t)=y0+∫t0tF(s,yn(s))ds.
在适当的连续性条件和利普希茨连续性条件下,在足够短的区间上,该算子是适当函数空间上的压缩映射。这是常微分方程解的局部存在唯一性理论的基础。
优化。 梯度下降就是不动点迭代
xn+1=xn−α∇F(xn).
它的不动点是 F 的驻点;这些驻点是否为极小值点,以及迭代是否收敛,都需要额外假设。
动态规划。 价值迭代反复应用贝尔曼算子。在奖励有界的标准折扣模型中,该算子在上确界范数下是压缩映射。
非线性模型与离散化方程。 耦合的均衡方程以及非线性微分方程离散化后得到的方程,通常可以通过反复计算映射值或求解较简单的子问题来求解。
皮卡迭代这一名称尤其常用于微分方程中的逐次逼近,而不动点迭代的使用范围更广。
停止准则与局限性
一种常见的停止准则是
∥xn+1−xn∥≤εabs+εrel∥xn+1∥.
它衡量的是迭代步长,而不是直接衡量误差。
定义不动点残差为
r(x)=g(x)−x.
在压缩常数为 q<1 的压缩估计下,
∥x−x∗∥≤1−q∥r(x)∥.
因此,已知适当的压缩常数时,就可以由残差得到有保证的误差界。如果 q 接近 1,即使残差很小,对应的误差也可能大得多。
对于改写后的方程 f(x)=0,原方程的残差同样重要。在迭代 g(x)=x−λf(x) 中,即使 f(x) 仍然很大,极小的 λ 也可能产生极小的步长。
其他局限性包括依赖初始近似值、收敛于非预期的不动点、出现周期循环、越出映射的定义域以及收敛缓慢。在浮点运算中,由于相邻迭代值被舍入为同一个数,计算出的迭代序列可能停滞。因此,有限精度下的终止本身并不能证明已经达到精确解。