不动点迭代法求解非线性方程组

摘要：一般非线性方程组可以写成F(x)0的形式，其中F:RR是定义在区域

nmDRn上的向量函数。把方程组F(x)0改写成与之等价的形式：xG(x)。因此，求

方程组F(x)0的解就转化为求函数的G(x)的不动点。本文首先介绍了多变量函数F(x)的微积分性质，接着介绍了用不动点迭代法求解非线性方程组。 关键词：多变量函数；微积分；不动点

Fixed Point Iteration Method For Solving Nonlinear Equations

Abstract：General nonlinear equations can be written in the form of F(x), where the vector functionF:RnRmis defined on the region DRn. Transform the equationsF(x)0 into its equivalent form: xG(x).Therefore, we can get the solution of

F(x)0 by finding the fixed point of G(x).In this paper, we first introduce some knowledge

about multivariable calculus, then introduce the fixed point iteration method for solving nonlinear equations.

Key words: multi-variable function; calculus; fixed point

1 引言

一般非线性方程组及其向量表示法:含有n个方程的n元非线性方程组的一般形式为

f1(x1,x2...,xn)0f(x,x...,x)0212n （1） ......fm(x1,x2...,xn)0n其中，fii1,2,...,n是定义在DR上的n元实值函数，且fi中至少有一个是非线性

函数。

x1x2令x，F(x)...xnnf1xf2x，则方程组可以表示为F(x) （2） ...fmxm*其中F:RR是定义在区域DRn上的向量函数。若存在xD，使

F(x*)，则称x*是方程组（1）或（2）的解。把方程组F(x)0改写成与之等价的形

式：xG(x)

nn**其中G：DRR。若xD满足xG(x)，则称x为函数G(x)的不动点。因此

**G(x)的不动点就是方程组F(x)0的解，求方程组F(x)0的解就转化为求函数的G(x)的不动点。适当选取初始向量x(0)D，构成迭代公式x(k+1)G(x(k)),k0,1,2,...迭代

公式也称为求解方程组F(x)0的简单迭代法，又称不动点迭代法。G(x)称为迭代函数。 由于F是多变量函数，所以我们先考虑多变量函数的微积分性质。

2多变量函数的微积分性质

在之前我们已经学习过很多关于单变量函数的微积分的性质，由于解非线性方程组经常用到的是多变量函数的相关性质，因此我们考虑多变量函数的微积分性质。相对于单变量函数的微积分的性质，多变量函数的微积分性质一些是类似的，一些是不同的。相对于单变量函数的可微的定义，我们事先给出多变量函数的可微定义。

R,n1的微积分性质 函数f:RnR,n1。我们首先考虑当f是连续的函数的情况，如设函数多变量函数f:R果f关于n个变量的偏导数都存在并且连续，把这n个偏导数组成一个n维向量，则我们把这个n维向量称作多变量函数f的梯度。

nR，如果定义1：连续可微函数f:Rnfx，i1,...,n；存在并且连续，则xiTffn称函数f在点xR上连续可微，并且称fxx,...,x为函数f在点

xxn1xRn的梯度。

如果函数f在开区域DRn上每一点连续可微，则称函数f在开区域DRn连续可微，记作fC1D。

下面我们给出关于多变量函数f的梯度的一些性质：

R在开凸集DRn连续可微，则对于xD以及任意一个非零引理1 设f:R扰动pRnn，则函数f在点x在方向p上的方向导数定义为

fxpfxfT存在并且等于fxp。对于x,xpD，xlim0pfxpf(x)fxtppdtf(x)0T1Txpxfzdz，并且存在

zx,xp使得，fxpf(x)fzp。

下面我们给我这个引理的证明过程，主要思想是把多变量函数转化为单变量函数，然后利用我们已知的单变量函数微积分的性质来证明多变量函数微积分的性质。

证明：首先在点x到点xp的连线上对函数f进行参数化，转变成单变量函数g。定义

x(t)xtp，g:RR,g(t)f(xtp)。由链式法则，对于01，

nnfxtdxtifdgx xpi dtxtidti1xii1 fxpp。 因为

gtg0f(x)(x)limg(0)，所以令0，我们就可以得到

