最后更新: 2026-06-12 19:02 查看: 7 次纠错评论(0) 课件开VIP

不动点迭代法

2.2 不动点迭代法

在正式介绍求解非线性方程数值解的不动点迭代法之前先看一个有趣的例子。选择任意初始值（例如选择初始值 $x=3$ ），在 Python（或其他编程语言）中执行命令 $x=$ 选择初始值．不断重复执行命令 $x=$ math．sqrt $(1+x)$ 得到如下结果：

$$
\begin{array}{ccccccc}
321.7321 & 1.6529 & 1.6288 & 1.6213 & 1.6191 & 1.6184 \\
1.6181 & 1.6181 & 1.6180 & 1.6180 & 1.6180
\end{array}
$$

尝试不同初始值，重复上述过程最后依然得到 1．6180．Python 中等号是赋值运算，上述命令由当前 $x$ 计算等式右边的 $\sqrt{1+x}$ 并将其值赋给等式左边的 $x$ 。而数学中等号是恒等。如果 $x^*$ 等于 $\varphi\left(x^*\right)$ ，则称 $x^*$ 为函数 $\varphi(x)$ 的不动点。我们可以将非线性方程 $f(x)=x^2-x-1=0$ 等价改写为 $x=\sqrt{1+x}$ ，则 $x^*=(1+\sqrt{5}) / 2$ 是非线性方程 $f(x)=0$ 的精确解也是 $\varphi(x)=\sqrt{1+x}$ 的不动点。有趣的是，选择初始数值 $x=3$ ，不断重复上述过程最后得到 1.6180 （即非线性方程 $f(x)=0$ 的解 $(1+\sqrt{5}) / 2$ 的近似解）．

受到上述引例的启发，我们将非线性方程 $f(x)=0$ 改写为等价的不动点形式 $x=\varphi(x)$ ，其中 $x^*$ 是非线性方程 $f(x)=0$ 的解也是 $\varphi(x)$ 的不动点，即 $x^*=\varphi\left(x^*\right)$ 。然后由不动点形式构造不动点迭代格式如下：

$$
\begin{equation*}
x_{k+1}=\varphi\left(x_k\right), \quad k=0,1, \cdots, \tag{2.3}
\end{equation*}
$$

其中 $x_0$ 为初始值，下标 $k$ 表示迭代步数．上述不动点迭代法将困难的非线性方程求解问题转化为简单的函数值计算问题。

迭代格式产生的序列 $\left\{x_k\right\}$ 如果满足

$$
x^*=\lim _{k \rightarrow \infty} x_k=\lim _{k \rightarrow \infty} \varphi\left(x_k\right)=\varphi\left(x^*\right),
$$

则 $x^*$ 是 $\varphi(x)$ 的不动点，即非线性方程 $f(x)=0$ 的解．
下面我们来看一个具体的例子。
例 2.2 不动点迭代法求非线性方程 $x^3+x-1=0$ 在区间 $[0,1]$ 上的解。
解 首先，非线性方程 $x^3+x-1=0$ 可以等价改写为不动点形式 $x=1-x^3$ 。其次，非线性方程等价改写为 $x^3=1-x$ ，然后等式两边同时开三次方得到不动点形式 $x=\sqrt[3]{1-x}$ ．最后，非线性方程还可等价改写如下：

$$
\begin{aligned}
x^3+x-1+2 x^3 & =2 x^3 \\
3 x^3+x-1 & =2 x^3 \\
\left(3 x^2+1\right) x & =2 x^3+1
\end{aligned}
$$

得到不动点形式 $x=\left(2 x^3+1\right) /\left(3 x^2+1\right)$ 。基于上述不动点形式，我们有如下不动点迭代格式：

$$
x_{k+1}=1-x_k^3, \quad x_{k+1}=\sqrt[3]{1-x_k}, \quad x_{k+1}=\frac{2 x_k^3+1}{3 x_k^2+1}, \quad k=0,1, \cdots
$$

