精选收敛加速的方法讲义

（优选）收敛加速的方法课件当前第1页\共有34页\编于星期三\10点当前第2页\共有34页\编于星期三\10点[a,b]称为有根区间.

则当前第3页\共有34页\编于星期三\10点当前第4页\共有34页\编于星期三\10点(2)

(3)

(1)

f(ak)f(bk)<0

当前第5页\共有34页\编于星期三\10点由此可见，如果二分过程无限地进行下去（），则有限区间必定缩为一点x*，该点显然就是所求的根。实际上，我们不可能去完成这种无穷过程，也无必要，只需得到满足一定精度的近似值就可以了。如果令有根区间[an,bn]的中点为

x*的近似值，则在二分过程中，得到下列以x*为极限的近似根序列由于当前第6页\共有34页\编于星期三\10点当前第7页\共有34页\编于星期三\10点当前第8页\共有34页\编于星期三\10点二分法优点：是方程求根问题的一种直接搜索方法，算法简单、直观、实用，收敛性总能得到保证。缺点（局限性）：不能求重根；计算速度慢。思考：为什么不能求重根？例2.1用二分法求方程在区间[1,1.5］内的一个实根，要求误差不超过0.005。解由公式估计所要二分的次数即只要二分6次，便能达到所要求的精度。当前第9页\共有34页\编于星期三\10点计算结果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-当前第10页\共有34页\编于星期三\10点作业：1、用二分法求方程在区间[1,2］内的一个实根，要求误差不超过0.005。当前第11页\共有34页\编于星期三\10点将一个计算过程反复进行一种常见常用的计算技术构造有效的迭代格式选取合适的迭代初值对迭代格式进行收敛性分析一种圆周率的计算方案:初值:x0=1(n=1,2,3,······)迭代格式:2.2迭代法当前第12页\共有34页\编于星期三\10点1选取初值把给定的方程改写成等价形式

f(x)=0若存在x*,使得,则称x*为不动点。在根x*的附近取一点x0作为x*的预测值,也叫迭代初值。(1)当前第13页\共有34页\编于星期三\10点把x0代入(1)的右端，得如果，则。如果，把x1作为根的新的预测值代入(1)，得如果，则。如果，把x2作为根的新的预测值代入(1)......如此重复上述步骤，则有迭代公式(k=0,1,2,···)2按迭代格式进行计算当前第14页\共有34页\编于星期三\10点3判别收敛其中，：迭代函数，得到迭代序列如果迭代序列的极限存在，则迭代过程收敛，显然有如果迭代序列的极限不存在，则称迭代过程发散。上述迭代过程也称不动点迭代法。当前第15页\共有34页\编于星期三\10点方程求根，在几何上就是确定曲线与直线的交点p*几何意义x*x2

x1

x0如果逐渐逼近p*，－－－迭代过程收敛y=xyox当前第16页\共有34页\编于星期三\10点如果逐渐远离p*，－－－迭代过程发散（无意义）x2

x1

x0x*

y=xyox当前第17页\共有34页\编于星期三\10点

例2.2求方程

f(x)=x3–x–1=0

在x=1.5附近的根x*。

解设将方程改写成下列形式由此得迭代公式迭代初值取x0=1.5，计算值用6位数字表示。迭代结果如下表当前第18页\共有34页\编于星期三\10点kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494从表中可看到x7与x8完全相同，这时可认为x8已满足方程，x8即为所求根的近似值。上述迭代过程是收敛的。当前第19页\共有34页\编于星期三\10点如果将方程改写成下列形式据此有迭代公式迭代初值仍取x0=1.5，则有当k增大时，xk随之增大而不趋于任何极限，此时迭代过程发散。通过此例说明，迭代过程只有在一定条件下才可能收敛。一个发散的过程没有任何意义。当前第20页\共有34页\编于星期三\10点定理2.3如果,满足条件:;(2)则方程在[a,b]有唯一的不动点x*。证若或,显然有不动点设,则有,记则有所以,存在x*,使得即,x*即为不动点.当前第21页\共有34页\编于星期三\10点唯一性：设在[a,b]上存在两个根x1*和x2*，则由微分中值定理，必有当前第22页\共有34页\编于星期三\10点定理2.4如果,满足条件:;(2)则对任意的x0∈[a,b],迭代格式产生的序列{xk}收敛到不动点x*,且有事后误差估计式证当前第23页\共有34页\编于星期三\10点(0<L<1)所以,，故迭代格式收敛当前第24页\共有34页\编于星期三\10点当前第25页\共有34页\编于星期三\10点当前第26页\共有34页\编于星期三\10点由此可见，迭代过程的收敛性通常依赖于迭代初值的选取当前第27页\共有34页\编于星期三\10点迭代法的计算步骤：1）准备：确定方程f(x)=0的等价形式及初值x0，为确保迭代收敛，要求满足或2）迭代：按迭代公式计算出xk3）判别：直到，则终止迭代，取当前第28页\共有34页\编于星期三\10点例2.3求方程

x=e–x在x=0.5附近的一个根，要求精度。当前第29页\共有34页\编于星期三\10点不动点迭代产生序列的收敛速度数列的p

阶收敛概念记迭代误差： 则称迭代过程是p

阶收敛的.特别:(1)收敛阶p=1时,称为线性收敛;(2)收敛阶p>1时,称为超线性收敛;(3)收敛阶p=2时,称为平方收敛序列的收敛阶数越高,收敛速度越快收敛速度：接近收敛时迭代误差的下降速度。定义当时，有当前第30页\共有34页\编于星期三\10点例2.3方程x3+10x-20=0,取x0=1.5,证明迭代法是线性收敛证令f(x)=x3+10x–20,绘出y=f(x)图形可知方程的根x*≈1.5,令求导数,得当前第31页\共有34页\编于星期三\10点利用Lagrange中值定理,有其中,介于xk和x*之间.所以由此可知,这一序列的收敛阶数为1,即迭代法是线性收敛.显然,在x*附近当前第32页\共有34页\编于星期三\10点定理2.6而则p阶收敛。证因为，所以迭代过程局部收敛。由Taylor公式其中,介于xk和x*之间.所以故迭代法p阶收敛.当