t0ptfTxfxp。 p由单变量函数的牛顿定理我们可知，g(1)g(0)义，上式也可以写成fxpf(x)后，由单变量函数的积分中值定理

10g(t)dt。根据前面对函数g的定

fxtp01Tpdt。这就得到我们所要的证明。最

10g(t)dtg,0,1，根据函数g的定义，我们

可以写成fxpf(x)fxpp，0,1。对替换zxtp，可得

Tfxtp01Tpdt进行变量

10fxtppdtTxpxfzdz，从而得证。

R的微积分性质 函数f:Rn下面给出多变量函数二次可微的定义，并进一步给出函数f的Hessian矩阵的定义。

2fR，如果定义2：连续可微函数f:Rx，1i,jn存在并且连续，

xixjnR在点x上二次连续可微；定义一个nn矩阵，其中第i,j元素为则称函数f:Rn2ff(x)ijx，1i,jn，则称这个矩阵为函数f的Hessian矩阵。

xixj2如果函数f在开区域DR上每一点连续可微，则称函数f在开区域DR连续可微，记作fC2nnD。

类似的我们给出关于多变量函数f的二阶连续可微的一个引理。

R在开凸集DRn二次连续可微，则对于xD以及任引理2：设函数f:Rn意一个非零扰动pR，则函数f在点x在方向p上的二阶方向导数

n2f(x)lim20pffxpxpp存在，并且等于pf(x)p。对于对于

T2x,xpD，存在zx,xp使得fxpf(x)f(x)Tp1T2pf(z)p。 2定理的证明过程与一阶连续可微情况的证明过程类似。从Hessian矩阵的定义可知，只要函数f是二次连续可微的，那么Hessian矩阵是对称的。

函数F:RnRm的微积分性质

我们进一步考虑更复杂的情况，也就是从R空间到R空间的函数，设函数

nmf1xf1(x1,x2...,xn)..nm。其中，非线性联立方F:RR，具体可以写成F(x)....f(x)f(x,x...,x)nmm12程问题是mn的情况；非线性最小二乘问题是mn的情况。下面我们给出函数F的相关可微性质：

nmm定义3 连续函数F:RR，如果每一个部分函数fi,i1,...,m在点xR连续可微，

m则称函数F在点xR连续可微。函数F在点x的导数叫作F在点x的Jacobian矩阵，它

mn的转置叫作F在点x的梯度。通常的表示为F(x)R，F(x)ijfix，xjF(x)JxFx。

如果F在开区域DRn上每一点连续可微，则称函数F在开区域DRn连续可微，记作FC1D。

用下面一个例子来具体说明这个定义。

2例1 设F:RR，f1xe1x2，f2xx12x2。

22Txf1xx1 解： J(x)f2xx1f1xex1x2f2x2x1x21 2下面我们研究单实值函数和向量值函数不同方面，对于实值函数存在中值定理，而对于向量值函数，中值定理不一定成立。也就是说，不一定存在zR，使得

nF(xp)F(x)J(z)p。直观上来看，尽管每个函数fi满足

fi(xp)fi(x)fizip，但是点zi是不同的。以上面例子中的函数来考虑， e11ez111z，也就是，e1e1并且2z11，这是不可能的，所以 102z121不存在zR，使得F1,1F(0,0)J(z)(1,1)。

nTT尽管标准的中值定理是不可能的，我们给出一个近似的中值定理，主要是利用牛顿定理和线性积分的三角不等式。其中，单变量向量值函数的积分可以理解为对每一个部分函数进行黎曼积分。

引理3：设F:RR在开凸集DRn上连续可微，对于x,xpD，有

nmF(xp)F(x)J(xtp)dt01xpxF(z)dz。

上式可以写成如下中值定理的形式：

11F(xp)F(x)JxtppdtJxtpdtp。

00因此，我们主要介绍了三种函数，从RR的函数、从RR的函数以及从

nRnRm的函数的可微性质。

3不动点迭代法

把方程组F(x)0改写成与之等价的形式：xG(x)。其中G：DRR。若

nnx*D满足x*G(x*)，则称x*为函数G(x)的不动点。因此G(x)的不动点就是方程组F(x)0的解，求方程组F(x)0的解就转化为求函数的G(x)的不动点。

适当选取初始向量x(0)D，构成迭代公式x(k+1)G(x(k)),k0,1,2,...迭代公式也

