$\begingroup$

I'm trying to implement a numerical integrator that should have the minimum relative error and is not slow. So I was looking for the best accepted state-of-the-art algorithm to do so but there seems to be so many approaches that I could not understand which one should I choose. So I'm turning to you for a recommendation.

Thank you for your attention,

$\endgroup$ 9

2 Answers

$\begingroup$

As @J.M noted, there are many methods, each suited for a certain purpose. If you don't know what the function is in advance, then for low-dimensional ($d < 3$) integrals a adaptive Gauss–Kronrod rule quadrature is probably the fastest.

In higher dimensions, you can really only use Monte-Carlo methods.

If you know apriori that the functions have a very large range, you can use a weighted Monte-Carlo approach, in which you select more points in the "large" regions, than in the "smaller" ones.

$\endgroup$ 4 $\begingroup$

There is no "best" numerical integration algorithm in the sense of being foolproof. This is because for any algorithm, there are some functions for which the algorithm fails to find the integral with a bounded error. For example, many integration algorithms require the integrand to have derivatives of bounded variation (and other conditions) to work correctly, and may give far-from-correct answers if the integrand has a pole or varies too greatly over a small interval (is "spiky").

Thus, to use numerical integration accurately, you have to know what kind of integrands you will be dealing with.

For example, Y. Zhang (2018) specifies adaptive algorithms for the trapezoidal and Simpson rules that are guaranteed to approximate integrals accurately for any 1-dimensional function whose first or third derivative, respectively—

• Has bounded total variation, and
• does not vary too greatly over a small interval.

The work cited below also includes a discussion on the minimum number of function values that any algorithm needs to work correctly on this class of integrands, and constructs functions that can fool any numerical integration algorithm (which can even be piecewise linear). These complexity results are based in part on the first or third derivative's total variation.

See also this question: Are expressions including radicals particularly difficult to integrate numerically?

REFERENCES:

• Y. Zhang, "Guaranteed, adaptive, automatic algorithms for univariate integration: methods, costs and implementations", dissertation, Illinois Institute of Technology, 2018.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy