《方程求根的迭代法ppt课件.ppt》由会员分享，可在线阅读，更多相关《方程求根的迭代法ppt课件.ppt（50页珍藏版）》请在三一办公上搜索。
1、本章处理,二分法和牛顿法在第二节课已讲过。加深算法收敛性方面的理解。介绍几种新方法。,引言,在科学研究和工程设计中, 经常会遇到的一大类问题是非线性方程f(x)=0 的求根问题，其中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) 当且仅当,记笔记,当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数
2、方程等）。一般称n次多项式构成的方程,为n次代数方程,当n1时,方程显然是非线性的 一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法,数值解法步骤,判定根的存在性。即方程有没有根？如果有 根，有几个根？ 确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。 根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止,二分法（略）,复习作业题,不动点迭代,对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,
3、用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,迭代法的基本思想 为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程 其中 为x的连续函数,即如果数 使f(x)=0, 则也有 , 反之, 若 , 则也有 , 称 为迭代函数 任取一个初值 , 代入式 的右端, 得到,再将 代入式 的右端, 得到 ,依此类推, 得到一个数列 ， 其一般表示,称为求解非线性方程的简单迭代法。,如果由迭代格式 产生的序列 收敛,即,则称迭代法收敛。,实际计算中当然不可能也没必要无穷多步地做下去, 对预先给定的精度要求，只要某个k满足,即可结束计算并取,当然，迭代函数 的构造
4、方法是多种多样的。,例1 用迭代法求方程 在x=1.5附近的一个根解 将方程改写成如下两种等价形式,相应地可得到两个迭代公式,如果取初始值 1.5，用上述两个迭代公式分别迭代，计算结果,几何意义,通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线y= 与直线y=x的交点P*的横坐标,(a),(b),几何意义,对方程f(x)=0可以构造不同的迭代公式, 但迭代公式并非总是收敛。那么,当迭代函数 满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值
5、的误差，以便适时终止迭代 。,不动点迭代收敛性,定理1 ，2 设函数 在a,b上具有连续的一阶导 数, 且满足 （1）对所有的xa,b 有 a,b （2）存在 0 L 1 ,使所有的xa,b有 L则方程 在a,b上的解 存在且唯一，对任意的 a ,b ，迭代过程均收敛于 。并有误差估计式,由连续函数介值定理知, 必有 a, b, 使 所以有解存在, 即假设有两个解 和 , , a, b，则 ，由微分中值定理有其中是介于x*和 之间的点 从而有a,b，进而有 由条件(2)有 1, 所以 - =0，即 = ，解唯一。,证: 构造函数 ,由条件（1）对任意的xa, b a, b有,按迭代过程 ,有,
6、由于L1,所以有 ,可见L越小,收敛越快,再证误差估计式,即 得证。,即 得证。,例2 对方程 ,构造收敛的迭代格式, 求其最小正根,计算过程保留4位小数。解 容易判断1,2是方程的有根区间, 且在此区间 内 ,所以此方程在区间1,2有 且仅有一根。将原方程改写成以下两种等价形式。, ,即 不满足收敛条件。 ,即 此时迭代公式满足迭代收敛条件。,局部收敛性 当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。 定理 3 设 在 的根 的邻域中有连续的一阶导数,且 则迭代过程 具有局部收敛性。 证:由于 ,存在充分小邻域: ,使成立 这里L为某个定数,根据微分中值定理当 故有由定理
7、1知 对于任意的 都收敛,例3 设 ,要使迭代过程 局部收敛到 ,求 的取值范围。解： 由在根 邻域具有局部收敛性时, 收敛 条件,所以,例4 已知方程 在 内有根 ,且在上满足 ,利用 构造一个迭代函数,使 局部收敛于 。解:由 可得,故 ,迭代公式,局部收敛,迭代法的收敛速度 一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。定义2.2 设迭代过程 收敛于 的根 ,记迭代误差若存在常数p（p1）和c（c0），使,则称序列 是 p 阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1 p 2时称为超线性收敛。,数p的大小反映了迭代法收敛的速度
8、的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。,定理4 设迭代过程 , 若 在所求根 的邻域连续且 则迭代过程在 邻域是p阶收敛的。证: 由于 即在 邻域 , 所以 有局部收敛性, 将 在 处泰勒展开,根据已知条件得,由迭代公式,及,有,例 5 已知迭代公式 收敛于 证明该迭代公式平方收敛。证: 迭代公式相应的迭代函数为,将 代入，,根据定理4可知，迭代公式平方收敛。,为了使迭代过程收敛或提高收敛的速度, 可设法 提高初值的精度以减少迭代的次数 提高收敛的阶数 p,设 是根 的某个近似值,用迭代公式校正一次得 又 根据中值定理有,其中,当 范围不大时,设 变化
9、不大,其估计值为L,则有,可见,若将迭代值 与 加权平均,则可得到的,是比 更好的近似根,迭代法的加速（加权法）,迭代： 改进： 或合并写成：,例 6 用加权法加速技术求方程 在0.5附近的一个根。解： 因为在 附近 取L=-0.6，建立如下迭代公式,仍取 ,逐次计算得 =0.56658 =0.56714 。迭代4次便可得到精度 的结果,而不用加速技术需迭代18次,效果显著。,埃特金（Aitken）方法在加权法中, 估计L的值有时不太方便。假设在求得 以后, 先求出由 , 利用中值定理可得( 在求根区间变化不大, 用某个定值L近似地替代之)L 将迭代值 再迭代一次, 得新的迭代值则 将上述两个
10、方程联立消去常数L化简可得,这样得到埃特金加速公式,例 7 用埃特金方法求方程 在初值 附近的一个根, 精度要求,取迭代格式,解 埃特金方法迭代格式为,只迭代二次就得到满足精度要求的解。,牛顿迭代法（略讲）,基本思想是将非线性函数f(x)逐步线性化, 从而将非线性方程f(x)=0近似地转化为线性方程求解。迭代格式构建方法：泰勒公式一阶展开式。,忽略高次项,用其线性部分作为函数f(x)的近似，,牛顿迭代法的收敛性,定理4 设 是方程 的单根, 且f(x)在 的某邻域内有连续的二阶导数, 则牛顿法在 附近局部收敛, 且至少二阶收敛, 有,证: 牛顿迭代公式对应的迭代函数为 若 是方程 的单根,则有
11、 , 从而,由定理2 知,牛顿迭代法在 附近局部收敛。又由定理3 知, 迭代公式至少具有二阶收敛速度。,利用泰勒公式,所以,证毕,X*,x2,不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况,例 8 用牛顿迭代法求 x=e-x的根,=10-4,取x0=0.5,逐次计算得 x1=0.57102, x2=0.56716， x3=0.56714,解：因 f (xk)= x ex 1 , f (x)=ex ( x+1)建立迭代公式,牛顿下山法,通常,牛顿迭代法的收敛性依赖于初始值 的选取,如果 偏离所求的根 比较远,则牛顿法可能发散。为了防止迭代发散,我们对牛顿迭代法的迭代过程再附
12、加一项要求,即具有单调性,将牛顿迭代法与下山法结合起来使用,即在下山法保证函数值下降的前提下,用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即,满足这项要求的算法称下山法。,其中(01)为下山因子,下山因子的选择是个逐步探索的过程，设从=1开始反复将减半进行试算, 即逐次取为从中挑选下山因子，直至找到其中某个使单调性条件成立，则称“下山成功”，否则“下山失败”，这时需另选初值重算。,重根情形,牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数 , 当 比较复杂时, 不仅每次计算 带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截
13、法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步 处的函数值，而且还使用 处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。,弦截法,弦截法的基本思想 为避免计算函数的导数 ，使用差商 替代牛顿公式中的导数 ,便得到迭代公式 称为弦截迭代公式， 相应的迭代法称为弦截法。,弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点 、 的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根 再过,P1点和点 作割线求出 ,再过P2点和点 作割线求出 ,余此类推，当收敛时可求出满足精度要求的,可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算 时只用到前一步的值 ，故称之为单点迭代法；而弦截法在求 时要用到前两步的结果 和 ，使用这种方法必须给出两个初始近似根 ，这种方法称为多点迭代法。,例 9 用弦截法求方程 在 初始 值邻近的一个根。要求解：取 , , 令 利用弦截迭代公式 计算结果， 易见取近似根 则可满足精度要求。,弦截法算法实现,抛物线法,解非线性方程组的迭代法,
