数值分析3.2.迭代加速、牛顿法及弦截法讲解课件.ppt

1、第第3章章 非线性方程的数值解法非线性方程的数值解法 3.1 方程求根与二分法方程求根与二分法 3.2 迭代法及其收敛性迭代法及其收敛性 3.3 迭代收敛的加速方法迭代收敛的加速方法 3.4 牛顿法牛顿法 3.5 弦截法与抛物线法弦截法与抛物线法3.3 迭代收敛的加速方法迭代收敛的加速方法3.3.1 3.3.1 埃特金加速收敛方法埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大慢，从而使计算量变得很大.设设 x0 是根是根

2、x*的某个近似值的某个近似值,用迭代公式校正一次得用迭代公式校正一次得 x1=(x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之间之间与与在在xxxxxxxx 假设假设 (x)改变不大改变不大,近似地取某个近似值近似地取某个近似值 L,则有则有由于由于 x2-x*L(x1-x*).)1.3().(01 xxLxx 若将校正值若将校正值 x1=(x0)再校正一次，又得再校正一次，又得 x2=(x1)将它与将它与(3.1)式联立，消去未知的式联立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxx

3、x .0lim1 xxxxkkk在计算了在计算了 x1 及及 x2 之后，可用上式右端作为之后，可用上式右端作为 x*的新近的新近似似,记作记作 x1，一般情形是由，一般情形是由xk计算计算 xk+1,xk+2，记，记它表明序列它表明序列xk的收敛速度比的收敛速度比xk的收敛速度快的收敛速度快.)2.3().,1,0()(2)(2212211 kxxxxxxxxxxkkkkkkkkkk (3.1)式称为式称为埃特金埃特金(Aitken)2加速方法加速方法.可以证明可以证明也称为也称为埃特金埃特金(Aitken)外推法外推法.可以证明可以证明:)(1kkxx 为线性收敛为线性收敛,则埃特金法为平

4、方收敛则埃特金法为平方收敛；注：注：埃特金埃特金(Aitken)加速迭代法也可写成下面格式加速迭代法也可写成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 为为 p(p 1)阶收敛，阶收敛，)(x 导数连续，则埃特金法为导数连续，则埃特金法为 2p1 阶收敛阶收敛.的的 p 阶阶若若3.3.2 3.3.2 斯蒂芬森斯蒂芬森(Steffensen)(Steffensen)迭代法迭代法 埃特金方法埃特金方法不管原序列不管原序列xk是怎样产生的，对是怎样产生的，对xk进行加速计算，得到序列进行

5、加速计算，得到序列 xk.如果把如果把埃特金加速技埃特金加速技巧与不定点迭代结合巧与不定点迭代结合，则可得到如下的迭代法：，则可得到如下的迭代法：),(),(kkkkyzxy )3.3().,1,0(2)(21 kxyzxyxxkkkkkkk称为称为斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法.实际上实际上(3.3)是将不定点迭代法是将不定点迭代法(2.2)计算两步合并计算两步合并成一步得到的，可将它写成另一种不动点迭代成一步得到的，可将它写成另一种不动点迭代)4.3(),1,0()(1 kxxkk)5.3(.)(2)()()(2xxxxxxx 其中其中 对不动点迭代对不动点迭代(3.

6、5)有以下局部收敛性定理有以下局部收敛性定理.若若x*为为(3.5)定义的迭代函数定义的迭代函数(x)的不动点，的不动点，则则x*为为(x)的不定点的不定点.反之，若反之，若x*为为(x)的不动点，的不动点，设设(x)在在 x*连续连续，(x*)1，则，则x*是是(x)的不动点，的不动点，且且斯蒂芬森迭代法斯蒂芬森迭代法(3.3)是是2阶收敛阶收敛的的.3.4 牛牛 顿顿 法法3.4.1 3.4.1 牛顿法及其收敛性牛顿法及其收敛性)()()(000 xxxfxfxf 牛顿法实质上是一种牛顿法实质上是一种线性化方法线性化方法，其基本思想，其基本思想是将非线性方程是将非线性方程 f(x)=0 逐

7、步归结为某种线性方程来逐步归结为某种线性方程来求解求解.设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为当当 f(x0)0 时，方程时，方程 f(x)=0 可用线性方程可用线性方程(切线切线)近似近似代替，即代替，即 f(x0)+f(x0)(x-x0)=0.(4.1)解此线性方程得解此线性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式.)2.4(),1,0()()(1 kxfxfxxkkkk牛顿法的牛顿法的几何意义：几何意义：设设x

8、k是根是根x*的某个近似值，的某个近似值，过曲线过曲线y=f(x)上横坐标为上横坐标为xk的点的点Pk引切线，并将该切引切线，并将该切线与线与x轴交点的横坐标轴交点的横坐标xk+1作为作为x*的新的近似值的新的近似值.注意注意到切线方程为到切线方程为这样求得的值这样求得的值xk+1必满足必满足(4.1),从而就是牛顿公式从而就是牛顿公式(4.2)的计算结果的计算结果.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy 牛顿迭代法的收敛性牛顿迭代法的收敛性)()()(xfxfxx 设设x*是是 f(x)的一个单根，即的一个单根，即 f(x*)=0，f(x*)0,

9、有有.0)()()(,0)()()()(2*xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为由定理由定理4可得可得212!122()()1()lim|lim|()|0.()()2!2()kkkkkkxxxxfxxxxxxfx 由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*的的邻近是邻近是二阶二阶(平方平方)收敛收敛的的.设设f C2a,b,若若x*为为 f(x)在在a,b上的根，且上的根，且 f(x*)0，则存在，则存在 x*的邻域的邻域 U,使得任取使得任取初值初值 x0 U，牛顿法产生的序列，牛顿法产生的序列 xk 收敛到收敛到 x*

10、，且满，且满足足12()lim|.()2()kkkxxfxxxfx 解解 将原方程化为将原方程化为 xex=0，则，则牛顿迭代公式为牛顿迭代公式为kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=xex，f(x)=1+ex，例例1 用牛顿迭代法求方程用牛顿迭代法求方程x=ex在在x=0.5附近的根附近的根.例例2 对于给定的正数对于给定的正数 C，应用牛顿法解二次方程，应用牛顿法解二次方程,02 Cx我们现在我们现在证明证明，这种迭代公式对于任意初值，这种迭代公式对于任意初值x00都是收敛的都是

11、收敛的.推导出求开方值推导出求开方值 的计算公式的计算公式.C.21)()()(,)(2 xCxxfxfxxCxxf)5.4(.211 kkkxCxx事实上，对事实上，对(4.5)式进行配方整理，易知式进行配方整理，易知 .2121CxxCxkkk 以上两式相除得以上两式相除得.211 CxCxCxCxkkkk据此反复递推有据此反复递推有)6.4(.200kCxCxCxCxkk 记记00 xCqxC整理整理(4.6)式，得式，得.1222kkqqCCxk 对任意初值对任意初值x00，总有，总有|q|0)重根重根时，则时，则 f(x)可表为可表为 f(x)=(x-x*)mg(x).其中其中 g(

12、x*)0，此时用牛顿迭代法，此时用牛顿迭代法(4.2)求求 x*仍然收敛，仍然收敛，只是只是 收敛速度将大大减慢收敛速度将大大减慢.事实上，因为迭代公式事实上，因为迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，则，则)()()(*11kkkkkkkkxgexmgxgeexxe 可见用牛顿法求方程的重根时仅为可见用牛顿法求方程的重根时仅为线性收敛线性收敛.011)()()(1limlim1 mxgexmgxgeekkkkkkkk从而有从而有两种两种的的方法方法：1)取如下迭代函数取如下迭代函数.0)(,)()()(xxfxf

13、mxx 则则)13.4().,1,0()()(1 kxfxfmxxkkkk得到迭代公式得到迭代公式下面介绍一个下面介绍一个求重数求重数m的方法的方法，令，令211 kkkkkxxxx 则则112121111kkkkkkkkkkkeeeeeeeeee 求求m重根具有重根具有2阶收敛阶收敛.但要知道但要知道x*的的重数重数m.由式由式11lim1kkkeem.111limmmmkk 得得因此得估计因此得估计m的式子为的式子为.11km 对对f(x)=(x-x*)mg(x),g(x*)0，令函数，令函数.)()()()()()()()(xgxxxmgxgxxxfxfx 则为求则为求(x)=0的单根的

14、单根x*的问题，对它用牛顿法是二阶的问题，对它用牛顿法是二阶(平方平方)收敛的收敛的.其迭代函数为其迭代函数为2)将求重根问题化为求单根问题将求重根问题化为求单根问题.)()()()()()()()(2xfxfxfxfxfxxxxx )14.4().,1,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk从而构造出迭代方法为从而构造出迭代方法为 例例3 用牛顿迭代法求函数用牛顿迭代法求函数 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95附近之根附近之根.解解 取取x0=0.95 用牛顿迭代法求用牛顿迭代法求得的得的xk见右表见右表.可可见见xk收敛很

