《计算方法第二章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), ,二、误差估计,定理
4、2.1:给定方程 f(x)=0,设 f(x)在区间a,b上连续,且f(a)f(b)0,则由二分法产生的序列xk收敛于方程的根x*,且具有误差估计:,三、收敛准则,1.事先误差估计:,利用误差估计定理,令,得,从而得到对分次数k,取xk作为根得近似值x*。,2.事后误差估计:,给定,每步检查 ,若成立,则取 ,否则继续对分。,Remark3:二分法的优点是方法及相应的程序均简单,且对f(x)性质要求不高,只要连续即可。但二分法不能用于求复数根和偶数重根,且收敛速度比较慢。因此,一般常用该方法求根的初始近似值,然后再用其它的求根方法精确化。,Remark2:也可以使用 来控制误差。,Remark1
5、:由于 , 故也可以用 来控制误差。(最常用),定义f (x),f (a) f (b)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),取
6、初值,计算结果如下:,上面的结果表明,不同的等价变形构造出来 的迭代格式,有的收敛,有的不收敛。,Remark:可以通过不同的途径将f(x)=0化为 的形式,从而构造不同的迭代公式,得到不同的迭代序列。在所有这些构造的迭代公式中形成的序列中,有的序列是收敛的,而有些是发散的。,问题:如何选取合适的迭代函数 ? 迭代函数 应满足什么条件,序列xk收敛? 怎样加速序列xk的收敛?,2.迭代法的收敛定理,(2)对任意初值x0a,b, 迭代公式 收敛,且,则有:,定理2.2 (全局收敛定理)设方程 ,如果满足,(3)存在常数0L1,使对任意,(1)迭代函数 在区间a,b具有一阶连续导函数;,(2)当x
7、a,b时, ;,(1)方程 在区间a,b上有惟一的根 ;,(3)误差估计,(4),证明:,由于 上连续,作辅助函数,故由连续函数的介值定理知,至少存在,又设,即 有唯一的根。,(1) 先证方程根的存在性。,,即 是方程 的根。,故由拉格朗日中值定理知,,(2)由拉格朗日中值定理,有,因,其中介于 之间,故有,(3)由,(4)由,证毕,由于 连续,且 (因为 介于 和 之间),所以有:,得,3.迭代法的局部收敛定理,迭代法的全局收敛性定理给出的是区间a,b上的收敛性,称之为全局收敛性,一般不易验证,并且在较大的隔根区间上此定理的条件不一定成立,而只能在根的一个较小的邻域内成立。下面给出局部收敛定
8、理:,定理2.3(局部收敛定理)设存在方程 根 的闭邻域 以及小于1的正数 L,使得 连续且 则对任意 ,迭代 收敛,将前述定理1中的a,b取为 ,则只需证明 即可。,证明:,证毕,故,当x ,即 时,由Lagrange中值定理有:,其中在x与x*之间,即 。,Remark2:可以证明,若在根 的邻域中 ,则可以以邻域内任何一点 为初始值,用迭代过程产生的序列就一定不会收敛于 。事实上,,Remark3:当 不取在 的邻域内时可能不收敛。,Remark1:全局与局部收敛定理中的条件都是充分 条件,条件满足则迭代法收敛,不满足则不能判定, 此时可以用试算来判定迭代法的是收敛性。,Remark4:
9、全局收敛定理中的两个误差估计式实际上 给出了迭代收敛的两个准则:事后误差估计与事先误 差估计(利用估计式可以预先求出迭代次数k)。,4.迭代收敛准则,方法一、事先误差估计法,方法二、事后误差估计法,先计算满足误差要求的迭代次数k,再进行迭代。,有,由,由,因此可以用 来控制迭代过程。,只要使 ,就可使 ,,对于较为复杂的迭代函数,其导数也较为复杂,使得L难以取得,因而实际中不常用此方法。,Remark1:迭代方法的优点是计算程序简单,并且虽然是以求解非线性方程的实根来讨论的,但类似的结果完全可以推广到求方程的复数根的情形。,Remark2:由全局收敛定理知,若L1,则xk必然收敛较慢;若L1,
10、则收敛速度快。,输出,结束,k=k+1,是,否,算法(迭代法),已到最大迭代次数,否,二、迭代法的收敛阶,若01称为超线性收敛;p2称为平方收敛(二次收敛)。 p 越大,收敛速度越快;反之,p越小,收敛速度就越慢。因此,迭代法的收敛阶是对迭代法收敛速度的一种度量。,( C称为渐近误差常数),定义:设 收敛于 ,令迭代误差 ,如果存在实数 及非零正常数C使得,则称该迭代过程以及该迭代式是p阶收敛的,也称相应的迭代法是p阶方法。,三、迭代法的加速,对于收敛的迭代序列,理论上迭代次数足够多时,就可以使计算结果满足任意给定的精度要求但在应用中,有的迭代过程收敛极为缓慢,计算量很大,因此研究迭代格式的加
11、速方法非常必要,1.线性收敛序列的Aitken加速法,设 是一个线性收敛的序列,即有小于1的正常数c使得:,从上式可以看出,右端第二项是对 的一种补偿。,当k充分大时,有,于是有,解得:,上述公式得到的序列同样收敛于 ,而且收敛更快。,2. Steffensen(斯蒂芬森)迭代法,将Aitken加速方法用于简单迭代法产生迭代序列时,得到著名的Steffensen迭代法,具体迭代公式如下:,可以证明Steffensen迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限,但Steffensen迭代法收敛速度更快,可以达到二阶收敛。,教材例2.5给出了用Steffensen迭代法求 解的一个
12、例子,可以看出其明显比简单迭代法收敛快。,一、Newton迭代法基本思想与Newton-Raphson公式,取前两项近似代替 得近似 的线性方程,2.3 Newton迭代法,设 是 的一个近似根,则,基本思想:将非线性方程转化为线性方程来求解。,由 知 是 处 的 切线 与 轴交点的横坐标,,故Newton法的几何意义是逐次用切线代替曲线, 求切线与横坐标轴的交点。 Newton法亦称为切线法。(如下图),x*,x0,x1,x2,Newton迭代法逼近过程,证明:(1)先证Nowton迭代法满足迭代法局部收敛定理的两个条件。,1.局部收敛性,故,(x)在x*的邻域可导。,由迭代函数 得:,定理
13、2.4(Newton迭代法局部收敛定理) 设 为 的单根,在 的邻域上 连续。则存在 ,当 时,Nowton迭代法产生的序列 至少二阶收敛。,二、Newton迭代法的收敛性,显然又有,根据连续函数的性质,一定存在x*的某个闭邻域 ,对于任意的 ,有,因此Nowton迭代法满足局部收敛性。,(2)下面证明Nowton迭代法二阶收敛。,将f(x)在xk处作一阶Taylor展开,,其中k在x与xk之间。因为x, xka,b,所以k(a,b)。,Remark:上述定理对于初值x0的要求比较高,只有当初值选的充分靠近 时,才能保证序列收敛。,将x=x*代入上式,有,于是有,由收敛阶定理知,牛顿迭代法至少
14、二阶收敛。,2.非局部收敛性,定理(Newton迭代法的非局部收敛性):设x*是方程f(x)=0在隔根区间a,b内的根,如果满足,(2)取 使,(1)对于xa,b, 连续且不变号;,则由Newton迭代公式产生的数列收敛于根x*。,Remark:定理的几何解释见下图。满足定理条件的情况只有4种。,证明:仅就图(c)的情况进行证明。此时,有,要证 ,应证数列xk单调递增上有界。,(1)用数学归纳法证明数列上有界,即证xkx*。,k0时,xkx*成立。,一般的,设xkx*成立,再证xk1x*成立即可。,将f(x)在xk处作一阶Taylor展开,,其中k在x与xk之间。因为x, xka,b,所以k(
15、a,b)。,将x=x*代入上式,有,于是有,由已知条件知,上式右端第二项小于零,从而有xk1x*成立。,故由数学归纳法知,xkx*(k=0,1,2,)成立。,(2)再证明数列单调递增。,因为 ,所以 ,,于是Newton迭代公式,中的第二项小于零,从而有,于是,即数列xk是单调递增有上界的数列,且上界为x*。,设该数列的极限为A,则对Newton迭代公式两边取极限,有,从而得 f(A)=0。,因为方程f(x)=0在隔根区间a,b中只有一个根,故Ax*,即,(3)证明 。,证毕,3.例题,用Newton迭代法建立平方根 的迭代公式。,解:,令 ,则x2-c=0,这样把开平方问题转化为求方程 f(
16、x)=x2-c=0 的正根。,Newton迭代公式为:,容易证明,只要选取初值x00,则可以保证Newton迭代法的收敛性。 #,三、牛顿迭代法的变形,Newton迭代优点: 格式构造容易; 迭代收敛速度快; Newton迭代缺点: 对初值的选取比较敏感,要求初值充 分接近真解; 对重根收敛速度较慢; 当函数复杂时,导数计算工作量大,1牛顿下山法,若序列 满足: ,则称 为 的下山序列。,牛顿迭代法中,初值的选取直接影响到迭代结果,如果初值选择的离方程的根较远,牛顿迭代法甚至不收敛。牛顿下山法是一种降低对初值要求的改进的牛顿迭代法。,引入下山因子 ,将牛顿迭代法修改为:,适当选择下山因子 ,使
17、得 成立。,取,下山因子 选取方法:试算法,如果找到合适的 ,则“下山成功”;否则,“下山失败”。,牛顿下山法计算步骤如下:,(1)选取初始近似值x0;,(2)取下山因子 = 1;,(3)计算,(4)计算f (xk+1),并比较 与 的大小,分以下二种情况:,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。,
链接地址:https://www.31doc.com/p-2075020.html