The Journal of Online Mathematics and Its Applications, Volume 6 (2006)
The Chebyshev Equioscillation Theorem, Robert Mayans

7. Improving the Approximation


Throughout this section, assume that f is a continuous real-valued function on the interval [a, b], and that p is a polynomial approximation to f, and that ||fp|| = E > 0.

Suppose that f, p has a sectioned alternating set with n + 1 points. Each upper section has an upper point, but no lower point, and each lower section has a lower point, but no upper point. In fact, we can say a little more:

Lemma 5

Suppose that f, p has a sectioned alternating set, and ||fp|| = E > 0. Then there is an ε > 0 such that:

E + εf(x) − p(x) ≤ E for every x in an upper section,
Ef(x) − p(x) ≤ Eε for every x in a lower section.

Proof

If the ith section is an upper section, then the continuous function fp assumes its maximum and minimum values on the section, as it is a closed interval. The maximum value is E at the alternating point, but the minimum value must be greater than E, since by construction the upper section has no lower points. So, there is an εi > 0 such that E + εif(x) − p(x) ≤ E for every x in the ith section.

Similarly, if the ith section is a lower section, there is an positive number εi such that Ef(x) − p(x) ≤ Eεi for every x in the section.

Take ε to be the minimum of the εi's, and the lemma is proved.

Lemma 6:

Suppose that fp has a sectioned alternating set of length n + 1, with ||fp|| = E > 0. Then there is a polynomial q of degree n such that ||f − (p + q)|| < E.

Proof

Let s1 < s2 < ... < sn be the endpoints of the sections that are interior to the interval. In other words, the n + 1 sections are [a, s1], [s1, s2], ..., [sn − 1, sn], [sn, b]. Let r(x) = (xs1) (xs2) ··· (x-sn). Then for any section [si, si + 1], r(x) is either positive for every x in (si, si + 1), or negative for every x in (si, si + 1).

Whether r(x) is positive or negative in (si, si + 1) alternates as you go through the sections from left to right. Either r(x) is positive on the upper sections and negative on the lower sections, or the other way around: positive on the lower sections and negative on the upper sections. Multiply r(x) by σ = 1 or σ = −1, so that the polynomial is positive on the upper sections and negative on the lower sections.

Finally, find ε > 0 such that Ef(x)-p(x) ≤ Eε for the lower sections, and E + εf(x) − p(x) ≤ E on the upper sections, and choose a positive scaling constant k such that |k · r(x)| < ε for all x in [a, b]. We will show that if q(x) = σ · k · r(x), then p + q is a better approximation to f than p is.

Claim: If x is in a lower section, then −E < f(x) − (p(x) + q(x)) < −E.

In the case where

then q(x) < 0 and so f(x) − (p(x) + q(x)) > f(x) − p(x) ≥ −E.

The remaining case is when x = si for some i, and q(x) = 0. But then x cannot be an upper point or a lower point, since it belongs to both an upper and lower section. Hence f(x) − (p(x) + q(x)) = f(x) − p(x) > −E.

So in all cases, if x is in a lower section, then f(x) − (p(x) + q(x)) > −E.

Since |q(x)| < ε, we must have |f(x) − (p(x) + (q(x))| ≤ |f(x) − p(x)| + |q(x)| < Eε + ε = E.

Combining, we have E < f(x) − (p(x) + q(x)) < E for every x in a lower section, and the claim is proved.

Claim: If x is in an upper section, then E < f(x) − (p(x) + q(x)) < −E. The proof is entirely analogous.

So the maximum value of f(x) − (p(x) + q(x)) on [a, b] is less than E, and the minimum value of f(x) − (p(x) + q(x)) on [a, b] is greater than E. We conclude that ||f − (p + q)|| < E = ||fp||.

Demonstration of the improved approximation

In the following applet, a randomized function fp is generated whose alternating points and section boundaries are among the numbers −1.0, −0.9, −0.8, ..., 0.8, 0.9, 1.0. By construction, the norm of fp is 1.0 and the ε value ≥ 1 / 3.

After pressing Next, a graph is displayed of the polynomial q(x) = ± k · (xs1) · (xs2) ···, scaled so that its norm is < 1 / 3, and with the sign set so that the positive values of q(x) are in the upper sections, and the negative values of q(x) are in the lower sections.

After pressing Next again, the graph is displayed of (fp) − q, the top graph minus the middle graph. The upper sections have been moved slightly downward, and the lower sections have been moved slightly upward, and the new function f − (p + q) has a norm < 1.0

By pressing Next again, a new example is generated and the cycle repeats.