Numerical analysis Numerical integration and differentiation Theorem

Gauss–Kronrod quadrature

Builds on Gauss–Kronrod quadrature formula Gauss–Legendre quadrature Legendre polynomials Degree of exactness of a quadrature rule

Statement

Let $n \ge 1$ and let $P_n$ be the Legendre polynomial of degree $n$ . Its zeros $x_1, \ldots, x_n$ are the nodes of the $n$ -point Gauss–Legendre rule on $[-1, 1]$ . Let $E_{n+1}$ be the Stieltjes polynomial: the unique monic polynomial of degree $n + 1$ with $\int_{-1}^{1} P_n(x) E_{n+1}(x) x^k \, dx = 0 \quad \text{for } k = 0, 1, \ldots, n.$ Then:

the zeros $y_1, \ldots, y_{n+1}$ of $E_{n+1}$ are real, simple, lie in $(-1, 1)$ , and interlace with $x_1, \ldots, x_n$ ;
the interpolatory rule $K_{2n+1}(f) = \sum_{i=1}^{n} a_i f(x_i) + \sum_{j=1}^{n+1} b_j f(y_j)$ on these $2n + 1$ nodes satisfies $K_{2n+1}(p) = \int_{-1}^{1} p(x) \, dx$ for every polynomial $p$ of degree at most $3n + 1$ .

Remarks

Clause 2 follows from clause 1 by division. Write $p = q \, P_n E_{n+1} + r$ with $\deg q \le n$ and $\deg r \le 2n$ . The term $q P_n E_{n+1}$ vanishes at all $2n+1$ nodes and has integral $0$ by the defining property of $E_{n+1}$ . The remainder $r$ is integrated exactly, because an interpolatory rule with $2n + 1$ nodes is exact up to degree $2n$ . Clause 1 is harder; it was proved by Szegő for the Legendre weight, and it can fail for other weight functions. Example: for $n = 1$ , $P_1 = x$ and the conditions give $E_2(x) = x^2 - \tfrac35$ , so the Kronrod rule uses the nodes $0, \pm\sqrt{3/5}$ and is the $3$ -point Gauss–Legendre rule, exact up to degree $5$ . In practice the difference $\abs{K_{2n+1}(f) - G_n(f)}$ , where $G_n$ is the Gauss rule, serves as an error estimate that costs only $n + 1$ new function values.

Going deeper

For a student

The $n$ -point Gauss rule has degree of exactness $2n - 1$ , and a fresh $(2n+1)$ -point Gauss rule would have degree $4n + 1$ but it would reuse almost none of the old nodes. The Kronrod rule gives up some degree, $3n + 1$ instead of $4n + 1$ , in exchange for reusing all $n$ old nodes. Pairs such as $G_7$ – $K_{15}$ and $G_{10}$ – $K_{21}$ are the basis of adaptive integrators, for example in the QUADPACK library.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Degree of exactness of a quadrature rule concept
Gauss–Kronrod quadrature formula concept
Gauss–Legendre quadrature concept
Legendre polynomials concept
Gauss–Kronrod quadrature statement

Tag	`E8QJJVC1KV`
URI	`m2://E8QJJVC1KV`
Kind	statement, theorem
Writing	W0 stub
MSC	65D32, 41A55
Status	This copy of the site has no build data. Run `m2 status E8QJJVC1KV`.
About	Gauss–Kronrod quadrature formula
Uses	Gauss–Kronrod quadrature formula, Gauss–Legendre quadrature, Legendre polynomials, Degree of exactness of a quadrature rule

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)
a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.