计算方法7.4-7.6

1、 用迭代法可逐步精确方程 根的近似值，但必须要找到 的等价方程 ,如果 选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法。7.4.1 7.4.1 牛顿迭代法的基本思想牛顿迭代法的基本思想 牛顿迭代法一种重要和常用的迭代法, 它的基本思想是借助泰勒展开，将非线性函数f(x)逐步线性化, 从而将非线性方程 f(x)=0 近似地转化为线性方程求解 0)(xf0)(xf)(xx)(x 7.4 牛顿迭代法牛顿迭代法2022-3-61 对于方程 ,设其近似根为 , 函数f(x)可在 附近作泰勒展开 0)

2、(xf0 x0 x 200000)(21)()()(xxxfxxxfxfxf忽略高次项,用其线性部分作为函数f(x)的近似， )()()(000 xxxfxfxf 设 的根 ,则有 ,即 0)(xf1x0)(1xf0)()(0100 xxxfxf)()(0001xfxfxx2022-3-62x1是比x0更接近于根x*的近似值。 )()(1kkkkxfxfxx)2,1 ,0(k同样将f(x)=0在x1附近作泰勒展开，取近似得到)()(1112xfxfxx依此类推，得到牛顿迭代公式牛顿迭代公式 因此得到方程f(x)=0的近似根数列 xi 。 2022-3-63注：当f(xk )=0时，由于此时在x

3、k处切线是水平的，因此无法计算出xk+1 Newton迭代的等价方程为：)( )()(0)(xfxfxxxxf所以2)( )( )()( )()( xfxfxfxfxfxx若f(x)在a处为单根，则0)( , 0)( , 0)(aafaf所以，迭代格式在根a附近收敛2022-3-647.4.2 牛顿迭代法的几何解释牛顿迭代法的几何解释 方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk ，f (xk)引切线交x轴于xk+1 , 并将其作为x*的近似值重复上述过程,每次通过求解切线方程来求解方程f(x)=0的

4、近似根,所以也称为切线法切线法。2022-3-651x*x)(xfy 0 x2x000:( ) ( )()T a n g e n tlin ey fx f x xx0100()()f xxxfx2022-3-66例7.用牛顿迭代法求方程的根:0133xx解:13)(3xxxf设33)(2xxf由牛顿迭代法)()(1kkkkxfxfxx得取初值,5 .00 xx0 =0.5x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553331323kkkkxxxx迭代四次精度达10-8 设函数 ，且满足,)(2baCxf定理定理2（

5、牛顿法收敛的充分条件牛顿法收敛的充分条件）1) f (a) f (b) 0；则牛顿迭代法产生的序列 xk 收敛到f (x) 在 a, b 的唯一根。有根有根只有单根，根只有单根，根唯一唯一产生的序列单调有产生的序列单调有界，保证收敛。界，保证收敛。2022-3-67 7.4.3 7.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性yx0B=x0f(x)0ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x02022-3-68例例8 用迭代法求 在隔根区间1.4,1.50123 xx内的根，要求准确到小数点后第4位。（1）牛顿迭代公式为nnnnnnnnnnnnnxxxxx

