迭代法和二分法

迭代法和二分法第1页，共13页，2023年，2月20日，星期四非线性方程——就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等。求解此类方程往往很难得到精确解，经常需要求近似解问题。解决此问题的最主要的两种方法是——迭代法和二分法。第2页，共13页，2023年，2月20日，星期四1、定义迭代法——逐次逼近的方法，在工程技术上也叫做试算法。从隔根区间（a0，b0）中的任一个初始近似值x0出发，按照某种格式构造一个序列x0，x1，x2，……使得这个序列的极限就是f(x)=0的跟x*，即另一种方法是把方程f(x)=0写成等价形式x=φ(x)，然后令xk+1=φ(xk)k=0,1,2，……第3页，共13页，2023年，2月20日，星期四2、算法核心参数说明：x0——开始存放初始值，迭代中存放第k次近似值（实型变量，输入参数）；x——迭代中存放第k+1次近似值，最终存放方程的跟（实型变量，输出参数）；eps——根的精度控制量（实型变量，输出参数）。

时，认为xk+1是方程的跟。第4页，共13页，2023年，2月20日，星期四3、迭代法的收敛性如果从初值x0出发，按照迭代公式进行迭代计算的过程中，xk逐次接近于方程的跟，则称迭代公式是收敛的，否则是发散的。迭代法可行的必要条件是迭代过程必须收敛，收敛越快，则其收敛性越好。判别条件——迭代函数的一阶导数在其定义区间[a,b]内的绝对值小于1，迭代过程收敛，否则，则发散。第5页，共13页，2023年，2月20日，星期四加速迭代过程的3个因素：（1）选择的迭代初值应尽量接近于方程的根；（2）迭代函数一阶导数在迭代区间的绝对值越小，收敛速度越快；（3）所求解方程的原函数f(x)的泰勒展开式中的二阶及二阶以上的高阶导数的值尽可能小，以致可以略去不计时，收敛速度越快。迭代法缺点——一是存在迭代过程不收敛的可能性，这将无法求解；二是存在收敛速度极缓慢的问题，这将导致大大降低效率甚至难于计算。第6页，共13页，2023年，2月20日，星期四1、定义二分法——也称对分法，是另一种简单易行的求非线性方程数值解的方法。不仅克服了迭代法可能不收敛的缺欠，即在有根区间用二分法肯定收敛于极值，而且其收敛速度也很快。假设有一个非线性方程f(x)=0，x在[a0,b0]区间内，当f(x)在区间[a0,b0]上单调连续，且f(x)在其区间[a0,b0]的两个端点处的值异号，即f(a0)·f(b0)<0时，则方程在[a0,b0]区间内有根，且只有一个根x*。第7页，共13页，2023年，2月20日，星期四2、求单根算法核心基本思想——将方程有根区间[a0,b0]分为两个小区间（称二分），取a0，b0的中点x1=(a0+b0)/2，并计算f(x1)的值；如果f(x1)与f(a0)同号，则方程的根必在[x1,b0]区间，反之，f(x1)与f(a0)异号，则根在[a0,x1]区间。通过这样的方法找出并确定新的有根区间[a1,b1]，然后再将新的有根区间二分为两个小区间，如此继续下去，就可得到一个有根区间套第8页，共13页，2023年，2月20日，星期四（1）直至某一小区间端点处的函数f(xk)的绝对值小于给定精度ε1，即f(xk)<ε1式中k为寻找中点或二分有根区间的次数，xk为第k次二分时的中点值，则有xk=ak；或xk=bk；（2）或者直至某区间[ak,bk]的长度小于给定的精度ε2，即跟的绝对误差限小于ε2，便可以得到一个满意的近似值。第9页，共13页，2023年，2月20日，星期四参数说明：a0，b0——求根区间的下限与上限（实型变量，输入参数）；eps——根的精度控制量，即ε2（实型变量，输入参数）；x，y——分别存放近似根及其相应的函数值（实型变量，输出参数）；f——函数子程序名，表示被求解的方程。第10页，共13页，2023年，2月20日，星期四函数特点——始终通过判断某一有根区间二分后的中点函数值f(xk)与求根初始区间的左端点处函数值f(a0)的乘积f(xk)·f(a0)是否大于零，来确定下一个有根区间。这里并没有考虑精度ε1的影响，即没有考虑某一小区间内端点处的函数的绝对值是否小于精度。缺点——不能判断某一区间是否有根或有几个根。第11页，共13页，2023年，2月20日，星期四3、求所有单重实根的算法核心基本思想——需求出区间[a,b]上所有的单重实根，满足两个求根精度控制量ε1或ε2。自a点开始，以一个基本步长h，向右逐次分割出宽度为h的小区间[a0,b0]。若小区间两端点处的函数值f(a0)与f(b0)异号，则用二分法找出其中存在的一个根；若同号，则继续向右分割，重复上述操作，直至分割的小区间已超过定义或求根区间[a,b]为止。步长h可以选的小些，以便每个小区间内最多只有一个根，这样并不浪费很多机时，根据问题的性质h也没有必要太小。第12页，共13页，2023年，2月20日，星期四参数说明：a，b——求根区间[a,b]（实型变量，输入参数）；h——步长（实型变量，输入参数）；n——估计根的最多个数（与x方次数有关，整型变量，输入参数）；ep1——函数值精度控制量ε1（实型变量，输入参数）；ep2——根的精度