非线性方程及方程组的数值解法ppt课件VIP

浙江大学研究生学位课程,.,1,第四章非线性方程和非性方程组的解法,4.1非线性方程的解法4.2非线性方程组的线性化解法4.3非线性方程组的极值求解法4.4最速下降法4.5共轭梯度法4.6牛顿过程及变度量法4.7直接法4.8方法的选择与总结,浙江大学研究生学位课程,.,2,.非线性方程的解法.非线性方程组的线性化解法牛顿迭代法.非线性方程组的极值求解法最速下降法|单纯形法共轭梯度法|Powell方法变尺度法|（可变矩阵方法）|直接法DFP方法|,浙江大学研究生学位课程,.,3,.1引言在科学研究中，常常会遇到非线性方程或非线性方程组的问题。例如解方程或一般的，我们记非线性方程为,浙江大学研究生学位课程,.,4,4.1非线性方程组的一般形式是：,其中fi（i=1,2,n）是n维实空间n上的实值函数。用向量形式表示：这里均是n维向量。为了方便计，还是用分别表示上述向量。简记为：,浙江大学研究生学位课程,.,5,4.1,c,a,d,c,a,d,b,图4.1非线性方程求根示意图,浙江大学研究生学位课程,.,6,4.1方程的解亦称方程的根或函数的零点。根可能是实数或复数。若则称为单根；若而，则称为k重根。常见的求解问题有两种：(1)要求定出在给定范围内的某个解。(2)要求定出在给定范围内的全部解。非线性问题，除少数情况外，一般不能不利用公式求解。而要采用某种迭代解法。即构造出一近似值序列逼近真解。,浙江大学研究生学位课程,.,7,4.1迭代过程的收敛性一般与初值的选取和方程的性态有关，某些解法仅与初值有关。收敛速度一般由迭代方法所决定，方程的性态也会起一些作用。本章主要介绍非线性方程组的解法，而方程的解法用较少的篇幅在4.2中扼要介绍。解非线性方程和方程组有很大区别。后者要困难得多。主要的区别在于一维情形可以找到一个根的范围，然后缩小，最终找到根。而多维情况则很难确定根的存在。直到你求得它的解。,浙江大学研究生学位课程,.,8,4.2非线性方程的解法,4.2.1二分法对于连续函数，如果在和处异号：则在内至少有一个根。,浙江大学研究生学位课程,.,9,4.2.1用图来表示这个过程：,y,x,a,b,a,b,a,b,确定根所在的范围a,b对有的函数也是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，在绝大部分场合是不困难的。对给定的函数也有确定范围的方法。,图4.2二分法方程求根,浙江大学研究生学位课程,.,10,a,b,b,a,x1,x1,x2,x3,d,c,f,c,4.2.1,图4.3寻找隔根区间示意1,浙江大学研究生学位课程,.,11,a,c,b,4.2.1,图4.4寻找隔根区间示意2,图4.5寻找隔根区间示意3,浙江大学研究生学位课程,.,12,例如，在a,b之间寻找f(x)可能有的根可以用等分试探法：,a,b,4.2.1,图4.6等分试探法寻找隔根区间示意,浙江大学研究生学位课程,.,13,用二分法求函数FUNC位于（x1,x2）之间的根，准确性为XACC。FUNCTIONRTBIS(FUNC,X1,X2,XACC)PARAMETER(JMAX=40)FMID=FUNC(X2)F=FUNC(X1)IF(F*FMID.GE.0.)PAUSE函数FUNC在x1,x2处不异号IF(F.LT.0.)THENRTIBIS=X1DX=X2-X1ELSERTBIS=X2DX=X1-X2ENDIFDO11J=1,JMAXDX=DX*0.5XMID=RTBIS+DXFMID=FUNC(XMID)IF(FMID.LE.0.)RTBIS=XMIDIF(ABS(DX).LT.XACC.OR.FMID.EQ.0.)RETURN11CONTINUEPAUSE迭代次数越界END,4.2.1,浙江大学研究生学位课程,.,14,FUNCTIONFF(X)FF=X*X+2.5*X+0.5+SIN(X)ENDPROGRAMROOTFINDEXTERNALFFX1=-1.0X2=0.0ROOT=RTBIS(FF,X1,X2,1.0E-5)PRINT*,方程在（-1，0）区间内有一个根，X=,ROOTSTOPEND,4.2.1,浙江大学研究生学位课程,.,15,4.2.2线性插值法（又称弦位法）,x,f(x),图4.7SecantMethod,浙江大学研究生学位课程,.,16,4.2.2,浙江大学研究生学位课程,.,17,4.2.2,浙江大学研究生学位课程,.,18,4.2.2,f(x),x,1,4,3,2,图4.8线性插值法求根示意,浙江大学研究生学位课程,.,19,4.2.2,f(x),x,1,3,4,5,图4.9线性插值法发散示例,浙江大学研究生学位课程,.,20,4.2.3Newton法,F(x),x,图4.10Newton法示意,浙江大学研究生学位课程,.,21,4.2.3,F(x),x,图4.11导数变化对算法的影响,浙江大学研究生学位课程,.,22,每次函数求值相当的收敛阶为：b.求fk有时工作量大，甚至不可能。(4)选用收敛域较大的方法（如二分法）先进行迭代，然后再用Newton法。组合方法。4.2.4二次插值法设f(x)=0的三个近似解及函数值构造二次函数g(y)使得：,浙江大学研究生学位课程,.,23,4.2.4,浙江大学研究生学位课程,.,24,4.2.4,F(x),x,g(x),f(x),图4.12二次插值法求根示意,浙江大学研究生学位课程,.,25,4.2.4(1)要有三个初始值(2)当。且收敛速度是1.84阶。（单根）二重根的收敛阶是1.23。(3)(4)发生超射、越界。,表4.1各种插值方法的比较,浙江大学研究生学位课程,.,26,4.2.5组合方法（BrentMethod）能否有一种方法综合上述方法的优点呢？Brent做了一些工作。Brent把二分法和二次插值法结合起来。（）一定收敛。（）收敛速度至少线性。（）在解附近足够光滑时，收敛速度将是1.84或1.23。有关多项式的求根还有一些特殊方法。,浙江大学研究生学位课程,.,27,4.3非线性方程组及牛顿法,非线性方程组的向量形式可表示为,解法：1.几乎不可能用直接法2.线性化，迭代逼近。牛顿法3.最优化，求函数极小值。下降法。例如，求的极小值点。最速下降法，共轭梯度法，变尺度方法。,浙江大学研究生学位课程,.,28,4.3.1牛顿法为方便计，用二维情形来讨论。,假定（4-6）的解,作线性函数（Taylor展开，取一阶精度）,浙江大学研究生学位课程,.,29,4.3.1在内用线性函数（4-7）代替非线性方程组(4-6)中的f1,f2,从而,如果在中矩阵（称Jacobi矩阵）,非奇异，则可解出。,浙江大学研究生学位课程,.,30,4.3.1,浙江大学研究生学位课程,.,31,4.3.1,浙江大学研究生学位课程,.,32,4.3.1,浙江大学研究生学位课程,.,33,4.3.2牛顿法的改进改进带松弛因子的牛顿迭代格式改善了对初始值近似程度的要求。,浙江大学研究生学位课程,.,34,4.3.2(4-10)中引入了松弛因子，有,浙江大学研究生学位课程,.,35,4.3.2,图4.13凸函数示例,浙江大学研究生学位课程,.,36,4.3.2,浙江大学研究生学位课程,.,37,4.3.2,图4.140.618法搜索极小点过程,浙江大学研究生学位课程,.,38,4.3.2(2)二次插值法求一维函数极小值：,图4.15二次插值法进行一维极小点搜索,浙江大学研究生学位课程,.,39,4.3.2改进.带阻尼因子的牛顿迭代格式克服了矩阵的奇异或病态。(4-10)中引入阻尼因子：,的选取可以在满足(4-12)的前提下取很大值。（）改善对初值的要求（）当时为牛顿法，收敛最快。（）为满足(4-12)，实际上需要多次试算，工作量大。改进3.修正牛顿法尽可能减少矩阵求逆次数。,浙江大学研究生学位课程,.,40,4.3.2一种简单的办法是每次使用同一个Jacobi矩阵的逆。,但大大影响收敛速度。另一种办法是若干次迭代后求一个矩阵逆：,它减少了矩阵求逆，又保证了收敛。换一个角度看，如果说它的求逆次数与牛顿法相同(k次)，则它的收敛阶为m+1。,浙江大学研究生学位课程,.,41,4.3.2,或,迭代格式(4-15)具有阶收敛速度。对一维情况，Newton法在几何上表现为m步迭代过程保持斜率f(xk)不变。如图4.16：,f(x),x,0,图4.16m=2的迭代效果,作为特例，取m=2:,浙江大学研究生学位课程,.,42,4.3.2非线性代数方程组求解问题1.Newton-Raphson迭代法2.极值化求解。问题的转化：,浙江大学研究生学位课程,.,43,4.4最速下降法,4.4.1极值化求解,的零极值点。求解(4-16)的极值点也是一个无约束的最优化问题。,浙江大学研究生学位课程,.,44,4.4.1求解最优化问题，通常采用下降法。下降法一般描述如下：,浙江大学研究生学位课程,.,45,4.4.1下降法的迭代步骤,浙江大学研究生学位课程,.,46,4.4.1最速下降法取因此,浙江大学研究生学位课程,.,47,4.4.1,等高线图：f(x)=Cif(x1,x2)=Ci,图4.17等高线,图4.18偏导数示意,浙江大学研究生学位课程,.,48,4.4.2讨论与改进优点：.程序简单，每步迭代计算量少，存储省。.对于不太好的初始点x0，往往也能收敛。缺点：最速下降法是名不符实的，一般来说，它只有线性的收敛速度。,浙江大学研究生学位课程,.,49,4.4.2,图4.19锯齿形搜索路径情况,浙江大学研究生学位课程,.,50,4.4.2,浙江大学研究生学位课程,.,51,4.4.2,浙江大学研究生学位课程,.,52,4.4.2一般来说，开始几步下降速度较快，但越靠近极小值点越慢。改进：,浙江大学研究生学位课程,.,53,4.4.2最速下降法算法框图：,停,停,图4.20最速下降法算法框图,浙江大学研究生学位课程,.,54,4.4.2,图4.21搜索路径示意,浙江大学研究生学位课程,.,55,4.5共轭梯度法（ConjugateGradientMethods）,4.5.1共轭方向,图4.22共轭方向,浙江大学研究生学位课程,.,56,4.5.1,浙江大学研究生学位课程,.,57,4.5.1,浙江大学研究生学位课程,.,58,4.5.1,图4.23二次函数的共轭方向,图4.24二次函数,浙江大学研究生学位课程,.,59,4.5.1,浙江大学研究生学位课程,.,60,4.5.1,浙江大学研究生学位课程,.,61,4.5.1,浙江大学研究生学位课程,.,62,4.5.2共轭梯度法ConjugateGradientMethod利用共轭方向，对二次型求极值问题可以得到n步收敛的结果。现在的问题是：1.如何构造n个共轭方向？2.对一般的非线性函数f(x)怎么办？3.由于舍入误差等影响，n次迭代不收敛时怎么办？,浙江大学研究生学位课程,.,63,4.5.2,浙江大学研究生学位课程,.,64,4.5.2,浙江大学研究生学位课程,.,65,4.5.10,浙江大学研究生学位课程,.,66,4.5.2,浙江大学研究生学位课程,.,67,4.5.2共轭梯度法是从梯度向量出发构造共轭向量。*由于误差积累等因素，对二次型，迭代n次也未能达到极小点。*F-R方法和P-R方法的区别在于它们对二次型是一样的。而对一般函数用P-R方法可能更合适。*共轭梯度法具有二次收敛速度。那么对一般的函数的共轭梯度法又是怎样的呢？,浙江大学研究生学位课程,.,68,4.5.2在极小值点附近进行二次逼近：,浙江大学研究生学位课程,.,69,4.5.2但是求导数f(xk)是必须的。另外，我们总假定f(x)在极值点附近性质足够好，满足各种要求。对一般函数f(x)，共轭梯度法(4-23)有限步收敛几乎是不可能的。如果迭代k步达到精度（kn）,则xk就作为x*的近似。当经过n步迭代仍不可能满足要求时，令再进行第二次循环。但是，实际计算中，不一定迭代k=n步才进行“重置”。,浙江大学研究生学位课程,.,70,4.5.2(1)在极小点附近是一个高度偏心的二次函数。则进行（m+n）次迭代（mn）就收敛了。而进行k次迭代（kn）就重置的话，有可能会不收敛。(2)在极小点附近或稍远处不是二次函数。此时称“扭曲”现象。则留有非二次函数的痕迹，故可能对收敛很有害。此时最好重置。,浙江大学研究生学位课程,.,71,4.5.2共轭梯度法ConjugateGradientMethods算法框图,图4.25共轭梯度法算法框图,浙江大学研究生学位课程,.,72,4.5.2(3)如何判别是高度偏心的二次函数还是扭曲的函数呢？启发性的办法是：对一般非二次函数，若x0离x*较远，则迭代n次不收敛时，就重置。但以后不再重置。对既高度偏心，又严重扭曲的函数，则经常性的重置是有好处的。,浙江大学研究生学位课程,.,73,4.5.2它在点（1,1）处有极小值4.其图象为：,图4.26函数等高线图,浙江大学研究生学位课程,.,74,4.5.2表4.3最速下降法计算结果,浙江大学研究生学位课程,.,75,4.5.2表4.4各种重置循环的共轭梯度法计算结果,浙江大学研究生学位课程,.,76,4.6牛顿过程及变度量法,4.6.1Newton-Raphson迭代把函数f(x)在第k次近似解xk附近进行Taylor展开：,浙江大学研究生学位课程,.,77,4.6.1,浙江大学研究生学位课程,.,78,4.6.1,浙江大学研究生学位课程,.,79,4.6.1,图4.27初值对Newton-Raphson方法的影响,浙江大学研究生学位课程,.,80,4.6.1,浙江大学研究生学位课程,.,81,然而这个方法的致命弱点是要计算Jk-1。4.2提供的办法，即迭代若干次修改一次Jk-1，是一种方案。但不是最好的。4.6.2变量的尺度变换为改变函数的偏心程度，从而改变极小化方法的收敛性质，采用变量替换是个很好的措施。,浙江大学研究生学位课程,.,82,4.6.2,浙江大学研究生学位课程,.,83,4.6.2,图4.28函数进行尺度变换的效果,浙江大学研究生学位课程,.,84,4.6.2尺度变换目的是把函数的偏心程度降到最低限度（它放大或缩小各个坐标），但并不能完全消除偏心问题。把尺度变换应用于各种算法，都有一定效果。一般地,浙江大学研究生学位课程,.,85,4.6.2即变换后的二次函数偏心率为，它是圆。它用最速下降法一步可以达到极小点。现在希望直接处理原来的函数，而定义一个算子。用它产生通过极小点的向量。考虑这样的：,从Newton-Raphson过程,浙江大学研究生学位课程,.,86,4.6.2,浙江大学研究生学位课程,.,87,4.6.3变尺度法DFP方法BFGS方法常用的度量是,浙江大学研究生学位课程,.,88,4.6.3,浙江大学研究生学位课程,.,89,4.6.3,浙江大学研究生学位课程,.,90,4.6.3,浙江大学研究生学位课程,.,91,4.6.3,浙江大学研究生学位课程,.,92,4.6.3,浙江大学研究生学位课程,.,93,4.6.3,浙江大学研究生学位课程,.,94,4.6.3,浙江大学研究生学位课程,.,95,4.6.3,浙江大学研究生学位课程,.,96,4.6.3变尺度法VariableMatrixMethods算法框图：,图4.29变尺度法算法框图,浙江大学研究生学位课程,.,97,4.6.3,浙江大学研究生学位课程,.,98,4.6.3,浙江大学研究生学位课程,.,99,4.6.3,浙江大学研究生学位课程,.,100,4.6.3,浙江大学研究生学位课程,.,101,4.6.3,表4.5各种方法比较,浙江大学研究生学位课程,.,102,4.7直接法（Simplex,Powell）,大量的目标函数是很复杂的，有时连解析式都没有，因而它的导数f(x)很难求，有时甚至不存在。4.7.1单纯形法SimplexMethodNelder-Mead(1965)提出这种简单的方法。它不需要求导数（梯度）对变元不多的情况是有效的。程序简单。,浙江大学研究生学位课程,.,103,4.7.1单纯形的思想是在n维空间的(n+1)个点(它们构成单纯形)上引进函数值比较。丢弃最坏的点并代之以新点。它们仍然构成单纯形。以此逐步逼近极小点。,浙江大学研究生学位课程,.,104,4.7.1,图4.30单纯形法中的反射,浙江大学研究生学位课程,.,105,4.7.1,图4.31单纯形法中的延伸,浙江大学研究生学位课程,.,106,4.7.1,浙江大学研究生学位课程,.,107,4.7.1,图4.32单纯形法中的收缩,浙江大学研究生学位课程,.,108,4.7.1e)缩小边长,图4.33单纯形法中的缩小边长,浙江大学研究生学位课程,.,109,4.7.1单纯形法（Simplex）框图：,解x*x0,图4.34单纯形法计算框图,浙江大学研究生学位课程,.,110,以上的迭代过程直到满足精度为止。精度：则x0作为所求的近似解。4.7.2Powelll方法Powelll方法是一种不依赖于目标函数梯度的直接搜索法。它逐步构造共轭方向并作为搜索方向，因此Powell方法也是一种共轭方向法。它的基本过程如下：,浙江大学研究生学位课程,.,111,4.7.2,图4.35Powell搜索路径,表4.6Powell方法解题过程,5.0,2.5,浙江大学研究生学位课程,.,112,4.7.2,浙江大学研究生学位课程,.,113,4.7.2Powell方法过程图示：,图4.36Powell方法计算过程图示,浙江大学研究生学位课程,.,114,4.7.2循环上面(1)-(3)，直至P0点函数值不再减小为止。当循环k次(kn)以后，un与它前面的k-1个向量un-k+1,un-1共轭。因此对于二次函数，理论上只要循环n次即可求得极小值。即具有二次收敛性。事实上，因为P0和Pn是沿相同方向un求得的极小值，所以PnP0与un方向共轭。,图4.37共轭方向,浙江大学研究生学位课程,.,115,4.7.2,图4.38Powell方法计算过程示意,浙江大学研究生学位课程,.,116,4.7.2,表4.7Powell方法第一次循环计算结果,浙江大学研究生学位课程,.,117,图4.39单纯形法求一维极值示意图（1）,4.7.2,浙江大学研究生学位课程,.,118,图4.40单纯形法求一维极值示意图（2）,4.7.2,浙江大学研究生学位课程,.,119,4.7.2但是，实际计算中对二次函数也不能保证n步内达到极小值点。因为每一循环都用Pn-P0“挤掉”u1,所以新的向量系ui(I=1,n)有可能线性相关，例如，某一循环中，如果1则这样，u2,u3,Pn-P0是线性相关的。当发生这种情况时，以后