6、xxxxxfxfxx2312231)()(2232231（2 2）2 . 0)4 . 1 (f2 . 0)5 . 1 (f 5 . 1 , 4 . 1 x当 时有，023)(2xxxf06)( xxf因 ,故取 ,牛顿迭代法收敛。0)5 . 1 ()5 . 1 ( ff5 . 10 x2022-3-69Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 102022-3-6x0 不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况2022-3-6110)arctan()(xxf0 x精确解为牛顿迭代法)1(arctan21kkkkxxxx

7、10 x取初值x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017如20 x若取初值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010 x5 = 0收敛发散7.4.4 牛顿迭代法求开方（自己看）的根方程，将开放问题转化为求设0)(axxfaxnn由牛顿迭代公式) 1(111nkkkxaxnnx，迭代收敛。选初始值axn02022-3-6122、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。1、优点：牛顿迭

8、代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。2022-3-6132022-3-614本节作业P168 （8）2022-3-615 7.5 迭代法的收敛速度迭代法的收敛速度7.5.1 收敛速度的概念 一个具有实用价值的迭代法，不仅要求它收敛，而且还要求它收敛比较快。迭代收敛的速度是指迭代误差的下降速度。在定理1中我们知道L越小或 迭代法收敛越快，但要准确反映收敛速度，还需要引进收敛阶的概念，它是衡量迭代好坏的标志之一。,| )(|上越小在bax局部收敛性局部收敛性 当迭代函数较复杂时,不能保证在整个域内收敛，通常只能设法使迭代过程

9、在根的邻域(局部)收敛。定理定理3 3 设 在 的根 的邻域中有连续的一阶导数,且 则迭代过程 具有局部收敛性。 证证: :由于 ,存在充分小邻域: ,使成立 ，这里L为某个定数,根据微分中值定理 。由于 ,又当 时 ,故有 由定理1知 对于任意的 都收敛 1)(* x*xx1)(*Lx)()()(*xxxx*)(xxx*)(xxxxLxx)(1kkxx0 x)(x)(xx*x1)(* x)(1kkxx2022-3-616注：局部收敛性定理对迭代函数的要求较弱，但对初始点要求较注：局部收敛性定理对迭代函数的要求较弱，但对初始点要求较高，即初始点必须选在精确解的附近高，即初始点必须选在精确解的附

10、近例9 设 ,要使迭代过程 局部收敛到 ,求 的取值范围。解： 由在根 邻域具有局部收敛性时, 收敛条件 ) 5()(2xxx)(1kkxx5*x)5()(2xxxxx21)(5*x1521)(*ax15211a0522a所以 051a2022-3-6172022-3-618*xxekk设定义1. 满足和若存在实数01cppkkkee|lim1c时称为平方收敛。时称为超线性收敛，时称为线性收敛当别地，称为渐进误差常数。特阶收敛，则称迭代法221 ,1pppcp收敛速度也就越快越大显然, p 数数p p的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的速度的快慢，p p愈大，愈大，则收

11、敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。度的一种度量。 2022-3-619从而确定收敛阶呢？如何确定那么,p即处处可导处充分光滑在精确解如果迭代函数,*)(xx有展开作在将,*)(Taylorxx 2*)(! 2*)(*)*)(*)()(xxxxxxxxppppxxpxxpx*)(!)(*)()!1(*)()(1) 1(0*)()1(xp *)(*)(xx如果*)()(xxppxxp*)(!)()(之间和位于其中xx*2022-3-620定理4. )(1kkxxpkpxxpx*)(!)(*)()(pkpxxp*)(!)()

