自适应辛普森法

并没想打算开篇小小结，只是随便写写（感觉开小小结的成本太高了啊……）

感觉还是挺妙的。以前听zyy 大佬讲课的时候说过，函数的积分用二次函数拟合一下。

加入我们要算 $\int_{l}^{r} F (x) d x$ ，我们用二次函数 $f (x) = a x^{2} + b x + c$ 来拟合。

我们发现：

\begin{aligned} \int_{l}^{r} f (x) d x & = \frac{a}{3} r^{3} + \frac{b}{2} r^{2} + c r - \frac{a}{3} l^{3} - \frac{b}{2} l^{2} - c l \\ = \frac{a}{3} (r - l) (r^{2} + l^{2} + l r) + \frac{b}{2} (r - l) (r + l) + c (r - l) \\ = \frac{r - l}{6} (2 a r^{2} + 2 a l^{2} + 2 a l r + 3 b r + 3 b l + 6 c) \\ = \frac{r - l}{6} (a r^{2} + b r + c + a l^{2} + b l + c + a r^{2} + a l^{2} + 2 a l r + 2 b r + 2 b l + 4 c) \\ = \frac{r - l}{6} (f (l) + f (r) + a (l + r)^{2} + 2 b (l + r) + 4 c) \\ = \frac{r - l}{6} (f (l) + f (r) + 4 (a {(\frac{l + r}{2})}^{2} + b (\frac{l + r}{2}) + c)) \\ = \frac{r - l}{6} (f (l) + f (r) + 4 f (\frac{l + r}{2})) \end{aligned}

于是我们有：

\int_{l}^{r} F (x) d x \approx \frac{r - l}{6} (F (l) + F (r) + 4 F (\frac{l + r}{2}))

然后就可以拟合辣！

cpp

inline double simpson(double l, double r)
{
	return (F(l) + F(r) + 4 * F((l + r) / 2)) * (r - l) / 6;
}

然而就是要么 WA（炸精度）要么 T……

有一种叫自适应辛普森的方法解决这个问题，我们用辛普森计算 $\int_{l}^{r} F (x) d x$ ， $\int_{l}^{(l + r) / 2} F (x) d x$ ， $\int_{(l + r) / 2}^{r} F (x) d x$ 的值，如果

| \int_{l}^{r} F (x) d x - (\int_{l}^{(l + r) / 2} F (x) d x + \int_{(l + r) / 2}^{r} F (x) d x) | \leq eps

那么直接返回值，否则递归下去算。

upd：忽然发现我学了个假的 simpson。其实 eps 应该是相对误差，所以每次递归下去时 $eps$ 都应该除 $2$ 。听说最后判定时应该是 $\leq 15 \cdot eps$ ，虽然我并不知道是为什么。话说这和 eps 乘上 15 有什么区别吗

这样复杂度就是 $O (玄学)$ ，交之前洗把脸就行了。

cpp

inline double asr(double l, double r, double ans, double eps)
{
	double mid = (l + r) * .5;
	double ll = simpson(l, mid), rr = simpson(mid, r);
	if(fabs(ll + rr - ans) < 15 * eps)
		return ll + rr;
	return asr(l, mid, ll, eps * .5) + asr(mid, r, rr, eps * .5);
}

Cite this post