收敛加速的方法.ppt

《收敛加速的方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、简单迭代法不动点迭代的收敛性迭代序列的收敛速度收敛加速的方法第二章非线性方程的求根方法[a,b]称为有根区间.则(2)(3)(1)f(ak)f(bk)<0由此可见，如果二分过程无限地进行下去（），则有限区间必定缩为一点x*，该点显然就是所求的根。实际上，我们不可能去完成这种无穷过程，也无必要，只需得到满足一定精度的近似值就可以了。如果令有根区间[an,bn]的中点为x*的近似值，则在二分过程中，得到下列以x*为极限的近似根序列由于二分法优点：是方程求根问题的一种直接搜索方法，算法简单、直观、实用，收敛性总能得到保证。缺点（局限

2、性）：不能求重根；计算速度慢。思考：为什么不能求重根？例2.1用二分法求方程在区间[1,1.5］内的一个实根，要求误差不超过0.005。解由公式估计所要二分的次数即只要二分6次，便能达到所要求的精度。计算结果kakbkxkf(xk)01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-作业：1、用二分法求方程在区间[1,2］内的一个实根，要

3、求误差不超过0.005。将一个计算过程反复进行一种常见常用的计算技术构造有效的迭代格式选取合适的迭代初值对迭代格式进行收敛性分析一种圆周率的计算方案:初值:x0=1(n=1,2,3,······)迭代格式:2.2迭代法1选取初值把给定的方程改写成等价形式f(x)=0若存在x*,使得,则称x*为不动点。在根x*的附近取一点x0作为x*的预测值,也叫迭代初值。(1)把x0代入(1)的右端，得如果，则。如果，把x1作为根的新的预测值代入(1)，得如果，则。如果，把x2作为根的新的预测值代入(1)......如此重复上述步骤，则有迭代

4、公式(k=0,1,2,···)2按迭代格式进行计算3判别收敛其中，：迭代函数，得到迭代序列如果迭代序列的极限存在，则迭代过程收敛，显然有如果迭代序列的极限不存在，则称迭代过程发散。上述迭代过程也称不动点迭代法。方程求根，在几何上就是确定曲线与直线的交点p*几何意义x*x2x1x0如果逐渐逼近p*，－－－迭代过程收敛y=xyox如果逐渐远离p*，－－－迭代过程发散（无意义）x2x1x0x*y=xyox例2.2求方程f(x)=x3–x–1=0在x=1.5附近的根x*。解设将方程改写成下列形式由此得迭代公式迭代初值取x0=1.5，计

5、算值用6位数字表示。迭代结果如下表kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494从表中可看到x7与x8完全相同，这时可认为x8已满足方程，x8即为所求根的近似值。上述迭代过程是收敛的。如果将方程改写成下列形式据此有迭代公式迭代初值仍取x0=1.5，则有当k增大时，xk随之增大而不趋于任何极限，此时迭代过程发散。通过此例说明，迭代过程只有在一定条件下才可能收敛。一个发散的过程没有任何意义。定理2.3如果,满足条件:;(2)则方程

6、在[a,b]有唯一的不动点x*。证若或,显然有不动点设,则有,记则有所以,存在x*,使得即,x*即为不动点.唯一性：设在[a,b]上存在两个根x1*和x2*，则由微分中值定理，必有定理2.4如果,满足条件:;(2)则对任意的x0∈[a,b],迭代格式产生的序列{xk}收敛到不动点x*,且有事后误差估计式证(0

7、，则终止迭代，取例2.3求方程x=e–x在x=0.5附近的一个根，要求精度。不动点迭代产生序列的收敛速度数列的p阶收敛概念记迭代误差：则称迭代过程是p阶收敛的.特别:(1)收敛阶p=1时,称为线性收敛;(2)收敛阶p>1时,称为超线性收敛;(3)收敛阶p=2时,称为平方收敛序列的收敛阶数越高,收敛速度越快收敛速度：接近收敛时迭代误差的下降速度。定义当时，有例2.3方程x3+10x-20=0,取x0=1.5,证明迭代法是线性收敛证令f(x)=x3+10x–20,绘出y=f(x)图形可知方程的根x*≈1.5,令求导数,得利用Lag

8、range中值定理,有其中,介于xk和x*之间.所以由此可知,这一序列的收敛阶数为1,即迭代法是线性收敛.显然,在x*附近定理2.6而则p阶收敛。证因为，所以迭代过程局部收敛。由Taylor公式其中,介于xk和x*之间.所以故迭代法p阶收敛.迭代公式的加速迭代公式产生的数列{