Polynomial Approximation On Partitions

Why Approximate Smooth Functions by Local Polynomials?

A smooth regression function can be complicated globally while being well described by a low-degree polynomial on a sufficiently small region. Partitioning the domain into regular cells makes that local description precise: smoothness controls the error on each cell, while the number and size of cells determine how those local errors combine in an integrated $L^2$ norm. The resulting bounds are a basic tool for understanding approximation spaces; they do not by themselves account for the statistical cost of estimating the polynomial coefficients.

Partitions and Approximation Error

Take the domain to be the unit cube $[0,1]^d$, where $d$ is the dimension. For an integer $m\geq 1$, divide each coordinate interval into $m$ equal pieces. This gives $m^d$ cubes, each with side length $h=1/m$. Boundaries shared by adjacent cubes can be assigned to either cell; they have Lebesgue measure zero and do not change an $L^2$ error.

Definition: For a nonnegative integer $q$, let $\mathcal{P}_{q,h}$ be the set of functions that, on each cell of the regular partition, agree almost everywhere with a polynomial in $d$ variables of total degree at most $q$. The polynomials may differ from cell to cell. For a function $f$, its best $L^2$ approximation error in this space is $$ \inf_{g\in\mathcal{P}_{q,h}} \|f-g\|_{L^2([0,1]^d)}, \qquad \|u\|_{L^2(A)}^2=\int_A |u(x)|^2\,dx. $$

The total-degree convention means that a monomial $x_1^{a_1}\cdots x_d^{a_d}$ is included when $a_1+\cdots+a_d\leq q$. Each cell has $\binom{q+d}{d}$ polynomial coefficients, so the space has dimension $m^d\binom{q+d}{d}$, when coefficients on distinct cells are unrestricted. This dimension count is separate from the approximation error bound.

Hölder Smoothness and Degree-Limited Approximation

For clarity, use the following convention for a Hölder smoothness index $\beta>0$. Write $\beta=k+\alpha$, where $k$ is a nonnegative integer and $0<\alpha\leq 1$. For integer $\beta$, take $k=\beta-1$ and $\alpha=1$. A function belongs to a Hölder ball of radius $L$ if its partial derivatives through order $k$ are bounded by $L$, and every derivative of order $k$ satisfies $|D^\nu f(x)-D^\nu f(y)|\leq L\|x-y\|^\alpha$. The derivatives are understood on the cube, with continuous extensions to its boundary. The norm $\|\cdot\|$ here is Euclidean.

Theorem: Suppose $f$ belongs to this Hölder ball on $[0,1]^d$. There is a constant $C$, depending only on $d,\beta,q$, such that $$ \inf_{g\in\mathcal{P}_{q,h}}\|f-g\|_{L^2([0,1]^d)} \leq C L h^{\min(\beta,q+1)}. $$ In particular, if $q\geq k$, the bound is $C L h^\beta$. The constant does not depend on $m$ or on the particular function $f$.

To prove the bound, consider one cell $A$ and choose a point $a$ in its closure. If $q\geq k$, use the Taylor polynomial of $f$ at $a$ through degree $k$. Along the line from $a$ to $x$, the one-dimensional Taylor remainder is controlled by the Hölder variation of the derivatives of order $k$. Since $\|x-a\|\leq\sqrt d\,h$, this gives $|f(x)-T_{a,k}(x)|\leq C L h^{k+\alpha}=C L h^\beta$ throughout the cell. This argument also covers $k=0$: it is just the Hölder condition on $f$.

If $q<k$, then $\beta>q+1$. Use instead the Taylor polynomial through degree $q$. The derivatives of order $q+1$ are bounded by a constant times $L$: when $q+1\leq k$ this is part of the assumed derivative bounds. Taylor's remainder is therefore at most $C L h^{q+1}$ on the cell. In either case, the chosen cell polynomial has pointwise error at most $C L h^{\min(\beta,q+1)}$. Its squared error integrated over the cell is at most $C^2L^2h^{2\min(\beta,q+1)}h^d$. There are $m^d=h^{-d}$ cells. Summing these integrals gives a squared global error at most $C^2L^2h^{2\min(\beta,q+1)}$; taking square roots proves the theorem. $\square$

