Uniform approximation

Uniform approximation minimizes the supremum norm of the difference between a target function and an approximant.

For a continuous periodic function setIt measures smoothness through second differences without requiring a derivative. For $h>0$, factoring the translation difference gives ${\omega }_2(f,t)\le (1+t/h{)}^2{\omega }_2(f,h)$. The second-difference integral formula gives ${\omega }_2(f,h)\le h^2\Vert f^{\prime \prime }{\Vert }_{\infty }$ for twice continuously differentiable functions.

For a twice continuously differentiable function and $h\ge 0$, the fundamental theorem of calculus givesThe nonnegative triangular weight has integral $h^2$, so its supremum norm estimate directly controls the second modulus of smoothness.

A uniformly continuous real function on a closed bounded interval can be approximated uniformly by finite step functions. Given $\epsilon >0$, choose a mesh smaller than the uniform-continuity distance and set the approximant equal to a sampled value on each interval. Then the supremum norm of the approximation error is at most $\epsilon$. If the function has a Lipschitz bound $L$, a mesh of maximum length $h$ gives the explicit error bound $\Vert f-g{\Vert }_{\infty }\le Lh$.

Given a family $A$ of approximating functions, a best uniform approximation to $f$ is an element $p\in A$ satisfying

Cosine substitution is an isometry from continuous functions on $[-1,1]$ to even continuous $2\pi$-periodic functions. It satisfies $\omega (\tilde{f},\delta )\le \omega (f,\delta )$ because cosine is Lipschitz continuous with constant one. Even degree-at-most-$n$ trigonometric polynomials correspond exactly to algebraic polynomials via $T_j(\cos \theta )=\cos (j\theta )$. Averaging a periodic approximant with its reflection cannot increase its error against an even target, so the algebraic and periodic best errors are equal.

If a bounded linear map $P$ reproduces every element of an approximating polynomial space $V$, then $f-Pf=(f-v)-P(f-v)$ for every $v\in V$. The triangle inequality and infimum over $v$ prove the displayed error bound. The same argument works for any linear approximating space, and applies in particular to de la Vallée Poussin sums.

For a fixed degree bound, two best approximating polynomials have a best approximating average. At each active point of that average their errors agree, hence the two polynomials agree. There must be at least two more active points than the degree: otherwise polynomial interpolation constructs a strictly improving sign-matching perturbation. The difference has too many zeros and must vanish. Finite-dimensional coefficient compactness also gives existence.

For real $f$, a candidate $u\in U\subset C(K,\mathbb{R})$, and active set $E=\{x:|f(x)-u(x)|=\Vert f-u{\Vert }_{\infty }\}$, the candidate is best precisely when every $v\in U$ has some $x\in E$ with $(f(x)-u(x))v(x)\le 0$. A direction with strictly matching error signs on the whole active set gives a uniformly improving small perturbation by compactness. Conversely one oppositely signed active value already prevents improvement. This criterion yields the Chebyshev alternation theorem.

A degree-at-most-$m$ polynomial is a best uniform approximation precisely when its error attains alternating extrema of equal magnitude at at least $m+2$ ordered points.

For positive summable coefficients, the Weierstrass M-test gives a continuous uniform sum. The partial sum over $3^k\le n$ is the unique best uniform approximation of degree at most $n$. If $3^K$ is the first omitted frequency, every tail term equals $(-1{)}^j$ at $x_j=\cos (j\pi /3^K)$ because its frequency ratio is odd. The entire tail therefore attains alternating extrema equal in magnitude to its coefficient sum at more than $n+1$ points. The Chebyshev alternation theorem proves the assertion, including the empty partial sum at $n=0$.

Bernstein's lethargy theorem says that best approximation errors in nested approximation spaces can tend to zero arbitrarily slowly. For algebraic polynomials on $[-1,1]$, given any decreasing positive sequence ${\delta }_n\to 0$, there is a continuous function $f$ whose best degree-$n$ uniform-approximation error is at least ${\delta }_n$ for every $n$.

For a strictly decreasing positive sequence ${ϵ}_n\to 0$, put $a_0={ϵ}_0-{ϵ}_1$ and $a_k={ϵ}_{3^{k-1}}-{ϵ}_{3^k}$ for $k\ge 1$. These are positive with sum ${ϵ}_0$. The positive lacunary Chebyshev series $f_{ϵ}={\sum }_k{a}_k{T}_{3^k}$ has error ${ϵ}_0$ at degree zero and error ${ϵ}_{3^{K-1}}\ge {ϵ}_n$ whenever $3^{K-1}\le n<3^K$. This proves the lower-bound form of Bernstein's lethargy theorem with an explicit continuous function.

A Jackson-type estimate bounds an approximation error by a smoothness quantity such as a modulus of continuity, with the smoothness evaluated at a scale comparable to the reciprocal of the approximating degree.

Every continuous $2\pi$-periodic function admits degree-at-most-$n$ trigonometric polynomials with supremum norm error bounded by a universal constant times its modulus of continuity at scale $1/n$, for $n\ge 1$. This first-order Jackson-type estimate transfers to algebraic polynomials through cosine substitution for polynomial approximation.

The normalized even kernelis nonnegative, has integral one, and is a trigonometric polynomial of degree $2(n-1)$. Its mass is concentrated on a scale $1/n$: $J_n(t)\le C\min (n,n^{-3}|t{|}^{-4})$ for $|t|\le \pi$. This controls a weighted second moment and produces the Jackson operator estimate.

For $j_{n}f(x)={\int }_{-\pi }^{\pi }f(x-t)J_n(t)dt$, evenness and unit mass reduce the error to an integral of second differences. The Jackson kernel bound and the scaling inequality for the second modulus of smoothness yield $\Vert j_{n}f-f{\Vert }_{\infty }\le C{\omega }_2(f,1/n)$. Since the degree is $2(n-1)$, a degree-$N$ estimate uses $n=\lfloor N/2\rfloor +1$. For $f\in C^2$ this gives $E_N(f)\le C^{\prime }{N}^{-2}\Vert f^{\prime \prime }{\Vert }_{\infty }$.

For periodic uniform approximation,

The first Jackson theorem for periodic approximation applied to $|\sin \theta |$ gives algebraic best error $O(n^{-1})$ for $\sqrt{1-x^2}$. Its ordinary interval modulus of continuity at $1/n$ is at least $\sqrt{2/n-1/n^2}$. Substituting that error rate into the unmodified inverse theorem for trigonometric approximation would instead bound the modulus by $O(\log (n+1)/n)$, a contradiction. Algebraic inverse estimates must incorporate the endpoint compression of cosine substitution for polynomial approximation.

Uniform convergence of positive linear operators on $1,x,x^2$ implies uniform convergence on every continuous function on a compact interval.

Let $K$ be a compact Hausdorff space. A test subspace $H\subset C(K,\mathbb{R})$ containing a strictly positive function is sufficient for uniform convergence of positive linear operators on continuous functions if, for each $x\in K$, the only positive linear functional agreeing with point evaluation on $H$ is that evaluation itself. By the Riesz-Markov-Kakutani representation theorem, this is uniqueness of the positive measure with the prescribed moments. Boundedness from the positive test function and the Banach-Alaoglu theorem prove the assertion by compactness. When $1\in H$, nonnegative tests with a unique zero at each prescribed $x$ give a convenient sufficient condition.

For $2\pi$-periodic continuous functions, convergence of positive linear operators on continuous functions to the identity on $1,\sin x,\cos x$ implies uniform convergence on every function. Indeed $1-\cos (t-x)$ is nonnegative and has just one zero on the circle, so the compact Korovkin test space criterion applies.

Spline interpolation matches prescribed function values at distinct sites by an element of a finite-dimensional spline space. In a B-spline basis its existence and uniqueness for all data are equivalent to invertibility of the B-spline collocation matrix. Distinct ordered sites satisfying the Schoenberg–Whitney theorem give this condition.

