隐藏
自适应Simpson(辛普森)学习笔记 | Bill Yang's Blog
0%

自适应Simpson(辛普森)学习笔记

补笔记。
辛普森,自适应辛普森,辛普森自适应,这几个都是一个东西。

用途

求解积分。
与一般的微积分的区别在于不能求出精确解,但能够给出近似解,且可以求出一些积分难以求解的图形面积。

要求

  1. 对精度要求不高
  2. 能通过自变量$x$快速计算函数值$f(x)$或计算图像被直线$x=a$覆盖的长度。

Simpson积分公式

若使用这个公式求解,在三次以上的函数时误差就非常大了,所以需要进行改进。

自适应Simpson

接下来就是强行让Simpson公式算出近似解的方法了。
我们用许多个图像去拟合$f(x)$的图像。
如果能够让用于拟合的函数最高次在三次内,就可以得到近似解。
怎么做呢?

上式显然成立。
调用Simpson积分公式验证上式是否在精度范围内成立。
若成立,就已经得到答案,若不成立,继续递归检查。
这里就体现出了自适应的特点,程序自己判断递归出口。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
const double eps=1e-8; //合理选择精度

double dcmp(double x) {return fabs(x)<=eps?0:x>eps?1:-1;}

double f(double x) {} //需要自行编写

double Cal(double Left,double Right) {return (Right-Left)/6*(f(Left)+4*f((Left+Right)/2)+f(Right));}

double Simpson(double Left,double Right,double ans) {
double mid=(Left+Right)/2,ans1=Cal(Left,mid),ans2=Cal(mid,Right);
if(dcmp(ans-ans1-ans2)==0)return ans;
else return Simpson(Left,mid,ans1)+Simpson(mid,Right,ans2);
}

时间复杂度

根据主定理不难得到时间复杂度:

其中$eps$是精度,$T(\text{calf})$是单次计算$f(x)$的时间。

注意事项与技巧

  • Simpson积分一般误差很大,在时间复杂度允许的情况下开大精度范围
  • Simpson积分可以用于计算图像面积,此时不能将$x$轴以下部分的面积算作负的,应该算作$x=a$被图像覆盖的长度。

例题

姥爷们赏瓶冰阔落吧~