[Math] formula of coefficients of Newton-Cotes Method in numerical intergation

numerical methods

We know the coefficients of Newton-Cotes method in numerical integration are:

2-points $ 0.5$ , $0.5$

3-points $ 1/6$, $2/3$, $ 1/6$

4-points $1/8$, $3/8$, $3/8$, $1/8$

and so on

I ask if there is a formula of all coefficients in this method.

Best Answer

Maybe read: http://people.clas.ufl.edu/kees/files/NewtonCotes.pdf

It presents a method easily convertible to MATLAB that can be used to generate the coefficients:

function q = NewtonCotesCoefficients(degree)

  q = 0:degree;
  m = fliplr(vander(q));
  for ii = 0: degree
    b(ii + 1) = degree^(ii + 1)/(ii + 1);
  end
  q = m'\b';
end

Related Solutions

[Math] Comparison of Newton-Cotes Quadrature and Gaussian Quadrature formulas

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.)

[Math] Newton-Cotes Quadrature formula

^{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:

Given a function $f$, interpolate $f$ by a polynomial $p$ of degree $n-1$; namely the Lagrange polynomial.
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$.

Best Answer

Related Solutions

[Math] Comparison of Newton-Cotes Quadrature and Gaussian Quadrature formulas

[Math] Newton-Cotes Quadrature formula

Related Question