牛顿迭代法解指数方程（aX + e^x解 = b )

时间：2022-03-24 02:10:38

牛顿迭代法解指数方程（aX + e^x解 = b )

高中好友突然问我一道这样的问题，似乎是因为他们专业要做一个计算器，其中的一道习题是要求计算器实现这样的功能。

整理一下要求：解aX + e^X = b 方程。解方程精度要求0.01，给定方程只有一解，a>0,b>0,0<X<20。

当被第一次问及这样一个问题的时候，我脑海里反映的第一个方法就是「牛顿迭代法（NewtonMethod」。然而自己算法功底太差了，从来没有真正去了解过牛顿迭代法，反正早晚都是要学的，正好便借着这个机会学习了一个。

我一直认为牛顿迭代法的效率应该是几个近似求解方程的最快方法，于是查了一下百度百科后进行了实现。

实现代码如下：

 #include<stdio.h>

 #include<math.h>

 #define MAX 20

 #define MIN 0

 #define MID 10

 #define eps 1e-2

 #define fx a*x+exp(x)-b

 #define fdx a + exp(x)

 double a,b,x;

 double binary() ; // 二分查找

 double NewtonMethod() ; // 牛顿迭代法

 int main()

 {

 scanf("%lf%lf",&a,&b);

 printf("%.2lf\n",binary()) ;

 printf("%.2lf\n",NewtonMethod()) ;

 return  ;

  } 

 double binary()   // 二分查找

 {

   x = MID ;

 double x1 =MIN , x2 = MAX ;

 while( fabs(fx) > eps)

  {

   if( fx < )

    x1 = x ;

   if( fx > )

    x2 = x ;

   x = ( x1 + x2) /  ;

  }

 return x ;

 }

 double NewtonMethod() // 牛顿迭代

 {

   x =   ;

 while()

  {

 if( fabs(fx) > eps )

   {

         x = x - (fx) / (fdx);

      }

 else return x ;

  }

 }

网上普遍都是牛顿迭代法求解一元二次方程或者平方根，我于是照猫画虎根据牛顿迭代法的核心x1=x0 - f(x) / f'(x)  照猫画虎学习了一个。关于证明还不是太会，自己手画了一下发现这样的方法近似非常快，我记得曾今刚看到过资料说两次迭代好像eps就可以小于多少……

自己代码功底还是太差了，二分也写跪多次，写出了什么if (fx < 0 ) x = ( x + MAX ) / 2这样现在看来有点羞耻想笑的代码。最后遇到最大的一个问题是在牛顿迭代法 fx / fdx 因为fx和fdx是用宏定义的，直接展开后导致运算优先级出现了问题然后各种程序跑崩……所以这里宏定义以后要考虑加括号，要认真考虑优先级问题，不然出了问题感觉挺难发现的。

以前前辈们总说代码要多写多练多手敲，就算把书上代码照抄到电脑上都是很好的。一直不能理解，觉得这样做没什么意义。现在深刻感觉到，代码看再多遍不如自己手写一遍，算法理论知道再清楚，不多手写几次就不知道坑在哪里，就实现不出来。以后一定多写代码。

不过最后有一个问题我一直不能理解：

为了比较其与二分的效率，我写了一个随机器准备对拍一下：

 #include<iostream>

 #include<ctime>

 #include<cstdlib>

 using namespace std ;

 int main()

 {

 srand((int) time() ) ;

 freopen("a.out","w"

  ,stdout) ;

 for( int x =  ; x <=   ; x++)

   cout << rand() %   +  <<' ' << rand() %   + <<endl ;

 return  ;

 }

产生了一万组 1 - 20 的数据文件，然后重定向到文件分别跑了一下数据，利用<ctime>下的 (double ) clock() / CLOCK_PER_SEC 来计算时间。

测试结果如下：

牛顿迭代法解指数方程（aX + e^x解 = b )

一万组数据 牛顿迭代反而慢于二分，不知道是因为我的数据产生中没有考虑过有方程有没有解的情况，还是程序写的不好或者输入输出有问题……？

不太会分析两个这样的算法的时间复杂度，真诚询问。二分法我感觉应该是O(nlgn) ?不会证明牛顿迭代法……就更难分析牛顿迭代法了……理论上我感觉牛顿迭代法的性能应该优于二分法啊。不知道问题出在哪里了……

相关文章