Newton-Cotes Quadrature formula

Question

Im trying to find more information about numerical integration methods. When is a Newton-Cotes Quadrature formula on n nodes exact?

Answer 1

^{The answer expands on the comments by Dan Fox.}

It is convenient to take $[-1,1]$ as the interval of integration (any other interval is handled by linear transformation). Let $x_1=-1,\dots, x_n=1$ be equally spaced points on this interval. The Newton Cotes formulas (implicitly) do the following:

1. Given a function $f$, interpolate $f$ by a polynomial $p$ of degree $n-1$; namely the Lagrange polynomial.
2. Find $\int_{-1}^1 p(x)\,dx$, and return this as an approximation to $\int_{-1}^1 f(x)\,dx$

Remarks:

• We do not actually go through these steps explicitly; the computation is done once, for general $f$, and results in a quadrature formula $\approx \sum w_i f(x_i)$ that we use.
• You can already see the pitfall of the method: when $n$ is large, due to Runge's phenomenon $p$ will likely be not very close to $f$ near endpoints.

Since the interpolating polynomial in 1 is unique, when $f$ is itself a polynomial of degree at most $n-1$, we have $f\equiv p$ identically. Therefore, in this case the formula is exact.

When $n$ is odd, we have $\int_{-1}^1 x^n\,dx = 0$ by symmetry. Also, the contribution of $x^n$ to the interpolating polynomial is an odd polynomial, also by symmetry. (E.g., interpolating $x^3$ at $\pm 1$ gives a multiple of $x$.) Therefore, $x^n$ contributes zero to both the quadrature formula, and to the actual integral. Conclusions:

• The $n$-node Newton-Cotes formula is always exact for polynomials of degrees $\le n-1$.
• When $n$ is odd, it is exact for polynomials of degrees $\le n$.