资源描述
上页,下页,第,3,章 非线性方程的数值解法,3.1,方程求根与二分法,3.2,迭代法及其收敛性,3.3,迭代收敛的加速方法,3.4,牛顿法,3.5,弦截法与抛物线法,3.3,迭代收敛的加速方法,3.3.1,埃特金加速收敛方法,对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大,.,设,x,0,是根,x,*,的某个近似值,用迭代公式校正一次得,x,1,=,(,x,0,),而由微分中值定理，有,假设,(,x,),改变不大,近似地取某个近似值,L,则有,由于,x,2,-,x,*,L,(,x,1,-,x,*,),.,若将校正值,x,1,=,(,x,0,),再校正一次，又得,x,2,=,(,x,1,),将它与,(3.1),式联立，消去未知的,L,，有,由此推知,在计算了,x,1,及,x,2,之后，可用上式右端作为,x,*,的新近似,记作,x,1,，一般情形是由,x,k,计算,x,k,+1,x,k,+2,，记,它表明序列,x,k,的收敛速度比,x,k,的收敛速度快,.,(3.1),式称为,埃特金,(Aitken),2,加速方法,.,可以证明,也称为,埃特金,( Aitken ),外推法,.,可以证明,:,为线性收敛,则埃特金法为平方收敛,；,注：,埃特金,(Aitken),加速迭代法也可写成下面格式,若,为,p,(,p ,1),阶收敛，,导数连续，则埃特金法为,2,p,1,阶收敛,.,的,p,阶,若,3.3.2,斯蒂芬森,(Steffensen),迭代法,埃特金方法,不管原序列,x,k,是怎样产生的，对,x,k,进行加速计算，得到序列,x,k,.,如果把,埃特金加速技巧与不定点迭代结合,，则可得到如下的迭代法：,称为,斯蒂芬森,(Steffensen),迭代法,.,实际上,(3.3),是将不定点迭代法,(2.2),计算两步合并成一步得到的，可将它写成另一种不动点迭代,其中,对不动点迭代,(3.5),有以下局部收敛性定理,.,定理,5,若,x,*,为,(3.5),定义的迭代函数,(,x,),的不动点，则,x,*,为,(,x,),的不定点,.,反之，若,x,*,为,(,x,),的不动点，设,(,x,),在,x,*,连续,，,(,x,*,),1,，则,x,*,是,(,x,),的不动点，且,斯蒂芬森迭代法,(3.3),是,2,阶收敛,的,.,3.4,牛 顿 法,3.4.1,牛顿法及其收敛性,牛顿法实质上是一种,线性化方法,，其基本思想是将非线性方程,f,(,x,)=0,逐步归结为某种线性方程来求解,.,设已知方程,f,(,x,)=0,有近似根,x,0,，且在,x,0,附近,f,(,x,),可用一阶泰勒多项式近似，表示为,当,f,(,x,0,)0,时，方程,f,(,x,)=0,可用线性方程,(,切线,),近似代替，即,f,(,x,0,)+,f,(,x,0,)(,x,-,x,0,)=0,.,(4.1),解此线性方程得,得迭代公式,此式称为,牛顿,(Newton),迭代公式,.,牛顿法的,几何意义：,设,x,k,是根,x,*,的某个近似值，过曲线,y,=,f,(,x,),上横坐标为,x,k,的点,P,k,引切线，并将该切线与,x,轴交点的横坐标,x,k,+1,作为,x,*,的新的近似值,.,注意到切线方程为,这样求得的值,x,k,+1,必满足,(4.1),从而就是牛顿公式,(4.2),的计算结果,.,x,y,x*,x,k,y,=,f,(,x,),x,k,+1,P,k,P,k,+1,x,k,+2,牛顿迭代法的收敛性,设,x,*,是,f,(,x,),的一个单根，即,f,(,x,*,)=0,，,f,(,x,*,)0,有,牛顿迭代法的迭代函数为,由定理,4,可得,由此得到，当,x,*,为,单根,时，牛顿迭代法在根,x,*,的邻近是,二阶,(,平方,),收敛,的,.,定理,(,局部收敛性,),设,f,C,2,a,b,若,x,*,为,f,(,x,),在,a,b,上的根，且,f,(,x,*,),0,，则存在,x,*,的邻域,U,使得任取初值,x,0,U,，牛顿法产生的序列,x,k,收敛到,x,*,，且满足,解,将原方程化为,x,e,x,= 0,，则,牛顿迭代公式为,取,x,0,=0.5,，迭代得,x,1,=0.566311,x,2,=0.5671431,x,3,=0.5671433,.,f,(,x,)=,x,e,x,，,f,(,x,)=1+,e,x,，,例,1,用牛顿迭代法求方程,x,=,e,x,在,x=,0.5,附近的根,.,例,2,对于给定的正数,C,，应用牛顿法解二次方程,我们现在,证明,，这种迭代公式对于任意初值,x,0,0,都是收敛的,.,推导出求开方值 的计算公式,.,事实上，对,(4.5),式进行配方整理，易知,以上两式相除得,据此反复递推有,记,整理,(4.6),式，得,对任意初值,x,0,0,，总有,|,q,|0),重根,时，则,f,(,x,),可表为,f,(,x,)=(,x,-,x,*,),m,g,(,x,),.,其中,g,(,x,*,)0,，此时用牛顿迭代法,(4.2),求,x,*,仍然收敛，只是,收敛速度将大大减慢,.,事实上，因为迭代公式,令,e,k,=,x,k,x,*,，则,可见用牛顿法求方程的重根时仅为,线性收敛,.,从而有,两种,提高求重根的收敛速度,的,方法,：,1,),取如下迭代函数,得到迭代公式,下面介绍一个,求重数,m,的方法,，令,则,求,m,重根具有,2,阶收敛,.,但要知道,x,*,的,重数,m,.,由式,得,因此得估计,m,的式子为,对,f,(,x,)=(,x,-,x,*,),m,g,(,x,),g,(,x,*,),0,，令函数,则为求,(,x,)=0,的单根,x,*,的问题，对它用牛顿法是二阶,(,平方,),收敛的,.,其迭代函数为,2,),将求重根问题化为求单根问题,.,从而构造出迭代方法为,例,3,用牛顿迭代法求函数,f,(,x,)=(,x,-,1)sin(,x,-,1)+3,x,-,x,3,+1=0,在,0.95,附近之根,.,解,取,x,0,= 0.95,用牛顿迭代法求得的,x,k,见右表,.,可见,x,k,收敛很慢,.,k,x,k,k,m,0,1,2,3,4,5,6,0.95,0.9744279,0.9870583,0.9934878,0.9967328,0.9983576,0.9991901,0.5090,0.5047,0.5007,0.5125,2.0369,2.0190,2.0028,2.0511,由重根数,m,=2,用,(4.13),式加速法，作,求得,x,0,=0.95,x,1,=0.9988559,x,2,=,x,3,=1.,收敛速度大大加快于直接用牛顿迭代公式,.,3.5,弦截法与抛物线法,用牛顿法求方程,f,(,x,)=0,的根，每步除计算,f,(,x,k,),外还要算,f,(,x,k,),，当函数,f,(,x,),比较复杂时，计算,f,(,x,),往往比较困难，为此可以利用已求函数值,f,(,x,k,),f,(,x,k,-,1,),来回避导数值,f,(,x,k,),的计算,.,这类方法是建立在,插值原理,基础上的，下面介绍,弦截法与抛物线法,.,3.5.1,弦截,(,割线,),法,设,x,k,x,k,-,1,是,f,(,x,)=0,的近似根，我们利用,f,(,x,k,),f,(,x,k,-,1,),构造一次插值多项式,p,1,(,x,),，并用,p,1,(,x,)=0,的根作为方程,f,(,x,)=0,的新的近似根,x,k,+1,，由于,因此有,这样导出的迭代公式,(5.2),可以看做牛顿公式,中的导数 用,差商,取代的结果,.,(5.2),式有明显的,几何意义：,设曲线,y,=,f,(,x,),上横坐标为,x,k,-,1,和,x,k,的点分别为,P,k-1,和,P,k,则差商 表示弦 的斜率,弦 的方程为,O,x,*,x,k,+1,x,k,P,k,x,k,-,1,y,x,P,k,-,1,因此，按,(5.2),式求得,x,k,+1,实际上是两点弦线,与,x,轴交点的横坐标,(,令,y,=0,解出,x,即可,).,这种算法因此而形象地称为,弦截,(,割线,),法,.,注：,弦截法与切线法,(,牛顿法,),都是线性化分法，但两者有本质的区别,.,切线法在计算,x,k,+1,时只用到前一步的值,x,k,，而弦截法要用到前面两步的结果,x,k,-,1,x,k,，因此使用这种方法必须先给出两个开始值,x,0,x,1,.,定理,6,假设,f,(,x,),在根,x,*,的邻域内,: |,x,-,x,*,|,具有二阶连续导数，且对任意,x,有,f,(,x,),0,，所取的初值,x,0,x,1,，那么当邻域,充分小时，弦截法,(5.2),将按阶,收敛到,x,*,.,这里,p,是方程,2,-,-,1=0,的正根,.,定理证明可见,P116.,因为,(5.2),式用到前两点,x,k,-,1,和,x,k,的值，故此方法又称为,双点割线法,.,每步只用一个新点,x,k,的值，此方法称为,单点割线法,.,如果把,(5.2),式中的,x,k,-,1,改为,x,0,，即迭代公式为,例,4,用牛顿迭代法和割线法求方程,f,(,x,)=,x,4,+2,x,2,x,3=0,，,在区间,(1, 1.5),内之根,(,误差为,10,-,9,).,解,取,x,0,=1.5,，用牛顿法,可得,x,6,=1.12412303030,；,取,x,0,=1.5,x,1,=1,，用,双点割线法,，迭代,6,次得到同样的结果，而采用,单点割线法,，则迭代,18,次得,x,18,=1.124123029,.,*,3.5.2,抛物线法,设已知方程,f,(,x,)=0,的三个近似根,x,k,x,k,-,1,x,k,-,2,，我们以这三点为节点构造,二次插值多项式,p,2,(,x,),，并适当选取,p,2,(,x,),的一个零点,x,k,+1,作为新的近似根，这样确定的迭代过程称为,抛物线法,，亦称为,密勒,(M,ller),法,.,在几何图形上,这种方法的基本思想是用抛物线,y,=,p,2,(,x,),与,x,轴的交点,x,k,+1,作为所求根,x,*,的近似位置,.,O,x,*,x,k,+1,x,k,y=P,2,(,x,),x,k,-,2,y,x,y,=,f,(,x,),x,k,-,1,抛物线法的,几何意义,见下面图形,.,现在推导抛物线法的计算公式,.,插值多项式,有两个零点,式中,因子在,(5.3),式定出一个值,x,k,+1,，我们需要讨论根式前正负号的取舍问题,.,在,x,k,x,k,-,1,x,k,-,2,三个近似值中，自然假定,x,k,更接近所求的根,x,*,，这时，为了保证精度，我们选,(5.3),式中接近,x,k,的一个值作为新的近似根,x,k,+1,.,为此，只要取根式前的符号与,的符号相同,.,例,5,用抛物线法求解方程,f,(,x,)=,xe,x,-,1=0,.,解,取,x,0,=0.5,x,1,=0.6,x,2,=0.56532,开始，计算得,f,(,x,0,)=,-,0.175639,f,(,x,1,)=0.093271,f,(,x,2,)=,-,0.005031,.,f,x,1,x,0,=2.68910,f,x,2,x,1,=2.83373,f,x,2,x,1,x,0,=2.21418,.,故,代入,(5.3),式求得,以上计算表明，抛物线法比弦截法收敛更快,.,在一定条件下可以证明,对于抛物线法，迭代误差有下列渐近关系式,由此式可见抛物线法也是超线性收敛的，其收敛的阶是,p,=1.840,(,是方程,3,-,2,-,-,1=0,的根,),，收敛速度比弦截法更接近于牛顿法,.,从,(5.3),式看到，即使,x,k,x,k,-,1,x,k,-,2,均为实数，,x,k,+1,也可以是复数，所以抛物线法适用于,求多项式的实根和复根,.,
展开阅读全文