Polynomial Approximation

Measuring Polynomial Approximation

In the previous tutorial, the supremum norm measured how far apart two functions are uniformly. We now use that norm to ask a specific question: among all polynomials of a prescribed degree, which one comes closest to a given continuous function? There are two distinct issues. We can define the smallest possible error as an infimum, but an infimum need not generally be attained. For polynomials on a closed interval, finite-dimensionality ensures that an optimal polynomial does exist.

Throughout, let $a<b$, and let $C[a,b]$ carry the supremum norm $\|f\|_\infty=\sup_{x\in[a,b]}|f(x)|$. We will focus on approximation of one function at a time, with a fixed degree bound. This is different from asking whether the errors can be made arbitrarily small by allowing the degree to increase; that broader question requires an additional theorem.

Definition: For an integer $n\geq0$, let $\mathcal{P}_n$ be the subspace of $C[a,b]$ consisting of all real polynomials of degree at most $n$, including the zero polynomial. For $f\in C[a,b]$, define its degree-$n$ uniform approximation error by $$ E_n(f;[a,b])=\inf_{p\in\mathcal{P}_n}\|f-p\|_\infty. $$ A polynomial $p_*\in\mathcal{P}_n$ is a best degree-$n$ approximant to $f$ if $\|f-p_*\|_\infty=E_n(f;[a,b])$.

The error is nonnegative and finite: the zero polynomial is an admissible choice, so $0\leq E_n(f;[a,b])\leq\|f\|_\infty$. The word “best” means that no other polynomial within the same degree bound has a smaller supremum error. It does not, by itself, imply that the best polynomial is unique.

Existence of a Best Approximant

The existence argument uses finite-dimensional compactness. The space $\mathcal{P}_n$ has dimension $n+1$, with basis $1,x,\ldots,x^n$. Earlier results established that finite-dimensional subspaces of normed spaces are closed, and that closed bounded subsets of finite-dimensional normed spaces are compact. We use these facts to show that a sequence of polynomials whose errors approach the infimum has a convergent subsequence.

Theorem (Existence of a Best Polynomial Approximant): Let $a<b$, let $f\in C[a,b]$, and let $n\geq0$. There exists $p_*\in\mathcal{P}_n$ such that $$ \|f-p_*\|_\infty=E_n(f;[a,b]). $$

Proof. Write $E=E_n(f;[a,b])$. By the definition of infimum, for each positive integer $k$ we can choose $p_k\in\mathcal{P}_n$ such that $\|f-p_k\|_\infty<E+1/k$. In particular, since $E\leq\|f\|_\infty$, the triangle inequality gives \[ \|p_k\|_\infty\leq\|f\|_\infty+\|f-p_k\|_\infty <2\|f\|_\infty+1. \] Thus $(p_k)$ is bounded in the normed space $\mathcal{P}_n$. This space is finite-dimensional, so the Bolzano–Weierstrass theorem in finite dimensions gives a subsequence $(p_{k_j})$ converging in the supremum norm to some $p_*\in\mathcal{P}_n$. The limit belongs to $\mathcal{P}_n$; equivalently, we may use the fact that a finite-dimensional subspace is closed.

The reverse triangle inequality for the supremum norm implies \[ \big|\|f-p_{k_j}\|_\infty-\|f-p_*\|_\infty\big| \leq\|p_{k_j}-p_*\|_\infty\longrightarrow0. \] Also, $E\leq\|f-p_{k_j}\|_\infty<E+1/k_j$, so these errors converge to $E$. Therefore $\|f-p_*\|_\infty=E$, as required. $\square$

A key point is that the minimizing sequence is bounded as a sequence of polynomials, not merely that its errors are bounded. The triangle inequality supplies this bound. Finite-dimensional compactness then provides an actual limiting polynomial. In an infinite-dimensional space, a bounded sequence need not have a convergent subsequence, so this proof does not automatically extend to arbitrary approximation spaces.

Worked Example: Exact Approximation of a Polynomial

