Proving Exactness of Gauss-Legendre Integration Formula

Question

In working through various schools' qualifying exams in numerical analysis, I have come across a problem that appears several times in a variety of different flavors:

The Legendre polynomials \begin{align*} P_n(x) = \frac{1}{2^n n!} \ \frac{d^n}{dx^n} [(1-x^2)^n] \end{align*} are orthogonal with respect to the inner product $(f,g) = \int_{-1}^1 f(x)g(x) \ dx$. Consider the Gauss-Legendre integration formula \begin{align*} \int_{-1}^1 f(x) \ dx \approx \sum\limits_{i=1}^n w_i f(x_i) \end{align*} where \begin{align*} w_i = \int_{-1}^1 L_i(x) \end{align*} with $L_i$ being the $i$th Lagrange interpolating polynomial, and the $x_i$'s being the roots of $P_n$. Show that this method is exact for all polynomials of degree $\leq 2n - 1$ by writing any such polynomial $p(x) = q(x)P_n(x) + r(x)$ where the degrees of $q$ and $r$ are less than $n$.

I believe there are a few clever ways to go about solving this depending on the prompt of the question and the hint given (if any). I have a complete answer (below), but I am looking for feedback to improve. In particular, in my dealings with $q(x)$, is it necessary for me to show that it's a linear combination of lower degree Legendre polynomials to show that the integral evaluates to zero, or would it be appropriate to just state that, since $q(x)$ is a polynomial of degree $< n$ that orthogonality with respect to the inner product follows? In general, I often feel that my proofs are sometimes a little cumbersome.

Answer 1

First, we assume that $f(x)$ is a polynomial of degree $\leq 2n-1$, which we write as $f(x) = q(x)P_n(x) + r(x)$. Rewriting the integral (and using linearity), we have \begin{align*} \int_{-1}^1 f(x) \ dx = \int_{-1}^1 q(x)P_n(x) + r(x) \ dx = \int_{-1}^1 q(x)P_n(x) \ dx + \int_{-1}^1 r(x) \ dx \end{align*} We will deal with each integral separately. Note that since $r(x)$ and $q(x)$ are both polynomials of degree less than $n$, the $n$th degree Lagrange polynomial interpolates each exactly, where \begin{align*} r(x) &= \sum\limits_{i=1}^n r(x_i) L_i(x) \\ q(x) &= \sum\limits_{i=1}^n q(x_i) L_i(x) \end{align*} For the integral of $r(x)$, then, we have \begin{align*} \int_{-1}^1 r(x) \ dx - \sum\limits_{i=1}^n w_i r(x_i) &= \int_{-1}^1 \sum\limits_{i=1}^n r(x_i) L_i(x) \ dx - \sum\limits_{i=1}^n \int_{-1}^1 L_i(x) \ dx \ r(x_i) \\ &=\int_{-1}^1 \sum\limits_{i=1}^n r(x_i) L_i(x) \ dx - \sum\limits_{i=1}^n \int_{-1}^1 r(x_i) L_i(x) \ dx = 0. \end{align*} It then remains to show that our approximation is exact for $q(x) P_n(x)$. As the Legendre polynomials up to degree $n$ are orthogonal, they are linearly independent, where $q(x)$ can be written as a linear combination of lower degree polynomials, i.e. \begin{align*} q(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n a_{ij}P_i(x)P_j(x) \quad \quad a_{ij} = 0 \text{ for } i + j \geq n \end{align*} Rewriting the integral of $P_n(x)q(x)$ and utilizing the orthogonality of the polynomials, we have that \begin{align*} \int_{-1}^1 q(x)P_n(x) \ dx = \int_{-1}^1 P_n(x) \left(\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_{ij}P_i(x)P_j(x)\right) \ dx = 0 \end{align*} Examining then our approximation, recall that each $x_i$ was chosen as a root of $P_n(x)$. Therefore, we have \begin{align*} \sum_{i=1}^n w_i \ q(x_i)P(x_i) = 0 \end{align*} and hence $\int_{-1}^1 q(x)P_n(x) = \sum\limits_{i=1}^n w_i \ q(x_i)P(x_i)$. We conclude that for $f$ a polynomial of degree $\leq 2n-1$, \begin{align*} \int_{-1}^1 f(x) \ dx \ = \int_{-1}^1 P_n(x)q(x) + r(x) = \sum_{i=1}^n w_i (r(x_i) + q(x_i)P_n(x_i)) = \sum_{i=1}^n w_i f(x_i) \end{align*}