第二章 迭代法及二分法

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

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

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

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

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

6、程假设有一个非线性方程f(x)=0，x在在a0, b0区间区间内，当内，当f(x)在区间在区间a0, b0上单调连续，且上单调连续，且f(x)在在其区间其区间a0, b0的两个端点处的值异号，即的两个端点处的值异号，即f(a0)f(b0)0时，则方程在时，则方程在a0, b0区间内有根，区间内有根，且只有一个根且只有一个根x*。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，然，然后再将新的有根区间二分为两个小区间，如此后再将新的有根区间二分为两个小区间，如此继续下去，就可得到一个有根区间套继续下去，就可得到一个有根区间套001122,.,.kkabababab（1）直至某一小区间端点处的函数）直至某一小区间端点处的函数f(xk)的绝的绝对值小于给定精度对值小于给定精度1，即，即f(xk) 1式

8、中式中k为寻找中点或二分有根区间的次数，为寻找中点或二分有根区间的次数，xk为第为第k次二分时的中点值，则有次二分时的中点值，则有xk=ak；或；或xk= bk；（2）或者直至某区间）或者直至某区间ak, bk的长度小于给定的长度小于给定的精度的精度2，即跟的绝对误差限小于，即跟的绝对误差限小于2， 便可以便可以得到一个满意的近似值。得到一个满意的近似值。200*12kkkkkkxxbababa参数说明：参数说明：a0，b0求根区间的下限与上限（实型变量，求根区间的下限与上限（实型变量，输入参数）；输入参数）；eps根的精度控制量，即根的精度控制量，即2（实型变量，（实型变量，输入参数）；输入

9、参数）；x，y分别存放近似根及其相应的函数值分别存放近似根及其相应的函数值（实型变量，输出参数）；（实型变量，输出参数）；f函数子程序函数子程序名，表示被求解的方程。名，表示被求解的方程。函数特点函数特点始终通过判断某一有根区间二分始终通过判断某一有根区间二分后的中点函数值后的中点函数值f(xk)与求根初始区间的与求根初始区间的左端点左端点处函数值处函数值f(a0)的乘积的乘积f(xk)f(a0)是否大于零，来是否大于零，来确定下一个有根区间。确定下一个有根区间。这里并没有考虑精度这里并没有考虑精度1的影响，即没有考虑某的影响，即没有考虑某一小区间内端点处的函数的绝对值是否小于精一小区间内端点

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

11、一个根；若同号，则继续向右分割，重复上述操作，直至分割的小区间已超过定义或复上述操作，直至分割的小区间已超过定义或求根区间求根区间a, b为止。为止。步长步长h可以选的小些，以便每个小区间内最多可以选的小些，以便每个小区间内最多只有一个根，这样并不浪费很多机时，根据问只有一个根，这样并不浪费很多机时，根据问题的性质题的性质h也没有必要太小也没有必要太小。参数说明：参数说明：a，b求根区间求根区间a, b（实型变量，输入参数）；（实型变量，输入参数）；h步长（实型变量，输入参数）；步长（实型变量，输入参数）；n估计根的最多个数（与估计根的最多个数（与x方次数有关，整型变方次数有关，整型变量，输入参数）；量，输入参数）；ep1函数值精度控制量函数值精度控制量1（实型变量，输入参（实型变量，输入参数）；数）；ep2根的精度控制量根