计算方法第二章ppt.ppt

《计算方法第二章ppt.ppt》由会员分享，可在线阅读，更多相关《计算方法第二章ppt.ppt（54页珍藏版）》请在三一办公上搜索。

1、第二章 方程的近似解法,2.0 引 言 2.1 二分法（对分法）2.2 简单迭代法2.3 Newton迭代法及其变形,2.1 引言,求解非线性方程 f(x)=0,一、问题,困难：方程的解难以用公式表达。,例如:1)多项式方程：,需要一定精度的近似解！,2)超越方程:,二、概念,设在区间a,b上方程有一个根，则称该区间为方程的一个有根区间。若在区间a,b上方程只有一个根，则称该区间为方程隔根区间。,Remark：若能把隔根区间不断缩小，则可以得出根的近似值。,三、根的隔离,基于函数f(x)的连续性质，常用的根的隔离的方法有：描图法与逐步搜索法。,1、描图法：画出y=f(x)的简图，从曲线与x轴交

2、点的位置确定出隔根区间，或者将方程等价变形为g1(x)=g2(x)，画出函数y=g1(x)和y=g2(x)的简图，从两条曲线交点的横坐标的位置确定隔根区间。,2、逐步搜索法：先确定方程f(x)=0的所有实根所在区间a,b，再按照选定的步长（n为正整数），取点xk=a+kh(k=0,1,n)，逐步计算函数值f(xk)，依据函数值异号以及实根的个数确定隔根区间。必要时可调整步长h，总可把隔根区间全部找出。,3、根据函数单调性判断,2.1 二分法（对分法）,一、算法,设 在a,b上连续，f(a)f(b)0且在a,b内f(x)=0仅有一个实根。二分法的基本思想是：逐步将有根区间分半，通过判别函数值的符

3、号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根 的近似值。,执行步骤：,1计算f(x)在有解区间a,b端点处的值，f(a)，f(b)。,2计算f(x)在区间中点处的值f(x1)。,3判断若f(x1)=0，则x1即是根，否则检验：,（1）若f(x1)与f(a)异号，则知解位于区间a,x1，b1=x1,a1=a;,（2）若f(x1)与f(a)同号，则知解位于区间x1,b，a1=x1,b1=b。,4.反复执行步骤2、3，便可得到一系列有根区间：(a,b),(a1,b1),(ak,bk),二、误差估计,定理2.1：给定方程 f(x)=0，设 f(x)在区间a,b上连续，且f(

4、a)f(b)0，则由二分法产生的序列xk收敛于方程的根x*，且具有误差估计：,三、收敛准则,1.事先误差估计：,利用误差估计定理，令,得,从而得到对分次数k，取xk作为根得近似值x*。,2.事后误差估计：,给定，每步检查，若成立，则取，否则继续对分。,Remark3：二分法的优点是方法及相应的程序均简单，且对f(x)性质要求不高，只要连续即可。但二分法不能用于求复数根和偶数重根，且收敛速度比较慢。因此，一般常用该方法求根的初始近似值，然后再用其它的求根方法精确化。,Remark2：也可以使用 来控制误差。,Remark1：由于，故也可以用 来控制误差。（最常用）,定义f(x),f(a)f(b)

5、0,f(a)f(b)=0,f(a)=0,打印b,k,打印a,k,结束,是,是,是,否,否,否,m=(a+b)/2,|a-b|,f(a)f(m)0,打印m,k,a=m,b=m,结束,k=K+1,是,是,否,否,输入,k=0,算法(二分法),2.2 迭代法,即序列 的极限 为 的根。,一、迭代法,1.基本思想：,因此，我们可以通过求迭代数列的极限的方法来求得方程f(x)=0的根，该方法称为简单迭代法。,例试为方程,解利用方程的等价变形建立如下4种迭代公式(1)(2)(3)(4),取初值,计算结果如下：,上面的结果表明，不同的等价变形构造出来的迭代格式，有的收敛，有的不收敛。,Remark：可以通过

6、不同的途径将f(x)=0化为 的形式，从而构造不同的迭代公式，得到不同的迭代序列。在所有这些构造的迭代公式中形成的序列中，有的序列是收敛的，而有些是发散的。,问题：如何选取合适的迭代函数？迭代函数 应满足什么条件，序列xk收敛？怎样加速序列xk的收敛？,2.迭代法的收敛定理,（2）对任意初值x0a,b,迭代公式 收敛，且,则有：,定理2.2(全局收敛定理)设方程，如果满足,（3）存在常数0L1,使对任意,（1）迭代函数 在区间a,b具有一阶连续导函数；,（2）当xa,b时，；,（1）方程 在区间a,b上有惟一的根；,（3）误差估计,（4）,证明：,由于 上连续，作辅助函数,故由连续函数的介值定

