精选收敛加速的方法讲义

（优选）收敛加速的方法课件目前一页\总数三十四页\编于八点目前二页\总数三十四页\编于八点[a,b]称为有根区间.

则目前三页\总数三十四页\编于八点目前四页\总数三十四页\编于八点(2)

(3)

(1)

f(ak)f(bk)<0

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

x*的近似值，则在二分过程中，得到下列以x*为极限的近似根序列由于目前六页\总数三十四页\编于八点目前七页\总数三十四页\编于八点目前八页\总数三十四页\编于八点二分法优点：是方程求根问题的一种直接搜索方法，算法简单、直观、实用，收敛性总能得到保证。缺点（局限性）：不能求重根；计算速度慢。思考：为什么不能求重根？例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］内的一个实根，要求误差不超过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)......如此重复上述步骤，则有迭代公式(k=0,1,2,···)2按迭代格式进行计算目前十四页\总数三十四页\编于八点3判别收敛其中，：迭代函数，得到迭代序列如果迭代序列的极限存在，则迭代过程收敛，显然有如果迭代序列的极限不存在，则称迭代过程发散。上述迭代过程也称不动点迭代法。目前十五页\总数三十四页\编于八点方程求根，在几何上就是确定曲线与直线的交点p*几何意义x*x2

x1

x0如果逐渐逼近p*，－－－迭代过程收敛y=xyox目前十六页\总数三十四页\编于八点如果逐渐远离p*，－－－迭代过程发散（无意义）x2

x1

x0x*

y=xyox目前十七页\总数三十四页\编于八点

例2.2求方程

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

在x=1.5附近的根x*。

解设将方程改写成下列形式由此得迭代公式迭代初值取x0=1.5，计算值用6位数字表示。迭代结果如下表目前十八页\总数三十四页\编于八点kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494从表中可看到x7与x8完全相同，这时可认为x8已满足方程，x8即为所求根的近似值。上述迭代过程是收敛的。目前十九页\总数三十四页\编于八点如果将方程改写成下列形式据此有迭代公式迭代初值仍取x0=1.5，则有当k增大时，xk随之增大而不趋于任何极限，此时迭代过程发散。通过此例说明，迭代过程只有在一定条件下才可能收敛。一个发散的过程没有任何意义。目前二十页\总数三十四页\编于八点定理2.3如果,满足条件:;(2)则方程在[a,b]有唯一的不动点x*。证若或,显然有不动点设,则有,记则有所以,存在x*,使得即,x*即为不动点.目前二十一页\总数三十四页\编于八点唯一性：设在[a,b]上存在两个根x1*和x2*，则由微分中值定理，必有目前二十二页\总数三十四页\编于八点定理2.4如果,满足条件:;(2)则对任意的x0∈[a,b],迭代格式产生的序列{xk}收敛到不动点x*,且有事后误差估计式证目前二十三页\总数三十四页\编于八点(0<L<1)所以,，故迭代格式收敛目前二十四页\总数三十四页\编于八点目前二十五页\总数三十四页\编于八点目前二十六页\总数三十四页\编于八点由此可见，迭代过程的收敛性通常依赖于迭代初值的选取目前二十七页\总数三十四页\编于八点迭代法的计算步骤：1）准备：确定方程f(x)=0的等价形式及初值x0，为确保迭代收敛，要求满足或2）迭代：按迭代公式计算出xk3）判别：直到，则终止迭代，取目前二十八页\总数三十四页\编于八点例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,令求导数,得目前三十一页\总数三十四页\编于八点利用Lagrange中值定理,有其中,介于xk和x*之间.所以由此可知,这一序列的收敛阶数为1,即迭代法是线性收敛.显然,在x*附近目前三十二页\总数三十四页\编于八点定理2.6而则p阶收敛。证因为，所以迭代过程局部收敛。由Taylor公式其中,介于xk和x*之间.所以故迭代法p阶收敛.