给定同样初始值 $x_0=0.5000$ ，三种迭代格式的计算结果见表2．2．我们可以观察到第一种迭代格式并不收敛（在 0 和 1 之间交替），第二种迭代格式缓慢收敛到精确解，而第三种迭代格式很快就收敛到精确解．

![图片](/uploads/2026-06/42bae7.jpg)
 
 对不同迭代格式的不同数值表现，么我们很自然有如下问题：
 
 （1）什么迭代格式收敛？
（2）如果迭代格式收敛，什么迭代格式的收敛速度更快？
研究不动点迭代法收敛性之前需要先讨论不动点的存在性．
定理 2.2 设 $\varphi(x)$ 在区间 $[a, b]$ 上连续．
（1）如果

$$
\begin{equation*}
a \leqslant \varphi(x) \leqslant b, \quad \forall x \in[a, b], \tag{2.4}
\end{equation*}
$$

则 $\varphi(x)$ 在区间 $[a, b]$ 上存在不动点．
（2）如果 $\varphi(x)$ 满足（2．4）且存在常数 $L \in(0,1)$ 使

$$
\begin{equation*}
|\varphi(x)-\varphi(y)| \leqslant L|x-y|, \quad \forall x, y \in[a, b], \tag{2.5}
\end{equation*}
$$

则 $\varphi(x)$ 在区间 $[a, b]$ 上存在唯一不动点．
证明 由（2．4）有 $a-\varphi(a) \leqslant 0$ 和 $b-\varphi(b) \geqslant 0$ ．若上述两式中有一等号成立，$\varphi(x)$在区间 $[a, b]$ 上存在不动点．若上述两式均严格不等号成立，由 $\varphi(x)$ 的连续性及零点存在定理，则存在 $x^* \in(a, b)$ 使 $x^*-\varphi\left(x^*\right)=0$ 成立，即存在不动点 $x^*=\varphi\left(x^*\right)$ 。

下面我们证明唯一性。设 $\varphi(x)$ 有两个不动点 $x_1^*, x_2^* \in[a, b]$ 且 $x_1^* \neq x_2^*$ ，则由（2．5）有

上式矛盾，所以不动点是唯一的．

通常称（2．5）为利普希茨（Lipschitz）条件（也称压缩映像条件），其中 $L$ 称为利普希茨常数。由于上述定理中利普希茨条件一般不容易检验，我们有如下相对容易检验的推论。

推论2．1 若 $\varphi(x)$ 在 $[a, b]$ 上连续和 $(a, b)$ 上可微，满足（2．4）且存在常数 $L \in (0,1)$ 使

$$
\begin{equation*}
\left|\varphi^{\prime}(x)\right| \leqslant L, \quad \forall x \in(a, b) \tag{2.6}
\end{equation*}
$$

则 $\varphi(x)$ 在区间 $[a, b]$ 上存在唯一不动点．
证明 由微分中值定理有

$$
|\varphi(x)-\varphi(y)|=\left|\varphi^{\prime}(\xi)\right||x-y| \leqslant L|x-y|, \quad \forall x, y \in[a, b],
$$

其中 $\xi \in(a, b)$ ．由定理2．2知 $\varphi(x)$ 在区间 $[a, b]$ 上存在唯一不动点．
与利普希茨条件（2．5）相比，上述推论中的条件（2．6）相对容易检验。
定理2．3（全局收敛定理）设 $\varphi(x)$ 在区间 $[a, b]$ 上连续且满足（2．4）和（2．5）。则对任意 $x_0 \in[a, b]$ ，迭代格式（2．3）产生的序列 $\left\{x_k\right\}$ 收敛到 $\varphi(x)$ 在区间 $[a, b]$ 上的不动点且满足

$$
\begin{gather*}
\left|x_k-x^*\right| \leqslant \frac{L}{1-L}\left|x_k-x_{k-1}\right|,  \tag{2.7}\\
\left|x_k-x^*\right| \leqslant \frac{L^k}{1-L}\left|x_1-x_0\right| \tag{2.8}
\end{gather*}
$$

