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?

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

Thank you for providing such a mathematical description of Simpson’s method. It is very helpful for the mathematical calculation. The description is given step by step so it is very easy to understand. We have to understand the derivation before putting in a code. Then we come to know where we can utilize it. If someone is looking for tips & advice on writing project then they can refer essaywritingUS . You will get great help from here.

1 Like

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

//