Section 16.2 Gauss-Legendre integration
The Gauss-Legendre integration rule is to let the evaluation points \(x_1,\dots, x_n\) be the roots of \(P_n\) and then choose their weights \(w_1,\dots, w_n\) so that the rule
is exact for \(f(x)=x^p\text{,}\) \(p=0,\dots,n-1\text{.}\) The second part is not new; this is exactly what we did for Newton-Cotes rules. But with this specific choice of evaluation points, the integration rule is exact for all polynomials of degrees \(\le 2n-1\text{,}\) not just \(\le n-1\text{.}\) This means the Gauss-Legendre integration has order of accuracy \(2n\text{:}\) for example, it has order \(14\) if we use 7 points.
Proof. Given a polynomial \(F\) of degree \(\le 2n-1\text{,}\) use long division of polynomials to write it as \(F = Q P_n +R\) with \(Q\) and \(R\) having degree \(\le n-1\) (why is this possible?). Plug this into the integral:
where the term \(QP_n\) integrates to zero because of orthogonality. Since \(\deg R\le n-1\text{,}\) the Gauss-Legendre integration rule is exact for \(R\text{.}\) Therefore,
where the last step uses the fact that \(F(x_k) =R(x_k)\) by virtue of \(P_n(x_k)=0\text{.}\) This completes the proof that
It turns out the Gauss-Legendre integration rule has the best possible order of accuracy. That is, there is no integration rule with \(n\) evaluation points that is exact for all polynomials of degrees \(\le 2n\text{.}\) Indeed, suppose such a rule exists, with some evaluation points \(x_1, \dots, x_n\text{.}\) Let \(F(x) = (x-x_1)^2 \cdots (x-x_n)^2\) which is a polynomial of degree \(2n\text{.}\) Since \(F(x_k)=0\) for every \(k\text{,}\) the evaluation rule will produce \(0\text{,}\) no matter what the weights. But \(\int_{-1}^1 F(x)\,dx > 0\) because \(F > 0\) in between the evaluation points.
Another nice feature of the integration rules based on orthogonal polynomials is that all weights \(w_k\) are positive (unlike in the Newton-Cotes rules, which may give negative weights to some points). To see why, consider the polynomial \(G(x) = F(x)/(x-x_k)^2\) where \(F\) is as in the previous paragraph. Since \((x-x_k)^2\) cancels out, \(G\) is a polynomial of degree \(2n-2\text{.}\) Therefore, the integration rule is exact for it:
where the right hand side has just one term because \(G(x_j)=0\) for all indices \(j\ne k\text{.}\) Since \(G\) is a square, the left hand side is positive and \(G(x_k)\) is also positive. Hence \(w_k > 0\text{.}\)
Since these integration rules are exact for the constant function \(f(x)=1\) (a polynomial of degree 0), we have \(\sum_{k=1}^n w_k = \int_{-1}^1 1\,dx = 2\text{.}\) As a consequence, all weights are between \(0\) and \(2\text{.}\)