证明 由定理2．2知 $\varphi(x)$ 在区间 $[a, b]$ 上存在唯一不动点 $x^* . x_0 \in[a, b]$ 及（2．4）保证 $\left\{x_k\right\} \in[a, b]$ ．由迭代格式（2．3）及（2．5）递推得

$$
\left|x_k-x^*\right|=\left|\varphi\left(x_{k-1}\right)-\varphi\left(x^*\right)\right| \leqslant L\left|x_{k-1}-x^*\right| \leqslant \cdots \leqslant L^k\left|x_0-x^*\right| .
$$

由于 $0<L<1$ ，所以 $\lim _{k \rightarrow \infty}\left|x_k-x^*\right|=0$ ，即序列 $\left\{x_k\right\}$ 收敛到 $\varphi(x)$ 在区间 $[a, b]$ 上的不动点 $x^*$ 。

下面证明式（2．7）。由（2．5）有

$$
\left|x_k-x^*\right|=\left|x_k-x_{k+1}+x_{k+1}-x^*\right| \leqslant\left|x_k-x_{k+1}\right|+\left|x_{k+1}-x^*\right| \leqslant L\left|x_{k-1}-x_k\right|+L\left|x_k-x^*\right| .
$$

整理得

$$
\left|x_k-x^*\right| \leqslant \frac{L}{1-L}\left|x_{k-1}-x_k\right|
$$
递推得

$$
\left|x_k-x^*\right| \leqslant \frac{L^k}{1-L}\left|x_1-x_0\right|
$$

上面讨论了迭代格式在区间 $[a, b]$ 上的全局收敛性．然而全局收敛性的判别条件一般不容易验证，通常讨论迭代格式在 $x^*$ 处的局部收敛性。

定义2．1 设 $\varphi(x)$ 在区间 $I$ 有不动点 $x^*$ ．若存在 $x^*$ 的一个邻域 $S \subset I$ ，对任意的 $x_0 \in S$ ，迭代格式（2．3）产生的序列 $\left\{x_k\right\} \subset S$ 且收敛到 $x^*$ ，则称迭代格式局部收敛到 $x^*$ 。

定理2．4（局部收敛性定理）设 $x^*$ 为 $\varphi(x)$ 的不动点，$\varphi^{\prime}(x)$ 在 $x^*$ 某邻域 $S$ 上连续且 $\left|\varphi^{\prime}\left(x^*\right)\right|<1$ ，则迭代格式（2．3）局部收敛到 $x^*$ 。

证明 一方面，$f(x)=1-\left|\varphi^{\prime}(x)\right|$ 连续且 $f\left(x^*\right)>0$ ，由连续函数的局部保号性知存在 $x^*$ 的一个邻域 $N\left(x^*\right)=\left[x^*-\delta, x^*+\delta\right] \subset S$ ，对任意 $x \in N$ 有 $f(x)=1-\left|\varphi^{\prime}(x)\right|>0$ ，即 $\left|\varphi^{\prime}(x)\right|<1$ 。另一方面，对于任意 $x \in N\left(x^*\right),\left|\varphi(x)-x^*\right|=\left|\varphi(x)-\varphi\left(x^*\right)\right| \leqslant \delta$ ，故 $\varphi(x) \in N\left(x^*\right)$ 。综上所述，由定理2．3及推论2．1知，对任意 $x_0 \in N\left(x^*\right)$ 迭代格式（2．3）产生的序列 $\left\{x_k\right\} \in N\left(x^*\right)$ 且收敛到 $x^*$ 。

上述定理回答了不动点迭代格式全局和局部收敛性的问题。下面我们进一步研究不动点迭代格式收敛速度的问题．如果迭代格式收敛，则 $x_k$ 和 $x_{k+1}$ 的绝对误差

$e_k=\left|x_k-x^*\right|$ 和 $e_{k+1}=\left|x_{k+1}-x^*\right|$ 均趋近于 0 。我们用 $e_k$ 生成的无穷小量 $\left\{e_k^1, \cdots, e_k^p\right\}$ 精准度量 $e_{k+1}$ 的量级．

定义2．2设序列 $\left\{x_k\right\}$ 收敛到 $x^*$ ，若存在 $p \geqslant 1$ 和 $c>0$ 满足