15、慢收敛很慢.kxk km01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511由重根数由重根数m=2,用用(4.13)式加速法，作式加速法，作求得求得 x0=0.95,x1=0.9988559,x2=x3=1.收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代公式.1()()kkkkf xxxmf x 3.5 弦截法与抛物线法弦截法与抛物线法用牛顿法求方程用牛顿法求方程 f(x)=0的根，每步除计算的根，每

16、步除计算 f(xk)外外还要算还要算 f(xk)，当函数，当函数 f(x)比较复杂时，计算比较复杂时，计算 f(x)往往往往比较困难，为此可以利用已求函数值比较困难，为此可以利用已求函数值 f(xk),f(xk-1),来来回避导数值回避导数值 f(xk)的计算的计算.这类方法是建立在这类方法是建立在插值原理插值原理基础上的，下面介绍基础上的，下面介绍弦截法与抛物线法弦截法与抛物线法.3.5.1 3.5.1 弦截弦截(割线割线)法法设设 xk,xk-1是是 f(x)=0的近似根，我们利用的近似根，我们利用 f(xk),f(xk-1)构造一次插值多项式构造一次插值多项式 p1(x)，并用，并用 p

17、1(x)=0 的根作为方程的根作为方程f(x)=0 的新的近似根的新的近似根 xk+1，由于，由于)1.5().()()()()(111kkkkkkxxxxxfxfxfxp 因此有因此有)2.5().()()()(111 kkkkkkkxxxfxfxfxx这样导出的迭代公式这样导出的迭代公式(5.2)可以看做牛顿公式可以看做牛顿公式.)()(1kkkkxfxfxx 11)()(kkkkxxxfxf中的导数中的导数 用用差商差商 取代的结果取代的结果.)(kxf(5.2)式有明显的式有明显的几何意义：几何意义：设曲线设曲线y=f(x)上横坐标为上横坐标为xk-1和和xk的点分别为的点分别为Pk-

18、1和和Pk,则差商则差商 表示弦表示弦 的斜率的斜率,弦弦 的方程为的方程为11)()(kkkkxxxfxfkkPP1 kkPP1)()()()(00kkkkxxxxxfxfxfy Ox*xk+1xkPkxk-1yxPk-1因此，按因此，按(5.2)式求得式求得xk+1实际上是两点弦实际上是两点弦线线 与与x轴交点轴交点的横坐标的横坐标(令令y=0解出解出x即可即可).这种算法因此这种算法因此而形象地称为而形象地称为弦截弦截(割线割线)法法.kkPP1 注：注：弦截法与切线法弦截法与切线法(牛顿法牛顿法)都是线性化分法，但两都是线性化分法，但两者有本质的区别者有本质的区别.切线法在计算切线法在

19、计算 xk+1 时只用到前一步时只用到前一步的值的值 xk，而弦截法要用到前面两步的结果，而弦截法要用到前面两步的结果 xk-1,xk，因，因此使用这种方法必须先给出两个开始值此使用这种方法必须先给出两个开始值 x0,x1.定理定理6 假设假设f(x)在根在根x*的邻域内的邻域内:|x-x*|具有具有二阶连续导数，且对任意二阶连续导数，且对任意x 有有f(x)0，所取的初，所取的初值值x0,x1，那么当邻域，那么当邻域充分小时，弦截法充分小时，弦截法(5.2)将将按阶按阶.618.1251 p收敛到收敛到x*.这里这里p是方程是方程2-1=0的正根的正根.定理证明可见定理证明可见P116.因为

20、因为(5.2)式用到前两点式用到前两点xk-1和和xk的值，故此方法的值，故此方法又称为又称为双点割线法双点割线法.).()()()(0001xxxfxfxfxxkkkk 每步只用一个新点每步只用一个新点xk的值，此方法称为的值，此方法称为单点割线法单点割线法.如果把如果把(5.2)式中的式中的xk-1改为改为x0，即迭代公式为，即迭代公式为例例4 用牛顿迭代法和割线法求方程用牛顿迭代法和割线法求方程 f(x)=x4+2x2x3=0，在区间在区间(1,1.5)内之根内之根(误差为误差为10-9).解解 取取x0=1.5，用牛顿法，用牛顿法,可得可得x6=1.12412303030；取取x0=1

21、.5,x1=1，用，用双点割线法双点割线法，迭代，迭代6次得到同样的次得到同样的结果，而采用结果，而采用单点割线法单点割线法，则迭代，则迭代18次得次得x18=1.124123029.*3.5.2 3.5.2 抛物线法抛物线法设已知方程设已知方程 f(x)=0的三个近似根的三个近似根 xk,xk-1,xk-2，我，我们以这三点为节点构造们以这三点为节点构造二次插值多项式二次插值多项式 p2(x)，并适当，并适当选取选取 p2(x)的一个零点的一个零点 xk+1 作为新的近似根，这样确作为新的近似根，这样确定的迭代过程称为定的迭代过程称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法

22、.在几何图形上在几何图形上,这种方法的基本思想是用抛物线这种方法的基本思想是用抛物线y=p2(x)与与 x 轴的交点轴的交点 xk+1 作为所求根作为所求根 x*的近似位置的近似位置.Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法的抛物线法的几何意义几何意义见下面图形见下面图形.现在推导抛物线法的计算公式现在推导抛物线法的计算公式.插值多项式插值多项式).)(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点有两个零点).(,1211 kkkkkkkxxxxxfxxf)3.5(.,)(4)(22121 kkkkkkkxxxfxf

23、xfxx 式中式中因子在因子在(5.3)式定出一个值式定出一个值xk+1，我们需要讨论根，我们需要讨论根式前正负号的取舍问题式前正负号的取舍问题.在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更接近更接近所求的根所求的根x*，这时，为了保证精度，我们选，这时，为了保证精度，我们选(5.3)式中式中接近接近xk的一个值作为新的近似根的一个值作为新的近似根xk+1.为此，只要取根为此，只要取根式前的符号与式前的符号与的符号相同的符号相同.例例5 用抛物线法求解方程用抛物线法求解方程f(x)=xex-1=0.解解 取取x0=0.5,x1=0.6,x2=0.56532开始

24、，计算得开始，计算得f(x0)=-0.175639,f(x1)=0.093271,f(x2)=-0.005031.fx1,x0=2.68910,fx2,x1=2.83373,fx2,x1,x0=2.21418.故故.75694.2)(,1201212 xxxxxfxxf 代入代入(5.3)式求得式求得.56714.0,)(4)(201222223 xxxfxfxfxx 以上计算表明，抛物线法比弦截法收敛更快以上计算表明，抛物线法比弦截法收敛更快.在一定条件下可以证明在一定条件下可以证明,对于抛物线法，迭代误对于抛物线法，迭代误差有下列渐近关系式差有下列渐近关系式.)(6)(42.0840.11 xfxfeekk由此式可见抛物线法也是超线性收敛的，其收敛的阶由此式可见抛物线法也是超线性收敛的，其收敛的阶是是p=1.840(是方程是方程3-2-1=0的根的根)，收敛速度比弦截，收敛速度比弦截法更接近于牛顿法法更接近于牛顿法.从从(5.3)式看到，即使式看到，即使 xk,xk-1,xk-2 均为实数，均为实数，xk+1也可以是复数，所以抛物线法适用于也可以是复数，所以抛物线法适用于求多项式的实根求多项式的实根和复根和复根.