方程求根的迭代法.ppt

方程求根的迭代法现在学习的是第1页，共51页本章处理本章处理n二分法和牛顿法在第二节课已讲过。二分法和牛顿法在第二节课已讲过。n加深算法收敛性方面的理解。加深算法收敛性方面的理解。n介绍几种新方法。介绍几种新方法。现在学习的是第2页，共51页引言 在在科科学学研研究究和和工工程程设设计计中中,经经常常会会遇遇到到的的一一大大类类问问题题是是非非线线性方程性方程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)当且当且仅仅当当现在学习的是第3页，共51页记笔记记笔记 当当f(x)不是不是x的的线线性函数性函数时时，称，称对应对应的函数方程的函数方程为为非非线线性性方程。如果方程。如果f(x)是多是多项项式函数，式函数，则则称称为为代数方程代数方程，否，否则则称称为为超越方程超越方程（三角方程，指数、（三角方程，指数、对对数方程等）。一般称数方程等）。一般称n次多次多项项式构成的方程式构成的方程 为为n次代数方程次代数方程,当当n1时时,方程方程显显然是非然是非线线性的性的 一般稍微复一般稍微复杂杂的的3次以上的代数方程或超越方程次以上的代数方程或超越方程,很很难难甚甚至无法求得精确解。本章将介至无法求得精确解。本章将介绍绍常用的求解非常用的求解非线线性方程的性方程的近似根的几种数近似根的几种数值值解法解法 现在学习的是第4页，共51页数值解法步骤n n判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有判定根的存在性。即方程有没有根？如果有n n 根，有几个根？根，有几个根？根，有几个根？根，有几个根？n n 确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔确定根的分布范围。即将每一个根用区间隔n n 离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的离开来，这个过程实际上是获得方程各根的n n 初始近似值。初始近似值。初始近似值。初始近似值。n n 根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法根的精确化。将根的初始近似值按某种方法n n 逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止逐步精确化，直到满足预先要求的精度为止 现在学习的是第5页，共51页二分法（略）n复习作业题现在学习的是第6页，共51页不动点迭代不动点迭代 对于一般的非线性方程对于一般的非线性方程,没有通常所说的求根公没有通常所说的求根公式求其精确解式求其精确解,需要设计近似求解方法需要设计近似求解方法,即即迭代法迭代法。它。它是一种逐次逼近的方法是一种逐次逼近的方法,用某个用某个固定公式反复校正固定公式反复校正根的近根的近似值似值,使之逐步精确化，最后得到满足精度要求的结果。使之逐步精确化，最后得到满足精度要求的结果。迭代法的迭代法的基本思想基本思想 为求解非线性方程为求解非线性方程f(x)=0f(x)=0的根，先将其写成便于迭的根，先将其写成便于迭代的等价方程代的等价方程 其中其中 为为x x的连续函数的连续函数现在学习的是第7页，共51页即如果数即如果数 使使f(x)=0,则则也有也有 ,反之反之,若若 ,则则也有也有 ,称称 为为迭代函数迭代函数 任取一个初任取一个初值值 ,代入式代入式 的右端的右端,得到得到 再将再将 代入式代入式 的右端的右端,得到得到 ,依此依此类类推推,得到一个数列得到一个数列 ，其一般表示其一般表示 称称为为求解非求解非线线性方程的性方程的简单简单迭代法。迭代法。现在学习的是第8页，共51页如果由迭代格式如果由迭代格式 产产生的序列生的序列 收收敛敛,即即 则则称称迭代法收迭代法收敛敛。实实际际计计算算中中当当然然不不可可能能也也没没必必要要无无穷穷多多步步地地做做下下去去,对预对预先先给给定的精度要求定的精度要求，只要某个只要某个k满满足足即可即可结结束束计计算并取算并取 当然，迭代函数当然，迭代函数 的构造方法是多种多的构造方法是多种多样样的。的。现在学习的是第9页，共51页例例1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根附近的一个根解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 相应地可得到两个迭代公式相应地可得到两个迭代公式如果取初始值如果取初始值 1.51.5，用上述两个迭代公式分别，用上述两个迭代公式分别迭代，计算结果迭代，计算结果现在学习的是第10页，共51页kxk012345671.51.357211.330861.325881.324941.324761.324731.32472现在学习的是第11页，共51页几何意义 通常将方程通常将方程f(x)=0化化为为与它同解的方程与它同解的方程的方法不止一种的方法不止一种,有的收有的收敛敛,有的不收有的不收敛敛,这这取决于取决于 的的性性态态,方程方程 的求根的求根问题问题在几何上就是确定曲在几何上就是确定曲线线y=与直与直线线y=x的交点的交点P*的横坐的横坐标标(a)(b)现在学习的是第12页，共51页几何意义现在学习的是第13页，共51页 对对方程方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式,但迭代公式但迭代公式并非并非总总是收是收敛敛。那么。那么,当迭代函数当迭代函数 满满足什么条件足什么条件时时，相，相应应的迭代公式才收的迭代公式才收敛敛呢？即使迭代收呢？即使迭代收敛时敛时，我，我们们也不可能迭代也不可能迭代很多次，而是迭代有限次后就停止，很多次，而是迭代有限次后就停止，这这就需要估就需要估计计迭代迭代值值的的误误差，以便适差，以便适时终时终止迭代止迭代。不动点迭代收敛性现在学习的是第14页，共51页定理定理1，2 设设函数函数 在在a,b上具有上具有连续连续的一的一阶导阶导 数数,且且满满足足 （1）对对所有的所有的xa,b 有有 a,b （2）存在存在 0 L 1,使所有的使所有的xa,b有有 L则则方程方程 在在a,b上的解上的解 存在且唯一存在且唯一，对对任意的任意的 a,b，迭代迭代过过程程均收均收敛敛于于 。并有。并有误误差估差估计计式式 现在学习的是第15页，共51页由由连续连续函数介函数介值值定理知定理知,必有必有 a,b,使使 所以有解存在所以有解存在,即即假假设设有两个解有两个解 和和 ,a,b，则则，由微分中由微分中值值定理有定理有其中其中是介于是介于x*和和 之之间间的点的点 从而有从而有a,b，进进而有而有 由条件由条件(2)有有 1,所以所以 -=0，即，即 =，解唯一。，解唯一。证证:构造函数构造函数 ,由条件（由条件（1）对对任意的任意的xa,b a,b有有现在学习的是第16页，共51页按迭代过程按迭代过程 ,有有 由于由于L1,L0），使 则称序列 是 p 阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a=x0现在学习的是第34页，共51页yx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离根不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况的情况而找不到根或死循环的情况现在学习的是第35页，共51页例例 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)建立迭代公式建立迭代公式现在学习的是第36页，共51页 牛顿下山法牛顿下山法 通常通常,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取,如如果果 偏离所求的根偏离所求的根 比较远比较远,则则牛顿法可能发散牛顿法可能发散。为了。为了防止迭代发散防止迭代发散,我们对牛顿迭代法的迭代过程再附加一项我们对牛顿迭代法的迭代过程再附加一项要求要求,即具有即具有单调性单调性 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用,即在下山法即在下山法保证函数值下降的前提下保证函数值下降的前提下,用牛顿迭代法加快收敛速度。用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。其中其中(01)(01)为下山因子为下山因子 现在学习的是第37页，共51页 下下山山因因子子的的选选择择是是个个逐逐步步探探索索的的过过程程，设设从从=1=1开始反复将开始反复将减半进行试算减半进行试算,即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性条件使单调性条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。现在学习的是第38页，共51页重根情形重根情形现在学习的是第39页，共51页现在学习的是第40页，共51页kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562现在学习的是第41页，共51页 牛牛顿顿迭代法迭代法虽虽然具有收然具有收敛敛速度快的速度快的优优点，但每迭代点，但每迭代一次都要一次都要计计算算导导数数 ,当当 比比较较复复杂时杂时,不不仅仅每次每次计计算算 带带来很多不便，而且来很多不便，而且还还可能十分麻可能十分麻烦烦，如果用不，如果用不计计算算导导数的迭代方法，往往只有数的迭代方法，往往只有线线性收性收敛敛的速度。本的速度。本节节介介绍绍的弦截法便是一种不必的弦截法便是一种不必进进行行导导数运算的求根方法。弦截数运算的求根方法。弦截法在迭代法在迭代过过程中不程中不仅仅用到前一步用到前一步 处处的函数的函数值值，而且，而且还还使用使用 处处的函数的函数值值来构造迭代函数，来构造迭代函数，这样这样做能提高迭做能提高迭代的收代的收敛敛速度。速度。弦截法现在学习的是第42页，共51页 弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用，使用差商差商 替替代代牛牛顿顿公公式式中中的的导导数数 ,便便得得到到迭迭代代公式公式 称为弦截迭代公式，称为弦截迭代公式，相应的迭代法称为弦截法相应的迭代法称为弦截法。现在学习的是第43页，共51页弦截法几何意弦截法几何意义义弦截法也称割弦截法也称割线线法法,其几何意其几何意义义是用是用过过曲曲线线上两点上两点 、的割的割线线来代替曲来代替曲线线,用割用割线线与与x轴轴交点的交点的横座横座标标作作为为方程的近似根方程的近似根 再再过过P1点和点点和点 作割作割线线求出求出 ,再再过过P2点和点点和点 作割作割线线求出求出 ,余此余此类类推，当收推，当收敛时敛时可求出可求出满满足精度要求的足精度要求的现在学习的是第44页，共51页 可以证明，弦截法具有超线性收敛，收敛的阶可以证明，弦截法具有超线性收敛，收敛的阶约为约为1.6181.618，它与前面介绍的一般迭代法一样都是线，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算性化方法，但也有区别。即一般迭代法在计算 时时只用到前一步的值只用到前一步的值 ，故称之为，故称之为单点迭代法单点迭代法；而弦；而弦截法在求截法在求 时要用到前两步的结果时要用到前两步的结果 和和 ，使用这，使用这种方法必须给出两个初始近似根种方法必须给出两个初始近似根 ，这种方法称，这种方法称为为多点迭代法。多点迭代法。现在学习的是第45页，共51页例例 9 9 用弦截法求方程用弦截法求方程 在在 初初始始 值邻近的一个根。要求值邻近的一个根。要求解：取解：取 ,令令 利用弦截迭代公式利用弦截迭代公式 计算结果，计算结果，易见取近似根易见取近似根 则可满足精度要求。则可满足精度要求。现在学习的是第46页，共51页 弦弦截截法法算算法法实实现现 现在学习的是第47页，共51页 抛物线法抛物线法现在学习的是第48页，共51页 解非线性方程组的迭代法解非线性方程组的迭代法现在学习的是第49页，共51页现在学习的是第50页，共51页现在学习的是第51页，共51页