不动点迭代

不动点迭代

调频电源-市恩贾义

2023年3月18日发(作者：鹿胎丸)

第四章一元方程求根/非线性方程组数值解法初步

4．1一元方程求根的主要概念、思想和二分法

1．主要概念

包含一个未知量的x的一元方程的一般形式记为

0)(xf

通常，考虑如下的情形：

（1）一元函数

f

在某个区间比如],[ba上连续，即],[baCf的情形。

（2）f是x的二次以上的代数多项式，如010423xx

这时称方程为多项式方程或高次代数方程。

（3）f不是代数多项式，如

01xxe,0cos2312xx,;012222xexx

这称为超越方程，也是本章的研究内容。

通常，对于f不是x的线性函数的方程，人们统称为一元非线性方程，

简称一元方程或非线性方程。

在实际应用中，f可能是非常复杂的表达式，甚至还包含多个其他参

数，令人眼花缭乱。因此，首先一定要识别未知量是哪一个，是不是

这里所研究的一元非线性方程的情形。只有这样，才能使用一元非线

性方程求根的计算方法。我们将看到，非线性方程的求根的方法主要

是迭代法。

方程0)(xf的解*x，即0)(*xf，也称为方程的根，或函数f的零点。

这里*x可为实数或复数，但我们主要考虑实数根。

我们熟悉一元二次方程有单根与重根的概念。推广到一般非线性方

程，若f可表示为

)()()(*xgxxxfm

其中m为正整数，0)(*xg，则称*x是方程0)(xf的m重根，或函数

f的m重零点。当1m时，*x是方程0)(xf的单根，或函数f的单重

零点。由此，若*x是0)(xf的m重根且)(xg充分光滑，则意味着















0*)(

0)(,,0)(',0)(

)(

*)1(**

xf

xfxfxf

m

m

2.主要思想

如果假设方程在区间],[ba有根，就称为],[ba为方程的有根区间；如果

还已知方程在],[ba上有且只有一个根，即有根区间把根隔离了，那样

更好。显然，在已知有根区间的前提下，把有根区间不断缩小，便可

逐步得出根的近似值。这正是一元非线性方程求根的基本思想。

这样说来，方程求根的全过程，就是先谋求“有根区间”或“根的邻

域”。然后展开对根的粗粗糙近似值的精确化。

寻找有根区间（包括根的邻域），通常有这样的一些线索：

(1)如果f是n次多项式，则由代数基本定理知，在复数域内方程

有n个根；如果f还是实系数多项式，则复根将成对出现。

(2)对一般方程，利用连续函数性质，如果],[baCf，且

0)()(bfaf（即)(af与)(bf异号），则方程在],[ba内至少有一实根；

又)('xf在],[ba中不变号且不为0，则方程在],[ba内只有惟一根。

（3）如果希望找出方程的所有实根，则可用一个适当的步长，对f的

定义区间进行“扫描“，利用(2)的方法搜索出对应的有根区间。

（4）此外，对具体的问题也可使用具体的试算手段。

在有根区间或根的邻域的基础上，各种著名的求根方法（如第一张介

绍的不动点迭代法、Newton迭代法等等）就从这里开始，把粗糙近

似值进行不断的精确化，直到满足精度为止。

3．二分法（对半法）

二分法本来是一个独立的求根方法，在计算机查找算法中也是很常用

的简单算法。但在数值计算中，直接用它来求根已经不多，但用它来

快速缩小有根区间则相当有效。

无妨设0)(af，0)(bf，则],[ba为有根区间。记],[],[

00

baba，第一

次计算中点

2

00

1

ba

x



及其函数值)(

1

xf，这时有0)()(

00

bfaf，于是得新有根区

间

],[],[

1110

baxa且

211

ab

ab





第二次计算中点

2

11

2

ba

x



及其函数值)(

2

xf，这时有0)()(

21

xfaf，

于是得新有根区间],[],[

2212

baxx且

2

222

ab

ab





如此继续，第n次计算中点

2

11



nn

n

ba

x及其函数值)(

n

xf后，可得新

有根区间

],[

nn

ba且

n

nn

ab

ab

2





于是在],[

nn

ba中任取一点，如取

n

a或

n

b（其中一个就是

n

x）或其他，

比如记为x（不一定是中点）作为方程根*x的近似值，则至少有误差

估计

n

ab

xx

2

||*



（若x取],[

nn

ba的中点

21

nn

n

ba

x







，则

1

1

*

2

||









n

n

ab

xx）

可见

1n

x必收敛于*x.

二分法简单可靠，只要求

)(xf

连续，收敛性总能得到保证。其缺点是

不能用来求复数和偶重根。二分法主要用来快速(一半一半地)缩小有

根区间，从而可提供较好的精确化初值。如果用来求],[ba的根，通常

不假定],[ba内只有一个根，而是先用一个适当的步长h对],[ba进行扫

描搜索，当发现哪个子区间有根时，便调用上述二分算法过程求出其

中之根。所谓适当的步长h，就是既不因为h过大而漏掉包含的根，

也不因h过小而耗费计算精力。

4．2不动点迭代法及其收敛性理论

1．迭代法(不动点迭代法)

迭代法是求解一元非线性方程0)(xf的主要方法。其做法是（类

似线性代数方程组的迭代法）：将方程0)(xf改写为等价方程

)(xx

这时，方程)(xx成为“隐式”形式，除非是x的线性函数，否则

不能直接算出它的根。对此，从某个初始值

0

x开始，对应)(xx构

造迭代公式（格式）

),2,.1,0)((

1





kxx

kk



这就可确定序列),2,1,0(kx

k

（因x是单变量，所以迭代标记k写为

下标即可）。

如果

k

x有极限

*limxx

k

k





并且由)(

1kk

xx



式两边取极限，可知*x就是方程)(xx的根，这

时称迭代公式)(

1kk

xx



是收敛的。实际求解中，只有对收敛的

)(

1kk

xx



才有意义，但不能做无穷多步，因此，按精度要求，取某

个迭代值

k

x作为方程)(xx的根的近似值，这种求根的方法称为迭

代法，式中)(x

称为迭代函数。

这里，由于)(**xx，直观看来，即解*x经计算后)(*x仍等于*x

（岂不是没有动），因此，称*x是函数的一个不动点，公式

),2,.1,0)((

1





kxx

kk

也称为不动点迭代公式，非线性方程的迭代法

也称为不动点迭代法。注意到迭代公式)(

1kk

xx



在求

1k

x时只依赖于

k

x，这称为单步迭代。

例4.2.1用不动点迭代法求方程010423xx在]2,1[内的一个实根。

解：将方程改写成等价形式。

先考虑方法一：

310

2

1

xx

即迭代函数310

2

1

)(xx，从而可得迭代公式

),,2,1,0(10

2

1

3

1





kxx

kk

取5.1

0

x，做迭代计算，发现所得的序列

k

x是收敛的。

考虑方法二：

x

x

x4

10



即x

x

x4

10

)(

1

从而得到迭代公式

),2,1,0(4

10

1





kx

x

x

k

k

k

考虑方法三：

10423xxxx

即104)(23

2

xxxx从而得到迭代公式

),2,1,0(10423

1





kxxxx

kkkk

对)(

1

x，计算过程出现负数开方，无法继续进行；对)(

2

x，可以认

为迭代序列并不收敛。

定理4.2.1设迭代公式)(

1kk

xx



中的迭代函数

],[baC，满足

条件：

（1）当bxa时，也有

bxa)(（称映内性）；

（2）存在常数10L（

L

称为压缩系数），使得

|||)()(|xxLxx

，],[,baxx（称压缩性）

可得：

①函数



在],[ba上存在惟一的不动点*x；

②对任意初值],[

0

bax，迭代公式)(

1kk

xx



收敛于*x；

③迭代值有误差估计式

||

1

||

1

*









kkk

xx

L

L

xx(4.2.6)

||

1

||

01

*xx

L

L

xx

k

k





(4.2.7)

证明（1）先证明存在性。由bxa，若aa)(

或bb)(

，

则a或

b

就是方程的根，否则，可设

aa)(

及

bb)(

，做辅助函

数

xxx)()(

显然

],[)(baCx，且有

0)()(aaa0)()(bbb

于是根据连续性质，至少存在一点

),(*bax

满足

0)(*x

，即

**)(xx

。这就是说，方程

)(xx

的根存在。

再证明惟一性。用反证法，若方程

)(xx

有两个不同的根

*

1

x

,

],[*

2

bax

,则由已知条件（2）可得

|||||)()(|||*

2

*

1

*

2

*

1

*

2

*

1

*

2

*

1

xxxxLxxxx

自相矛盾！可知方程

)(xx

只能有惟一根。

要证迭代公式)(

1kk

xx



收敛，即要证序列],[}{

0

bax

kk





且

*limxx

k

k





。由已知条件（1），显然每一个],[bax

k

,故

],[}{

0

bax

kk





；再由条件（2）可得

|||||||)()(|||

0

*

2

*2

1

*

1

**xxLxxLxxLxxxxk

kkkk







因10L，故有0||lim*



k

k

xx，即*limxx

k

k





。

（3）从|||||)()(|||

1

**

1

**

1



kkkkkk

xxxxxxxxxx

||)1(||||***

kkk

xxLxxLxx

于是可得||

1

1

||

1

*

kkk

xx

L

xx







又注意到

|||||||)()(|||

0121

2

111

xxLxxLxxLxxxxk

kkkkkkkk







故可得

||

1

1

||

1

1

||

11

*













kkkkk

xx

L

xx

L

xx

继续利用前述递推式，于是可得（3）。

对定理的应用，需要说明下列几点：

①由定理可得一个推论，这就是定理条件（2）也可换为更强的条件，

即设



在

),(ba

上可导，且存在常数

10L

，使得

1|)('|Lx),(bax

这是因为，如果上式成立，由中值定理有

|||||)('||)()(|xxLxxxx

即条件（2）必成立。实际应用中上式倒是常用。

②由误差估计4.2.6可见，当1

1

1



L

即

2

1

0L时，有

||||

1

*





kkk

xxxx

也即只要前后两次迭代值的误差||

1



kk

xx足够小，则

k

x就足够接近

*x,因此在设计计算机算法时，通常预先给定一个允许误差，然后

检查绝对误差或相对误差























)(||

||

||

)(||||

1

1

某个控制常数当

某个控制常数当

Cx

x

xx

Cxxx

k

k

kk

kkk

当时，便控制迭代结束，由当前的

k

x作为方程)(xx根的

近似值，否则，继续进行迭代。通常取1C来控制选用上述两种误

差之一。

③当

1

2

1

L

，特别是

L

很靠近

1

时，尽管||

1



kk

xx很小，

k

x，*x

仍然相差很大，

k

x不宜做近根。这时，可根据精度要求





||

1

*

k

xx，先确定最低迭代次数

k

使得





||

101

xx

L

LK

可知迭代次数应满足

K

L

xx

L

k







ln

||

)1(

ln

01



因此，可取迭代次数

KN

（的整数部分）+1，把迭代值

N

x作为根

的近似值。

不过，需要指出的是，实际计算中

L

难以确定，事实上可以选择“充

分小“的来控制精度要求，故对上述②③两种情况，不妨均简化为

只要



||

1kk

xx，即认为有||*

k

xx。

例4.2.2用不动点迭代法求解方程

)1(2lnxxx

要求相对

误差810。

解：先来确定方程的有根区间。令

2ln)(xxxf

由

x

xf

1

1)('，对1x，有0)('xf，故)(xf在),1(单调递增，

可知方程在),1(只有一个根。试算若干个值：

021ln1)1(f022ln2)2(f

023ln3)3(f

024ln4)4(f

可知]4,3[为方程的惟一有根区间。

现自然地改写方程为2lnxx，即迭代函数xxln2)(当

]4,3[x时

满足条件

44ln2)(3ln23x

和

1

3

1

|

1

||)('|

x

x

故对任意的]4,3[

0

x，迭代公式),1,0(ln2

1





kxx

kk

收敛于方程的根。取3

0

x实际计算，并同时计算相对误差

||

||

1

k

kk

x

xx







注意到88

15

101035.0，故取146193216.3

15

*xx

例4.2.3试用定理4.2.1分析例4.2.1中同一方程的3种不同迭代

函数。

解：对310

2

1

x，有

3

2

104

3

)('

x

x

x



，考虑区间]2,1[，因

12.2)2('，不满足收敛条件（2）的推论。但如果改为考虑区间

]5.1,1[，则由'表达式应有

66.0|)5.1('||)('|x

且由于



是减函数，故5.1)1()()5.1(28.1x

即收敛定理的两个条件满足，于是对任意的]5.1,1[

0

x，迭代收敛。

对x

x

4

10

1

有).4

10

2/()4

10

()('

2

1

x

xx

x

可知当21x时，不能保证2)(1

1

x

；同时还有

4.3|)('|*

1

x，也难以找到包含*x的区间使在其上

1|)('|

1

Lx

，故无法保证迭代收敛。

对

104)(23

2

xxxx

有

xxx831)('2

2



，由

365.1*x找不到包含*x的区间使在其上

1)('

2

x

,故也无法

保证迭代收敛。

上述例子说明，有根区间缩小了，不满足定理的条件也有可能变

成满足。

3.局部收敛性的提出

定义4.2.1若存在



的不动点*x及其一个邻域

],[**xx

，使得对任意的

0

x,由迭代公式)(

1kk

xx



产生的序列

k

x收敛于*x（即要求

k

x且*limxx

k

k





），则称迭

代公式)(

1kk

xx



或序列

k

x是局部收敛的。

定理4.2.2(局部收敛性定理)设*x为



的一个不动点，'在*x的

某个邻域上存在、连续且

1)('*x

，则迭代公式)(

1kk

xx



局部收

敛。

证明：因'连续，故存在*x的一个邻域],[**xx，使得在



上

1|)('|Lx，且

|||||||)('||)()(||)(|*****xxxxLxxxxxx

因而对x有**)(xxx，根据定理4.2.1，可知对

任意的

0

x，迭代公式)(

1kk

xx



收敛，即局部收敛。

对定理4.2.2可能有一个疑问：根*x还没有求出来，如何判断

1)('*x

呢？

其实，由于'的连续性，在*x的某个邻域就应该有1|)('|x

。应用

中有时可采用这样一个不严格的准则；只要在一个不大的有根区间

上，

|)('|x

明显地小于1，那么从该区间内一点

0

x出发，由

)(

1kk

xx



式产生的迭代序列

k

x一般是收敛的。

4.收敛速度与收敛阶的概念

定义4.2.2设迭代过程)(

1kk

xx



产生的迭代序列

k

x收敛于方

程的根*x，记迭代误差

kk

xxe*，如果存在实数1p和非零数

C

，

使得

C

e

e

p

k

k

k



||

||

lim1

则称迭代过程)(

1kk

xx



是

p

阶收敛的，

C

称为渐进误差常数。

特别地，1p时称为线性收敛；2p时称为平方收敛或2阶

收敛；1p称为超线性收敛。

p

的大小反映了

k

x收敛速度的快慢，

p越大收敛越快。

定理4.2.3如果*x是



的不动点，定理4.2.2条件中还有

0)('x，则迭代过程)(

1kk

xx



在*x的邻域是线性（1阶）收敛

的。

证明：由

kkkkk

exxxxe)(')()(*

1

*

1





其中

k

在*x和

k

x之间，故有

0|)('|

||

||

lim*

1



x

e

e

k

k

k



按定义可知迭代过程确是线性(1阶)收敛的。

定理4.2.4如果*x是



的不动点，对整数1p，迭代函数



及其

p~1阶导数在*x邻域上连续，且满足











0)(

0)()('')('

*)(

*)1(**

x

xxx

p

p





则迭代过程)(

1kk

xx



在*x的邻域是

p

阶收敛的，且有

!

)(

||

||

lim

*)(

1

p

x

e

ep

k

k

k







证明由

0)('*x

及定理4.2.2可知，迭代过程)(

1kk

xx



局部收

敛。又由taylor展开得

p

k

k

p

p

k

p

kkk

xx

p

xx

p

x

xxxxxx

)(

!

)(

)(

)!1(

)(

))((')()(

*

1*

*)1(

***

1



















其中

k

在

k

x和*x之间。代入**)(xx

可得：

p

k

k

p

k

xx

p

xx)(

!

)(

*

)(

*

1







于是有

0

!

)(

!

)(

lim

)(

lim

||

lim

*)(

)(

*

*

11















p

x

p

xx

xx

e

ep

k

p

k

p

k

k

k

p

k

k

k





按定义可知迭代过程确是p阶收敛的。