算法基础 - 求解非线性方程(二分迭代法)

二分迭代法使用了二分算法思想求解非线性方程式。

下面要求使用二分迭代法求解：

2x³-5x-1=0

方程式，且要求误差不能大于10e-5。 二分迭代法也只是近似求解算法。

所谓求解，指求其与横坐标轴相交时的点的 x 值.

1. 基本思想

预测或初步判断值的范围。

• 如上述方程，把 0代入方程式，可知 f(0)=-1，然后把 1 代入方程式，则 f(1)=-4，再把 2代入方程式，得到f(2)=5。如下绘制函数在 [0,1,2] 3 个点之间的大致走势图，分析后可知在[1,2]之间必然会有一个解。

• 使用二分思想，计算出 [1,2]之间的中间点 x=(1+2)/2=1.5。把1.5代入方程式得到函数值为f(1.5)=-1.75。重新修正一下走势图。因为 f(1.5)*f(1)>0，说明f(1.5)和f(1)在同一边，其真实值应该在 1.5的右边。如果f(1.5)*f(1)<0，则说明f(1.5)和f(1)在横坐标的两侧，说明真实值应该在 1.5的左边。分析后可知直实值缩小在[1.5,2]之间。

• 再计算[1.5,2]之间的中间点x=(1.5+2)/2=1.75，把1.75代入方程式得f(1.75)=0.96875，发现值已经慢慢接近 0。分析可知，真实值应该在[1.5，1.75]之间，继续二分迭代，便可以找到近似值。

2. 编程实现

二分迭代法同样有递归和非递归两种方案。

2.1. 非递归

#include <iostream>
#include <cmath>
using namespace std;
/*
* 原函数
*/
double yfun(double x) {return 2*pow(x,3)-5*x-1;
}
/*
* 非递归实现二分迭代法，
* left:左边界
* right:右边界
* precision:精度
* 为了避免找不到结果，可以限制迭代次数。
*/
double binaryIter(double left,double right,double precision) 
{//计算左边界的函数值double leftVal=yfun(left);//右边界的函数值double rightVal=yfun(right);while(true) {//中间位置double midPos=(left+right) /2;//函数值double midVal= yfun(midPos);if( midVal==0.0  || fabs(midVal) < precision ) {//找到return midPos;}else if( leftVal * midVal > 0 ) {//真实值应该在 midPos 的右边left=midPos;} else {right=midPos;}}
}
int main() {cout<<"左边界"<<endl;double left=0.0;cin>>left;cout<<"右边界"<<endl;double right=0.0;cin>>right;cout<<"精度："<<endl;double precision=0;cin>>precision;double res= binaryIter(left, right, precision);cout<<res;return 0;
}

输出结果：

根据前面的函数走势图，可以直观感觉到在横坐标轴的左边还有一个值。把-1代入函数，知f(-1)=2，可预测在[-1,0]之间还有一个近似值。

同样，可以使用二分迭代法求解上文的方程式 f(x)=x⁴-3x³+1.5x²-4 的解：

很容易预测出函数在[2,3]之间有解。只需要修改 yfun函数。

double yfun(double x) 
{return pow(x,4)-3*pow(x,3)+1.5*pow(x,2)-4.0;
}

其结果和牛顿迭代法计算出来的一样。

2.2. 递归方案

最后提供二分迭代法的递归实现。

double binaryIter_(double left,double right,double precision) 
{if(left>right)return -1;//计算左边界的函数值double leftVal=yfun(left);//右边界的函数值double rightVal=yfun(right);//中间位置double midPos=(left+right) /2;//函数值double midVal= yfun(midPos);if( midVal==0.0  || fabs(midVal) < precision ) {//找到return midPos;}else if( leftVal*midVal>0 ) {//真实值应该在 midPos 的右边return binaryIter_(midPos,right,precision);} else {return binaryIter_(left,midPos,precision);}
}

3. 总结

本文讲解了牛顿、二分迭代求解非线性方程。虽然牛顿迭代没有二分迭代那么容易理解，但其功能却是强大很多。