Clenshaw–Curtis and extrapolation quadrature

Input a real function $f$ on a nondegenerate closed interval $[a,b]$ and an integer $L\ge 0$. The output is the finite triangular table $(R_{\mathrm{\ell },j}{)}_{0\le j\le \mathrm{\ell }\le L}$ and its top entry $R_{L,L}$.

1. For each $\mathrm{\ell }=0,\dots ,L$, set $N_{\mathrm{\ell }}:=2^{\mathrm{\ell }}\in \mathbb{N}$ using natural exponentiation of Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$. Since $2^0=1$ and $2^{\mathrm{\ell }+1}=2^{\mathrm{\ell }}\cdot 2$, induction gives $N_{\mathrm{\ell }}\ge 1$, as required by Composite trapezoidal rule. Set $h_{\mathrm{\ell }}:=(b-a)\mathrm{/}{N}_{\mathrm{\ell }}$ and $R_{\mathrm{\ell },0}:=T_{N_{\mathrm{\ell }}}(f)$ using its composite trapezoidal value. Natural powers in real scalar expressions are understood through their canonical real images.
2. For $j=1,\dots ,L$, and then for each $\mathrm{\ell }=j,\dots ,L$, set $R_{\mathrm{\ell },j}:=R_{\mathrm{\ell },j-1}+\frac{R_{\mathrm{\ell },j-1}-R_{\mathrm{\ell }-1,j-1}}{4^j-1}\mathrm{.}$

For $j\ge 1$, claim 3 of Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$ gives $4^j\ge 4>1$, using the natural-to-real power identity of Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$; thus every displayed denominator $4^j-1$ is the positive real $4^j-1$ and is invertible by The reals form a field. This definition returns only the stated finite table; it makes no accuracy claim for nonsmooth inputs or finite-precision arithmetic.

Let $\iota :\mathbb{N}\to \mathbb{R}$ be the canonical natural map of The canonical natural $\iota (n)=n\cdot 1_F$ of a field. Define polynomials $B_m\in \mathbb{R}[X]$ recursively. Put $B_0(X)=1$. If $m\ge 1$ and $B_{m-1}(X)={\sum }_{q=0}^{m-1}{\beta }_{m-1,q}{X}^q$, set $B_m(X):=\iota (m){\sum }_{q=0}^{m-1}{\beta }_{m-1,q}(\frac{X^{q+1}}{\iota (q+1)}-\frac{1}{\iota (q+1)\iota (q+2)})\mathrm{.}$ Every sum is finite. The denominator factors are positive by Canonical naturals are positive and strictly increasing, hence invertible in $\mathbb{R}$ by The reals form a field. Write $B_m:=B_m(0)$ for the Bernoulli number of index $m$.

Let $n\in \mathbb{N}$ with $n\ge 1$ and let $y=(y_0,\dots ,y_n)\in {\mathbb{R}}^{n+1}$. In real-valued formulas, each natural index denotes its canonical real image (The canonical natural $\iota (n)=n\cdot 1_F$ of a field). Since $n>0$ by Canonical naturals are positive and strictly increasing, division by $n$ is defined in $\mathbb{R}$ (The reals form a field). The type-I discrete cosine transform, in the Lobatto convention used here, is the vector $X=(X_0,\dots ,X_n)$ defined by $X_k:=y_0+(-1{)}^k{y}_n+2{\sum }_{j=1}^{n-1}{y}_j\cos \text{\hspace{0.17em}⁣}\left(\frac{jk\pi }{n}\right),0\le k\le n\mathrm{.}$ Here $(-1{)}^k$ is the natural power of the real number $-1$ from Integer powers $a^m$, and the sum is the finite sum of Finite sums and finite products, by recursion, empty when $n=1$. The data $y_j$ are ordered from the right endpoint toward the left endpoint at nodes $\cos (j\pi \mathrm{/}n)$. This definition fixes the unnormalised DCT-I convention; the transform is not defined at $n=0$.

For $j=0,\dots ,8$, set $x_j=-1+j\mathrm{/}4$ and $w_j:=\frac{1}{14175}(989,5888,-928,10496,-4540,10496,-928,5888,989{)}_j\mathrm{.}$ For any real-valued function $f$ on $[-1,1]$, define the closed nine-node rule $Q_8(f):={\sum }_{j=0}^8{w}_{j}f(x_j),$ where the sum is finite. The nodes are equally spaced and include both endpoints; the subsequent weight and exactness lemma verifies that these coefficients are the integrated Lagrange-cardinal weights.

