东北农业大学《数值分析》课件-第七章（隋老师）.pptx

东北农业大学东北农业大学 数值分析数值分析 第七章第七章 二分法 迭代法 迭代法的加速（Aitken加速法、Steffensen迭代法）牛顿迭代法 非线性方程组的迭代法 第七章第七章 非线性方程（组）的数值解非线性方程（组）的数值解 1.非线性方程实根的对分法(二分法)二分法的收敛性 a x*x0 b()f x a1 b1 *201,32;0;0,63;0,3,3,60,3 0,1.5,1.5,31.5,3 1.5,2.25,2.25,3 1.5,2.251.875f xxcf cxccx2.迭代法 222010221120110110 3,1.2,11;1;1xxxxxxf xxxxxxxx xxx a b，取,=选 迭代过程的几何表示 ()yxyxO x*x2 x1 x0 x y 0P1Q1P2P*P2Q()()yxxxxy交点即为真根迭代法需解决的三个问题 迭代函数的构造 由迭代函数产生的解序列的收敛性 序列的收敛速度和误差估计 3*0()10 1.5.f xxxxx 例：求方程 在附近的根331k 1 1 1(0,1,2)k 0 1 2 7 8 x 1.5 1.35721 1.330861.324721.32472kkxxxxk解：（）将方程改写为由此建立迭代公式迭代收敛。331k2 11.k 0 1 2 x1.52.37512.39kkxxxx（）若将方程改写为建立迭代公式 迭代不收敛。如何选取合适的迭代函数？下面介绍三个迭代法的收敛定理。()x2(),()(),(),()()0,()()0,0,(),xa bxxxxa baaabbba bxxa b 证：存在性 由条件（）知在上连续。令则在上连续，且故存在，使得（）即（）,所以方程在内有根。*12*12121212(),2()()xxa bxxxxxxL xxxx唯一性 假设方程在内有两个根由条件（），有导出矛盾，唯一性得证。0*11*0*0*11110,()()01,limx,()()nnnnnnnnkkkkkkkxa bxxxxL xxxxL xxLxxa bxxkxxxxL xxL xx对任意由迭代公式有依此类推，得因 所以即对任意初值迭代序列均收敛到方程的根。类似地，对任意正整数,有,()()()()()()()()()()()2x ya bx yxyxyxyxyxyL xyx 证：设为上任意两点，由微分中值定理，在之间至少存在一点，使得即满足上一定理的条件（），故结论成立。()(),xxa b因而构造迭代函数的原则是使在有根区间上有尽可能小的上界。*10 1nnLxxxxL误差估计式表明:L 常数 越小，简单迭代法收敛越快 cossin/4;242.1.cossin/4 ,2 cossin/414xxxxxxxLxxxxxxx例：能否用迭代法求解下列方程，如果不能，试将方程改成能用迭代法求解的形式。1分析：判断在根的附近能否满足解 1，有能用迭代法求根。14242,10,2012 2 ln22ln21.386291ln 4-/ln2,ln 4-/ln2,111111,4ln242 ln22ln2 ln 4-xxxkkxf xxffxxxxxxxxx2，令，区间，内有根,但不能直接用该迭代函数迭代。改写原方程为则可以用下述迭代公式来求解：/ln22 ()10 f xxx 例：用简单迭代法求方程的根。(1.5)0.250,(2)10 1.5,2 ff 解：为有根区间。11111()1.51.5 1()2 12111()3.162212 2.5xxxxxx （）因且22222111(2)1()1.51()1221.5111 ()1.52.25xxxxxx 因且0 1.5,2,x 根据定理，任取由这两种等价方程所构造的简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。0.2*110 0 511,1,10.21550.41260.5121kxxxxxnxknxexf xxexexeLeeLxexxxxLnnn-5例：用简单迭代法求方程在.附近的根，要求精度=10。解：令=0,显然方程在0.2，1有根,迭代函数收敛迭代格式为由，得，*01*()(,)()()1,()(0,1,2,).nnxxO xxxxxxxxxxnx 定理3：如果函数在 的一邻域内连续可微，为方程的根，且则存在正数使得对任意迭代序列收敛于局部收敛性*1 ()(,)()1,1,()1(),()()()(),()nnxO xxLxxxxLxxxxxxL xxxxxxxx 证：因在内连续，且故存在正数使得对，有另一方面，由又有即。由上面定理知，迭代序列收敛于。实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。迭代法收敛速度定义迭代法收敛速度定义()1*(1)*()*(),()()()()0;()0pkkppxxxxxxxxxp定理：对于迭代过程如果在所求根 的邻近连续，并且则该迭代过程在点 邻近是 阶收敛的。*1*()*()()*11()01,()()()()()()!()()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep证：由于故具有局部收敛性。将在根 处展开，由条件有 (),()0,1()1,()0,2()0,()0,kkxxa bxxxxxxx迭代过程的收敛速度依赖于迭代函数的选取。如果当时则该迭代过程只可能是线性收敛。特别地，当序列线性收敛；当序列平方收敛。迭代法加速（迭代法加速（AitkenAitken法）法）21121 ()()2kkkkkkkkkkxxxxxxxxxx设序列线性收敛，迭代格式为，且序列平方收敛。*01021*1010*2121*1021*12 ()()()()()()()()()()(),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx 设 是根 的某个预测值，通过两次迭代校正有 由微分中值定理，有假定改变不大，近似地取某个近似值则由*2*0212*1012()2xxxxxxxxxxx此种加速需用两次迭代值进行加工。1112111111 ()()()2kkkkkkkkkkkxxxxxxxxxxx校正再校正改进如果将一次改进值作为一步，则计算公式如下：Steffensen迭代法 Aitken加速法的加速技巧与原迭代法的结合，即 1 ()1kkxx设原迭代法为21()()()2kkkkkkkkkkkyxzyyxxxzyx 2()()2xxxxxxx 其中 1 ()kkxx迭代格式为，2 1 pp结论：若迭代公式 1 是 阶收敛的，则迭代公式 2 是阶收敛的。Newton 迭代法 Newton 迭代法的收敛性 简单Newton 迭代法 Newton 下山法 Newton 迭代法的重根处理 弦截法 3.Newton 迭代法 非线性问题的最简单解法是线性近似。将非线性方程线性化，以线性方程的解逐步逼 近非线性方程的解，这就是Newton法的基本思想。一、牛顿迭代法一、牛顿迭代法 Newton 法的几何解释 0 1 (0，f(0)12*(),()()()()()()()()()()0,()0,()0,kkkkf xxxfxf xxxfxf x fxxfxxf xf xfxxx对牛顿公式其迭代函数为 由于假定 是的一个单根，即则由上式知由上述定理知，牛顿法在根 的邻近至少是平方收敛的。1 10.()1,()(1)()()()1 1kxxxxxkkkkxef xxefxexf xxexxxfxxxexxx 例：用牛顿法解方程解：牛顿法迭代函数为牛顿迭代公式为00.5x 可先用二分法或经验确定迭代初值，再按牛顿公式进行迭代。例：用牛顿法求 115的近似值。2*021()1150,1015,116,10,11()20,()20,11()()()115 2kkkkf xxffxfxxfxxf xxxfxxxxx 解：取 ，牛顿法迭代函数为牛顿迭代公式为 2210()0,()()()1 0,0,1,2,221,2,kkkkkkkkf xxaf xxxfxaxaaxxxxkxxkxax一般的，牛顿法迭代函数为求 的牛顿迭代公式为，可以证明：对一切且序列是单减的，从而迭代过程收敛。1111 21211022kkkkkkkkkaxxxxaxaxxaxaxa22可以证明：迭代过程平方收敛。13Page 23910.;2)lim0;kkkkxaxaCxa例.第题分析：1）证明的极限为 0222222222220,0,01,2,.3/3,3333633kaxxkxx xaxaxaxax xaxxaxxaxa证明：1）令则 220,1,3/30,.kxxxlll lalalla laa 即迭代法收敛，设的极限为 则有迭代序列收敛于 3213333223/32 limlim11limlim0433kkkkkkkkkkkkkkaxaxxaaxaxaxaxaxaaxxaa）迭代式是的三阶方法。33120001()101.5()()()1 311.50 60 617 9kkkkkf xxxxf xxxfxxxxxxxxxx 例 用牛顿迭代法求在附近的一个根。解：牛顿法迭代函数为牛顿迭代公式为比较与.，可以发现在取.时，所得.，偏离较大。Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。二、Newton 迭代法的收敛性 三、简单迭代法 四、下山迭代法 331201010()101.5()()()1 321 32 310 617.9()1.14062(),kkkkkf xxxxf xxxfxxxxxxxxxxx 例 用下山迭代法求在附近的一个根。解：迭代函数为取,迭代公式为取.与 偏离很大，与 偏离不大五五、弦截法、弦截法 1(),(),()kkkf xf xfx基本思想：利用一些函数值回避导数值的计算。11111 ,()0(),(),(),(),()0()0 (,).12kkk rkkk rrrkkkkk rx xxf xf xf xf xp xp xf xxxx xxrr设是的一组近似根，利用函数值构造插值多项式并适当选取的一个根作为的新的近似根，这就确定了一个迭代过程，记迭代函数为：当时为弦截法，当时为抛物线法。弦截法弦截法 11111111111 ,()0(),()()()0()0.()()()()()()().()()kkkkkkkkkkkkkkkkkkx xf xf xf xp xp xf xxf xf xp xf xxxxxxxxxf xf xf x设是的近似根，利用构造一次插值多项式，并用的根作为的新的近似根由111()()()()()kkkkkkkkf xxxfxf xf xfxxx此迭代公式可看作牛顿公式中的导数用差商取代的结果。11011,.,kkkkkxxxx xxx弦截法在求时要用到前面两步的结果需两个初值，而牛顿切线法在计算时，只用到前一步 的值。弦截法的几何表示 x0 X x*x1 x2 x3 Y f(x)0 P0 P2 P1 弦截法收敛性定理弦截法收敛性定理*01111*():()0,()().()()151.618.2kkkkkkkf xxxxxfxx xf xxxxxf xf xpx定理：假设在根 的邻域内具有二阶连续导数，且对任意有又初值那么当邻域 充分小时，弦截法将按阶收敛到根11*11111*11111.11 ,()0(),()()()()()2()()()()()22 ()0kkkkkkkkkkkkxxxf xp xxxff xp xxxxxffp xxxxxe exp x 证：用数学归纳法证明迭代值全属于。首先证明当时必属于。设，是以为节点的插值多项式。由又由于是的根，故有*111111*11211()()()()()()()()().kkkkkkkkp xp xp xpxxf xf xxxfexx 1112121112().2(),max(),.2mi