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

《数值分析3.2.迭代加速、牛顿法及弦截法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章非线性方程的数值解法3.1方程求根与二分法3.2迭代法及其收敛性3.3迭代收敛的加速方法3.4牛顿法3.5弦截法与抛物线法3.3迭代收敛的加速方法3.3.1埃特金加速收敛方法对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大.设x0是根x*的某个近似值,用迭代公式校正一次得x1=(x0)而由微分中值定理，有假设(x)改变不大,近似地取某个近似值L,则有由于x2-x*≈L(x1-x*).若将校正值x1=(x0)再校正一次，又得x2=(x1)将它与(3.1)式联立，消去未知的L，有由此推知

2、在计算了x1及x2之后，可用上式右端作为x*的新近似,记作̄x1，一般情形是由xk计算xk+1,xk+2，记它表明序列{̄xk}的收敛速度比{xk}的收敛速度快.(3.1)式称为埃特金(Aitken)△2加速方法.可以证明也称为埃特金(Aitken)外推法.可以证明:为线性收敛,则埃特金法为平方收敛；注：埃特金(Aitken)加速迭代法也可写成下面格式若为p(p>1)阶收敛，导数连续，则埃特金法为2p–1阶收敛.的p阶若3.3.2斯蒂芬森(Steffensen)迭代法埃特金方法不管原序列{xk}是怎样产生的，对{xk}进行加速计算，得到序列{̄xk}.如果把埃特

3、金加速技巧与不定点迭代结合，则可得到如下的迭代法：称为斯蒂芬森(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逐步

4、归结为某种线性方程来求解.设已知方程f(x)=0有近似根x0，且在x0附近f(x)可用一阶泰勒多项式近似，表示为当f(x0)≠0时，方程f(x)=0可用线性方程(切线)近似代替，即f(x0)+f(x0)(x-x0)=0.(4.1)解此线性方程得得迭代公式此式称为牛顿(Newton)迭代公式.牛顿法的几何意义：设xk是根x*的某个近似值，过曲线y=f(x)上横坐标为xk的点Pk引切线，并将该切线与x轴交点的横坐标xk+1作为x*的新的近似值.注意到切线方程为这样求得的值xk+1必满足(4.1),从而就是牛顿公式(4.2)的计算结果.xyx*xky=f(x)xk

5、+1PkPk+1xk+2牛顿迭代法的收敛性设x*是f(x)的一个单根，即f(x*)=0，f(x*)≠0,有牛顿迭代法的迭代函数为由定理4可得由此得到，当x*为单根时，牛顿迭代法在根x*的邻近是二阶(平方)收敛的.定理(局部收敛性)设fC2[a,b],若x*为f(x)在[a,b]上的根，且f(x*)0，则存在x*的邻域U,使得任取初值x0U，牛顿法产生的序列{xk}收敛到x*，且满足解将原方程化为x–e–x=0，则牛顿迭代公式为取x0=0.5，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=x–e–x，f(x

6、)=1+e–x，例1用牛顿迭代法求方程x=e–x在x=0.5附近的根.例2对于给定的正数C，应用牛顿法解二次方程我们现在证明，这种迭代公式对于任意初值x0>0都是收敛的.推导出求开方值　的计算公式.事实上，对(4.5)式进行配方整理，易知以上两式相除得据此反复递推有记整理(4.6)式，得对任意初值x0>0，总有

7、q

8、<1，故由上式推知，当k→∞时，即迭代过程恒收敛.3.4.2重根情形当x*为f(x)的m(m>0)重根时，则f(x)可表为f(x)=(x-x*)mg(x).其中g(x*)≠0，此时用牛顿迭代法(4.2)求x*仍然收敛，只是收敛速度将大大减慢.事实上，

9、因为迭代公式令ek=xk–x*，则可见用牛顿法求方程的重根时仅为线性收敛.从而有两种提高求重根的收敛速度的方法：1)取如下迭代函数得到迭代公式下面介绍一个求重数m的方法，令则求m重根具有2阶收敛.但要知道x*的重数m.由式得因此得估计m的式子为对f(x)=(x-x*)mg(x),g(x*)≠0，令函数则为求μ(x)=0的单根x*的问题，对它用牛顿法是二阶(平方)收敛的.其迭代函数为2)将求重根问题化为求单根问题.从而构造出迭代方法为例3用牛顿迭代法求函数f(x)=(x-1)[sin(x-1)+3x]-x3+1=0在0.95附近之根.解取x0=0.95用牛顿迭代法

10、求得的xk见右表.可见x