1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ The standard Newton-Cotes approximation to the integral of $f$ over $[a, b]$ with $n$ nodes is the integral $[a, b]$ of the polynomial $P$ of degree $n-1$ interpolating $f$ at the $n$ equally spaced nodes in $[a, b]$ dividing $[a, b]$ into $n-1$ subintervals of equal sizes. Since whenever $f$ is a polynomial of degree at most $n-1$, the interpolating polynomial $P$ is simply $f$, in this case the approximation is exact. For some particular choices of $n$ (e.g. $n = 3$, which gives Simpson's rule), the formula is exact for polynomials of higher degree. $\endgroup$
    – Dan Fox
    Jul 18 '14 at 14:12
  • $\begingroup$ Is the $P$ you mentioned unique? Also I don't understand your last statement about the formulas being exact for polynomials of higher degree. $\endgroup$
    – Jed
    Jul 18 '14 at 14:26
  • $\begingroup$ If one specifies $n$ distinct nodes and $n$ values at these nodes there is a unique polynomial of degree $n-1$ taking the given values at the given nodes. The requirement that it take the given values at the given nodes gives $n$ equations for its $n$ unknown coefficients. It is straightforward to construct a solution (the Lagrange formulas are the easiest), which must therefore be unique by elementary linear algebra. My last statement is a caveat - the argument given shows exactness for polynomials up to a certain degree, but this degree is not in all cases the best possible. $\endgroup$
    – Dan Fox
    Jul 18 '14 at 14:43
  • $\begingroup$ See wikipedia, Numerical Analysis by Burden definition 4.1 for degree of precision, theorem 4.2 for closed Newton-Cotes formulas and theorem 4.3 for open Newton-Cotes formulas. You can find many more details in this book. $\endgroup$
    – Dante
    Jul 18 '14 at 21:08
1
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.