The bound displays two distinct limits. If the degree is high enough, smoothness determines the rate. If the degree is too low, adding smoothness alone cannot improve the order beyond $q+1$ for this approximation space. The dimension $d$ appears in the constant and in the number of coefficients, while the power of $h$ is the smoothness or degree-limited order.

Worked Example: A Hölder Function on a Two-Dimensional Grid

Suppose $d=2$, $\beta=3/2$, and $f$ lies in a Hölder ball of radius $L=2$. Use polynomials of degree $q=1$ on a grid with $m=8$, so $h=1/8$. Here $\beta=1+1/2$, hence $k=1$, and $q=k$. The theorem gives $$ \inf_{g\in\mathcal{P}_{1,1/8}}\|f-g\|_{L^2} \leq 2C(1/8)^{3/2} =\frac{C}{8\sqrt{2}}. $$

There are $8^2=64$ cells. A bivariate polynomial of total degree at most one has $1+2=3$ coefficients on each cell, so the piecewise space has dimension $64\cdot3=192$. The approximation order is $h^{3/2}$, not $h^2$: the function's stated smoothness, rather than the availability of a higher-degree space, is the limiting factor here.

Worked Example: Increasing Degree Does Not Always Improve the Rate

Let $d=1$, $\beta=5/2$, $L=1$, and $m=4$, so $h=1/4$. With degree $q=1$, the exponent is $\min(5/2,2)=2$, and the error is at most $C(1/4)^2=C/16$. With degree $q=3$, the exponent is $\min(5/2,4)=5/2$, and the error is at most $C'(1/4)^{5/2}=C'/32$. The constants may differ, but the powers of the mesh width are explicit.

The linear space cannot exploit all the stated smoothness: its rate is limited to $h^2$. Degree three is sufficient to reach the smoothness-limited rate $h^{5/2}$; choosing an even higher degree does not improve that exponent under this bound.

Integer-Order Sobolev Approximation

A Sobolev condition controls weak derivatives in an integrated rather than pointwise sense. For an integer $s\geq1$, let $W^{s,2}([0,1]^d)$ consist of functions whose weak derivatives $D^\nu f$ are square-integrable for every multi-index $\nu$ with $|\nu|\leq s$. Write the order-$s$ seminorm as $$ |f|_{W^{s,2}(A)}^2=\sum_{|\nu|=s}\|D^\nu f\|_{L^2(A)}^2. $$ This seminorm measures the highest-order derivatives; lower-order polynomial components need not be small.

Theorem: For integer $s\geq1$ and $q\geq s-1$, there is a constant $C=C(d,s,q)$ such that every $f\in W^{s,2}([0,1]^d)$ satisfies $$ \inf_{g\in\mathcal{P}_{q,h}}\|f-g\|_{L^2([0,1]^d)} \leq C h^s |f|_{W^{s,2}([0,1]^d)}. $$

We prove the local bound first. On a cube $A$ of side $h$, there is a polynomial $p_A$ of degree at most $s-1$ for which the average of every derivative $D^\nu(f-p_A)$, $|\nu|\leq s-1$, over $A$ is zero. To see existence, choose the polynomial coefficients in descending degree. At degree $s-1$, the averages of derivatives of order $s-1$ determine the coefficients of the monomials of that degree. Having chosen the terms of degrees greater than $j$, choose the degree-$j$ terms to set the averages of derivatives of order $j$ to zero. Derivatives of those new terms of order $j$ are constants, and lower-degree terms cannot affect those averages. Continuing down to degree zero gives the required polynomial.

