ch7非线性方程求根

河海大学理学院数值分析河海大学理学院数值分析 河海大学理学院数值分析第第7 7章章 非线性方程求根非线性方程求根7 71 1 方程求根与二分法方程求根与二分法 1.1.引言引言设设 若有若有 使使 则称则称 是方程是方程 的的根根或或 的的零点零点。若若 ，当当 时时,称称 为方程为方程 的的单根单根，当，当 时时,称称 为方程为方程 的的m m重根重根或或 的的m m重零点重零点。baCxf,*x0*xf*x 0 xf xf 0*,*xgxgxxxfm,2,1m1m*x 0 xf1m*x 0 xf xf河海大学理学院数值分析 定理定理 若 有m阶导数，则 是 的 m重根的充分必要条件是 ，。xf*x 0 xf0*)1(xfxfxfm0*)(xfm证明:依据泰勒中值定理知.泰勒公式：mmmmxxmfxxmxfxxxfxxxfxfxf*!*!1*!2*1)1(2 河海大学理学院数值分析2.2.二分法二分法 零点定理零点定理 若 又 则 。依据零点定理对区间 逐次分半进行根的搜索，这就是二分法二分法。baCxf,0bfaf 0,fba使ba,，；河海大学理学院数值分析 具体作法如下：0af 0bf20bax设，令 ，00 xf0 x（1）若，则 是根；00 xfbbxa101,（2）若，令 ；00 xfaaxb101,（3）若，令 。11,ba1x,22ba kx对再二分且同样的讨论，得和一半的区间将此过程继续下去，得 则*limxxkk。河海大学理学院数值分析 定理定理 设 又 则由 二分法得到的 收敛于根 ，且有根的 近似值 误差估计式：。baCxf,0bfaf kx*xkx,2,12*kabxxkk河海大学理学院数值分析7 72 2 迭代法及收敛性迭代法及收敛性1.1.不动点迭代法的概念不动点迭代法的概念 将 改写成等价形式 。若有 使 ,则将 称为 的不动点不动点。求 的根 ,也就是找 的不动点。设选择 （初始近似值）并构造 （2.2）计算公式（2.2）称为迭代格式迭代格式,称为迭迭 代函数代函数,得到的 称为迭代序列迭代序列,用公式（2.2）逐步代入求近似解的方法称为迭代法迭代法(或 不动点迭代法不动点迭代法)。0 xf xx*x*xx*x x 0 xf*x x,2,1,01kxxkk0 x x kx河海大学理学院数值分析 若 ,则称迭代收敛迭代收敛,否则,就称迭代迭代 发散发散。若 ,迭代都收敛，则称迭 代全局收敛全局收敛。*limxxkkbax,0河海大学理学院数值分析 压缩映象原理压缩映象原理 设 若 (1)当 时，有 ，(2)使 有 则 使 。baCx,bax,bax,10LL且bayx,yxLyxbax,*)(唯一*xx证明 河海大学理学院数值分析 压缩映象原理证明压缩映象原理证明 baCxxxF,0aFax*0bFbx*0bbaabFaFbax,*0*xF 证存在性。令（1），则（2），则（3），据零点定理，使。；0 x0*xx 000*0 xxLxxxx10 L证唯一性。若另有是不动点，这与矛盾。证毕河海大学理学院数值分析2.2.全局收敛全局收敛 全局收敛性定理全局收敛性定理 设 若 时，有 ;，使 有 迭代公式 则 ,迭代法收敛，且有以下估计式 baCx,bax,bax,10LL且bayx,yxLyx ,2,1,01kxxkkbax,00*xxLxxkk11*kkkxxLLxx011*xxLLxxkk（1）（2）（3）河海大学理学院数值分析*xx1kkxx1*kkxxxx 11kkkkxxxx证明 ，1*kkxxxx221*kkxxLxxL0*xxLk证（1）0*xx 又由于 10 L*limxxkk是固定数，而，所以，迭代收敛。11*kkkkxxxxxx1*kkxxxxkxxL*1证（2）所以，河海大学理学院数值分析 注：全局收敛性定理中条件(2)换成 ,，定理结论仍成立。bax,1Lxkxx*kkxxL111111kkxxL11kkxxLLkxx*2121kkxxLL011xxLLk证（3）因而 证毕 yxyx yxLyxyx据拉格朗日定理，河海大学理学院数值分析3 3局部收敛和局部收敛和p p阶收敛阶收敛 定义定义 若 是 的不动点，,使 ,由迭代公式 产生的序列 ，有 ，则称迭代局部收敛局部收敛。*x x0*,*0 xxxkkxx1 kx*limxxkk,2,1,0k 局部收敛性定理局部收敛性定理 是 的不动点，在 连续，迭代公式 ，则(1)当 时，迭代局部收敛；(2)当 时，迭代发散。*x x x*x kkxx11*x1*x河海大学理学院数值分析*lim*xxxx0证明 由于 存在，故,当*,*xxx x x时，存在，连续。且由 1*x10LL且极限的保号性，当 时，1Lx1*x 1 x使；当 时，有。*xxxxxx*xx满足(2);当 1*x时，满足（1）；据全局收敛定理,在*,*xx上收敛。当 1*x时，*1xxxxkk*1xxk*1xxk*0 xx 所以，*limxxkk，迭代不收敛。证毕河海大学理学院数值分析 定义定义 设 ，若 ，则称迭代过程是p p阶收敛阶收敛。特别地，p=1称为线性收敛线性收敛，p1称为超线性收超线性收敛敛，p=2称为平方收敛平方收敛。*xxekk0lim1Ceepkkk 定理定理 若 ,则迭代过程是p阶收敛。0*)1(xxxp0*)(xp河海大学理学院数值分析 证明 kkxx1*x*xxxk1)1(*!1*pkpxxpx pkpxxp*!)(pkpxxpx*!*)(*11xxekk pkpep!)(0!*lim1pxeeppkkk证毕河海大学理学院数值分析 例例 设方程 ，根 ,将 方程改写成下列等价形式：（1）；（2）；（3）。试建立相应的迭代格式，并分析它们的收敛性，然后选取一个格式作为计算公式。013 xx32472.1*x31xx13 xx13123xxxxx311kkxx 311xx131kkxx 132 xx131231kkkkkxxxxx 131213123233xxxxxxx解解（1），；，；，。（2）（3）河海大学理学院数值分析 321131xx1132.131*321x，收敛；223xx 132.13*22x，不收敛；22331316xxxxx0*3x，收敛。因为，*13xx，取 kkxx31作为计算公式。解毕河海大学理学院数值分析7 74 4 牛顿法（切线法）牛顿法（切线法）其牛顿迭代函数牛顿迭代函数 由 解出 得。kkkkxfxfxx1 xfxfxxxx 0令kkxxxf xfkxf河海大学理学院数值分析 例 设用牛顿迭代法求方程 2lnxx,2内的根，在 取 30 x，要求610。解 2ln xxxf xxf11 012 xxf1ln11kkkkxxxx，3210k1461932.31461934.31479184.33kx因为,672310102 xx所以,1461932.3*3 xx 解毕河海大学理学院数值分析1 1牛顿迭代法及其收敛性牛顿迭代法及其收敛性 例例 设 ,写出用牛顿法求 的迭代计算公式，并分析收敛性。0CC解解 令,xC,2Cx ，Cxxf2,1,022221kxCxxCxxxkkkkkk取 0,00kxx则kkkkkxxCCxxCx222221022kkxCx所以，Cxk102,21kkkkxxCxx河海大学理学院数值分析 单减有下界，kxnnxlim 存在，于是，对本题计算公 式取极限，有*limxxnn，说明，本题计算公式在,00 x上全局收敛。解毕河海大学理学院数值分析 牛顿迭代函数设 是 的单根，即 ,。,xfxfxx 故，牛顿法牛顿法在 邻近至少是至少是2 2阶收敛阶收敛的。*x xf0*xf0*xf。2xfxfxfx 0*x*x河海大学理学院数值分析2 2简化牛顿法简化牛顿法 特别 即牛顿法。kkkxCfxx1kxfC1河海大学理学院数值分析7 75 5 弦截法与抛物线法弦截法与抛物线法3 3弦截法弦截法 取 是1步迭代法，1阶收敛 00 xxxfxfxfkkk 001xfxfxxxfxxkkkkk河海大学理学院数值分析4 4快速弦截法快速弦截法 取 是2步迭代法，1618阶收敛11kkkkkxxxfxfxf 111kkkkkkkxfxfxxxfxx河海大学理学院数值分析5 5抛物线法（密勒法）抛物线法（密勒法）若用三点 ,连接成抛物线取与 轴上靠近 的交点当作 的近似值 。该法称作抛物线法抛物线法或或密勒密勒法法.计算公式为计算公式为2,2kkxfx1,1kkxfx kkxfx,xkx*x 212,4sgn2kkkkkxxxfxfxfkkxx11kx 是3步迭代法，1840阶收敛.河海大学理学院数值分析 证明 二次牛顿插值 kkkkxxxxfxfxN12,121,kkkkkxxxxxxxfkkxxxf221,kkkkxxxxxf1211,kkkkkkkxxxxxfxxf其中 令 02xNx 解出 21212,2,4kkkkkkkkxxxfxxxfxfxx.sgn1 号取与符号相同，即 河海大学理学院数值分析6 6牛顿下山法（全局收敛）牛顿下山法（全局收敛）0 xf设*x xfxfmin*0的解，则若视 xf为 xf在x处的高度，则*x是山谷的最低点，若 kx有 kkxfxf1，则 kx是一个下山序列,若 baCxf,2，且 0 xf 0 xf xfxfxftxf，取 1,0kt，例取 121kkt kkkkkxfxftxx1河海大学理学院数值分析7 7重根情形重根情形 复习定理复习定理 若 有k阶导数，则 是 的k重根的充分必要条件是 ，。xf*x 0 xf0*)1(xfxfxfk0*)(xfk kkxxkfxf*!1)(12)(*!1kkxxkfxf 23)(*!2 kkxxkfxf河海大学理学院数值分析 牛顿迭代函数 xfxfxx 21)(*kkkffxxx*xx*xx，收敛。2xfxfxfx 2231)(1kkkfkffk*xx 3,2,1*ixi 1111lim*kkkxxx，所以，收敛是1阶收敛。河海大学理学院数值分析(1)(1)已知重数已知重数k k 修改修改牛顿迭代函数 xfxkfxx 0lim*xxx，收敛是2阶收敛。kkkkxfxkfxx1河海大学理学院数值分析2.2.重数重数k k未知未知 设 迭代函数 xfxfxu*x xu，则是的单零点.xuxuxx xfxfxfxfxfx 2 收敛是2阶收敛。kkkkkkkxfxfxfxfxfxx 21河海大学理学院数值分析7 73 3 迭代收敛的加速方法迭代收敛的加速方法1.1.埃特金加速法埃特金加速法设 kkxx1*limxxkk kx,是1阶收敛，且有*xxekk0lim1CeekkkkkkeCe1CCk112kkkeCeCCk1kkCC1 ,相除得：kkkkeeee112即：*112xxxxxxxxkkkk解出：kkkkkkxxxxxxx122122*河海大学理学院数值分析 埃特金加速法埃特金加速法 kkkkkkxxxxxxx122122*kkkkkkxxxxxx12212kkkxxx22记kkkkxxxx221河海大学理学院数值分析2.2.斯蒂芬森迭代法斯蒂芬森迭代法 斯蒂芬森迭代斯蒂芬森迭代 由于 kkxx112kkxx kx，新迭代函数 xxxxxxx22kkxx1河海大学理学院数值分析7 76 6 非线性方程组的解法非线性方程组的解法 00,0,21211nnnxxxfxxxfxF 非线性方程组非线性方程组两种解法两种解法:不动点迭代法不动点迭代法(简单迭代法简单迭代法)牛顿迭代法牛顿迭代法河海大学理学院数值分析1不动点迭代法不动点迭代法（简单迭代法简单迭代法）改写成等价形式改写成等价形式 xxxxfxxxxfxxnnnn,212111 简单迭代法：简单迭代法：压缩映象原理和收敛性定理也成立。压缩映象原理和收敛性定理也成立。kkxx1河海大学理学院数值分析2.2.牛顿迭代法牛顿迭代法 雅可比矩阵雅可比矩阵 nnxxxfffJ,2121nnnnxfxfxfxf1111 kknnkkxFxxxfffxx121211,牛顿迭代法牛顿迭代法河海大学理学院数值分析例 写出解以下非线性方程组的迭代格式0cossin40sincos3yxyyxx解 简单迭代法：kkkyxxsincos311 kkkyxycossin411 100 yx 取 迭代至28步后，得解的近似值为 415169.0 x336791.0y，河海大学理学院数值分析 牛顿迭代法：yxxfsincos3yxygcossin4xxfsin3yyfcosxxgcosyygsin4Jyxyxsin4coscossin3 kkkkkgfyxJ 其中：kkkxxx1 kkkyyy1取 100 yx 仅迭代了4步，得解的近似值为415169.0 x336791.0y，解毕 河海大学理学院数值分析 例 求解以下非线性方程组(仅迭代2步).02242212221xxxxx0332222121xxxx 4.001x 9.002x ,解 22422122211xxxxxf3322221212xxxxf J21211221233412228xxxxxxxx9.0,4.00 x 79.0,73.0,0201ff，河海大学理学院数值分析 0J0.33.46.10.5 00 xJ 0201ff0.33.46.10.5 02120111xxxx79.073.0 02120111xxxx100.0114.0 514.011x 000.112x，070392.0,084784.0,1211ff 1J542.3056.5028.2112.6 11xJ 1211ff 河海大学理学院数值分析,542.3056.5028.2112.6 12221121xxxx070392.0084784.0 12221121xxxx000.0014.0所以，得方程组解的近似值为500.01x000.12x，解毕