计算方法第七章ppt课件.ppt

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

1、,第7章 非线性方程与方程组的数值解法,7.1方程求根与二分法,7.2不动点迭代法及其收敛性,7.3迭代收敛的加速方法*,7.4牛顿法,7.5弦截法与抛物线法,7.6求根问题的敏感性与多项式的零点*,7.7非线性方程组的数值解法*,2,在科学研究和工程设计中, 经常会遇到的一大类问题是非线性方程f(x)=0 (7.1)的求根问题，其中f(x)为非线性函数。 方程f(x)=0的根, 亦称为函数f(x)的零点。 如果f(x)可以分解成 ,其中m为正整数且 ,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。若f(x)存在m阶导数,则是方程f(x)的m重根(m1)

2、当且仅当,7.1 方程求根与二分法,3,非线性方程的概念,4,求根步骤,通常方程根的数值解法大致分为三个步骤进行判定根的存在性。即方程有没有根？如果有 根，有几个根？ 确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。 根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止,5,二分法,二分法又称二分区间法,是求解方程(7.1)的近似根的一种常用的简单方法。 设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,根据连续函数的性质可知, f(x)= 0在(a,b)内必有实根,称区间a,b为有根区间。为明确起见,假定方程f(x

3、)=0在区间a,b内有惟一实根x*。 二分法的基本思想是: 首先确定有根区间,将区间二等分, 通过判断f(x)的符号, 逐步将有根区间缩小, 直至有根区间足够地小, 便可求出满足精度要求的近似根。,6,有根区间的确定,为了确定根的初值，首先必须圈定根所在的范围， 称为圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲,是求曲线 y=f (x)与 x轴交点的横坐标。,7,有根区间的确定,由高等数学知识知, 设f (x

4、)为区间a,b上的单值连续, 如果f (a)f (b)0 , 则a,b中至少有一个实根。如果f (x)在a,b上还是单调地递增或递减，则仅有一个实根。,大体确定根所在子区间的方法有： (1) 画图法 (2) 逐步搜索法,8,画图法,画出y = f (x)的略图，从而看出曲线与x轴交点的 大致位置。 也可将f (x) = 0分解为1(x)= 2(x)的形式，1(x) 与 2(x)两曲线交点的横坐标所在的子区间即为含根 区间。例如 xlogx-1= 0可以改写为logx=1/x画出对数曲线y=logx,与双曲线y= 1/x,它们交 点的横坐标位于区间2,3内,9,画图法,10,搜索法,11,例题,

5、12,搜索法,用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当h ，使之既能把根隔离开来，工作量 又不太大。 为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。,13,二分法求根过程, 取有根区间a,b之中点, 将它分为两半,分点 ,这样就可缩小有根区间,设方程f(x)=0在区间a,b内有根，二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下,14,二分法求根过程,15,二分法求根过程,16,二分法求根过程,17,二分法求根过程,18,二分法算法实现,19,例题,20,例题,21,小结,二分法的优点是不管有根区间

6、多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为 的等比级数相同。,22,7.2 不动点迭代法及其收敛性,对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,23,不动点迭代法的基本思想,23,为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程 (7.3)其中 为x的连续函数,24,不动点迭代法的基本思想,25,迭代法的基本思想,2

7、6,“不动点”,不动点，是一个函数术语，在数学中是指“被这个函数映射到其自身一个点”。,例如： 定义在实数上的函数f， f(x) = x2 - 3x + 4，则2是函数f的一个不动点，因为f(2) = 2。,27,例题,28,例题,29,迭代法的几何意义,通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线y= 与直线y=x的交点P*的横坐标(如图所示),(a),(b),30,迭代法的几何意义,31,迭代法收敛的条件,对方程f(x)=0可以构造不同的迭代公式, 但迭代公式并非总是收敛。那么,当迭代函数 满足什么条件

8、时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代,32,迭代法收敛的条件,定理7.1 设函数 在a,b上具有连续的一阶导 数, 且满足 （1）对所有的xa,b 有 a,b （2）存在 0 L 1 ,使所有的xa,b有 L则方程 在a,b上的解 存在且唯一，对任意的 a ,b ，迭代过程均收敛于 。并有误差估计式,33,迭代法收敛的条件,34,迭代法收敛的条件,由连续函数介值定理知, 必有 a, b, 使 所以有解存在, 即假设有两个解 和 , , a, b，则 ，,证: 构造函数 ,由条件对任意的xa, b

