自适应辛普森积分

辛普森积分

在求图像面积的时候我们通常会使用定积分,但对于一些图像我们很难求出其定积分,那么我们就可以使用辛普森公式进行计算。

辛普森公式的思想是在一段小区间内,用二次函数去逼近原函数,这样的效果往往比用矩形/梯形逼近更好。

$$\int_a^bf(x)\text{d}x\approx\int_a^b(Ax^2+Bx+C)\text{d}x$$

$$\int_a^bf(x)\text{d}x\approx\frac{(b-a)(f(a)+f(b)+4f(\frac{a+b}2))}6$$

自适应

为了满足精度的要求,采用三点式辛普森法。

对于一段区间 $[a,b]$,我们取其终点 $mid$。

如果 $fabs(ans(a,b) - (ans(a,mid) + ans(mid, b))) \leq 15 \times eps$,我们认为其满足了精度要求,不然则要继续细分区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double F(double x) {}
double simpson(double a, double b) { // 三点Simpson法
double c = a + (b - a) / 2;
return (F(a) + 4 * F(c) + F(b)) * (b - a) / 6;
}
double asr(double a, double b, double eps, double A) {
//自适应Simpson公式(递归过程)。已知整个区间[a,b]上的三点Simpson值A
double c = a + (b - a) / 2;
double L = simpson(a, c), R = simpson(c, b);
if (fabs(L + R - A) <= 15 * eps) return L + R + (L + R - A) / 15.0;
return asr(a, c, eps / 2, L) + asr(c, b, eps / 2, R);
}
double asr(double a, double b, double eps) {
return asr(a, b, eps, simpson(a, b));
}

题目

洛谷 4525, 4526 可以测试模板。