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

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

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

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. 总结

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