9、a, b有,35,迭代法收敛的条件,36,迭代法收敛的条件,再证误差估计式,37,迭代法收敛的条件,即 得证。,即 得证。,38,迭代法的算法框图,39,局部收敛性,当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。 定理7.2 设 在 的根 的邻域中有连续的一阶导数,且 则迭代过程 具有局部收敛性。 证:由于 ,存在充分小邻域: ,使成立 这里L为某个定数,根据微分中值定理 由于 ,又当时 ,故有由定理7.1知 对于任意的 都收敛,40,例题,例7.4 设 ,要使迭代过程 局部收敛到 ,求 的取值范围。解： 由在根 邻域具有局部收敛性时, 收敛 条件,41,例题,所以,42,

10、例题,例7.5 已知方程 在 内有根 ,且在上满足 ,利用 构造一个迭代函数,使 局部收敛于 。解:由 可得,故 ,迭代公式,局部收敛,43,收敛速度,一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。定义7.2 设迭代过程 收敛于 的根 ,记迭代误差若存在常数p（p1）和c（c0），使,则称序列 是 p 阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1 p 2时称为超线性收敛。,44,收敛速度,数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。,45,收敛阶数,定理7.3 设迭

11、代过程 , 若 在所求根 的邻域连续且 则迭代过程在 邻域是p阶收敛的。证: 由于 即在 邻域 , 所以 有局部收敛性, 将 在 处泰勒展开,根据已知条件得,46,收敛阶数,由迭代公式,及,有,47,例题,例7.6 已知迭代公式 收敛于 证明该迭代公式平方收敛。证: 迭代公式相应的迭代函数为,将 代入，,根据定理7.3可知，迭代公式平方收敛。,48,7.3 迭代收敛的加速方法,略,49,7.4 牛顿法,用迭代法可逐步精确方程 根的近似值，但必须要找到 的等价方程 ,如果 选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题。

12、这就是本节要介绍的牛顿迭代法。,牛顿迭代法一种重要和常用的迭代法, 它的基本思想是将非线性函数f(x)逐步线性化, 从而将非线性方程f(x)=0近似地转化为线性方程求解。,50,牛顿迭代公式,对于方程 ,设其近似根为 , 函数f(x)可在 附近作泰勒展开,忽略高次项,用其线性部分作为函数f(x)的近似，,设 的根 ,则有 ,即,将左端取为 ,即 是比 更接近于 的近似值,牛顿迭代公式,51,牛顿迭代法的几何解释,方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk, f (xk)引切线交x轴于xk+1 , 并

13、将其作为x*,新的近似值,重复上述过程,可见一次次用切线方程来求解方程f(x)=0的根,所以亦称为牛顿切线法。,52,牛顿迭代法的收敛性,定理7.4 设 是方程 的单根, 且f(x)在 的某邻域内有连续的二阶导数, 则牛顿法在 附近局部收敛, 且至少二阶收敛, 有,证: 牛顿迭代公式对应的迭代函数为 若 是方程 的单根,则有 , 从而,53,牛顿迭代法的收敛性,由定理7.2知,牛顿迭代法在 附近局部收敛。又由定理7.3知, 迭代公式至少具有二阶收敛速度。,利用泰勒公式,54,牛顿迭代法的收敛性,所以,证毕,55,牛顿迭代法的收敛性,X*,x2,不满足迭代条件时，可能导致迭代值远离根的情况而找不

14、到根或死循环的情况,56,牛顿迭代法的算法实现,57,例题,58,7.5 弦截法,牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数 , 当 比较复杂时, 不仅每次计算 带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步 处的函数值 ，而且还使用 处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。,59,弦截迭代公式,为避免计算函数的导数 ，使用差商 替代牛顿公式中的导数 ,便得到迭代公式 称为弦截迭代公式， 相应的迭代法称为弦截法。,60,弦截法几何意义,61,收敛速度,可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算 时只用到前一步的值 ，故称之为单点迭代法；而弦截法在求 时要用到前两步的结果 和 ，使用这种方法必须给出两个初始近似根 ，这种方法称为多点迭代法。,62,例题,63,例题,64,随堂测验,65,弦截法算法实现,66,本章习题,67,本章结束,