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
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.