Back to the on-screen lesson ·
Minimising the worst error rather than the average: what Weierstrass promises, how equioscillation at $n + 2$ points recognises the answer, and why a Chebyshev interpolant is usually close enough.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the Weierstrass and equioscillation theorems and what each does and does not give, prove that too few alternations rule out optimality, count the alternations a degree requires, and produce the best approximation to a power exactly.
You can compute a least-squares approximation, which minimises an average, and you know that the monic Chebyshev polynomial minimises a worst case among monic polynomials. This lesson is the general theory of minimising a worst case, and the Chebyshev result turns out to be its one elementary instance.
The uniform norm of an error is its largest size on the interval, $\|f - p\|_\infty = \max|f(x) - p(x)|$. A best uniform or minimax approximation minimises it. The error equioscillates at a set of points when it attains $\pm\|f - p\|_\infty$ there with alternating signs. The Remez algorithm computes a minimax approximation by iterating towards the equioscillation condition.
Least squares minimises an average and can be found by solving equations. Minimax minimises $\|f - p\|_\infty$, the worst error anywhere, and no system of equations produces it — because the maximum is not a differentiable function of the coefficients. Two theorems make the subject workable. Weierstrass says a best approximation is worth looking for: on a closed bounded interval, polynomials come arbitrarily close to any continuous function, so the best uniform error at degree $n$ tends to zero. It gives no rate and names no polynomial. Chebyshev's equioscillation theorem says how to recognise the answer: $p$ of degree $n$ is the best uniform approximation exactly when the error attains its largest size with alternating signs at $n + 2$ points, and the best approximation is unique. The count is one more than the $n + 1$ coefficients, because the level of the error is an unknown too. The necessity half is proved by supposing fewer alternations, building a polynomial with the same sign pattern, and subtracting a little of it to improve every extreme at once — a sign pattern turned into a degree count, exactly as in the Chebyshev minimality proof. That turns an unbounded search into a condition a single candidate can be tested against, which is what the Remez algorithm iterates towards.
Another way: steps
Another way: picture
Draw the error curve of a best approximation between two horizontal lines at $\pm\|f - p\|_\infty$. It touches the top line, then the bottom, then the top again, $n + 2$ times in all. Now imagine pushing the curve down anywhere to reduce one peak: with that many alternations in the way, the same push raises a trough somewhere else. That is the whole theorem — there is no slack left to spend.
Weierstrass is read as a promise that interpolation converges. It is not: it says a good polynomial exists, and Faber's theorem says that for any fixed scheme of nodes there is a continuous function whose interpolants do not converge to it. Existence and construction are different claims, and the whole of approximation theory lives in the gap. The second mistake is expecting the minimax approximation to be much better than a good interpolant. It is better by a factor of about $\log n$ and costs an iteration rather than a formula, which is usually a bad trade.
Approximate $x^{2}$ on $[-1, 1]$ by a linear polynomial. Try $p(x) = 0$: the error is $x^{2}$, largest at $\pm 1$ with the same sign both times.
Two alternations at most; three are needed.
Try $p(x) = \tfrac12$: the error $x^{2} - \tfrac12$ is $+\tfrac12$ at $\pm 1$ and $-\tfrac12$ at $0$.
Three alternations: this is the best.
And the error is $\tilde{T}_2 = x^{2} - \tfrac12$, with largest size $2^{-1}$, as the monic theorem predicts.
The two theorems agreeing.
$f(x) = |x|$ on $[-1, 1]$ is continuous, so the best error tends to zero.
Existence.
It does so like $1/n$ — spectacularly slowly next to a smooth function's geometric rate.
No rate was promised.
A cubic has four coefficients.
The theorem asks for one more alternation than coefficients.
So five points where the error reaches its largest size, with signs alternating — and any cubic whose error does that is the best one.
A polynomial of degree $3$ is the best uniform approximation to a continuous $f$ on an interval. At how many points must the error reach its largest size with alternating signs?
Answer:
Build the argument that a polynomial whose error alternates at fewer than $n + 2$ points is not the best uniform approximation of degree $n$.
This task has no paper form; do it on a device.
Match each notion of a best polynomial approximation to what it minimises.
| The average of the squared error, by solving linear equations | The largest error anywhere, by an iteration towards equioscillation | The error at the nodes, which is made exactly zero | The error near one point, to as high an order as possible | |
|---|---|---|---|---|
| Least squares | ||||
| Minimax | ||||
| Interpolation | ||||
| A Taylor polynomial |
Select every statement the Weierstrass approximation theorem supports.
This task has no paper form; do it on a device.
What is the error of the best uniform approximation of degree $4$ to $f(x) = x^{5}$ on $[-1, 1]$? Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For best uniform approximation of degrees $1$, $2$ and $3$, give the number of alternation points the equioscillation theorem requires.
| Coefficients | Alternation points required | |
|---|---|---|
| Degree $1$ | 2 | |
| Degree $2$ | 3 | |
| Degree $3$ | 4 |
You can recognise a best uniform approximation by its alternations and say what Weierstrass promises. Say in your own words why minimising a worst case cannot be done by solving linear equations.
8. Your turn: how many alternations for the best cubic approximation?, step 3