7、理知，至少存在,又设,即 有唯一的根。,(1)先证方程根的存在性。,，即 是方程 的根。,故由拉格朗日中值定理知，,（2）由拉格朗日中值定理,有,因,其中介于 之间，故有,（3）由,（4）由,证毕,由于 连续，且（因为 介于 和 之间），所以有：,得,3.迭代法的局部收敛定理,迭代法的全局收敛性定理给出的是区间a,b上的收敛性，称之为全局收敛性，一般不易验证，并且在较大的隔根区间上此定理的条件不一定成立，而只能在根的一个较小的邻域内成立。下面给出局部收敛定理：,定理2.3(局部收敛定理)设存在方程 根 的闭邻域 以及小于1的正数 L，使得 连续且 则对任意，迭代 收敛,将前述定理1中的a,b取

8、为，则只需证明 即可。,证明：,证毕,故,当x，即 时，由Lagrange中值定理有:,其中在x与x*之间，即。,Remark2：可以证明，若在根 的邻域中，则可以以邻域内任何一点 为初始值，用迭代过程产生的序列就一定不会收敛于。事实上，,Remark3：当 不取在 的邻域内时可能不收敛。,Remark1：全局与局部收敛定理中的条件都是充分条件，条件满足则迭代法收敛，不满足则不能判定，此时可以用试算来判定迭代法的是收敛性。,Remark4：全局收敛定理中的两个误差估计式实际上给出了迭代收敛的两个准则：事后误差估计与事先误差估计（利用估计式可以预先求出迭代次数k）。,4.迭代收敛准则,方法一、事

9、先误差估计法,方法二、事后误差估计法,先计算满足误差要求的迭代次数k，再进行迭代。,有,由,由,因此可以用 来控制迭代过程。,只要使，就可使，,对于较为复杂的迭代函数，其导数也较为复杂，使得L难以取得，因而实际中不常用此方法。,Remark1:迭代方法的优点是计算程序简单，并且虽然是以求解非线性方程的实根来讨论的，但类似的结果完全可以推广到求方程的复数根的情形。,Remark2：由全局收敛定理知，若L1，则xk必然收敛较慢；若L1，则收敛速度快。,输出,结束,k=k+1,是,否,算法(迭代法),已到最大迭代次数,否,二、迭代法的收敛阶,若01称为超线性收敛；p2称为平方收敛（二次收敛）。p 越

10、大，收敛速度越快；反之，p越小，收敛速度就越慢。因此，迭代法的收敛阶是对迭代法收敛速度的一种度量。,（C称为渐近误差常数）,定义：设 收敛于，令迭代误差，如果存在实数 及非零正常数C使得,则称该迭代过程以及该迭代式是p阶收敛的，也称相应的迭代法是p阶方法。,三、迭代法的加速,对于收敛的迭代序列，理论上迭代次数足够多时，就可以使计算结果满足任意给定的精度要求但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因此研究迭代格式的加速方法非常必要,1.线性收敛序列的Aitken加速法,设 是一个线性收敛的序列，即有小于1的正常数c使得：,从上式可以看出，右端第二项是对 的一种补偿。,当k充分大时，有,

11、于是有,解得：,上述公式得到的序列同样收敛于，而且收敛更快。,2.Steffensen(斯蒂芬森)迭代法,将Aitken加速方法用于简单迭代法产生迭代序列时，得到著名的Steffensen迭代法，具体迭代公式如下：,可以证明Steffensen迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限，但Steffensen迭代法收敛速度更快，可以达到二阶收敛。,教材例2.5给出了用Steffensen迭代法求解的一个例子，可以看出其明显比简单迭代法收敛快。,一、Newton迭代法基本思想与Newton-Raphson公式,取前两项近似代替 得近似 的线性方程,2.3 Newton迭代法,设

