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

不动点迭代法求解非线性方程组摘要：一般非线性方程组可以写成()0Fx的形式，其中:nmFRR是定义在区域nDR上的向量函数。把方程组()0Fx改写成与之等价的形式：(xGx)。因此，求方程组()0Fx的解就转化为求函数的(Gx)的不动点。本文首先介绍了多变量函数()Fx的微积分性质，接着介绍了用不动点迭代法求解非线性方程组。关键词：多变量函数；微积分；不动点FixedPointIterationMethodForSolvingNonlinearEquationsAbstract：Generalnonlinearequationscanbewrittenintheformof()Fx,wherethevectorfunction:nmFRRisdefinedontheregionnDR.Transformtheequations()0Fxintoitsequivalentform:(xGx).Therefore,wecangetthesolutionof()0Fxbyfindingthefixedpointof(Gx).Inthispaper,wefirstintroducesomeknowledgeaboutmultivariablecalculus,thenintroducethefixedpointiterationmethodforsolvingnonlinearequations.Keywords:multi-variablefunction;calculus;fixedpoint1引言一般非线性方程组及其向量表示法:含有n个方程的n元非线性方程组的一般形式为11221212(,...,)0(,...,)0......(,...,)0nnmnfxxxfxxxfxxx（1）其中，1,2,...,ifin是定义在nDR上的n元实值函数，且if中至少有一个是非线性函数。令12...nxxxx，12()...mfxfxFxfx，则方程组可以表示为()Fx（2）其中:nmFRR是定义在区域nDR上的向量函数。若存在*xD，使*()Fx，则称*x是方程组（1）或（2）的解。把方程组()0Fx改写成与之等价的形式：(xGx)其中nnGDRR：。若*xD满足**(xGx)，则称*x为函数(Gx)的不动点。因此(Gx)的不动点就是方程组()0Fx的解，求方程组()0Fx的解就转化为求函数的(Gx)的不动点。适当选取初始向量(0)xD，构成迭代公式(+1)()(),0,1,2,...kkxGxk迭代公式也称为求解方程组()0Fx的简单迭代法，又称不动点迭代法。(Gx)称为迭代函数。由于F是多变量函数，所以我们先考虑多变量函数的微积分性质。2多变量函数的微积分性质在之前我们已经学习过很多关于单变量函数的微积分的性质，由于解非线性方程组经常用到的是多变量函数的相关性质，因此我们考虑多变量函数的微积分性质。相对于单变量函数的微积分的性质，多变量函数的微积分性质一些是类似的，一些是不同的。相对于单变量函数的可微的定义，我们事先给出多变量函数的可微定义。2.1函数:,1nfRRn的微积分性质设函数多变量函数:,1nfRRn。我们首先考虑当f是连续的函数的情况，如果f关于n个变量的偏导数都存在并且连续，把这n个偏导数组成一个n维向量，则我们把这个n维向量称作多变量函数f的梯度。定义1：连续可微函数:nfRR，如果ifxx，1,...,in；存在并且连续，则称函数f在点nxR上连续可微，并且称1,...,Tnfffxxxxx为函数f在点nxR的梯度。如果函数f在开区域nDR上每一点连续可微，则称函数f在开区域nDR连续可微，记作1fCD。下面我们给出关于多变量函数f的梯度的一些性质：引理1设:nfRR在开凸集nDR连续可微，则对于xD以及任意一个非零扰动npR，则函数f在点x在方向p上的方向导数定义为0limfxpfxfxp存在并且等于Tfxp。对于,xxpD，10()()xpTxfxpfxfxtppdtfxfzdz，并且存在,zxxp使得，()Tfxpfxfzp。下面我们给我这个引理的证明过程，主要思想是把多变量函数转化为单变量函数，然后利用我们已知的单变量函数微积分的性质来证明多变量函数微积分的性质。证明：首先在点x到点xp的连线上对函数f进行参数化，转变成单变量函数g。定义()xtxtp，:,()()gRRgtfxtp。由链式法则，对于01，1niiifxtdxtdgxdtxtdt1niiifxpxfxpp。因为00()()lim(0)tgtgfxxgpt，所以令0，我们就可以得到Tfxfxpp。由单变量函数的牛顿定理我们可知，10(1)(0)()gggtdt。根据前面对函数g的定义，上式也可以写成10()Tfxpfxfxtppdt。这就得到我们所要的证明。最后，由单变量函数的积分中值定理10(),0,1gtdtg，根据函数g的定义，我们可以写成()Tfxpfxfxpp，0,1。对10Tfxtppdt进行变量替换zxtp，可得10Txpxfxtppdtfzdz，从而得证。2.2函数:nfRR的微积分性质下面给出多变量函数二次可微的定义，并进一步给出函数f的Hessian矩阵的定义。定义2：连续可微函数:nfRR，如果2ijfxxx，1,ijn存在并且连续，则称函数:nfRR在点x上二次连续可微；定义一个nn矩阵，其中第,ij元素为22()ijijffxxxx，1,ijn，则称这个矩阵为函数f的Hessian矩阵。如果函数f在开区域nDR上每一点连续可微，则称函数f在开区域nDR连续可微，记作2fCD。类似的我们给出关于多变量函数f的二阶连续可微的一个引理。引理2：设函数:nfRR在开凸集nDR二次连续可微，则对于xD以及任意一个非零扰动npR，则函数f在点x在方向p上的二阶方向导数220()limffxpxfppxp存在，并且等于2()Tpfxp。对于对于,xxpD，存在,zxxp使得21()()()2TTfxpfxfxppfzp。定理的证明过程与一阶连续可微情况的证明过程类似。从Hessian矩阵的定义可知，只要函数f是二次连续可微的，那么Hessian矩阵是对称的。2.3函数:nmFRR的微积分性质我们进一步考虑更复杂的情况，也就是从nR空间到mR空间的函数，设函数:nmFRR，具体可以写成112112(,...,)..()....(,...,)()nmnmfxxxfxFxfxxxfx。其中，非线性联立方程问题是mn的情况；非线性最小二乘问题是mn的情况。下面我们给出函数F的相关可微性质：定义3连续函数:nmFRR，如果每一个部分函数,1,...,ifim在点mxR连续可微，则称函数F在点mxR连续可微。函数F在点x的导数叫作F在点x的Jacobian矩阵，它的转置叫作F在点x的梯度。通常的表示为()mnFxR，()iijjfFxxx，()TFxJxFx。如果F在开区域nDR上每一点连续可微，则称函数F在开区域nDR连续可微，记作1FCD。用下面一个例子来具体说明这个定义。例1设22:FRR，112xfxex，22122fxxx。解：11112221121()22xffxxxxeJxffxxxxx下面我们研究单实值函数和向量值函数不同方面，对于实值函数存在中值定理，而对于向量值函数，中值定理不一定成立。也就是说，不一定存在nzR，使得()()()FxpFxJzp。直观上来看，尽管每个函数if满足()()Tiiiifxpfxfzp，但是点iz是不同的。以上面例子中的函数来考虑，11111110122zeez，也就是，11zee并且121z，这是不可能的，所以不存在nzR，使得1,1(0,0)()(1,1)TFFJz。尽管标准的中值定理是不可能的，我们给出一个近似的中值定理，主要是利用牛顿定理和线性积分的三角不等式。其中，单变量向量值函数的积分可以理解为对每一个部分函数进行黎曼积分。引理3：设:nmFRR在开凸集nDR上连续可微，对于,xxpD，有10()()()()xpxFxpFxJxtpdtFzdz。上式可以写成如下中值定理的形式：1100()()FxpFxJxtppdtJxtpdtp。因此，我们主要介绍了三种函数，从RR的函数、从nRR的函数以及从nmRR的函数的可微性质。3不动点迭代法把方程组()0Fx改写成与之等价的形式：(xGx)。其中nnGDRR：。若*xD满足**(xGx)，则称*x为函数(Gx)的不动点。因此(Gx)的不动点就是方程组()0Fx的解，求方程组()0Fx的解就转化为求函数的(Gx)的不动点。适当选取初始向量(0)xD，构成迭代公式(+1)()(),0,1,2,...kkxGxk迭代公式也称为求解方程组()0Fx的简单迭代法，又称不动点迭代法。(Gx)称为迭代函数。定理1（压缩映射原理）设nnGDRR：在闭域0DD上满足条件：（1）G把0D映入它自身，即00()GDD；（2）G在0D上是压缩映射，即存在常数(0,1)L，使对任意的0,xyD，()()GxGyLxy则以下结论成立：（1）对任取的(0)0xD，由迭代公式(+1)()()kkxGx，0,1,2,...k产生的序列()0kxD收敛于函数()Gx在区域0D内存在唯一的不动点*x；（2）成立误差估计式*()(1)(0)1kkLxxxxL，*()()(1)1kkkLxxxxL。证明：由于(0)0xD以及条件（1）可知序列()0kxD，又由条件（2）可得(1)()()()()(1)(1)(0)()()...kkkkkkkxxGxGxLxxLxx当1m时有()()()(1)1(1)(0)11mmkmkkikikiiixxxxLxx(1)(0)(1)(0)(1)11kmkLLLxxxxLL（1）因为01L，所以当k时，上式的最后一项是无穷小量，由Cauchy收敛原理，序列()kx在nR中收敛，又由0D是闭区域()kx的极限(*)0xD，由条件（2）知，()Gx在0D上连续，因而*(1)()*limlim()()kkkkxxGxGx，即*x是方程组()0Fx的解。设**0,xyD是()0Fx的两个不同的解，则有********()()xyGxGyLxyxy，这表明*x是()0Fx在内的唯一解。让m，得*()(1)(0)1kkLxxxxL()()()(1)()(1)11mmkmkkikiikkiixxxxLxx