Let $a<b$, let $x_1,\dots ,x_s\in [a,b]$ be a finite indexed list (repetitions are allowed), and let $w_1,\dots ,w_s\in \mathbb{R}$. For every Riemann-integrable $f:[a,b]\to \mathbb{R}$, define the quadrature value and residual by $Q(f):={\sum }_{i=1}^s{w}_{i}f(x_i),L(f):={\int }_a^{b}f(x)dx-Q(f)\mathrm{.}$ Every formal real polynomial's evaluation function is continuous by Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function and integrable by A continuous function on $[a,b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion. In the following exactness predicate, $L(p)$ means $L$ applied to that evaluation function. For a natural $r\ge 1$, say that $Q$ is exact through degree $r-1$ if $L(p)=0$ for the zero polynomial and every nonzero formal real polynomial $p$ with degree at most $r-1$ (Formal real polynomials, evaluation, degree, leading coefficient, and monic polynomials). Here $r-1$ is the natural predecessor specified by The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$. For any natural $q$, the factorial $q!$ in a real-valued formula denotes its canonical real image under The canonical natural $\iota (n)=n\cdot 1_F$ of a field. This denominator is nonzero: $q!\mathrm{\ne }0$ by The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$, every nonzero natural is a successor by Every nonzero natural number is a successor and therefore is at least $1$ in the natural order Order on the natural numbers, and its canonical real image is positive by Canonical naturals are positive and strictly increasing, hence invertible by The reals form a field. For $t\in [a,b]$ define $g_{r,t}(x):=\{\begin{array}{ll}{\displaystyle \frac{(x-t{)}^{r-1}}{(r-1)!}},& x>t,\\ 0,& x\le t,\end{array}{K}_r(t):=L(g_{r,t})\mathrm{.}$ The power is the natural power of Integer powers $a^m$. For $r\ge 2$, $g_{r,t}$ is polynomial and continuous on each side of $t$ by Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function; the polynomial branch extends to $t$ with value $0$ because $r-1\ge 1$, agreeing with the zero branch. Thus it is continuous on $[a,b]$ and Riemann-integrable by A continuous function on $[a,b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion. For $r=1$ it is the indicator of $(t,b]$; if $t=b$ it is zero, and if $t<b$, for each $\epsilon >0$ choose $s\in (t,b)$ with $s-t<\epsilon$ and use the partition with breakpoints $a,t,s,b$ after deleting repeated endpoints. The indicator is constant on all panels except $[t,s]$, where its oscillation is $1$, so its upper-minus-lower sum is at most $s-t<\epsilon$; Riemann's criterion: a bounded $f$ on $[a,b]$ is Darboux integrable if and only if for every real $\epsilon >0$ there is a partition $P$ with $U(f,P)-L(f,P)<\epsilon$ makes it integrable. At $r=1$ the denominator is $0!=1$. Once $K_1$ is shown integrable, changing its values at the finitely many quadrature nodes does not change its integral by Changing an integrable function at finitely many points changes neither its integrability nor its integral.

For every integer $n\ge 0$, the coefficient list of the first-kind Chebyshev polynomial $T_n$ from Chebyshev polynomials of the first and second kinds by their three-term recurrences has no nonzero coefficient above index $n$. In particular, $\mathrm{deg}{T}_n\le n$.

For every integer $n\ge 0$ and every real $\theta$, the first-kind Chebyshev polynomial from Chebyshev polynomials of the first and second kinds by their three-term recurrences satisfies $T_n(\cos \theta )=\cos (n\theta )\mathrm{.}$

For the polynomials of Bernoulli polynomials by a normalized coefficient recursion and every natural $m\ge 1$, $B_m^{\mathrm{\prime }}(x)=\iota (m)B_{m-1}(x),{\int }_0^1{B}_m(x)dx=0.$ In particular, $B_0(x)=1$ and $B_1(x)=x-\frac{1}{2}$. Consequently $B_m(1)=B_m(0)$ for $m\ge 2$. The reflection identity $B_m(1-x)=(-1{)}^m{B}_m(x)$ holds for every $m\ge 0$, so $B_m(0)=0$ for odd $m\ge 3$. Each $B_m$ is bounded on $[0,1]$.

For every integer $k\ge 0$, let ${\mu }_k:={\int }_{-1}^1{T}_k(x)dx$, where $T_k$ is the first-kind Chebyshev polynomial. Then ${\mu }_k=\{\begin{array}{ll}2,& k=0,\\ 0,& k\text{ odd},\\ {\displaystyle \frac{2}{1-k^2}},& k\ge 2\text{ even}\mathrm{.}\end{array}$ Equivalently, ${\mu }_{2r}=2\mathrm{/}(1-4r^2)$ for every integer $r\ge 0$.

For $n\in \mathbb{N}$ with $n\ge 1$ and $k,\mathrm{\ell }\in \mathbb{N}$ with $0\le k,\mathrm{\ell }\le n$, define $S_{k\mathrm{\ell }}:=\frac{1}{2}\cos (0)+{\sum }_{j=1}^{n-1}\cos \text{\hspace{0.17em}⁣}\left(\frac{jk\pi }{n}\right)\cos \text{\hspace{0.17em}⁣}\left(\frac{j\mathrm{\ell }\pi }{n}\right)+\frac{1}{2}(-1{)}^{k+\mathrm{\ell }}\mathrm{.}$ Then $S_{k\mathrm{\ell }}=n$ when $k=\mathrm{\ell }=0$ or $k=\mathrm{\ell }=n$, $S_{k\mathrm{\ell }}=n\mathrm{/}2$ when $k=\mathrm{\ell }$ is strictly between $0$ and $n$, and $S_{k\mathrm{\ell }}=0$ when $k\mathrm{\ne }\mathrm{\ell }$. The half-endpoint convention is the one used by the DCT-I of Type-I cosine transform for Chebyshev–Lobatto data.

Let $a<b$, let $x_1,\dots ,x_s\in [a,b]$ and $w_1,\dots ,w_s\in \mathbb{R}$ define the finite quadrature $Q$ and residual $L$ of Peano kernel of a finite quadrature functional, and let $r\in \mathbb{N}$ with $r\ge 1$. Assume $L$ vanishes on the evaluation functions of the zero polynomial and every nonzero formal polynomial of degree at most $r-1$, and let $f\in C^r([a,b])$. For the kernel $K_r(t)=L(g_{r,t})$ of Peano kernel of a finite quadrature functional, $L(f)={\int }_a^b{K}_r(t)f^{(r)}(t)dt,\mathrm{\mid }L(f)\mathrm{\mid }\le ({\int }_a^b\mathrm{\mid }{K}_r(t)\mathrm{\mid }dt)\mathrm{\parallel }{f}^{(r)}{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{.}$