迭代法和二分法优秀课件.ppt

《迭代法和二分法优秀课件.ppt》由会员分享，可在线阅读，更多相关《迭代法和二分法优秀课件.ppt（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、迭代法和二分法迭代法和二分法第1页，本讲稿共13页非非线线性性方方程程就就是是因因变变量量与与自自变变量量之之间间的的关关系系不不是是线线性性的的关关系系，这这类类方方程程很很多多，例例如如平平方方关关系系、对对数数关关系系、指指数数关关系系、三三角角函函数数关关系系等等等等。求求解解此此类类方方程程往往往很难得到精确解，经常需要求近似解问题。往很难得到精确解，经常需要求近似解问题。解解决决此此问问题题的的最最主主要要的的两两种种方方法法是是迭迭代代法法和和二分法二分法。第2页，本讲稿共13页1、定义、定义迭迭代代法法逐逐次次逼逼近近的的方方法法，在在工工程程技技术术上上也也叫叫做做试试算算法

2、法。从从隔隔根根区区间间（a0，b0）中中的的任任一一个个初初始始近似值近似值x0出发，按照某种格式构造一个序列出发，按照某种格式构造一个序列x0，x1，x2，使得这个序列的极限就是使得这个序列的极限就是f(x)=0的跟的跟x*，即，即另一种方法是把方程另一种方法是把方程f(x)=0写成等价形式写成等价形式x=(x)，然后令然后令xk+1=(xk)k=0,1,2，第3页，本讲稿共13页2、算法核心、算法核心参数说明：参数说明：x0开开始始存存放放初初始始值值，迭迭代代中中存存放放第第k次次近近似似值值（实型变量，输入参数）；（实型变量，输入参数）；x迭迭代代中中存存放放第第k+1次次近近似似值

3、值，最最终终存存放放方方程程的跟（实型变量，输出参数）；的跟（实型变量，输出参数）；eps根的精度控制量（实型变量，输出参数）。根的精度控制量（实型变量，输出参数）。时，认为时，认为xk+1是方程的跟。是方程的跟。第4页，本讲稿共13页3、迭代法的收敛性、迭代法的收敛性如如果果从从初初值值x0出出发发，按按照照迭迭代代公公式式进进行行迭迭代代计计算算的的过过程程中中，xk逐逐次次接接近近于于方方程程的的跟跟，则则称称迭迭代代公公式式是是收收敛敛的的，否否则则是是发发散散的的。迭迭代代法法可可行行的的必必要要条条件件是迭代过程必须收敛，收敛越快，则其收敛性越好。是迭代过程必须收敛，收敛越快，则其

4、收敛性越好。判判别别条条件件迭迭代代函函数数的的一一阶阶导导数数在在其其定定义义区区间间a,b内内的的绝绝对对值值小小于于1，迭迭代代过过程程收收敛敛，否否则则，则则发散。发散。第5页，本讲稿共13页加速迭代过程的加速迭代过程的3个因素：个因素：（1）选择的迭代初值应尽量接近于方程的根；）选择的迭代初值应尽量接近于方程的根；（2）迭迭代代函函数数一一阶阶导导数数在在迭迭代代区区间间的的绝绝对对值值越越小小，收敛速度越快；收敛速度越快；（3）所所求求解解方方程程的的原原函函数数f(x)的的泰泰勒勒展展开开式式中中的的二二阶阶及及二二阶阶以以上上的的高高阶阶导导数数的的值值尽尽可可能能小小，以以致

5、致可以略去不计时，收敛速度越快。可以略去不计时，收敛速度越快。迭迭代代法法缺缺点点一一是是存存在在迭迭代代过过程程不不收收敛敛的的可可能能性性，这这将将无无法法求求解解；二二是是存存在在收收敛敛速速度度极极缓缓慢慢的的问问题题，这这将将导导致致大大大大降降低低效效率率甚甚至至难难于于计计算。算。第6页，本讲稿共13页1、定义、定义二二分分法法也也称称对对分分法法，是是另另一一种种简简单单易易行行的的求求非非线线性性方方程程数数值值解解的的方方法法。不不仅仅克克服服了了迭迭代代法法可可能能不不收收敛敛的的缺缺欠欠，即即在在有有根根区区间间用用二二分分法法肯定收敛于极值，而且其收敛速度也很快。肯定

6、收敛于极值，而且其收敛速度也很快。假假设设有有一一个个非非线线性性方方程程f(x)=0，x在在a0,b0区区间间内内，当当f(x)在在区区间间a0,b0上上单单调调连连续续，且且f(x)在在其其区区间间a0,b0的的两两个个端端点点处处的的值值异异号号，即即f(a0)f(b0)0时时，则方程在则方程在a0,b0区间内有根，且只有一个根区间内有根，且只有一个根x*。第7页，本讲稿共13页2、求单根算法核心、求单根算法核心基基本本思思想想将将方方程程有有根根区区间间a0,b0分分为为两两个个小小区区间间（称称二二分分），取取a0，b0的的中中点点x1=(a0+b0)/2，并并计计算算f(x1)的的