12、(*1xxkpkkxxxx*1!)()(pppxxkk的收敛阶是即迭代法)(1附近满足：在根如果迭代法迭代函数*)(xx阶导数且连续；存在px)() 1 (,0*)()1(xp *)(*)()2(xx0*)()(xp而pxxkk的收敛阶是则迭代法)(1( )*1()lim!pkpkkexep例10 已知迭代公式 收敛于 证明该迭代公式平方收敛。证: 迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，将 代入，根据定理4可知，迭代公式平方收敛。3*3x032336)(0)(33* xx，为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提

13、高收敛的速度, , 可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 p p2022-3-6217.5.2 牛顿迭代法的收敛性定理定理5 5 设 是方程 的单根, 且 f(x) 在 的某邻域内有连续的二阶导数, 则牛顿法在 附近局部收敛, 且至少二阶收敛, 有*x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 证: 牛顿迭代公式对应的迭代函数为 若 是方程 的单根,则有 , 从而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx由定理3知,牛顿迭代

14、法在 附近局部收敛。又由定理4知, 迭代公式至少具有二阶收敛速度。 *x2022-3-622利用泰勒公式kkkkkxxxxfxxxfxfxf,)(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以 证毕2022-3-623 7.6 弦截法弦截法 牛顿迭代法牛顿迭代法具有收敛快，稳定性好，精度高具有收敛快，稳定性好，精度高等优点，等优点，是它在实际中被广泛应用的主要原因。是它在实际中被广泛应用的主要原因。

15、然而，牛顿法要求求出导数然而，牛顿法要求求出导数f ，这是它的缺点。，这是它的缺点。如果如果f 复杂，求导可能很困难，当复杂，求导可能很困难，当f 只是隐含地定只是隐含地定义时，求导则是不可能的。义时，求导则是不可能的。如果用不计算导数的如果用不计算导数的迭代方法，往往只有线性收敛的速度。迭代方法，往往只有线性收敛的速度。2022-3-624问题： 保证收敛速度 避免求导弦截法弦截法 弦截法弦截法（割线法）（割线法）牛顿迭代法牛顿迭代法一步要计算一步要计算 f 和和 f ，相当于，相当于2个函数值，比较个函数值，比较费时。现用费时。现用 f 的值近似的值近似 f ，可少算一个函数值。，可少算一

16、个函数值。x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率01011)()()(xxxfxfxf收敛比切线法慢，且收敛比切线法慢，且对初值要求同样高。对初值要求同样高。2022-3-625262022-3-6 本节介绍的弦截法弦截法则是避开了求导数运算，具体又分为单点弦截法和双点弦截法。 图上不变号，如在区间内有一个单根，在区间条件：设方程P64),()(),(0)(baxfbaxf 单点弦截法单点弦截法)()()()()(101011xxxxxfxfxfxf此弦与x轴交点的横坐标设为 的弦的方程：及，则过，取)(,()(,(11100010 xfxPxfxPbxax)()()

17、()(1010112xfxfxfxxxx2022-3-627在作弦和点否则选取点即为所求根。，则如果)(,)(,0)(002222xfxxfxxxxf)()()()()(202022xxxxxfxfxfxf此弦与x轴交点的横坐标设为 )()()()(2020223xfxfxfxxxx重复上述过程。是否等于零，否则继续判断)(3xf依此类推写成一般迭代格式)()()()(001kkkkkxfxfxfxxxx，3 , 2 , 1 , 0k2022-3-628x2x30)()(0)(0000 xfxfxxfx必须满足，因此选择本例中果。的选择会影响迭代的结样，注意：与牛顿迭代法一x*a=x0b=x1

18、)(xfy 单点弦截法的几何意义单点弦截法的几何意义是用过曲线上两点 、 的割线来代替切线,用割线与x轴交点的横坐标作为方程的近似根 再过P0点和点 作割线)(,(000 xfxP)(,(111xfxP2x求出 ,依此类推，可求出满足精度要求的 。)(,(222xfxP3xkx计算中计算中P P0是不变的，因此单点弦截法又称为是不变的，因此单点弦截法又称为定端点弦截法定端点弦截法。29误差绝对值不超过0.510-2解:由迭代公式进行迭代得，满足精度要求。2022-3-6令 ，得408)(3xxxf例11 用单点弦截法求方程在区间4,6内的根04083 xx83)(2xxfxxf6)( 代入端点值8)4(f24)4( f128)6(f36)6( f4, 60)6()6(10 xxff取，1877674. 46xx 双点弦截法双点弦截法)()()()(001xxxfxfxfxxkkkkk3 , 2 , 1 , 0k单点弦截法单点弦截法固定一个端点x0，若在作第k+1次迭代时，将迭代公式中的点(x0，f(x0)换成(xk-1，f(xk-1),即得到双点弦双点弦截法截法。迭代公式为)()()()(111kkkkkkkxfxfxfxxxx3 , 2 , 1 , 0k2022-3-630需要需要2个初值个初值 x0 和和 x12022-3-