For a fixed spline space and admissible interpolation sites, this linear operator sends a continuous function to its unique interpolating spline. Here $Rf$ is the vector of sampled values and $A$ is the B-spline collocation matrix. It reproduces every spline in its range. Its sensitivity to perturbing the data is quantified by the B-spline interpolation operator norm.

For distinct interpolation sites and an invertible B-spline collocation matrix, the interpolant is $P=B{A}^{-1}R$, where $R$ samples data and $Ba={\sum }_i{a}_i{N}_i$. Sampling and basis synthesis have operator norms at most one in the supremum norm. For the reverse inequality, realize the signs of a maximal absolute row sum of $A^{-1}$ as values of a continuous function of norm one, and apply uniform-norm stability of a B-spline basis. This yields both displayed bounds.

For the degree-two Cardinal B-spline basis on knots $1,\dots ,n+3$, sampling at $x_i=i+2$ gives the upper-bidiagonal B-spline collocation matrix $A=(I+S)/2$, where $S$ is the one-step upper shift. Since $S^n=0$, $A^{-1}=2{\sum }_{r=0}^{n-1}(-S{)}^r$ and its maximum absolute row sum is $2n$. The B-spline interpolation operator norm estimate with the order-three stability constant $d_3=3$ gives the displayed linear upper and lower bounds. The lower bound proves failure of uniform boundedness.

For the orthogonal B-spline projector $P$, the normal equations in the mixed-normalization spline Gram matrix give $Ga=r$, with $r_i=(M_i,f)$. Positivity and unit integral of $M_i$ imply $\Vert r{\Vert }_{{\ell }^{\infty }}\le \Vert f{\Vert }_{\infty }$. Nonnegativity and subpartition of unity of $N_i$ give $\Vert {\sum }_i{a}_i{N}_i{\Vert }_{\infty }\le \Vert a{\Vert }_{{\ell }^{\infty }}$. Hence $\Vert P{\Vert }_{\infty }\le \Vert G^{-1}{\Vert }_{{\ell }^{\infty }}$, where the matrix norm is maximum absolute row sum. The range is the spline space, which lies in $C[0,1]$ only for continuous splines.

A regression spline fits a regression function in a finite-dimensional spline approximation space with selected knots. Evaluating its basis at predictor values gives a design matrix, reducing fitting to regression on basis coefficients.

A cubic regression spline represents a mean function in a finite-dimensional space of piecewise cubic functions, with continuity of the function and its first two derivatives at chosen knots. A penalized fit minimizes a residual criterion plus $\lambda \int (f^{\prime \prime }{)}^2$, using ${\Omega }_{jk}=\int B_j^{\prime \prime }{B}_k^{\prime \prime }$. Unlike a full cubic smoothing spline with knots at every distinct observation, its knot set can be much smaller. The mgcv basis bs="cr" uses a penalized natural cubic regression-spline basis with linear tails.

A penalized regression spline estimates basis coefficients by minimizing a residual or likelihood criterion plus a curvature penalty. Basis size limits the available complexity; the penalty controls how much of that complexity is used.

The nonnegative functional $J(g)={\int }_a^b(g^{\prime \prime }(x){)}^{2}dx$. Its null space on $C^2[a,b]$ consists of affine functions. The natural cubic spline interpolant uniquely minimizes this penalty among functions matching at least two prescribed knot values. It is a squared second derivative penalty, not the exact geometric curvature energy of a graph.

A junction between adjacent polynomial pieces of a cubic spline or other spline. Continuity conditions at these junctions determine which piecewise polynomial functions are splines.

A spline knot sequence is a nondecreasing list of spline knots, including their multiplicities, that specifies the junctions and smoothness constraints of a spline space. An order-$k$ B-spline uses $k+1$ consecutive knot entries. Its support must have positive width, and repeated knots are interpreted by confluent divided differences or their limiting convention.

