关于非线性方程组Newton解法的研究综述

1、关于非线性方程组的Newton解法的研究综述关于非线性方程组Newton解法的研究综述作者：谢玉婧 王培一、研究现状非线性代数方程组求解是一个基本而又重要的问题，这是因为在工程实践、经济学、信息安全和动力学等方面有大量的实际问题最终转化为代数方程组。这一类问题，我们不可能找到它们的解析解，数值解是目前主要的研究方向。数值解法较为成熟，速度快，但其往往只能求出部分解，而且通常只能求出近似解。它一般用于解决大型问题。Newton法是数值方法求解非线性方程组的一种基本方法。根据其特点和不足，对Newton法进行简化和修正。并且与其他数值解法(如区间法)相结合，形成其他更加完善的求解非线性方程组的方法

2、。二、问题的提出n个变量n个方程的非线性方程组, 其一般形式如下:f1(x1,x2,L,xn)=0f(x,x,L,x)=0n 212 (1) Mfn(x1,x2,L,xn)=0式(1)中fi(x1,x2Lxn)(i=1,2,L,n)是定义在n维欧式空间Rn中开域D上的实值函数。若用向量记,令:x1x2X=Mxnf1(x1,x2L,xn)=0f1(X)f(x,xL,x)=0f(X)n =2,F(X)=212MML=f(x,x,x)0f(X)nnn12则方程组(1)也可以表示为:F(X)=0 (2) 其中：XRn,F:RnR0,F(X)Rn，Rn为赋值空间。非线性数值方法种类较多，最常用的是New

3、ton迭代法。求解非线性方程组的Newton法是一个最基本而且十分重要的方法,目前使用的很多有效的迭代法关于非线性方程组的Newton解法的研究综述都是以Newton法为基础,或由它派生而来。下面首先介绍几种Newton法及其原理，然后使用Mathwmatica编写求解程序，最后通过一个计算实例说明几种牛顿法的差异。为方便起见记： F(X)=f1(X),L,fn(X)T,X=x1,LxnT以及雅可比矩阵:f1(X)x1f2(X)F(X)=x1fn(X)x1f1(X)f1(X)Lx2xnf2(X)f2(X)Lx2xn Mfn(X)fn(X)Lx2xn三、各种方法原理及math程序1、Newton

4、法(1) 方法原理简述像单个方程的Newton迭代法一样，采用逐次线性化的方法构造方程(1)的Newton迭代法。在某个近似解Xk处，将向量函数F(X)作Taylor展开，则有：F(X)F(Xk)+F(Xk)(Xk+1Xk)从而得到(2)的近似方程F(Xk)+F(Xk)(Xk+1Xk)=0令Xk=Xk+1XK，将Newton法的迭代公式改写为:Xk+1=Xk+Xk k=0,1,2,L (3) F(Xk)(Xk)=F(Xk)每一步迭代均需解Newdon方程组:F(Xk)(Xk)=F(Xk)这是一个线性方程组,可用高斯消去法求解。 通常可用:Xk<或F(Xk)<作为Newton法的终止

5、迭代准则,其中，为预先给定的精度要求,有时也可用关于非线性方程组的Newton解法的研究综述预先确定的最大迭代次数M作为终止迭代条件。(2) math程序及程序说明Clearx,y,zf1x_,y_,z_:=4x+y2+Exp-2*z-8.03;f2x_,y_,z_:=Sinx-y*(z+10)+3.01;f3x_,y_,z_:=-2(x+0.3)2-Cosy+10z+3Pi;F1x_,y_,z_:=TableDfix,y,z,x,Dfix,y,z,y,Dfix,y,z,z,i,1,3; F1x,y,z;MatrixForm%I1=IdentityMatrix3;DD=DiagonalMatr

6、ixF1x,y,z1,1,F1x,y,z2,2,F1x,y,z3,3/N;L=-0,0,0,F1x,y,z2,1,0,0,F1x,y,z3,1,F1x,y,z3,2,0/N; DDLN=InverseDD-L/N;G=I1-DDLN.F1x,y,z;MatrixForm%;Fx_,y_,z_:=Tablefix,y,z,i,1,3;f=DDLN.(-Fx,y,z/N);x,y,z=2,2,2;Fork=1,k<=10,k+,tx,ty,tz=1,1,1;Dotx1,ty1,tz1=G.tx,ty,tz+f/N;tx,ty,tz=tx1,ty1,tz1,i,1,10;x,y,z=x+tx1