7、值值；如如果果f(x1)与与f(a0)同同号号，则则方方程程的的根根必必在在x1,b0区区间间，反反之之，f(x1)与与f(a0)异异号号，则则根根在在a0,x1区区间间。通通过过这这样样的的方方法法找找出出并并确确定定新新的的有有根根区区间间a1,b1，然然后后再再将将新新的的有有根根区区间间二二分分为为两两个个小小区区间间，如如此此继继续续下下去去，就就可可得得到到一一个个有有根根区区间间套套第8页，本讲稿共13页（1）直直至至某某一一小小区区间间端端点点处处的的函函数数f(xk)的的绝绝对对值值小于给定精度小于给定精度1，即，即f(xk)1式式中中k为为寻寻找找中中点点或或二二分分有有根

8、根区区间间的的次次数数，xk为为第第k次二分时的中点值，则有次二分时的中点值，则有xk=ak；或；或xk=bk；（2）或或者者直直至至某某区区间间ak,bk的的长长度度小小于于给给定定的的精精度度2，即即跟跟的的绝绝对对误误差差限限小小于于2，便便可可以以得得到到一一个个满意的近似值。满意的近似值。第9页，本讲稿共13页参数说明：参数说明：a0，b0求求根根区区间间的的下下限限与与上上限限（实实型型变变量量，输输入入参数）；参数）；eps根根的的精精度度控控制制量量，即即2（实实型型变变量量，输输入入参参数）；数）；x，y分分别别存存放放近近似似根根及及其其相相应应的的函函数数值值（实实型型变

9、变量量，输输出出参参数数）；f函函数数子子程程序序名名，表表示示被求解的方程。被求解的方程。第10页，本讲稿共13页函函数数特特点点始始终终通通过过判判断断某某一一有有根根区区间间二二分分后后的的中中点点函函数数值值f(xk)与与求求根根初初始始区区间间的的左左端端点点处处函函数数值值f(a0)的的乘乘积积f(xk)f(a0)是是否否大大于于零零，来来确确定定下下一一个有根区间。个有根区间。这这里里并并没没有有考考虑虑精精度度1的的影影响响，即即没没有有考考虑虑某某一一小小区间内端点处的函数的绝对值是否小于精度。区间内端点处的函数的绝对值是否小于精度。缺缺点点不不能能判判断断某某一一区区间间是

10、是否否有有根根或或有有几几个个根。根。第11页，本讲稿共13页3、求所有单重实根的算法核心、求所有单重实根的算法核心基基本本思思想想需需求求出出区区间间a,b上上所所有有的的单单重重实实根根，满满足足两两个个求求根根精精度度控控制制量量1或或2。自自a点点开开始始，以以一一个个基基本本步步长长h，向向右右逐逐次次分分割割出出宽宽度度为为h的的小小区区间间a0,b0。若若小小区区间间两两端端点点处处的的函函数数值值f(a0)与与f(b0)异异号号，则则用用二二分分法法找找出出其其中中存存在在的的一一个个根根；若若同同号号，则则继继续续向向右右分分割割，重重复复上上述述操操作作，直直至至分分割割的

11、小区间已超过定义或求根区间的小区间已超过定义或求根区间a,b为止。为止。步步长长h可可以以选选的的小小些些，以以便便每每个个小小区区间间内内最最多多只只有有一一个个根根，这这样样并并不不浪浪费费很很多多机机时时，根根据据问问题题的的性性质质h也也没有必要太小没有必要太小。第12页，本讲稿共13页参数说明：参数说明：a，b求根区间求根区间a,b（实型变量，输入参数）；（实型变量，输入参数）；h步长（实型变量，输入参数）；步长（实型变量，输入参数）；n估估计计根根的的最最多多个个数数（与与x方方次次数数有有关关，整整型型变变量量，输入参数）；输入参数）；ep1函数值精度控制量函数值精度控制量1（实型变量，输入参数）；（实型变量，输入参数）；ep2根的精度控制量根的精度控制量2（实型变量，输入参数）；（实型变量，输入参数）；k实际求出的根的个数（整型变量，输出参数）；实际求出的根的个数（整型变量，输出参数）；xn存放所求的根的一维实型数组（输出参数）；存放所求的根的一维实型数组（输出参数）；f求求解解方方程程的的函函数数名名，可可以以嵌嵌套套调调用用，但但需需要要在在调调用用它它的函数前出现。的函数前出现。第13页，本讲稿共13页