For a mean-zero function $u$ on a cube of side $h$, the Poincaré inequality gives $\|u\|_{L^2(A)}\leq C_dh\|\nabla u\|_{L^2(A)}$. Applying this inequality to each $D^\nu(f-p_A)$ for $|\nu|=0$, then to derivatives of order one, and continuing up to order $s-1$, yields $$ \|f-p_A\|_{L^2(A)} \leq C_{d,s}h^s \left(\sum_{|\nu|=s}\|D^\nu f\|_{L^2(A)}^2\right)^{1/2}. $$ At each application the relevant derivative has mean zero by the choice of $p_A$; derivatives of order $s$ of $p_A$ vanish. The Poincaré inequality applies to weakly differentiable functions as well as smooth ones. One way to obtain its cube version is first to prove it for smooth functions using the fundamental theorem of calculus along coordinate directions and Jensen's inequality, then extend it to $W^{1,2}$ by density. Thus the local argument also holds for Sobolev functions.

Now use $p_A$ on each cell to construct $g\in\mathcal{P}_{q,h}$; this is allowed because $q\geq s-1$. Squaring the local inequality and summing over cells gives $$ \|f-g\|_{L^2([0,1]^d)}^2 \leq C_{d,s}^2 h^{2s} \sum_A\sum_{|\nu|=s}\|D^\nu f\|_{L^2(A)}^2 =C_{d,s}^2h^{2s}|f|_{W^{s,2}([0,1]^d)}^2. $$ Taking square roots proves the theorem. $\square$

Worked Example: Exact Sobolev Error for a Quadratic

Take $f(x)=x^2$ on $[0,1]$, $s=2$, and degree $q=1$. Divide the interval into $m$ cells of width $h=1/m$. On a cell centered at $c$, write $x=c+t$, with $-h/2\leq t\leq h/2$. Then $x^2=c^2+2ct+t^2$. The first two terms are linear in $t$, so the best local linear approximation leaves the residual $t^2-h^2/12$; $h^2/12$ is the average of $t^2$ over the cell.

The squared error on one cell is $$ \int_{-h/2}^{h/2}(t^2-h^2/12)^2\,dt =h^5\left(\frac{1}{80}-\frac{1}{144}\right) =\frac{h^5}{180}. $$ There are $m=1/h$ cells, so the global squared error is $h^4/180$, and the global $L^2$ error is $h^2/\sqrt{180}$. This has the predicted order $h^s=h^2$. In this case $|f|_{W^{2,2}}=\|f''\|_{L^2}=2$, so the explicit calculation is consistent with the theorem's bound, whose constant need not be sharp.

Using the Bounds Carefully

These approximation inequalities explain how a smoothness condition translates into a deterministic error for a finite-dimensional function space. They do not state how well data can estimate the best approximating polynomial; that is a separate statistical question. In particular, a smaller mesh width reduces the approximation bound but increases the number of coefficients, approximately as $m^d\binom{q+d}{d}$. Dimension therefore affects the balance that arises when approximation is combined with estimation.

Common pitfall: It is incorrect to claim that a degree-$q$ piecewise polynomial always has error $O(h^\beta)$ for every $\beta$. If $q+1<\beta$, the available Taylor polynomial may only give order $h^{q+1}$. Conversely, for a Sobolev $W^{s,2}$ bound of order $h^s$, the degree must be at least $s-1$. Check both the smoothness and the approximation degree before stating the rate.

Key takeaway: On regular cubes, the Hölder approximation order is $h^{\min(\beta,q+1)}$, while integer-order Sobolev smoothness $s$ gives order $h^s$ when $q\geq s-1$. Summing local squared errors over the partition preserves these powers of $h$ in the global $L^2$ norm.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

For a Hölder function with $\beta=1.8$, what approximation exponent does degree $q=1$ give? What exponent does degree $q=2$ give?
Why does summing cellwise squared errors over $h^{-d}$ cells not introduce an extra power of $h$ into the final Hölder $L^2$ rate?
For integer Sobolev smoothness $s=3$, what is the minimum polynomial degree required by the stated theorem?
How many coefficients are in the piecewise-polynomial space when $d=2$, $m=5$, and $q=1$?
Explain why increasing $q$ beyond the smoothness-limited threshold need not improve the exponent in the Hölder bound.