A cubic spline is a twice continuously differentiable piecewise polynomial of degree at most three whose polynomial pieces meet at specified knots.

A natural cubic spline is linear beyond its two outer knots, equivalently its second derivative vanishes at those knots.

For at least two distinct knots $x_1<\cdots <x_n$ and values $v_i$, the unique natural cubic spline matching those values and linear beyond $x_1,x_n$. Its interpolation map is a linear map by uniqueness. Over a larger domain $[a,b]$, the two exterior pieces remain linear. With only one knot, arbitrary slopes of affine functions make uniqueness false.

Let $b_i=N{e}_i$ be the interpolating cardinal basis and set ${\Gamma }_{ij}={\int }_a^b{b}_i^{\prime \prime }{b}_j^{\prime \prime }dx$. Linearity gives $J(N\mathbf{v})={\mathbf{v}}^T\Gamma \mathbf{v}$, and this Gram matrix is a positive semidefinite matrix. Its null space consists precisely of vectors $(\alpha +\beta x_i{)}_i$, by the null-space statement for the second derivative roughness penalty. Thus its rank is $n-2$, including the zero matrix when $n=2$.

For $g=N\mathbf{v}$ and any $\tilde{g}\in C^2[a,b]$ taking the same values at at least two distinct knots, $J(\tilde{g})=J(g)+J(\tilde{g}-g)$. To prove it, set $r=\tilde{g}-g$, integrate $g^{\prime \prime }{r}^{\prime \prime }$ by parts on each polynomial interval and use $g^{(4)}=0$, $r(x_i)=0$, continuous $g^{\prime \prime }$ and linear exterior pieces. Boundary terms cancel. Expanding the square proves the identity. Equality forces $r^{\prime \prime }=0$, so $r$ is an affine function and its two prescribed zeros make it identically zero.

The minimum roughness property of the natural cubic spline interpolant extends to interpolants with an absolutely continuous first derivative and square-integrable second derivative. For $h=f-g$ vanishing at the knots, integration by parts on each cubic interval gives $\int g^{\prime \prime }{h}^{\prime \prime }=0$: the knot boundary terms cancel by continuity, the exterior terms vanish by natural boundary conditions, and the remaining constant-third-derivative term vanishes because $h$ is zero at the interval endpoints. Expanding the square proves minimality. Equality makes $h$ affine; its zeros at two distinct knots force $h=0$, proving uniqueness. Competitors with infinite roughness cannot improve the finite spline penalty.

A B-spline is a compactly supported piecewise polynomial basis function determined by consecutive knots.

For a linearly independent partition-normalized B-spline basis, equivalence of norms gives a lower coefficient-stability constant. The upper bound follows from the subpartition of unity for B-splines. A knot-independent stability bound can be chosen depending on spline order. This norm comparison transfers matrix estimates to the B-spline interpolation operator norm.

A finite collection of the standard partition-normalized B-splines is nonnegative and has sum at most one on the entire real line. Extend the knot sequence in both directions. The full order-one collection sums to one, and summing the Cox-de Boor recurrence preserves that sum because the two coefficients of each lower-order function add to one. The finite collection is a subset. On the basic knot interval the finite sum equals one, also following from Marsden's identity.

For distinct increasing knots and $k\ge 2$, the explicit divided difference formula writes an order-$k$ B-spline as a finite sum of truncated power functions of degree $k-1$. It is a piecewise polynomial function and is globally $C^{k-2}$. Below its first knot the order-$k$ divided difference annihilates a degree-$k-1$ polynomial; above its last knot all values vanish. Nonzero first and last pieces give the exact closed support. Order one gives interval indicators instead of continuous splines.

An order-$k$ B-spline is supported on $[t_i,t_{i+k}]$. Below this interval its truncated-power knot data agree with a degree-$k-1$ polynomial, annihilated by the order-$k$ divided difference; above it all data vanish. Therefore its ordinary or mixed Gram matrix has entries zero when $|i-j|\ge k$. The half-bandwidth is $k-1$, and for strictly increasing knots this bound is sharp.

