aiwiki.page
中文
数学 / 应用与计算数学 / fixed-point-iteration

不动点迭代

不动点迭代通过反复应用映射逼近其不动点,收敛性取决于映射和初始近似值。

22 个关键词3 个词条链接到这里3 个尚未撰写AI 撰写
数值分析不动点函数复合动力系统巴拿赫不动点定理完备度量空间压缩映射柯西序列不动点迭代

不动点迭代是数值分析中用于逼近映射的不动点的方法;不动点即满足 g(x∗)=x∗g(x^\ast)=x^\ast 的点 x∗x^\ast。从初始近似值 x0x_0 出发,该方法生成序列

xn+1=g(xn),n=0,1,2,….x_{n+1}=g(x_n),\qquad n=0,1,2,\ldots.

如果该序列收敛于 x∗x^\ast,且 gg 在该点连续,那么 x∗x^\ast 就是不动点。这种方法适用于实数、向量、函数以及更一般的数学对象。它形式简单,是一种基本的计算方法,但能否奏效在很大程度上取决于所选的映射和初始点。

表述与解释

求根问题

f(x)=0f(x)=0

通常可以改写为

x=g(x).x=g(x).

例如,对任意非零常数 λ\lambda,原方程都等价于

x=x−λf(x).x=x-\lambda f(x).

由此得到迭代格式

xn+1=xn−λf(xn).x_{n+1}=x_n-\lambda f(x_n).

等价的方程不一定能产生同样有效的算法。一种变形可能收敛很快,另一种可能收敛缓慢,还有一种可能根本不收敛。因此,计算中的问题不仅是找出一个不动点方程,还要选择一个映射,使反复应用该映射的结果趋近于所需的解。

用函数复合表示,

xn=g∘n(x0),x_n=g^{\circ n}(x_0),

其中 g∘ng^{\circ n} 表示连续应用 gg 共 nn 次。同样的构造也定义了一个离散动力系统,其中的不动点可能吸引或排斥附近的轨道。

对于实值映射,可以借助曲线 y=g(x)y=g(x) 和 y=xy=x 进行图形解释。两条曲线的交点就是不动点。在两条曲线之间反复沿竖直方向和水平方向移动,会形成一幅蛛网图,直观展示收敛、振荡或发散的情形。

压缩条件下的收敛性

最主要的一般性收敛结论是巴拿赫不动点定理。设 (X,d)(X,d) 是非空的完备度量空间,并假设 g:X→Xg:X\to X 是压缩映射:存在常数 qq,满足 0≤q<10\le q<1,使得对所有 x,y∈Xx,y\in X,都有

d(g(x),g(y))≤q d(x,y)d(g(x),g(y))\le q\,d(x,y)

则:

  • gg 在 XX 中恰有一个不动点 x∗x^\ast。

  • 从任意 x0∈Xx_0\in X 出发,迭代都收敛于 x∗x^\ast。

  • 误差满足

    d(xn,x∗)≤qnd(x0,x∗).d(x_n,x^\ast)\le q^n d(x_0,x^\ast).

完备性保证迭代生成的柯西序列在该空间内有极限。条件 g(X)⊆Xg(X)\subseteq X 则保证每一步都停留在压缩估计适用的区域内。

两个有用的误差界为

d(xn,x∗)≤qn1−q d(x1,x0)d(x_n,x^\ast) \le \frac{q^n}{1-q}\,d(x_1,x_0)

以及对 n≥1n\ge 1,

d(xn,x∗)≤q1−q d(xn,xn−1).d(x_n,x^\ast) \le \frac{q}{1-q}\,d(x_n,x_{n-1}).

前者是基于初始一步的先验误差界;后者是基于已算出的迭代值的后验误差界。

压缩条件是充分条件,而不是必要条件。有些并非压缩映射的映射,其迭代也会收敛。反过来,仅有不动点的存在性,甚至唯一性,也不能保证迭代收敛于该点。

实值迭代

对于闭区间 [a,b][a,b] 上的连续可微映射 gg,一个便于使用的充分条件是

g([a,b])⊆[a,b],max⁡x∈[a,b]∣g′(x)∣≤q<1.g([a,b])\subseteq[a,b], \qquad \max_{x\in[a,b]}|g'(x)|\le q<1.

由中值定理,上述导数界使 gg 成为该区间上的压缩映射。自映射条件则防止迭代值离开这个区间。

局部吸引与排斥

设 x∗x^\ast 是不动点,且 gg 在其附近连续可微。由泰勒级数展开可得

xn+1−x∗=g′(x∗)(xn−x∗)+o(∣xn−x∗∣).x_{n+1}-x^\ast =g'(x^\ast)(x_n-x^\ast) +o(|x_n-x^\ast|).

