使用“牛顿迭代法”求解方程 (2)

使用“牛顿迭代法”求解方程

图:牛顿迭代法的收敛

 在上图的4个部分中,f(x)以粗实线表示,a和b都表示为垂直的虚线。如果f(a)满足前面给出的规定,则从a开始迭代,且切线会朝着根收敛的方向倾斜。如果f(b)满足前面给定的规定,迭代就从b开始。且切线也会朝着根收敛的方向倾斜。

牛顿迭代法的工作过程

假设我们想找出方程f(x) = x3 - x2 - 3x + 1.8的根。根据函数图像(如下图),该方程会有三个根:一个在区间[-2,-1],另一个在区间[0,-1],第三个在区间[2,3]。一旦知道了方程的根的个数以及它们所在的区间,就根据上面的要求对每个区间做测试,以此挑出一个初始迭代值。要实现这一点,首先得知道如下信息:

f(x) = x3 - x2 - 3x + 1.8,f '(x) = 3x2 - 2x - 3,f ''(x) = 6x - 2

利用这些信息,我们发现[-1,-2]满足第一个要求,因为f(-2) = -4.2,f(-1) = 2.8,且f '(x)在该区间内没有改变符号(一直都是正的)。到这,我们知道在区间[-2,-1]内有且只有一个根。现在需要检查是否满足第二个要求,我们发现f ''(x)在区间上并没有改变过符号(一直都是负的)。因为f(-2)=-4.2也是负值,所以选择x0 = -2作为迭代的初始值。下图展示了在该区间内迭代计算根的过程,其精度达到了0.0001。只经过5次迭代就得到了这个近似值。

使用“牛顿迭代法”求解方程

图:计算方程f(x) = x3 - x2 - 3x + 1.8 = 0的3个根的近似值,精确度0.0001

再来看看如何求出区间[0,1]上的根。我们能够看到第一个要求在该区间上是能够满足的,但是在该区间的f''(x)的符号并不是不变的,因此这个区间不能满足第二个要求。我们怀疑这个根更接近于1而不是0,因此我们接下来尝试使用区间[0.5,1],这个可以解决不满足第二个要求的问题了。f(0.5) = 0.175,f(1) = -1.2,f '(x)在这个区间内都是负值,因此第一个要求可以满足。要完成第二个要求让初始值x0 = 0.5,因为f(0.5)=0.175为正值,且同f ''(x)在区间[0.5,1]上的符号相同。上图也展示了在区间[0.5,1]上迭代计算根的过程,其精度达到了0.0001。最后用了4次迭代就达到了根的近似值。计算第3个根的过程也与此类似。

方程求解的接口定义

root

int root(double (*f)(double x), double (*g)(double x), double *x, int *n, double delta)

返回值:如果找到了根返回0;否则返回-1。

描述:采用牛顿迭代法,根据给定的初始值来计算方程f的根。初始值由x[0]指定。函数f的导数由参数g指定。参数n代表迭代的最大次数。参数delta表示逐次逼近的差值,用该值来决定何时应该结束迭代。函数返回后,迭代过程中计算出的近似值都保存在数组x中,此时n代表数组x中的元素个数。由调用者负责管理同x相关联的存储空间。

复杂度: O(n),这里n表示调用者希望进行的最大迭代次数。

方程求解的实现与分析

求解形如f(x) = 0的方程,本质上就是要找出它的根。函数root采用牛顿迭代法以给定的初始迭代值开始逐次迭代逼近,从而找到实际根。

root函数包含单个循环,该循环采用牛顿迭代公式来连续计算根的近似值。在本节给出的实现中,f就代表需要求解的方程,g代表f的导函数。每一次迭代,我们要判断当前得到的近似值是否满足需求。如果当前得到的近似值与前一轮迭代得到的近似值之差小于delta所指定的值,则认为当前的近似值满足要求。如果经过n次迭代后还是没有找到满足要求的近似根,则从函数中返回-1以表示没有找到近似根。

root函数的时间复杂度为O(n),这里n表示调用者希望进行迭代的最大次数。最坏情况是当没有找到所需要的近似根时,此时一共会进行n次迭代。

示例:方程求解的实现

#include <math.h> #include "nummeths.h" int root(double (*f)(double x), double (*g)(double x), double *x, int *n, double delta) { int satisfied,i; i = 0; satisfied = 0; while(!satisfied && i+1 < *n) { /*x的下一个迭代值*/ x[i+1] = x[i] - (f(x[i]) / g(x[i])); /*确定是否获得期望的近似值*/ if(fabs(x[i+1] - x[i]) < delta) satisfied = 1; /*为下一次迭代做准备*/ i++; } /*即使没有迭代,也表明一个值已经存储在x中*/ if (i==0) *n=1; else *n=i+1; /*找到实根返回0,或者达到最大迭代次数仍没有找到实根,返回-1*/ if(satisfied) return 0; else return -1; }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpzsyw.html