Welcome to a new post on thoughts-on-cpp.com. This time I would like to start a new series, Numerical Methods. But don’t be disappointed if you’re expecting a new post on the n-body-problem, I’m still planning to continue the “My God, It’s Full of Stars” series. With this new series, I would like to talk about numerical methods which are important in my daily business, starting from Trapezoidal and Simpson integration methods of type Newton-Cotes.
The Newton-Cotes formula is a quadratic numerical approximation for integral calculations. The idea is to interpolate the function, which shall be integrated, by a polynomial with equidistant nodes. The polynomial can be of, for example, a form of aligned trapezoids or aligned parables. Common Newton-Cotes integration polynomial rules are
- Trapezoid rule
- Simpson rule
- Romberg
- Pulcherrima
- Milne/Boole rule
- 6-Node rule
- Weddle rule
With this post, we will have a closer look at the first two integration rules, Trapezoidal and Simpson.
Trapezoidal Integral Approximation
The integral approximation by trapezoids is very simple to explain. All we need to do is to subdivide the example function
we want to integrate into equidistant areas whose exact integrations we can sum up. Clearly, the accuracy of the approximation is depending on the number of subdivisions N. The width of each area is therefore defined by
with and
.

The area of each trapezoid can be calculated by
and therefore the approximated integral of our function f(x) can be defined as
The implementation of the Trapezoidal integration is taking 4 parameters, the range [a,b] of integration of the function f(x), the number of subdivisions n, and the function f(x).
Simpson Integral Approximation
The Simpson rule is approximating the integral of the function f(x) by the exact integration of a parable p(x) with nodes at a, b, and . In order to increase the approximation accuracy, the function can be subdivided by N, similar to the Trapezoidal integral approximation.

The exact integration can be done by summing up the area of 6 rectangles with equidistant width. The height of the first rectangle is defined by , the height of the next 4 rectangles is defined by
, and the height of the last rectangle is defined by
. As a result, the formula of the approximated integral according to Simpson rule can be defined as
The implementation of the Simpson integration is, similar to the Trapezoidal based solution, taking 4 parameters, the range [a,b] of integration of the function f(x), the number of subdivisions n, and the function f(x)
Romberg Integral Approximation
If we integrate the function f(x) with the Trapezoidal approach but bisecting the step size based on the step size of the previous step, we get the approximation sequence
The idea of the Romberg integration is now to introduce a y-axis symmetric parable which is crossing the points and extrapolate to
.

Therefore every term of the first column R(n,0) of the Romberg integration is equivalent to the Trapezoidal integration, were every solution of the second column R(n,1) is equivalent to the Simpson rule, and every solution of the third column R(n,2) is equivalent to Boole’s rule. As a result, the Formulas for the Romberg integration are

The repository numericalIntegration can be found at GitHub. It will also contain the other numerical integration methods, as the name suggests, later on.
Did you like the post?
What are your thoughts?
Feel free to comment and share this post.
I know that multiplication is commutative and it technically is correct, but I think your trapezoidal equation is wrong. Well, maybe not wrong, but just hard to read. You wrote it first as (a+b)/2 * h and then as (x1-x0)/2 * (f(x1)+f(x0)). Someone might wonder why h = f(x1)+f(x0), when h is in fact x1 – x0.
It would change the second equation so it matches the first one. Just a minor nitpick 🙂
LikeLike
Thanks for your suggestions, I will have a look
LikeLike