首页 > 代码库 > 二分法求一元三次方程的一个实数根

二分法求一元三次方程的一个实数根

2024-07-07 14:44:54   216人阅读

一元一次方程的一般形式是$ax+b=0$，很容易解得$x=-\frac{b}{a}$。对于一元二次方程，也有一个简单的求根公式可以解出方程的根。但是一元三次方程的求根公式较为复杂，需分情况，编写程序的复杂度比前两个要大得多。

你可能已经听说过二分查找法，在已排序的数组中查找某一个数的时间复杂度从$O(n)$降到了$O(lg n)$。类似地，我们可以用二分法来求解一个一元三次方程的实数根。

以下是非递归版本的实现。calc函数用于计算方程取某个$x$值时方程左端的值。因为这个函数只是返回一个计算表达式的值，将其声明为内联函数，编译器可以将其展开到调用处，节省调用函数耗费的时间。solve函数的参数L、R指定二分查找的范围。

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 double a, b, c, d;
 7 
 8 inline double calc(double x)
 9 {
10     return a*x*x*x + b*x*x + c*x + d;
11 }
12 
13 double solve(double L, double R)
14 {
15     double x = (L+R)/2, step = (R-L)/2, result;
16     while(fabs(result=calc(x)) > 0.001)
17     {
18         if(result < 0)
19             x += step;
20         else if(result > 0)
21             x -= step;
22         step /= 2;
23     }
24     return x;
25 }
26 
27 int main()
28 {
29     cin >> a >> b >> c >> d;
30     cout << solve(-10000, 10000) << endl;
31     return 0;
32 }

此算法的时间复杂度为$O(lg\frac{L+R}{2})$，和查找范围有关，与方程的系数无关。范围在-10000～+10000时，在我的Core i3的笔记本上，平均时间只在5ms左右。

这种方法在方程系数较小且只需要得到实数根时是非常有效的。

 


联系
我们