A tutorial on Adaptive Simpson's Method

In competitive programming, Adaptive Simpson’s Method is commonly used to compute Definite Integrals. If you don’t know what is an Integral, please read this article.

Introduction to Simpson’s rule

Now we want to compute \int_L^Rf(x)\text dx.

We use a quadratic function to simulate the given function f(x).

\int_L^Rf(x)\text dx\approx\int_L^R(ax^2+bx+c)\text dx\\=\frac{a}{3}(R^3-L^3)+\frac{b}{2}(R^2-L^2)+c(R-L)\\=\frac{R-L}{6}(2a(R^2+RL+L^2)+3b(R+L)+6c)\\=\frac{R-L}{6}\Big((aR^2+bR+c)+(aL^2+bL+c)+4(a(\frac{R+L}{2})^2+b\frac{R+L}{2}+c)\Big)\\ approx\frac{R-L}{6}(f(R)+f(L)+4f(\frac{R+L}{2}))

So we have

\int_L^Rf(x)\text dx\approx\frac{R-L}{6}(f(L)+f(R)+4f(\frac{L+R}{2}))
double simpson(double l,double r){return (r-l)/6*(f(l)+4*f((l+r)/2)+f(r));}

Adaptive Simpson’s Method

Simpson’s rule gives us a good method for Numerical Integration. However, if we want higher precision, we should improve it.

Suppose s(L,R) equals to \int_L^Rf(x)\text dx computed directly using Simpson’s rule.That is,

s(L,R)=\frac{R-L}{6}(f(L)+f(R)+4f(\frac{L+R}{2}))

When we compute calc(L^\prime,R^\prime)=\int_{L^\prime}^{R^\prime}f(x)\text dx for higher precision, suppose M=\frac{L+R}{2}. Recall that \int_a^b=\int_a^c+\int_c^b.

If |s(L^\prime,M)+s(M,R^\prime)-s(L^\prime,R^\prime)|<\epsilon, that means we have enough precision, thus calc(L^\prime,R^\prime) should return s(L^\prime,M)+s(M,R^\prime).

If not, then we should compute calc(L^\prime,M) and calc(M,R^\prime) separately, and add them together.

Here’s the code of Adaptive Simpson’s Method.

    const double eps=1e-12; // represents how much precision you need
    double f(double x){ /* function for integration */}
    double simpson(double l,double r){return (r-l)/6*(f(l)+4*f((l+r)/2)+f(r));}
    double calc(double l,double r,double ans)
    {
    	double m=(l+r)/2,x=simpson(l,m),y=simpson(m,r);
    	if(abs(x+y-ans)<eps)return x+y;
    	return calc(l,m,x)+calc(m,r,y);
    }
    int main()
    {
        double L,R;
        scanf("%lf%lf",&L,&R);
        printf("%.8f\n",calc(L,R,simpson(L,R)));
    }

That’s all. Thanks for reading.

Problems

I’ve collected several problems solvable using this method. You can find them here.

13 Likes

Great Article, but how close to correct would be to assume the following?

"We use a quadratic function to simulate the given function f(x)."

Not necessary that we can always simulate f(x) as quadratic, I think?

Can someone please share some problems where we can use this method?

2 Likes

problems in which we can use Adaptive Simpson’s Method ???
@wangrq ??

Here are several problems involving Simpson’s Method: link

@rksthegreat_1

@devang77

since its just an approximation, i’m guessing that the first terms from taylor series of the function (if it exists) can be used.

1 Like