The Journal of Online Mathematics and Its Applications, Volume 6 (2006)

The Chebyshev Equioscillation Theorem, Robert Mayans

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
||`f` − `p`|| = `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:

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

−`E` + `ε` ≤ `f`(`x`) − `p`(`x`) ≤ `E` for every `x` in an upper section,

−`E` ≤ `f`(`x`) − `p`(`x`) ≤ `E` − `ε` for every `x` in a lower section.

If the `i`th section is an upper section, then the continuous function
`f` − `p`
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` + `ε`_{i} ≤ `f`(`x`) − `p`(`x`) ≤ `E`
for every `x` in the `i`th section.

Similarly, if the `i`th section is a lower section, there is an positive number
`ε`_{i}
such that
−`E` ≤ `f`(`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.

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

Let
`s`_{1} < `s`_{2} < ... < `s`_{n}
be the endpoints of the sections that are interior to the interval. In other words, the
`n` + 1
sections are
[`a`, `s`_{1}], [`s`_{1}, `s`_{2}], ..., [`s`_{n − 1}, `s`_{n}], [`s`_{n}, `b`].
Let
`r`(`x`) = (`x` − `s`_{1}) (`x` − `s`_{2}) ··· (`x`-`s`_{n}).
Then for any section
[`s`_{i}, s_{i + 1}], `r`(`x`)
is either positive for every `x` in
(`s`_{i}, s_{i + 1}),
or negative for every `x` in
(`s`_{i}, s_{i + 1}).

Whether
`r`(`x`)
is positive or negative in
(`s`_{i}, `s`_{i + 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
−`E` ≤ `f`(`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

`x`is an interior point of a lower section [`s`_{i}, s_{i + 1}], or-
[
`x`,`s`_{0}] is a lower section and`x`=`a`, or -
[
`s`_{n},`b`] is a lower section and`x`=`b`,

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

The remaining case is when
`x` = `s`_{i}
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` = ||`f` − `p`||.

In the following applet, a randomized function
`f` − `p`
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
`f` − `p`
is 1.0 and the `ε` value
≥ 1 / 3.

After pressing **Next**, a graph is displayed of the polynomial
`q`(`x`) = ± `k` · (`x` − `s`_{1}) · (`x` − `s`_{2}) ···,
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
(`f` − `p`) − `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.