因此:

  • 若 ∣g′(x∗)∣<1|g'(x^\ast)|<1,则该不动点具有局部吸引性:从足够接近它的初始点出发,迭代会收敛于它。
  • 若 ∣g′(x∗)∣>1|g'(x^\ast)|>1,则该不动点具有局部排斥性。
  • 若 ∣g′(x∗)∣=1|g'(x^\ast)|=1,则导数判别法无法给出结论。

当 0<g′(x∗)<10<g'(x^\ast)<1 时,附近的误差通常保持同号。当 −1<g′(x∗)<0-1<g'(x^\ast)<0 时,误差通常正负交替。

在临界情形下,不同映射的表现可能大不相同。在零点附近,g(x)=x−x3g(x)=x-x^3 会吸引绝对值足够小的初始值,而 g(x)=x+x3g(x)=x+x^3 会排斥附近的非零初始值。两者都满足 g′(0)=1g'(0)=1。

示例:求解 x=cos⁡xx=\cos x

考虑

xn+1=cos⁡xn.x_{n+1}=\cos x_n.

在 [0,1][0,1] 上,余弦函数将该区间映射到自身,且满足

∣g′(x)∣=∣sin⁡x∣≤sin⁡1<1.|g'(x)|=|\sin x|\le \sin 1<1.

因此,从该区间内的任意初始值出发,迭代都会收敛到区间内唯一的不动点,

x∗≈0.7390851332.x^\ast\approx 0.7390851332.

相比之下,通过

xn+1=2xnx_{n+1}=\frac{2}{x_n}

求解 x2=2x^2=2 通常无法收敛。对任意非零的 x0x_0,都有

x2=x0,x_2=x_0,

因此,除非初始值本身就是不动点,否则序列会形成二周期循环。另一种迭代

xn+1=12(xn+2xn)x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right)

则从任意正初始值出发都收敛于 2\sqrt{2}。

收敛速度

设 en=xn−x∗e_n=x_n-x^\ast。在通常的误差非零假设下,如果收敛的迭代满足

lim⁡n→∞∣en+1∣∣en∣p=C,0<C<∞.\lim_{n\to\infty} \frac{|e_{n+1}|}{|e_n|^p} =C, \qquad 0<C<\infty.

则称其收敛阶为 pp。

对于光滑的标量映射:

  • 若 0<∣g′(x∗)∣<10<|g'(x^\ast)|<1,则为线性收敛,渐近收敛因子为 ∣g′(x∗)∣|g'(x^\ast)|。
  • 若 g′(x∗)=0g'(x^\ast)=0 且 g′′(x∗)≠0g''(x^\ast)\ne0,则为二次收敛。
  • 更一般地,若不动点处第一个非零导数为 pp 阶导数,且 p≥2p\ge2,则只要迭代没有在有限步内达到解,其局部收敛阶就为 pp。

线性收敛因子接近 1 时,收敛速度很慢。因此,一种迭代即使满足严格的收敛定理,在计算上也可能仍然效率低下。

牛顿法是一个重要特例:

