收敛加速的方法

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次，便能达到所要求的精度。,计算结果,作业：1、用二分法求方程 在区间1,2内的一个实根，要求误差不超过0.005。,将一个计算过程反复进行 一种常见常用的计算技术 构造有效的迭代格式 选取合适的迭代初值 对迭代格式进行收敛性分析,一种圆周率的计算方案:,初值: x0=1,2.2 迭代法,1 选取初值 把给定的方程 改写成等价形式,f (x)= 0,若存在 x*,使得 ,则称x*为不动点。 在根x*的附近取一点x0作为x*的预测值,也叫迭代初

3、值。,(1),把x0代入(1)的右端，得,如果 ，则 。,如果 ，把 x1作为根的新的预测值代入(1)，得,如果 ，则 。,如果 ，把 x2作为根的新的预测值代入(1). 如此重复上述步骤，则有迭代公式,( k = 0, 1, 2, ),2 按迭代格式进行计算,3 判别收敛,其中， ：迭代函数，得到迭代序列,如果迭代序列的极限存在，则迭代过程收敛，显然有,如果迭代序列的极限不存在，则称迭代过程发散。,上述迭代过程也称不动点迭代法。,方程 求根，在几何上就是确定曲线 与直线 的交点 p*,几何意义,x* x2 x1 x0,如果 逐渐逼近p*，迭代过程收敛,如果 逐渐远离p*，迭代过程发散 （无意

4、义）,例2.2 求方程 f (x)=x3 x 1 = 0 在x =1.5附近的根 x*。,解 设将方程改写成下列形式,由此得迭代公式,迭代初值取x0 =1.5，计算值用6位数字表示。 迭代结果如下表,从表中可看到 x7与 x8完全相同，这时可认为x8已满足方程， x8 即为所求根的近似值。,上述迭代过程是收敛的。,如果将方程改写成下列形式,据此有迭代公式,迭代初值仍取 x0 =1.5，则有,当 k增大时，xk随之增大而不趋于任何极限，此时迭代过程发散。,通过此例说明，迭代过程只有在一定条件下才可能收敛。一个发散的过程没有任何意义。,证 若 或 ,显然 有不动点,设 , 则有 ,记 则有,所以,

5、存在x*,使得 即 , x*即为不动点.,唯一性： 设在a, b 上存在两个根x1*和x2*，则 由微分中值定理,，必有,定理2.4 如果 ,满足条件: ; (2),则对任意的 x0 a, b , 迭代格式 产生的序列 xk 收敛到不动点x*,且有事后误差估计式,证,( 0L1 ),所以, ，故迭代格式收敛,由此可见，迭代过程的收敛性通常依赖于迭代初值的选取,迭代法的计算步骤： 1）准备：确定方程 f(x)=0 的等价形式 及初值x0，为确保迭代收敛，要求 满足 或,2）迭代：按迭代公式 计算出xk,3）判别：直到 ，则终止迭代，取,例2.3 求方程 x=ex 在 x=0.5 附近的一个根，要

6、求精度 。,不动点迭代产生序列的收敛速度,数列的 p 阶收敛概念,记迭代误差：,则称迭代过程是 p 阶收敛的.,特别: (1) 收敛阶p=1时,称为线性收敛; (2) 收敛阶p1时,称为超线性收敛; (3) 收敛阶p=2 时,称为平方收敛,序列的收敛阶数越高,收敛速度越快,收敛速度：接近收敛时迭代误差的下降速度。,定义 当 时，有,例2.3 方程 x3+10 x-20=0,取 x0 = 1.5, 证明迭代法,是线性收敛,证 令 f (x) = x3 + 10 x 20, 绘出 y = f(x) 图形可知 方程的根 x*1.5, 令,求导数, 得,利用Lagrange中值定理, 有,其中, 介于xk和x*之间. 所以,由此可知,这一序列的收敛阶数为1,即迭代法是线性收敛.,显然,在x*附近,定理2.6,而 则 p 阶收敛。,证 因为 ，所以迭代过程局部收敛。由Taylor公式,其中, 介于xk和x*之间.所以,故迭代法p阶收敛.,迭代公式的加速,迭代公式 产生的数列xk有时收敛得很慢。令新的迭代函数为,要得到收敛速度更快的迭代函