On $[-1,1]$, consider $f(x)=2x^3-x+4$. This polynomial has degree three, so $f\in\mathcal{P}_3$. Choosing $p=f$ gives \[ \|f-p\|_\infty=\|0\|_\infty=0. \] Because every approximation error is nonnegative, no smaller value is possible. Hence $E_3(f;[-1,1])=0$, and $f$ itself is a best degree-three approximant. More generally, if $f\in\mathcal{P}_n$, then $E_n(f;[a,b])=0$.

How the Best Error Changes with Degree

The polynomial spaces are nested: every polynomial of degree at most $n$ also has degree at most $n+1$. Increasing the degree bound therefore adds choices without removing any existing choices. The resulting error cannot increase.

Proposition (Monotonicity of Best Approximation Error): For $f\in C[a,b]$ and every integer $n\geq0$, $$ E_{n+1}(f;[a,b])\leq E_n(f;[a,b]). $$

Proof. Since $\mathcal{P}_n\subseteq\mathcal{P}_{n+1}$, every error $\|f-p\|_\infty$ available when taking the infimum over $\mathcal{P}_n$ is also available when taking the infimum over $\mathcal{P}_{n+1}$. The infimum over the larger set cannot be greater. Thus $E_{n+1}(f;[a,b])\leq E_n(f;[a,b])$. $\square$

Monotonicity does not say that the error strictly decreases at every degree. For instance, if $f$ is already a polynomial of degree at most $n$, then both $E_n$ and all later errors are zero. Nor does the definition alone say that the errors tend to zero as $n$ increases. It says only that they form a nonincreasing sequence of nonnegative numbers.

Worked Example: Best Linear Approximation to a Quadratic

Find the best degree-one approximation to $f(x)=x^2$ on $[-1,1]$. Let an arbitrary linear polynomial be $q(x)=ux+v$, and put $R=\|x^2-q\|_\infty$. At $x=1$ and $x=-1$, the residuals are $1-u-v$ and $1+u-v$. Their average is $1-v$, so \[ R\geq|1-v|. \] At $x=0$, the residual is $-v$, giving $R\geq|v|$. Since $1=|(1-v)+v|\leq|1-v|+|v|$, at least one of $|1-v|$ and $|v|$ is at least $1/2$. Consequently $R\geq1/2$ for every linear polynomial $q$.

Now take $q(x)=1/2$. Its residual is $x^2-1/2$, which lies between $-1/2$ and $1/2$ for every $x\in[-1,1]$, and takes both endpoint values of that range. Therefore \[ \|x^2-1/2\|_\infty=1/2. \] The lower bound is attained, so $q(x)=1/2$ is a best degree-one approximant and $E_1(x^2;[-1,1])=1/2$.

Changing the Interval

An approximation problem on $[a,b]$ can be transferred to $[-1,1]$ by an affine change of variable. This is useful because it lets us work on a standard interval without changing the degree bound or the uniform error. The transformation must be applied to both the function and the approximating polynomial.

Theorem (Affine Invariance of Polynomial Approximation Error): Let $a<b$, $f\in C[a,b]$, and define $$ F(t)=f\left(\frac{a+b}{2}+\frac{b-a}{2}t\right),\qquad t\in[-1,1]. $$ Then for every $n\geq0$, $$ E_n(f;[a,b])=E_n(F;[-1,1]). $$

Proof. Define $\phi(t)=(a+b)/2+(b-a)t/2$. This is a bijection from $[-1,1]$ to $[a,b]$. If $p\in\mathcal{P}_n$ on $[a,b]$, then $q(t)=p(\phi(t))$ is a polynomial of degree at most $n$. Conversely, if $q\in\mathcal{P}_n$ on $[-1,1]$, then $p(x)=q((2x-a-b)/(b-a))$ is a polynomial of degree at most $n$ on $[a,b]$. These operations are inverse to one another, so they give a bijection between the two sets of admissible polynomials.

For corresponding polynomials $p$ and $q$, the relation $F(t)-q(t)=f(\phi(t))-p(\phi(t))$ and the fact that $\phi$ maps $[-1,1]$ onto $[a,b]$ give \[ \|F-q\|_{\infty,[-1,1]}=\|f-p\|_{\infty,[a,b]}. \] Taking the infimum over the corresponding sets of polynomials proves the stated equality. $\square$

