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