12、是 的一个近似根，则,基本思想：将非线性方程转化为线性方程来求解。,由 知 是 处 的切线 与 轴交点的横坐标，,故Newton法的几何意义是逐次用切线代替曲线，求切线与横坐标轴的交点。Newton法亦称为切线法。（如下图）,x*,x0,x1,x2,Newton迭代法逼近过程,证明：（1）先证Nowton迭代法满足迭代法局部收敛定理的两个条件。,1.局部收敛性,故，(x)在x*的邻域可导。,由迭代函数 得:,定理2.4(Newton迭代法局部收敛定理)设 为 的单根，在 的邻域上 连续。则存在，当 时，Nowton迭代法产生的序列 至少二阶收敛。,二、Newton迭代法的收敛性,显然又有,根据

13、连续函数的性质，一定存在x*的某个闭邻域，对于任意的，有,因此Nowton迭代法满足局部收敛性。,（2）下面证明Nowton迭代法二阶收敛。,将f(x)在xk处作一阶Taylor展开，,其中k在x与xk之间。因为x，xka,b,所以k(a,b)。,Remark：上述定理对于初值x0的要求比较高，只有当初值选的充分靠近 时，才能保证序列收敛。,将x=x*代入上式，有,于是有,由收敛阶定理知，牛顿迭代法至少二阶收敛。,2.非局部收敛性,定理（Newton迭代法的非局部收敛性）：设x*是方程f(x)=0在隔根区间a,b内的根，如果满足,（2）取 使,（1）对于xa,b，连续且不变号；,则由Newto

14、n迭代公式产生的数列收敛于根x*。,Remark：定理的几何解释见下图。满足定理条件的情况只有4种。,证明：仅就图(c)的情况进行证明。此时，有,要证，应证数列xk单调递增上有界。,（1）用数学归纳法证明数列上有界，即证xkx*。,k0时，xkx*成立。,一般的，设xkx*成立，再证xk1x*成立即可。,将f(x)在xk处作一阶Taylor展开，,其中k在x与xk之间。因为x，xka,b,所以k(a,b)。,将x=x*代入上式，有,于是有,由已知条件知，上式右端第二项小于零，从而有xk1x*成立。,故由数学归纳法知，xkx*（k=0,1,2,）成立。,(2)再证明数列单调递增。,因为，所以，,

15、于是Newton迭代公式,中的第二项小于零，从而有,于是,即数列xk是单调递增有上界的数列，且上界为x*。,设该数列的极限为A，则对Newton迭代公式两边取极限，有,从而得 f(A)=0。,因为方程f(x)=0在隔根区间a,b中只有一个根，故Ax*，即,（3）证明。,证毕,3.例题,用Newton迭代法建立平方根 的迭代公式。,解：,令，则x2-c=0，这样把开平方问题转化为求方程 f(x)=x2-c=0 的正根。,Newton迭代公式为：,容易证明，只要选取初值x00，则可以保证Newton迭代法的收敛性。#,三、牛顿迭代法的变形,Newton迭代优点：格式构造容易；迭代收敛速度快；New

16、ton迭代缺点：对初值的选取比较敏感，要求初值充 分接近真解；对重根收敛速度较慢；当函数复杂时，导数计算工作量大,1牛顿下山法,若序列 满足：，则称 为 的下山序列。,牛顿迭代法中，初值的选取直接影响到迭代结果，如果初值选择的离方程的根较远，牛顿迭代法甚至不收敛。牛顿下山法是一种降低对初值要求的改进的牛顿迭代法。,引入下山因子，将牛顿迭代法修改为：,适当选择下山因子，使得 成立。,取,下山因子 选取方法：试算法,如果找到合适的，则“下山成功”；否则，“下山失败”。,牛顿下山法计算步骤如下：,（1）选取初始近似值x0；,（2）取下山因子=1；,（3）计算,（4）计算f(xk+1)，并比较 与 的

17、大小，分以下二种情况：,1）若，则当 时，取x*xk+1，计算过程结束;当 时，则把xk+1作为新的xk值，并重复回到（3）。,当；且，则将下山因子缩小一半，取/2代入，并转向（3）重复计算。,例5：求方程f(x)=x3 x 1=0 的根,牛顿下山法的计算结果：,2针对重根情形的加速算法,设 是方程的m 重根，并且存在函数，使得,可见，此时牛顿迭代法仅为线性收敛,法1：令,法2：,为加速收敛，可以采取如下两种方法：,3、单点弦截法：,牛顿法一步要计算 f 和 f，相当于2个函数值。现用 f 的值近似 f:,切线,割线,切线斜率割线斜率,4、双点弦截法：,切线斜率割线斜率,需要2个初值 x0 和 x1。,