Last time I talked about quadratures and orthogonal polynomials, so now it’s time to combine the two.
Theorem: A quadrature scheme with interpolation points will be exact for polynomials of order up to
if the quadrature points are chosen to be the roots of the associated
th-order orthogonal polynomial.
Note that, for an arbitrary choice of sample points, we would generally expect points to give a quadrature for polynomials of order
so
is a substantial improvement. For example, a single interpolation point can exactly integrate over polynomials of order one rather than just zero — as we had in our original example — and two interpolation points can integrate over polynomials of order three rather than one, even better than our original example. Three points can integrate up to order five!
Proof: We can split any -order polynomial
according to the orthogonal polynomial
In particular, we can use the decomposition
where and
are polynomials of order
Since
is predetermined, we must specify a
-order polynomial, with
coefficients, by choosing the polynomials
and
with
coefficients between them. We have as many free coefficients to choose as we need, so this decomposition is always possible.
When we integrate over this expression, we see that
by being orthogonal to any
regardless of our choice of integration points. We therefore have the equality
so we must show that is equal to any one of these expressions. But, if we take
to be the roots of
then equality to the third expression follows immediately, since the first term in the decomposition of
disappears for every
and so
We can, therefore, choose our interpolation points to be the roots of an orthogonal polynomial to optimise our quadrature method, with respect to the order of polynomials whose integrals are computed exactly. For our case over the interval this gives the first optimal sets of interpolation points as
Weighted Quadratures
As a final extension, suppose the function we are integrating is not polynomial, but it is a polynomial times some other function — say — that is explicitly known. In this case, we wish to estimate
For this case, we can proceed as before, except that now we choose polynomials that are orthogonal, in the sense that
In other words, the known function becomes a weight function inside the integral, changing our choice of orthogonal polynomials, and of interpolation points. Common examples on the space
are the Jacobi polynomials for
and the Chebyshev polynomials of first type for
That’s about all I have to say. Gaussian quadratures are a reasonably straightforward step-up from basic quadratures, but give a sizeable increase in efficiency if we’re dealing with some function of known type, with an unknown polynomial term.