7、,y+ty1,z+tz1;h=MaxAbstx1,Absty1,Abstz1/N;Printk," ",x," ",y," ",z," ",h程序2-6行是在定义雅克比矩阵(方程组的维数及各个方程的具体形式以后面出现的例题为参考)，7-14行是高斯法求解方程组的矩阵分解准备，15-22行是程序的主体部分，是一个循环，是对方程组(3)的数学程序语言翻译。在这个循环中又嵌套了一个循环(18-19行)，是高斯法求解F(Xk)(Xk)=F(Xk)的具体形式，求出Xk。其中h是误差控制(Xk<)。2、简化的Newdon

8、法关于非线性方程组的Newton解法的研究综述(1) 方法原理简述尽管Newton法具有较高的收敛速度,但在每一步迭代中,要计算n个函数值f以及n2个导数值f形成雅可比矩阵F(Xk)而且要求F(Xk)的逆矩阵或者解一个n阶线性方程组,计算量很大。为了减少计算量。在上述Newton法中，对于一切k=0,1,2,L，取F(Xk)为F(X0)，于是迭代公式便修正成为:Xk+1=Xk+Xk k=0,1,2,L (4) F(X0)(Xk)=F(Xk)式(3)即为简化的Newton法。该方法能使计算量大为减少,但却大大降低了收敛速度。简化的Newton法的算法与Newton法的算法区别就在于只由给定的初始

9、近似值计算一次F(X)，以后在每一次迭代过程中不再计算F(X), 保持初始计算值。(2) math程序及程序说明Clearx,y,zf1x_,y_,z_:=4x+y2+Exp-2*z-8.03;f2x_,y_,z_:=Sinx-y*(z+10)+3.01;f3x_,y_,z_:=-2(x+0.3)2-Cosy+10z+3Pi;F1x_,y_,z_:=TableDfix,y,z,x,Dfix,y,z,y,Dfix,y,z,z,i,1,3; F1x,y,z;N%/.x->2,6;N%/.y->2,6;F0=N%/.z->2,6;MatrixForm%I1=IdentityMatr

10、ix3;DD=DiagonalMatrixF01,1,F02,2,F03,3/N;L=-0,0,0,F02,1,0,0,F03,1,F03,2,0/N;DDLN=InverseDD-L/N;G=I1-DDLN.F0;MatrixForm%;Fx_,y_,z_:=Tablefix,y,z,i,1,3;f=DDLN.(-Fx,y,z/N);x,y,z=2,2,2;关于非线性方程组的Newton解法的研究综述Fork=1,k<=40,k+,tx,ty,tz=1,1,1;Dotx1,ty1,tz1=G.tx,ty,tz+f/N;tx,ty,tz=tx1,ty1,tz1,k,1,10;x,y,z=

11、x+tx1,y+ty1,z+tz1;h=MaxAbstx1,Absty1,Abstz1/N;Printk," ",x," ",y," ",z," ",h 与上面Newton法类似，区别在于整个工程中只计算了一次雅克比矩阵，2-10行是在计算F(X0)。3、修正的Newdon法(1) 方法原理简述从以上两种方法可以看出, 它们各有利弊,如果吸取法收敛快与简化的Newton法工作量省的优点, 把m步简化的Newton步合并成一次Newton步。则可以得到下列迭代程序: Xk,j=Xk,j1f(Xk)1f(Xk,j1)

12、(5)Xk+1=Xk,m式中：j=1,2,L,m，k=0,1,2,L，该式称为修正的Newton法。在实际应用中,较为常用的是m=2的情形。此时,(5)式也可以简化为: Xk,0=Xkxk+1=xkf(Xk)1f(Xk)+fXk-f(Xk)1f(Xk),k=0,1,2,L (6) 下面给出的程序是m取一般值时的情形。(2) math程序及程序说明Clearx,y,zx0,y0,z0=2,2,2/N;f1x_,y_,z_:=4x+y2+Exp-2*z-8.03;f2x_,y_,z_:=Sinx-y*(z+10)+3.01;f3x_,y_,z_:=-2(x+0.3)2-Cosy+10z+3Pi;F

13、1x_,y_,z_:=TableDfix,y,z,x,Dfix,y,z,y,Dfix,y,z,z,i,1,3; F1x,y,z;关于非线性方程组的Newton解法的研究综述Form=1,m<=2,m+,ClearF1;NF1x,y,z/.x->x0,8;N%/.y->y0,8;F0=N%/.z->z0,8;MatrixForm%;I1=IdentityMatrix3;DD=DiagonalMatrixF01,1,F02,2,F03,3/N;L=-0,0,0,F02,1,0,0,F03,1,F03,2,0/N;DDLN=InverseDD-L/N;G=I1-DDLN.F0

14、;MatrixForm%;Fx_,y_,z_:=Tablefix,y,z,i,1,3;f=DDLN.(-Fx,y,z/N);x,y,z=2,2,2;Fork=1,k<=10,k+,tx,ty,tz=1,1,1;Dotx1,ty1,tz1=G.tx,ty,tz+f/N;tx,ty,tz=tx1,ty1,tz1,k,1,10;x,y,z=x+tx1,y+ty1,z+tz1;h=MaxAbstx1,Absty1,Abstz1/N;x0,y0,z0=x,y,z;Printx," ",y," ",z," ",h该程序是随前两种程序的结合和

15、改进。Newton法收敛速度较快，但是计算量大，计算时间较长。其主要原因是每次高斯法求解方程组都要计算雅克比矩阵，而简单Newton法避免了这个问题。这也是两者可以结合的主要契合点。程序中m是Newton步中简单步的子步数。即通过m控制雅克比矩阵计算次数的(最外层For循环)。整个程序相当于运行了m个简单Newton步。每一个简单步的结果作为下一次运行的X0。四、应用实例关于非线性方程组的Newton解法的研究综述4x1+x2+e2x38.03=0下面以求解非线性方程组:sinx1x2(x3+10)+3.01=0为例，用2-2(x1+0.3)cosx2+10x3+3=0上面的Newton法程序

16、，简化的Newton法程序和修正的Newton法程序分别求得不同结果，并进行分析比较。精度要求<10-10，取初值X0=2,2,2T。Newton法结果如下： -0.0585813 -0.0687513 -0.0640291 0.678301 0.114619 0.00472220.425532 0.403821 0.4029350.402938 0.402938-0.0640681 -0.06406816.40322×10-10 2.33108×10-12可见，迭代7次可以达到精度要求。 简化Newton法结果如下：0.19931 0.0354587 -0.0217

17、450.50366 0.163851 0.0631420.453904 0.428501 0.4139110.404016 0.403468-0.0612167 -0.06303470.00659764 0.002847060.403055 0.403055-0.0643795 -0.06437951.46445×10-9 6.24478×10-10关于非线性方程组的Newton解法的研究综述可见，迭代26次才能达到精度要求，但运算速度较快。修正的Newton法结果如下： -0.0642561 -0.0640681 0.000208382 6.14578×10-1

18、0 0.402961 0.402938可见，只迭代两次即达到精度要求，且速度较快。五、各方法比较与不足通过分析Newton 法、简化的Newton 法和修正Newton 法的原理,并通过对算例的分析比较,我们可知:Newton 法(3)式具有较高的收敛速度,但计算量大,在每一步迭代中,要计算n个函数值f以及n2个导数值f形成雅可比矩阵F(Xk),而且要求F(Xk)的逆阵或者解一个n阶线性方程组;简化的Newton 法(4)式,它用迭代初值X0来计算F(Xk),并在每个迭代步中保持不变,它能使每步迭代过程的计算量大为减少,但大大降低了收敛速度;修正Newton 法(5)与Newton 法(3)相比,在每步迭代过程中增加计算n个函数值,并不增加求逆次数,然而收敛速度提高了.然而，与一般的数值解法类似，修正的Newton法仍然是往往只能求出不分解，而且也只能求得精度较高的近似解，比较适合解决大型问题。六、国