不动点迭代法求解非线性方程组26032.pdf
不动点迭代法求解非线性方程组 摘要：一般非线性方程组可以写成()0F x 的形式，其中:nmF RR是定义在区域nDR上的向量函数。把方程组()0F x 改写成与之等价的形式：(xG x)。因此，求方程组()0F x 的解就转化为求函数的(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 function:nmF RRis defined on the region nDR.Transform the equations()0F x into its equivalent form:(xG x).Therefore,we can get the solution of()0F x 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元非线性方程组的一般形式为 11221212(,.,)0(,.,)0.(,.,)0nnmnf x xxfx xxfx xx （1）其中，1,2,.,if in是定义在nDR上的n元实值函数，且if中至少有一个是非线性函数。令12.nxxxx，12().mfxfxF xfx，则方程组可以表示为()F x （2）其中:nmF RR是定义在区域nDR上的向量函数。若存在*xD，使*()F x，则称*x是方程组（1）或（2）的解。把方程组()0F x 改写成与之等价的形式：(xG x)其中nnGDRR：。若*xD满足*(xG x)，则称*x为函数(G x)的不动点。因此(G x)的不动点就是方程组()0F x 的解，求方程组()0F x 的解就转化为求函数的(G x)的不动点。适当选取初始向量(0)xD，构成迭代公式(+1)()(),0,1,2,.kkxG xk迭代公式也称为求解方程组()0F x 的简单迭代法，又称不动点迭代法。(G x)称为迭代函数。由于F是多变量函数，所以我们先考虑多变量函数的微积分性质。2 多变量函数的微积分性质 在之前我们已经学习过很多关于单变量函数的微积分的性质，由于解非线性方程组经常用到的是多变量函数的相关性质，因此我们考虑多变量函数的微积分性质。相对于单变量函数的微积分的性质，多变量函数的微积分性质一些是类似的，一些是不同的。相对于单变量函数的可微的定义，我们事先给出多变量函数的可微定义。函数:,1nfRR n 的微积分性质 设函数多变量函数:,1nfRR n。我们首先考虑当f是连续的函数的情况，如果f关于n个变量的偏导数都存在并且连续，把这n个偏导数组成一个n维向量，则我们把这个n维向量称作多变量函数f的梯度。定义 1：连续可微函数:nfRR，如果 ifxx，1,.,in；存在并且连续，则称函数f在点nxR上连续可微，并且称 1,.,Tnfff xxxxx为函数f在点nxR的梯度。如果函数f在开区域nDR上每一点连续可微，则称函数f在开区域nDR连续可微，记作 1fCD。下面我们给出关于多变量函数f的梯度的一些性质：引理 1 设:nfRR 在开凸集nDR连续可微，则对于xD以及任意一个非零扰 动npR，则 函 数f在 点x在 方 向p上 的 方 向 导 数 定 义 为 0limfxpfxfxp存 在 并 且 等 于 Tf xp。对 于,x xpD，10()()xpTxfxpf xfxtppdtf xfz dz，并且存在,zx xp使得，()Tf xpf xf zp。下面我们给我这个引理的证明过程，主要思想是把多变量函数转化为单变量函数，然后利用我们已知的单变量函数微积分的性质来证明多变量函数微积分的性质。证明：首先在点x到点xp的连线上对函数f进行参数化，转变成单变量函数g。定义()x txtp，:,()()g RR g tf xtp。由链式法则，对于01，1niiif x tdx tdgxdtx tdt 1niiifxpx f xp p。因 为 00()()lim(0)tg tgf xxgpt，所 以 令0，我 们 就 可 以 得 到 Tfxf xpp。由单变量函数的牛顿定理我们可知，10(1)(0)()ggg t dt。根据前面对函数g的定义，上式也可以写成10()Tf xpf xf xtppdt。这就得到我们所要的证明。最后，由单变量函数的积分中值定理 10(),0,1g t dtg，根据函数g的定义，我们可以写成()Tf xpf xf xpp，0,1。对10Tf xtppdt进行变量替换zxtp，可得 10Tx pxf xtppdtf z dz，从而得证。函数:nfRR 的微积分性质 下面给出多变量函数二次可微的定义，并进一步给出函数f的 Hessian 矩阵的定义。定义 2：连续可微函数:nfRR，如果 2ijfxx x，1,i jn存在并且连续，则称函数:nfRR 在点x上二次连续可微；定义一个nn矩阵，其中第,i j元素为 22()ijijff xxx x，1,i jn，则称这个矩阵为函数f的 Hessian 矩阵。如果函数f在开区域nDR上每一点连续可微，则称函数f在开区域nDR连续可微，记作 2fCD。类似的我们给出关于多变量函数f的二阶连续可微的一个引理。引理 2：设函数:nfRR 在开凸集nDR二次连续可微，则对于xD以及任意 一 个 非 零 扰 动npR，则 函 数f在 点x在 方 向p上 的 二 阶 方 向 导 数 220()limffxpxfppxp存 在，并 且 等 于2()Tpf x p。对 于 对 于,x xpD，存在,zx xp使得21()()()2TTf xpf xf xppf z p。定理的证明过程与一阶连续可微情况的证明过程类似。从 Hessian 矩阵的定义可知，只要函数f是二次连续可微的，那么 Hessian 矩阵是对称的。函数:nmF RR的微积分性质 我们进一步考虑更复杂的情况，也就是从nR空间到mR空间的函数，设函数:nmF RR，具体可以写成 112112(,.,).().(,.,)()nmnmf x xxfxF xfx xxfx。其中，非线性联立方程问题是mn的情况；非线性最小二乘问题是mn的情况。下面我们给出函数F的相关可微性质：定义 3 连续函数:nmF RR，如果每一个部分函数,1,.,if im在点mxR连续可微，则称函数F在点mxR连续可微。函数F在点x的导数叫作F在点x的 Jacobian 矩阵，它的 转 置叫 作F在 点x的 梯 度。通常 的 表示 为()m nF xR，()iijjfF xxx，()TF xJ xF x。如果F在开区域nDR上每一点连续可微，则称函数F在开区域nDR连续可微，记作 1FCD。用下面一个例子来具体说明这个定义。例 1 设22:F RR，112xfxex，22122fxxx。解：11112221121()22xffxxxxeJ xffxxxxx 下面我们研究单实值函数和向量值函数不同方面，对于实值函数存在中值定理，而对于向 量 值 函 数，中 值 定 理 不 一 定 成 立。也 就 是 说，不 一 定 存 在nzR，使 得()()()F xpF xJ z p。直 观 上 来 看，尽 管 每 个 函 数if满 足()()Tiiiif xpf xfzp，但是点iz是不同的。以上面例子中的函数来考虑，11111110122zeez ，也就是，11zee并且121z，这是不可能的，所以 不存在nzR，使得 1,1(0,0)()(1,1)TFFJ z。尽管标准的中值定理是不可能的，我们给出一个近似的中值定理，主要是利用牛顿定理和线性积分的三角不等式。其中，单变量向量值函数的积分可以理解为对每一个部分函数进行黎曼积分。引 理 3：设:nmF RR在 开 凸 集nDR上 连 续 可 微，对 于,x xpD，有10()()()()xpxF xpF xJ xtp dtF z dz。上式可以写成如下中值定理的形式：1100()()F xpF xJ xtp pdtJ xtp dt p。因此，我们主要介绍了三种函数，从RR的函数、从nRR的函数以及从nmRR的函数的可微性质。3 不动点迭代法 把方程组()0F x 改写成与之等价的形式：(xG x)。其中nnGDRR：。若*xD满足*(xG x)，则称*x为函数(G x)的不动点。因此(G x)的不动点就是方程组()0F x 的解，求方程组()0F x 的解就转化为求函数的(G x)的不动点。适当选取初始向量(0)xD，构成迭代公式(+1)()(),0,1,2,.kkxG xk迭代公式也称为求解方程组()0F x 的简单迭代法，又称不动点迭代法。(G x)称为迭代函数。定理 1（压缩映射原理）设nnGDRR：在闭域0DD上满足条件：（1）G把0D映入它自身，即00()G DD；（2）G在0D上是压缩映射，即存在常数(0,1)L，使对任意的0,x yD，()()G xG yL xy 则以下结论成立：（1）对任取的(0)0 xD，由迭代公式(+1)()()kkxG x，0,1,2,.k 产生的序列()0kxD 收敛于函数()G x在区域0D内存在唯一的不动点*x；（2）成立误差估计式*()(1)(0)1kkLxxxxL，*()()(1)1kkkLxxxxL。证明：由于(0)0 xD以及条件（1）可知序列()0kxD，又由条件（2）可得 (1)()()()()(1)(1)(0)()().kkkkkkkxxG xG xL xxLxx 当1m 时有()()()(1)1(1)(0)11mmk mkk ik ik iiixxxxLxx (1)(0)(1)(0)(1)11kmkLLLxxxxLL （1）因为01L，所以当k 时，上式的最后一项是无穷小量，由 Cauchy 收敛原理，序列()kx在nR中收敛，又由0D是闭区域()kx的极限(*)0 xD，由条件（2）知，()G x在0D上连续，因而*(1)()*limlim()()kkkkxxG xG x，即*x是方程组()0F x 的解。设*0,xyD是()0F x 的两个不同的解，则有*()()xyG xG yL xyxy，这表明*x是()0F x 在内的唯一解。让m ，得*()(1)(0)1kkLxxxxL()()()(1)()(1)11mmk mkk ik iikkiixxxxL xx ()(1)()(1)(1)11mkkkkLLLxxxxLL 说明：（1）简单迭代法的精度控制与终止条件()(1)()kkkxxx；（2）由*(+1)*()kkxxLxx知简单迭代法是线性收敛的；（3）对线性方程组迭代函数()G xBxd，有=1LB；定理 2（局部收敛定理）设*int()nnGDRRxD：,是方程组()0 F x 的解，在*x可微。若()G x谱半径()1G x，则存在开球*0,0Dx xx，对任取的(0)0 xD，由迭代公式(+1)()()kkxG x，0,1,2.k 产生序列()0kxD收敛于*x。下面我们给出一个例子，通过来求函数(G x)的不动点来解非线性方程组。例 2 用简单迭代法求解以下方程 1122123cossin04sincos0 xxxxxx 要求满足精度()(1)12()()10kkkxxe kx 解：设12xxx，12121(cossin)3()1(sincos)4xxG xxx 则方程组可以改写成()xG x，并且对于任意的22,xRyR，112212221(coscossinsin)3()()1(sinsincoscos)4xyxyG xG yxyxy 712A xyAxyxy 其中，121211sincos3311cossin44A，712A 因此，任取初始向量(0)xR，简单迭代法产生序列()kx收敛于原方程组的唯一解。迭代公式(1)()()112(1)()()2121=cossin31sincos4kkkkkkxxxxxx 计算结果：k 1kx 2kx e k 0 1 2 0.4 26 27 28 参考文献：1 李庆杨,关治,白峰杉.数值计算原理M.清华大学出版社.2000;2 李庆杨，王能超，易大义.数值分析M.武汉：华中理工大学出版社，1986.3 黄象鼎，曾钟钢，马亚男.非线性数值分析的理论与方法M.武汉：武汉大学出版社，2004.4 曾金平，李湘良.数值计算方法M.长沙：湖南大学出版社，2004.5 马吕凤，林伟川.现代数值计算方法M.北京：科学教育出版社，2008.6 王德人.非线性方程组解法与最优化方法。人民教育出版社，1979 7 林成森.数值计算方法（第二版）M.北京：科学出版社，2005.