Worked Example: A Cubic on a Shifted Interval

Consider $f(x)=(x-3)^3$ on $[2,4]$. Under the change of variable $x=3+t$, the interval becomes $[-1,1]$ and the transformed function is $F(t)=t^3$. We first find the best degree-two approximation to $t^3$ on $[-1,1]$.

Let $q$ be any polynomial of degree at most two. Its odd part \[ q_{\mathrm{o}}(t)=\frac{q(t)-q(-t)}{2} \] has the form $ct$ for some real number $c$. The odd part of $t^3-q(t)$ is $t^3-ct$. For every $t$, its absolute value is at most $\|t^3-q\|_\infty$, because it is the average of the residual at $t$ and the negative of the residual at $-t$. Thus $\|t^3-q\|_\infty\geq\|t^3-ct\|_\infty$.

Write $r(t)=t^3-ct$. Direct evaluation gives \[ r(1)-2r(1/2)=(1-c)-2(1/8-c/2)=3/4. \] Consequently $3/4\leq|r(1)|+2|r(1/2)|\leq3\|r\|_\infty$, so every such $q$ has error at least $1/4$. For $c=3/4$, take $q(t)=3t/4$. The residual $r(t)=t^3-3t/4$ has derivative $3t^2-3/4$, which vanishes at $t=-1/2$ and $t=1/2$. At $t=-1, -1/2, 1/2, 1$, its values are respectively $-1/4, 1/4, -1/4, 1/4$. The derivative has constant sign on each interval between these critical points and the endpoints, so the maximum absolute value is $1/4$. This attains the lower bound.

Therefore the best degree-two error for $t^3$ on $[-1,1]$ is $1/4$. By affine invariance, the polynomial $p(x)=3(x-3)/4$ is a best degree-two approximant to $(x-3)^3$ on $[2,4]$, with error $1/4$.

Interpreting the Error and Its Limits

The existence theorem and the explicit examples answer fixed-degree questions: they guarantee an optimizer and, in certain cases, identify it. A different question is whether every continuous function can be approximated with arbitrarily small uniform error by polynomials of increasing degree. The existence of a best polynomial at each individual degree does not answer that question. It guarantees an optimizer for each $n$, not that the sequence of optimal errors tends to zero. The next tutorial addresses this broader issue.

One practical way to organize a fixed-degree problem is to separate the lower-bound argument from the construction. First, establish that no admissible polynomial can have error below a proposed value, often by evaluating the residual at carefully chosen points or using symmetry. Then exhibit a polynomial whose error reaches that value. The quadratic and cubic examples follow this pattern. The existence theorem ensures an optimizer even when finding it explicitly is difficult; it does not, on its own, provide a formula for that optimizer.

Specify the degree bound and norm.
Identify the admissible space $\mathcal{P}_n$ and measure error with the supremum norm on the interval.

Use an affine change if convenient.
Transfer the function to $[-1,1]$; polynomial degrees and uniform approximation errors are preserved.

Prove a lower bound and attain it.
Show every admissible polynomial has at least the proposed error, then verify that a particular polynomial achieves that error.

Takeaway: For every continuous function on a closed interval and every fixed degree bound, a best uniform polynomial approximant exists. The optimal errors are nonincreasing as the degree grows, and an affine change of interval leaves those errors unchanged. These facts provide a framework for studying approximation without yet asserting that the errors tend to zero.

Check Your Understanding

Use the definitions and results in this tutorial to answer the following questions.

Why is the degree-$n$ approximation error finite for every $f\in C[a,b]$?
In the existence proof, what inequality shows that a minimizing sequence of polynomials is bounded?
What does monotonicity of $E_n(f;[a,b])$ say, and what does it not say about the limit as $n$ increases?
Why does an affine change of variable preserve both polynomial degree bounds and uniform approximation error?
For the best linear approximation to $x^2$ on $[-1,1]$, how do the residuals at $-1$, $0$, and $1$ give a lower bound of $1/2$?

What You'll Learn