问题描述

给定一个闭区间，我们假设函数f(x)在该区间内有且仅有一个零点，则令f(x) = 0，在该区间内不断折半区间，根据有根的判别条件f(x₁) × f(x₂) < 0,则经过不断地折半，我们总能找到一个给定了精度的根，并且有理由相信，该根x关于精度是 “准确” 的。在实际操作过程中，我们用在精度控制下找到有根区间的中点的值作为方程的近似解。

例：用二分法求方程x³ - x - 1 = 0 在区间[1,1.5]内的一个实根，要求误差不超过0.005。

运行示例

源码

//实现用二分查找求根法：求出给定精度给定方程的根
#include<iostream>
#include<cmath>
using namespace std;

//函数名：function
//参数：用户输入的值x
//返回值：输入参数值的函数值
//功能：求解给定值的函数值
double function(double x)   //用户自定义的函数，可修改
{
	double result;
	//求解自定义函数值的函数
	result = pow(x, 3) - x - 1;
	return result;
}

int main(void)
{
	double low, up, mid=0, accuracy;    //区间上下限、中点、精度
	int i=0;

	cout << "请输入区间上、下限：";
	cin >> low;
	cin >> up;
	cout << "请输入精度：";
	cin >> accuracy;

	cout << endl;

	do
	{

		//区间取半
		mid = (low + up) / 2;
		
		//判断根的位置
		if ((function(low) * function(mid)) < 0)    //根在前半区间
		 {  
			up = mid;   //将区间中点值赋值给区间上限
			i++;    //折半查找次数自增1
			cout << "第" << i << "次折半！" << endl ;
			cout << "根位于前半区间！" << endl<<endl;
		}
		else   //根在后半区间
		{   
			low = mid;   //将区间中点的值赋值给区间下限
			i++;   //折半查找次数自增1
			cout << "第" << i << "次折半！" << endl ;
			cout << "根位于后半区间！" << endl << endl;
		}
	} while ((up - low) > accuracy);   //若i次二分区间后，区间长度小于精确度，则二分结束，找到近似根

	cout << "解为：";  //用区间中点的值作为根的近似解
	cout << mid << endl;

	return 0;
}

【练习】

题目要求：
	按如下递归公式求函数值。
	x=1时 f(x)=10；x>1时 f(x)=f(x-1)+2

例如：
输入：10
输出：28

#include <stdio.h>

int  main()
{
	int Fx(int a);
	
    int a;
    
    scanf("%d",&a);
    
    printf("%d\n",Fx(a));
    
    return 0;

}

int Fx(int a)
{
	int b;
	
	if(a == 1)
	{
		b = 10;
	}
	
	else if(a > 1)
	{
		b= Fx(a-1)+2;
	
	}
	
    return b;
}

梯形递推的变步长求积公式虽然算法简单，但精度低，收敛的速度慢，因此，研究收敛速度快、精度高的龙贝格算法显得尤为重要。

例：用龙贝格算法求f(x) = sin(x) / x 在区间[0,1]的数值积分，精度要求为1e-6.

• 加工流程：

• 程序框图设计：

• 运行示例：

• 源码：

#include<iostream>
#include<cmath>
double f(double x);   //自定义函数

using namespace std;

int main(void)
{
	double a, b, accuracy;   //a为区间下限，b为区间上限，accuracy为精度

	cout << "请输入积分区间:";   //输入提示
	cin >> a >> b;

	cout << "请输入精度:";   //输入提示
	cin >> accuracy;

	double h;   //步长

	h = b - a;  

	double T1, T2;   //T1：二分前的梯形法积分值；T2：二分后的梯形法积分值；

	T1 = h / 2 * (1 + f(b));    
	T2 = 0;

	int k = 1;  //记录二分次数

	cout << "T" << pow(2, 0) << " = " << T1 << endl;

	double S1, S2;   //对T1与T2加权平均，得辛普森积分值
	double C1, C2;   //对S1与S2加权平均，得柯特斯积分值
	double R1, R2;   //对C1，C2加权平均，得龙贝格积分值
	int flag = 1;   //flag作为循环控制标志性变量

	while (flag == 1)
	{
		double sum = 0;  //各分点的函数值和
		double x = a + h / 2;   //分点值

		while (x < b)   //在区间上限范围内求各分点的函数值和
		{
			sum += f(x);   
			x += h;   
		}

		T2 = T1 / 2 + h / 2 * sum;    //计算梯形序列得下一个二分结果
		cout << "T" << pow(2, k) << " = " << T2 << endl;

		S2 = T2 + 1.0 / 3 * (T2 - T1);   //线性组合外推值simpson
		cout << "S" << pow(2, k - 1) << " = " << S2 << endl;

		if (k == 1)   //至少外推2次得出S1，S2
		{
			k++;
			h /= 2;
			T1 = T2;
			S1 = S2;
			continue;
		}
		else
		{
			C2 = S2 + 1.0 / 15 * (S2 - S1);  //线性组合外推值Cotes
			cout << "C" << pow(2, k - 2) << " = " << C2 << endl;

			if (k == 2)   //至少外推3次得出C1，C2
			{
				C1 = C2;
				k++;
				h /= 2;
				T1 = T2;
				S1 = S2;
				continue;
			}
			else
			{
				R2 = C2 + 1.0 / 63 * (C2 - C1);   //线性组合外推至Romberg
				cout << "R" << pow(2, k - 3) << " = " << R2 << endl;

				if (k == 3)   //至少外推4次得出R1,R2
				{
					R1 = R2;
					C1 = C2;
					k++;
					h /= 2;
					T1 = T2;
					S1 = S2;
					continue;
				}
				else if (abs(R2 - R1) >= accuracy)   //精度仍然不符合要求，继续二分步长、继续外推
				{
					R1 = R2;
					C1 = C2;
					k = k + 1;
					h = h / 2;
					T1 = T2;
					S1 = S2;
				}
				else   //精度符合要求，修改flag为0，跳出while循环
				{
					flag = 0;
					cout << "Romber算法求得数值积分结果为:" << R2 << endl;
				}
			}
		}
	}

	return 0;
}

double f(double x)   //自定义被积函数
{
	double result;

	result = sin(x) / x;

	return result;
}