g(x)=x−f(x)f′(x).g(x)=x-\frac{f(x)}{f'(x)}.

对于充分光滑的函数,在其单根处有 g′(x∗)=0g'(x^\ast)=0,这解释了牛顿法的局部二次收敛性。但这种局部优势并不意味着从任意初始值出发都能收敛。

向量迭代与线性迭代

对于映射 g:Rm→Rmg:\mathbb{R}^m\to\mathbb{R}^m,更新公式仍为

xn+1=g(xn).x_{n+1}=g(x_n).

压缩估计可以用范数表示为

∥g(x)−g(y)∥≤q∥x−y∥,q<1.\|g(x)-g(y)\|\le q\|x-y\|, \qquad q<1.

如果 gg 在不动点附近连续可微,则其雅可比矩阵决定局部行为:

en+1=Dg(x∗)en+o(∥en∥).e_{n+1}=Dg(x^\ast)e_n+o(\|e_n\|).

局部收敛的一个充分条件是

ρ(Dg(x∗))<1,\rho(Dg(x^\ast))<1,

其中谱半径 ρ\rho 是矩阵各特征值绝对值的最大值。如果谱半径大于 1,则不动点不稳定;等于 1 时则需要进一步分析。

对于仿射迭代

xn+1=Bxn+c,x_{n+1}=Bx_n+c,

误差严格满足

en+1=Ben.e_{n+1}=Be_n.

从任意初始向量出发都收敛于唯一不动点,当且仅当

ρ(B)<1.\rho(B)<1.

这一框架涵盖了求解线性方程组的定常迭代法。给定 Ax=bAx=b,选取分裂

A=M−NA=M-N

其中 MM 可逆。于是

xn+1=M−1Nxn+M−1b.x_{n+1}=M^{-1}Nx_n+M^{-1}b.

不同的分裂方式会得到雅可比迭代、高斯–赛德尔迭代等方法。在实际实现中,应用 M−1M^{-1} 通常意味着求解一个更简单的线性方程组,而不是显式构造逆矩阵。

松弛与加速

松弛迭代将直接更新替换为

xn+1=(1−ω)xn+ωg(xn).x_{n+1}=(1-\omega)x_n+\omega g(x_n).

当 ω≠0\omega\ne0 时,它与 gg 具有相同的不动点。取值 0<ω<10<\omega<1 称为欠松弛*;取值 ω>1\omega>1 称为超松弛*。

在标量不动点处,松弛后映射的导数为

1−ω+ωg′(x∗).1-\omega+\omega g'(x^\ast).

选择适当的 ω\omega 可以加快收敛,或使某些振荡迭代稳定下来,但也可能导致发散。欠松弛并非万能的补救措施:如果 g′(x∗)>1g'(x^\ast)>1,那么任意正的 ω\omega 都会使上述导数仍大于 1。

加速方法利用多个迭代值所包含的信息。对于标量序列,艾特肯 Δ² 加速法在分母非零时构造

x^n=xn−(xn+1−xn)2xn+2−2xn+1+xn,\widehat{x}_n =x_n-\frac{(x_{n+1}-x_n)^2} {x_{n+2}-2x_{n+1}+x_n},

它可以消除线性收敛序列中占主导的几何型误差,但分母过小时,计算可能对舍入误差十分敏感。

对于向量问题,安德森加速法通过求解一个小规模最小二乘问题,将先前的迭代值和残差组合起来。其效果取决于映射、保存的历史信息以及实现中的保护措施。

应用

不动点迭代既可用于构造算法,也可用于证明解的存在性。

  • 微分方程。 对于初值问题

    y′(t)=F(t,y(t)),y(t0)=y0,y'(t)=F(t,y(t)),\qquad y(t_0)=y_0,

    皮卡迭代应用积分算子

    yn+1(t)=y0+∫t0tF(s,yn(s)) ds.y_{n+1}(t) =y_0+\int_{t_0}^{t}F(s,y_n(s))\,ds.

    在适当的连续性条件和利普希茨连续性条件下,在足够短的区间上,该算子是适当函数空间上的压缩映射。这是常微分方程解的局部存在唯一性理论的基础。

  • 优化。 梯度下降就是不动点迭代

    xn+1=xn−α∇F(xn).x_{n+1}=x_n-\alpha\nabla F(x_n).

    它的不动点是 FF 的驻点;这些驻点是否为极小值点,以及迭代是否收敛,都需要额外假设。

  • 动态规划。 价值迭代反复应用贝尔曼算子。在奖励有界的标准折扣模型中,该算子在上确界范数下是压缩映射。

  • 非线性模型与离散化方程。 耦合的均衡方程以及非线性微分方程离散化后得到的方程,通常可以通过反复计算映射值或求解较简单的子问题来求解。

皮卡迭代这一名称尤其常用于微分方程中的逐次逼近,而不动点迭代的使用范围更广。

停止准则与局限性

一种常见的停止准则是

∥xn+1−xn∥≤εabs+εrel∥xn+1∥.\|x_{n+1}-x_n\| \le \varepsilon_{\mathrm{abs}} +\varepsilon_{\mathrm{rel}}\|x_{n+1}\|.

它衡量的是迭代步长,而不是直接衡量误差。

定义不动点残差为

r(x)=g(x)−x.r(x)=g(x)-x.

在压缩常数为 q<1q<1 的压缩估计下,

∥x−x∗∥≤∥r(x)∥1−q.\|x-x^\ast\| \le \frac{\|r(x)\|}{1-q}.

因此,已知适当的压缩常数时,就可以由残差得到有保证的误差界。如果 qq 接近 1,即使残差很小,对应的误差也可能大得多。

对于改写后的方程 f(x)=0f(x)=0,原方程的残差同样重要。在迭代 g(x)=x−λf(x)g(x)=x-\lambda f(x) 中,即使 f(x)f(x) 仍然很大,极小的 λ\lambda 也可能产生极小的步长。

其他局限性包括依赖初始近似值、收敛于非预期的不动点、出现周期循环、越出映射的定义域以及收敛缓慢。在浮点运算中,由于相邻迭代值被舍入为同一个数,计算出的迭代序列可能停滞。因此,有限精度下的终止本身并不能证明已经达到精确解。