$$
\begin{equation*}
\lim _{k \rightarrow \infty} \frac{e_{k+1}}{e_k^p}=c, \tag{2.9}
\end{equation*}
$$

则称序列 $\left\{x_k\right\}$ 具有 $p$ 阶收敛速度．当 $p=1$ 和 2 时分别称序列 $\left\{x_k\right\}$ 具有线性收敛和平方收敛速度。

下面定理提供了判断序列具有整数阶收敛速度的简明判别条件。
定理2．5 设 $x^*$ 为 $\varphi(x)$ 的不动点，$\varphi^{(p)}(x)$ 在 $x^*$ 邻域上连续且满足

$$
\begin{equation*}
\varphi^{\prime}\left(x^*\right)=0, \quad \varphi^{\prime \prime}\left(x^*\right)=0, \quad \cdots, \quad \varphi^{(p-1)}\left(x^*\right)=0, \quad \varphi^{(p)}\left(x^*\right) \neq 0, \tag{2.10}
\end{equation*}
$$

其中整数 $p>1$ 。则迭代格式 $x_{k+1}=\varphi\left(x_k\right)$ 产生的序列 $\left\{x_k\right\}$ 局部收敛且具有 $p$ 阶收敛速度，并满足

$$
\begin{equation*}
\lim _{k \rightarrow \infty} \frac{e_{k+1}}{e_k^p}=\frac{\varphi^{(p)}\left(x^*\right)}{p!} . \tag{2.11}
\end{equation*}
$$

证明 由 $\varphi^{\prime}\left(x^*\right)=0$ 及定理2．4知迭代格式局部收敛。在 $x^*$ 处泰勒展开

$$
\varphi\left(x_k\right)=\varphi\left(x^*\right)+\varphi^{\prime}\left(x^*\right)\left(x_k-x^*\right)+\cdots+\frac{\varphi^{(p-1)}\left(x^*\right)}{(p-1)!}\left(x_k-x^*\right)^{p-1}+\frac{\varphi^{(p)}(\xi)\left(x_k-x^*\right)^p}{p!},
$$

其中 $\xi$ 在 $x_k$ 与 $x^*$ 之间．由条件（2．10）我们有

$$
x_{k+1}-x^*=\varphi\left(x_k\right)-\varphi\left(x^*\right)=\frac{\varphi^{(p)}(\xi)\left(x_k-x^*\right)^p}{p!} .
$$

等式两边同时取极限，由 $\varphi^{(p)}(x)$ 的连续性整理得

$$
\lim _{k \rightarrow \infty} \frac{e_{k+1}}{e_k^p}=\lim _{k \rightarrow \infty} \frac{x_{k+1}-x^*}{\left(x_k-x^*\right)^p}=\lim _{k \rightarrow \infty} \frac{\varphi^{(p)}(\xi)}{p!}=\frac{\varphi^{(p)}\left(x^*\right)}{p!} .
$$

我们可以，验证例 2.2 中不同迭代格式

$$
x_{k+1}=\varphi_1\left(x_k\right)=1-x_k^3, \quad x_{k+1}=\varphi_2\left(x_k\right)=\sqrt[3]{1-x_k}, \quad x_{k+1}=\varphi_3\left(x_k\right)=\frac{2 x_k^3+1}{2 x_k^2+1}
$$

的一阶导数绝对值在不动点 $x^* \approx 0.6823$ 处为

$$
\left|\varphi_1^{\prime}\left(x^*\right)\right|>1, \quad\left|\varphi_2^{\prime}\left(x^*\right)\right|<1, \quad\left|\varphi_3^{\prime}\left(x^*\right)\right|=0 .
$$

根据不动点迭代法收敛理论，第一种迭代格式不收敛，第二种和第三种迭代格式局部收敛且第三种迭代格式具有更快的收敛速度。我们可以从表2．2 观察到不同迭代格式的数值表现与上述理论分析相互印证．

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：二分法

下一篇：牛顿迭代法

本文对您是否有用？有用 (0) 无用 (0)