称为求解方程组F(x)0的简单迭代法，又称不动点迭代法。G(x)称为迭代函数。

nn定理1（压缩映射原理）设G：DRR在闭域D0D上满足条件：

（1）G把D0映入它自身，即G(D0)D0；

（2）G在D0上是压缩映射，即存在常数L(0,1)，使对任意的x,yD0，

G(x)G(y)Lxy

则以下结论成立： （1）对任取的x(0)(k+1)D0，G(x(k))，k0,1,2,...产生的序列x(k)D0 由迭代公式x收敛于函数G(x)在区域D0内存在唯一的不动点x；

*（2）成立误差估计式xx证明：由于x(0)*(k)LkLx(1)x(0) ，x*x(k)x(k)x(k1) 。 1L1LD0以及条件（1）可知序列x(k)D0，又由条件（2）可得

 x(k1)x(k)G(x(k))G(x(k))Lx(k)x(k1)...Lkx(1)x(0) 当m1时有

x(km)x(k)xi1m(ki)x(ki1)Lki1x(1)x(0)i1mLk(1Lm)(1)Lk(0)xxx(1)x(0)1L1L （1）

因为0L1，所以当k时，上式的最后一项是无穷小量，由Cauchy收敛原理，序列

x(k)在Rn中收敛，又由D0是闭区域x(k)的极限x(*)D0，由条件（2）知，

G(x)在D0上连续，因而x*limx(k1)limG(x(k))G(x*)，即x*是方程组

kkF(x)0的解。

** 设x,yD0是F(x)0的两个不同的解，则有

*这表明x是F(x)0在内的唯一解。 x*y*G(x*)G(y*)Lx*y*x*y*，

让m，得xxm*(k)Lkx(1)x(0) 1Lx(ki1)x(km)x(k)xi1(ki)Lix(k)x(k1)

i1mL(1Lm)(k)Lxx(k1)x(k)x(k1) 1L1Lx(k)x(k1)x(k)说明：（1）简单迭代法的精度控制与终止条件

；

（2）由

x*x(k+1)xx*(k)L知简单迭代法是线性收敛的；

（3）对线性方程组迭代函数G(x)Bxd，有L=B<1；

*定理2（局部收敛定理）设G：DRR,xint(D)是方程组F(x)0 的解，在xnn*可微。若G(x)谱半径G(x)1，则存在开球D0xxx*,0，对任取的

x(0)D0，由迭代公式x(k+1)G(x(k))，k0,1,2...产生序列x(k)D0收敛于x*。

下面我们给出一个例子，通过来求函数G(x)的不动点来解非线性方程组。 例2 用简单迭代法求解以下方程

3x1cosx1sinx20 4xsinxcosx0212要求满足精度e(k)x(k)x(k1)x(k)1012

1(cosxsinx)123x1解：设x，G(x)

1x(sinxcosx)2124则方程组可以改写成xG(x)，并且对于任意的xR,yR，

221(cosxcosysinxsiny)11223G(x)G(y)

1(sinxsinycosxcosy)12224Axy13sin1其中，A1cos14因此，任取初始向量x(0)Axy7xy 121cos273，A

112sin24R，简单迭代法产生序列x(k)收敛于原方程组的唯一解。

(k1)1(k)(k)x=cosxsinx1123迭代公式

1x(k1)sinx(k)cosx(k)2124计算结果：

k 0 1 2 … 4 26 27 28

x1k …… …… kx2 ek 0. …… 参考文献：

[1] 李庆杨, 关治, 白峰杉. 数值计算原理[M].清华大学出版社.2000;

[2] 李庆杨，王能超，易大义.数值分析[M].武汉：华中理工大学出版社，1986.

[3] 黄象鼎，曾钟钢，马亚男.非线性数值分析的理论与方法[M].武汉：武汉大学出版社，2004. [4] 曾金平，李湘良.数值计算方法[M].长沙：湖南大学出版社，2004. [5] 马吕凤，林伟川.现代数值计算方法[M].北京：科学教育出版社，2008. [6] 王德人.非线性方程组解法与最优化方法。人民教育出版社，1979 [7] 林成森.数值计算方法（第二版）[M].北京：科学出版社，2005.