Numerical integration
Numerical integration is the first algorithm of this part that a reader can check against a formula, which makes it the right place to measure something: the error of a quadrature rule falls at a rate that its order predicts, and the rate is visible in a table of five lines. This lesson writes the trapezoid rule and Simpson's rule for a function passed as an argument, prints the error against the exact value, and reads the ratios.
The trapezoid rule
The interval is cut into n pieces of width h and the area under each piece is a trapezoid: h * (f(x_i) + f(x_i+1)) / 2. Summing them gives h * (f(a)/2 + f(x_1) + ... + f(x_n-1) + f(b)/2), which is the form the code uses: one half of each endpoint and the whole of every interior point, then multiply by h.
The file integ.f90:
module quadrature
implicit none
private
public :: square, expo, trapezoid, simpson
abstract interface
pure function fun_iface(x) result(y)
real, intent(in) :: x
real :: y
end function fun_iface
end interface
contains
pure function square(x) result(y)
real, intent(in) :: x
real :: y
y = x * x
end function square
pure function expo(x) result(y)
real, intent(in) :: x
real :: y
y = exp(x)
end function expo
function trapezoid(f, a, b, n) result(s)
procedure(fun_iface) :: f
real, intent(in) :: a, b
integer, intent(in) :: n
real :: s, h
integer :: i
h = (b - a) / real(n)
s = 0.5 * (f(a) + f(b))
do i = 1, n - 1
s = s + f(a + real(i) * h)
end do
s = s * h
end function trapezoid
function simpson(f, a, b, n) result(s)
procedure(fun_iface) :: f
real, intent(in) :: a, b
integer, intent(in) :: n
real :: s, h
integer :: i
h = (b - a) / real(n)
s = f(a) + f(b)
do i = 1, n - 1
if (mod(i, 2) == 1) then
s = s + 4.0 * f(a + real(i) * h)
else
s = s + 2.0 * f(a + real(i) * h)
end if
end do
s = s * h / 3.0
end function simpson
end module quadrature
program integdemo
use quadrature
implicit none
integer :: n
real :: exact, et, es, pt, ps
logical :: first
exact = exp(1.0) - 1.0
pt = 0.0
ps = 0.0
first = .true.
print '(a,es12.4)', 'simpson on x*x, n = 8, error = ', abs(simpson(square, 0.0, 1.0, 8) - 1.0 / 3.0)
print '(a,f9.7)', 'integral of exp on [0,1], exact = ', exact
print '(a)', ' n trap error ratio simpson error ratio'
n = 8
do while (n <= 128)
et = abs(trapezoid(expo, 0.0, 1.0, n) - exact)
es = abs(simpson(expo, 0.0, 1.0, n) - exact)
if (first) then
print '(i5,2es13.4)', n, et, es
first = .false.
else
print '(i5,es13.4,f8.2,es13.4,f8.2)', n, et, ratio(pt, et), es, ratio(ps, es)
end if
pt = et
ps = es
n = 2 * n
end do
contains
function ratio(prev, now) result(r)
real, intent(in) :: prev, now
real :: r
if (now > 0.0) then
r = prev / now
else
r = 0.0
end if
end function ratio
end program integdemo
gfortran -Wall -Wextra -std=f2018 integ.f90 -o integ
./integ
simpson on x*x, n = 8, error = 0.0000E+00
integral of exp on [0,1], exact = 1.7182817
n trap error ratio simpson error ratio
8 2.2367E-03 2.3842E-06
16 5.5933E-04 4.00 1.1921E-07 20.00
32 1.4007E-04 3.99 1.1921E-07 1.00
64 3.5167E-05 3.98 3.5763E-07 0.33
128 8.5831E-06 4.10 3.5763E-07 1.00
Simpson's rule
Simpson's rule fits a parabola through three points and weights them 1, 4, 1; summed over pairs of intervals it gives weights 4 for the odd points and 2 for the even ones, which is the loop in the code. For a smooth function it is far more accurate than the trapezoid for the same number of function evaluations, and the first line of the output is the extreme case: on x*x the rule is exact, and the error at eight intervals is zero to the last printed digit.
That is not a numerical accident. Simpson's rule integrates every polynomial of degree three exactly, so a quadratic has no error at any n. The rule is the first of the Newton-Cotes family, and the family continues with weights that are exact for higher degrees and less stable at the ends; for production work the Gaussian rules with a weight function are the ones numerical libraries use.
A function as an argument
Both rules take the function as a dummy procedure, which is what makes them reusable: one quadrature routine integrates anything with the shape of fun_iface. That is the mechanism of lesson 070, and this is the use it was designed for. The module makes the interface explicit, so a call with a function of the wrong shape is a compile error rather than a wrong answer.
The two functions are pure and so is the interface, which is a promise the compiler can use: a pure function may not change a module variable, so the integrand cannot quietly count its calls in a global. If a program needs that count, the interface must drop pure and the optimiser loses a little freedom with it.
The measured table
The table integrates exp(x) from zero to one, whose exact value is e - 1 = 1.7182817, and prints the absolute error for n = 8, 16, 32, 64 and 128. The third and fifth columns are the ratio of the previous error to the current one, which is how a rate is measured: a method whose error falls like h^2 shows a ratio near four when h is halved, and one that falls like h^4 shows sixteen.
Reading the ratios
The trapezoid column is the textbook result: 4.00, 3.99, 3.98 and 4.10, four within the noise of single precision. The rule is second order, the number of function evaluations doubles, and the error quarters. That is a measured convergence order, and it is the kind of number a report should quote rather than the word "convergent".
The Simpson column has no such pattern, and the reason is in its own values: 2.4e-07, 1.2e-07, 3.6e-07. Simpson is so accurate on this function that the error is at the resolution of a single-precision real near 1.7, which is about 1.2e-07. The ratios are then a record of rounding, not of the method. Wall-clock time would have shown the same thing at a different cost: both rules evaluate a hundred and twenty-nine points at n = 128, and Simpson gets an answer a thousand times closer.
This is the practical lesson of the page. A convergence table is read for the slope before the roundoff floor, and a method that reaches the floor at n = 8 has to be measured in double precision or on a function with a bigger derivative. A table of ratios that jumps between 0.33 and 20 is not a broken program; it is a program measuring noise.
Where the error stops falling
Every quadrature rule has the same shape of error curve: it falls like a power of h, then flattens when the rounding error of the sum is larger than the truncation error, and then rises as the number of additions grows. The flat part is the precision of the type, and the rise is the accumulation of roundoff.
So the right step is not the smallest one. For a real function with a few derivatives, the useful range is where the ratio is still the predicted one, and a program that keeps halving the step past that point pays twice the work for a worse answer. In double precision the floor is a thousand million times lower, which is why a serious quadrature routine declares its accumulator as real64 even when the integrand is single.
Exercises
- Integrate sin(x) from zero to pi and compare with the exact value two. Which rule reaches the single-precision floor first?
- Change the accumulator of trapezoid to real64 and rerun the table. Where does the trapezoid ratio stop being four?
- Write a rule that uses the midpoint of each interval instead of the endpoints. What is its order, measured the same way?
- Integrate x**7 from zero to one with Simpson at n = 8. Is the answer exact, and why is that the last polynomial degree for which it is?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the error of the trapezoid rule proportional to?
Answer
h squared, so it quarters when h halves
The measured ratio of four is the evidence.
-
Why is Simpson's rule exact for x*x?
Answer
It integrates every polynomial of degree three exactly
The parabola through three points matches a quadratic.
-
What does this program print?
program p implicit none real :: h, s integer :: i h = 0.5 s = 0.0 do i = 1, 3 s = s + h h = h / 2.0 end do print *, s end program pAnswer
0.875
Half plus a quarter plus an eighth is seven eighths.
-
What does a ratio of about four in the table mean?
Answer
Halving h divided the error by four: a second-order method
The ratio of two errors is the measured order.
-
Why does the Simpson column stop showing a pattern?
Answer
Its error reached the single-precision floor, so the numbers are rounding noise
About 1e-07 is the resolution near 1.7 in real32.
-
Why is the integrand passed as a procedure argument?
Answer
So one routine integrates any function of the right shape
It is the design lesson 070 prepared for.
-
What does the
pureon the interface promise?Answer
The integrand does not change anything outside itself
A pure function may not touch a module variable.
-
What is the useful step size for a quadrature rule?
Answer
Where the error still falls at the predicted rate
Past the roundoff floor more work buys a worse answer.
-
Which accumulator should a serious quadrature routine use?
Answer
real64, even for a single-precision integrand
The sum is where the rounding accumulates.
-
How many function evaluations does the trapezoid rule use for n intervals?
Answer
n + 1 points
Both endpoints and every interior point.
The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev