Im trying to find more information about numerical integration methods. When is a Newton-Cotes Quadrature formula on n nodes exact?
[Math] Newton-Cotes Quadrature formula
approximationintegrationnumerical methodspolynomials
Related Solutions
It means that in the case where $f$ is such a polynomial, the formula gives the exact value of the integral of $f$ (and not just an approximation).
Newton-Cotes says "pick evenly spaced points in the interval, draw the interpolating polynomial of minimal degree through them, and integrate the polynomial." From the Lagrange interpolation theorem, a Newton-Cotes rule on $n$ nodes is exact for polynomials of degree at most $n-1$. It is not exact for polynomials of any higher degree, because one can add a polynomial of degree $n$ which vanishes at the $n$ nodes and takes on any desired value at an additional point, and the Newton-Cotes rule will not "detect" this change.
Gaussian quadrature says "find a rule that lets us exactly integrate polynomials of as large a degree as possible." This winds up being degree $2n-1$, since we have control of $2n$ parameters in specifying a quadrature rule at $n$ nodes, and the parameters are independent.
Analysis of either method is generally inspired by the Weierstrass approximation theorem, which generates the following type of argument. Here $I$ denotes exact integration, $Q_n$ denotes quadrature integration with a rule on $n$ nodes, and $p$ is a polynomial.
$$| I(f) - Q_n(f) | \leq | I(f) - I(p) | + | I(p) - Q_n(p) | + | Q_n(p) - Q_n(f) | $$
The Weierstrass theorem and the fact that $I$ is a bounded linear functional (in particular, $\| I \| = I(1)$) allow us to make the first term small, possibly at the expense of $p$ having a large degree.
Once the degree of $p$ is fixed, choosing $n$ large enough enables us to make the second term zero, since both Newton-Cotes and Gaussian quadrature can be made exact for polynomials by taking enough nodes.
The problem for the numerical analyst is to control the last term, when $\| p - f \|$ is small and $n$ might be arbitrarily large.
Now $Q_n$, like $I$, is linear, so we can write
$$Q_n(p) - Q_n(f) = Q_n(p-f).$$
Also, $Q_n$ is bounded:
$$|Q_n(f)| \leq \| f \| \sum_{k=1}^n |w_k|,$$
where $w_k$ are the weights. Hence
$$\| Q_n \| \leq \sum_{k=1}^n |w_k|.$$
This inequality is actually an equality, as we can check by integrating $f$ such that $\| f \|=1$ and $f(x_k)=\text{sign}(w_k)$.
The fact that the $Q_n$ are each bounded is not good enough. Since simultaneously controlling the first two terms takes away our control over $n$, we need $Q_n$ to be uniformly bounded.
It turns out that Newton-Cotes rules do not have $Q_n$ uniformly bounded, whereas Gaussian quadrature does. The idea is to recognize that, because these methods are exact for polynomials of degree $0$, $\sum_{k=1}^n w_k = I(1)$. If the $w_k$ are all positive, then $\| Q_n \| = \sum_{k=1}^n |w_k| = I(1)$, which is independent of $n$, as we want.
One can prove from the property of being exact for polynomials of degree $2n-1$ that all of the weights in Gaussian quadrature are positive. (The trick is to integrate $\prod_{k=1,k \neq j}^n (x-x_k)^2$ for each $j$.) Consequently Gaussian quadrature is convergent. In particular, if there exists $p$ such that $\| p - f \| < \varepsilon/(2I(1))$ and the degree of $p$ is at most $m$, then $|I(f)-Q_n(f)|<\varepsilon$ provided $n \geq (m+1)/2$.
The weights in Newton-Cotes quadrature are not positive. Moreover, $\| Q_n \|$ is unbounded for Newton-Cotes rules. This means that if $f=p+g$, where $p$ is a polynomial of degree at most $n-1$ and $g$ is a continuous function with $g(x_k)=\| g \| \text{sign}(w_k)$, then $|Q_n(p-f)|=\| Q_n \| \| g \| \gg \| g \|$.
Consequently Newton-Cotes rules are not convergent for all continuous $f$. Very "nice" functions $f$ will converge with Newton-Cotes rules, but Runge's well-known example with $1/(x^2+1)$ shows that the number of derivatives is not what "nice" means. (The answer turns out to be that the Fourier coefficients decay sufficiently fast.)
Best Answer
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:
Remarks:
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: