Motivation
Interpolation commits to reproducing selected samples exactly. Another goal is to keep the largest error over an entire interval as small as possible. These goals can disagree. A polynomial may improve its worst error by moving away from every sampled value, sharing the error more evenly across the interval. To judge that trade, we need a norm and a precise optimization problem.
Uniform approximation leads to an unexpectedly concrete certificate: the error of a best degree- polynomial reaches its maximum magnitude with alternating signs at at least ordered points. The number of points comes from the number of zeros a competing polynomial difference can have. We prove both directions, including existence and uniqueness, using only continuity, compactness, and elementary polynomial facts. No differentiability of the target function is required.
Definitions
Definition 16.1.1
(Best uniform approximant)
Fix a nondegenerate closed interval , a real continuous function , and an integer . Let be the real polynomials of degree at most , including the zero polynomial. The uniform norm and best error are
The maximum exists by continuity and compactness. A polynomial attaining the infimum is a best uniform approximant. This is also called a minimax approximant: minimize the maximum absolute error, with no weighting in this unit.
Definition 16.1.2
(Alternating extremal sequence)
For a candidate , put and . When , an alternating extremal sequence consists of ordered points
These are extremal error points, rather than interpolation nodes where the error vanishes. The polynomial degree bound counts all coefficients, including a constant term. If itself belongs to , then and its unique best approximant is simply ; the positive-error alternation argument is unnecessary.
Definition 16.1.3
(Chebyshev polynomial)
The Chebyshev polynomial is defined by . The recurrence , starting with , proves it is a polynomial. For its leading coefficient is , and its values at alternate between and .
Theorem/Proposition
Theorem 16.1.4
(Existence, alternation, and uniqueness)
Every real continuous on has a unique best approximant in . For a candidate with positive error , it is best if and only if its error has an alternating extremal sequence of at least points, equivalently one containing a sequence of length .
The statement concerns the entire interval and exact extremal magnitudes. An alternating pattern observed on a finite sample grid is not by itself a certificate for the continuous problem.
Corollary 16.1.5
(Chebyshev extremality as an actual best-approximation problem)
For , the unique best polynomial of degree at most approximating on is
Equivalently, is the unique smallest-uniform-norm monic degree- polynomial. On , the corresponding monic residual is
and the best approximant to is , with error .
Proof sketch or proof idea
First establish that an optimizer exists
Proof
(Attainment by compactness in coefficient space)
Choose a minimizing sequence with , discarding finitely many terms so these norms are at most . Fix distinct points in the interval. Their values are uniformly bounded by .
The linear map from a polynomial's coefficient vector to these values is invertible: a polynomial in its kernel has distinct zeros and degree at most , so must vanish. Consequently the coefficient vectors of form a bounded sequence in finite-dimensional Euclidean space. A convergent subsequence exists. Its coefficients define a polynomial , and coefficient convergence implies uniform convergence on the bounded interval, since each fixed monomial is bounded there. The reverse triangle inequality for norms gives . This proves attainment without assuming the minimizing sequence itself converges.
Alternation prevents a better competitor
Proof
(Sufficiency by counting zeros of a difference)
Suppose has alternating extremal points and a competitor had strictly smaller error. Set . At a point where , the inequality forces ; where , it forces . Thus changes sign between every successive pair of the points. The intermediate value theorem supplies distinct zeros, impossible for a nonzero polynomial of degree at most . The zero polynomial cannot have the required strict signs either. Hence no better competitor exists.
Without enough alternation, construct a better polynomial
Proof
(Necessity by a sign-matching perturbation)
This direction needs care: looking only at a few local maxima does not cover the whole error function. Let
These are compact, and is nonempty. If both signs occur, the disjoint compact sets have positive distance. Starting at the leftmost point of , take the first extremal point of the opposite sign to its right, then repeat. Each transition crosses at least that positive distance, so this process stops after finitely many steps. If only one sign occurs, there is just one block.
The procedure partitions the ordered extremal set into consecutive constant-sign blocks with alternating signs. Before the first point of the next block, the preceding block has a last extremal point: compactness and the positive separation prevent its points from accumulating at an opposite-sign extremum. Therefore adjacent blocks are separated by a nonempty gap containing no point of . If there is no alternating sequence of length , the number of blocks is .
Choose one separator in each of the gaps. A polynomial
can be given the same sign as on the first block, and then on every block because both signs flip across each gap. When , take the appropriate constant. Its degree is at most , it has no zero on , and compactness gives . Put .
Choose a relative open neighborhood of on which and have the same sign, , and . Such a neighborhood exists by continuity. For sufficiently small with , subtraction does not overshoot zero on , so
The compact complement , if nonempty, contains no extremal point. Its maximum error is at most for some . Further require . There,
Combining the two uniform estimates shows that has strictly smaller error. Thus a best positive-error polynomial must have the required alternation. The construction explains why continuity and control away from the exact extrema are essential.
Proof X-ray
Where the number of blocks meets the degree
The necessity proof is a contrapositive: from too little alternation it constructs a strictly better polynomial . Three separate ingredients are needed, and each uses a different hypothesis.
First, the extremal set is split into at most blocks of constant sign. This is where continuity of is essential: it makes and compact and disjoint, hence at positive distance, so there are finitely many blocks with genuine gaps between them. The count is exactly the negation of an alternating sequence of length .
Second, the key move: one separator per gap gives of degree , so is an admissible direction in , and it has the sign of on all of , not merely at a few visible peaks. This is the only place the degree bound enters, and it is the same count as in the sufficiency proof, where alternation points force zeros of a polynomial of degree at most .
Third, the step size. Near , subtracting reduces because the signs agree and prevents overshooting zero. Away from , compactness of gives a strict margin , and keeps the perturbation inside it. Without that margin, a point where is close to but outside could become a new worst point.
Why the best polynomial is unique
Proof
(Uniqueness by averaging two best approximants)
If distinct polynomials were both best with positive error , their average would also be best: convexity gives error at most , and minimality gives equality. At any point where its error reaches or , both original errors must equal that same extreme, because they lie in and their average is an endpoint. Hence at each extremal point of the average. Necessity supplies such points, forcing the polynomial to vanish identically. This contradiction proves uniqueness. The zero-error case was already settled directly.
Chebyshev's role changes from a bound to an optimizer
Proof
(The Chebyshev residual is optimal)
The leading terms of and cancel, so the displayed has degree at most . Its error is , with alternating extrema after ordering the cosine points from left to right. The theorem proves best approximation and uniqueness. Every monic degree- polynomial can be written with , establishing the equivalent monic problem. Affine scaling gives the interval formula, including the coefficient that makes its leading term exactly one.
Worked examples
Worked example 16.1.6
(The best line for a quadratic is constant)
For on , take . The error ranges from to and has values at . Three alternating extrema certify the unique best approximant even in , not merely among constants. Endpoint interpolation instead gives the line , with maximum error one. Matching the two endpoint samples exactly has doubled the best achievable uniform error. Interpolation at gives and happens to be best; interpolation and minimax can coincide, but need not.
Worked example 16.1.7
(A cubic's best quadratic loses its quadratic term)
Since , the best polynomial in for is , with error . Its residual has successive values at . This also certifies optimality in the smaller space . There is no requirement that a best polynomial use the highest allowed degree; the space specifies an upper bound.
Worked example 16.1.8
(A nonsmooth function still has an alternation certificate)
For on , choose . Setting gives
Thus the error magnitude is at most . At its signs alternate, beginning negative. Any four of these consecutive points certify that this is the unique best quadratic; the full five-point sequence even certifies optimality in . The corner at zero causes no difficulty because the theorem requires continuity, rather than derivatives.
Common mistakes
Counterexample mode
A small integral error norm does not control a peak
On , let for . The zero polynomial has uniform error one, while its squared error is , tending to zero. Optimizing an integral norm and optimizing the largest error are different problems. A narrow continuous peak can be almost invisible to an integral average or a coarse sample grid.
Common mistake
(Sign changes are not alternation)
Alternation requires the error to reach the full value , with , at each listed point, rather than merely to change sign several times. For on and the constant , the error takes the values at : the signs alternate at three points, but . The norm exceeds the optimal , so this is not a best approximant even among constants.
Any alternating sign pattern of its error gives a lower bound for the best error, which is how exchange algorithms are monitored.
A natural next question
What does a candidate that is not best still prove?
Any alternating sign pattern of its error gives a lower bound for the best error, which is how exchange algorithms are monitored.
If has nonzero values of alternating sign at ordered points , then : a competitor with smaller error would make take the sign of at each point, giving zeros. With the upper bound , this brackets . For above, . The Remez exchange algorithm moves the points to narrow this bracket.
The criterion supplies a certificate, not a complete numerical algorithm for locating the points. A sampled maximum can miss an unsampled peak. If an error function is known to be -Lipschitz and every interval point lies within distance of a checked grid point, then the triangle inequality gives . That is a justified grid-to-continuum bound; continuity alone gives no explicit numerical margin without further information.
Concept lensStructural
Zeros impose interpolation; alternating peaks certify optimality
Interpolation uses vanishing errors at prescribed nodes. Minimax approximation uses alternating largest errors at points determined by the solution. Their different constraints explain why a best polynomial can miss the sample values while improving the worst error. Both exploit polynomial dimension, but in different ways.
Summary
Compactness in coefficient space proves existence. Alternating extrema rule out every better competitor by a zero count. Conversely, too few sign blocks allow a polynomial perturbation that improves the error uniformly. Averaging then proves uniqueness. Chebyshev residuals solve the monic extremal problem and furnish explicit best approximants to powers; continuity suffices even for targets with corners.
Exercises
Quick check
(A continuous real function on a compact interval has minimum and maximum . Find its best constant approximant and error, including , and justify uniqueness.)
Solution · Answer
For a constant , the maximum error is . Its minimum is , uniquely at : any smaller radius cannot contain both endpoint values, and at the minimal radius their midpoint is forced. If , the exact constant is the unique zero-error choice.
Quick check
(Find the best polynomial of degree at most two approximating on . Expand its coefficients and list four alternating extremal points and their errors.)
Solution · Answer
The monic optimal residual is . Therefore the approximant is , with error . At the errors are respectively , certifying degree-two optimality.
Quick check
(Show that is the best quadratic approximant to on . Compare its maximum error with interpolation at .)
Solution · Answer
The error is , of norm . At it alternates between and , so the theorem applies to quadratics. The interpolant at the three stated nodes is . Its error ranges from to zero, with norm , twice the optimum.
Quick check
(For degree at most one, can two alternating extremal points certify optimality? Test the target and candidate on , and explain the zero count required by the theorem.)
Solution · Answer
The candidate error is , with alternating extrema at the endpoints, but its norm is one while the zero polynomial is exact. Two points force only one zero of a competing difference, which a nonzero linear polynomial can have. Degree one requires three alternating extremal points to force two distinct zeros and obtain a contradiction.