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