For partition-normalized B-splines $N_i$ and integral-normalized $M_i=k{N}_i/(t_{i+k}-t_i)$, let $H_{ij}=(N_i,N_j)$ and $D_{ii}=(t_{i+k}-t_i)/k$. The mixed matrix $G_{ij}=(M_i,N_j)$ equals $D^{-1}H$. It is invertible whenever the splines form a basis and their support widths are positive. It need not be symmetric, unlike the ordinary Gram matrix.

For distinct increasing knots, let ${\ell }_i(\cdot ,t)$ interpolate $(\cdot -t{)}_{+}^{k-1}$ on $t_i,\dots ,t_{i+k-1}$ and let ${\omega }_i(x)={\prod }_{r=1}^{k-1}(x-t_{i+r})$. Adjacent interpolants share $k-1$ values; their difference is a multiple of ${\omega }_i$. Its leading coefficient, by the divided difference recurrence, is the order-$k$ B-spline $N_i(t)$. Thus ${\ell }_{i+1}(x,t)-{\ell }_i(x,t)={\omega }_i(x)N_i(t)$. Telescoping proves the Marsden identity. Repeated knots require the well-defined confluent or limiting convention.

A cardinal B-spline is a B-spline whose knots are consecutive integers.

This degree-two Cardinal B-spline has three consecutive unit knot intervals as its support. Its first and last polynomial pieces are $(t-i{)}^2/2$ and $(i+3-t{)}^2/2$; on the middle interval it equals $3/4-(t-i-3/2{)}^2$. Its two interior integer values are $1/2$, and its endpoint values are zero. The maximum is $3/4$, emphasizing that partition normalization does not mean unit maximum height.

A cardinal cubic B-spline is a degree-three Cardinal B-spline. At the three interior integer knots, its nonzero normalized values are $1/6$, $4/6$, and $1/6$.

The Cox-de Boor formula recursively expresses an order-$k$ B-spline using two adjacent order-$(k-1)$ B-splines.

The Marsden identity expands $(x-t{)}^{k-1}$ in a B-spline basis with knot-polynomial coefficients.

For order $k$ B-splines, comparison of coefficients in the Marsden identity giveson the basic knot interval. Here $e_m$ is the elementary symmetric polynomial, with $e_0=1$. The $m=0$ case is partition of unity; the $m=1$ coefficients are the Greville abscissae.

For an order-$k$ B-spline with $k\ge 2$, its Greville abscissa is the arithmetic mean of its $k-1$ interior knots. These are precisely the coefficients reproducing the linear function in the monomial B-spline coefficients formula. The irregular plural is Greville abscissae.

The Marsden dual functionals extract coefficients in a B-spline expansion. If ${\psi }_i$ is the knot polynomial in the Marsden identity, then on polynomials of degree at most $k-1$ one such functional isand the right-hand side is independent of $x$.

When the knot polynomial is normalized as ${\psi }_i(x)={\prod }_{\ell =1}^{k-1}(x-t_{i+\ell })/(k-1)!$, the displayed formula has no additional factorial prefactor. Applied to Marsden's identity, it extracts the coefficient of the corresponding B-spline in any polynomial of degree at most $k-1$. Differentiating the finite sum makes adjacent terms cancel, proving independence of $x$. For linear polynomials the coefficient is their value at the Greville abscissa.

For B-splines $N_j$ and interpolation sites $x_i$, the B-spline collocation matrix is $A_{ij}=N_j(x_i)$. Its invertibility is the existence-and-uniqueness condition for interpolation in that B-spline basis.

For increasing interpolation sites $x_i$ and an order-$k$ B-spline basis with knots $t_i$, the B-spline collocation matrix is invertible exactly whenfor every $i$, equivalently when $N_i(x_i)>0$ for every $i$.

A Schoenberg spline operator is a positive quasi-interpolant ${\sum }_{i}f({\tau }_i)N_i$ with each sample point inside the corresponding B-spline support.