自适应Simpson（辛普森）学习笔记

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

用途

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

要求

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

Simpson积分公式

$$\int_a^b f(x) \,\rm{d}x\approx\frac{b-a}6\left[f(a)+4f\left(\frac{a+b}2\right)+f(b)\right]$$

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

自适应Simpson

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

$$\int_a^b f(x) \,\rm{d}x=\int_a^{\frac{a+b}2} f(x) \,\rm{d}x+\int_{\frac{a+b}2}^b f(x) \,\rm{d}x$$

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

模板

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);
}

时间复杂度

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

$$O(\log\frac{r-l}{eps}T(\text{calf}))$$

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

注意事项与技巧

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

例题

• 「BZOJ2178」圆的面积并
• 「NOI2005」月下柠檬树