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

The Chebyshev Equioscillation Theorem, Robert Mayans

Suppose that `f` is continuous on
[`a`, `b`],
and `p` is a polynomial approximation, and that
`x`_{0}, ..., `x`_{n − 1}
is an alternating set for
`f`, `p`.
Let
`E` = ||`f` − `p`||.
By definition, the values of
`f`(`x`_{i}) − `p`(`x`_{i})
for
`i` = 0, 1, ..., `n` − 1
are alternately `E` or
−`E`.
Call a point
`x` in [`a`, `b`]
an upper point if
`f`(`x`) − `p`(`x`) = `E`,
and a lower point if
`f`(`x`) − `p`(`x`) = −`E`.

Let us define the notion of sections for an alternating set. A sectioned alternating set is an alternating set `x`_{0}, ..., `x`_{n − 1}, together with nontrivial closed intervals `I`_{0}, ..., `I`_{n − 1}, called sections, with the following properties:

- The intervals partition
[
`a`,`b`]: every point in [`a`,`b`] belongs to some`I`_{i}, and the intersection of two different sections is either empty or contains just the common endpoint. - For every
`i`,`x`_{i}is in`I`_{i}. - If
`x`_{i}is an upper point, then`I`_{i}contains no lower points. If`x`_{i}is an lower point, then`I`_{i}contains no upper points.

The sections alternate between sections containing upper points (called upper sections) and sections containing lower points (called lower sections).

In the following example,
`f`(`x`) = cos(`π` `e`^{x})
and
`p`(`x`) = 0.
The unique lower point is at
`x` = 0 and the unique upper point is at
`x` = ln 2 = 0.693147.
We selected sections
[−1, 0.3] and
[0.3, 1] for the alternating set
(0, ln 2).
Our convention is to plot upper sections in blue and lower sections in red.

Let `f` be continuous on
[`a`, `b`], and let `p` be a polynomial approximation, and suppose that
`f` ≠ `p`.
Then there is a finite bound on the length of any alternating set.

The function
`f`(`x`) − `p`(`x`)
is uniformly continuous on
[`a`, `b`].
Choose
`δ` > 0
such that
|(`f`(`x`)-`p`(`x`)) − (`f`(`y`) − `p`(`y`))| < `E` / 2
whenever
|`x` − `y`| < `δ`.
So the distance between any upper point and any lower point is ≥ `δ`. This puts a finite upper bound on the length of any alternating set.

Note that the bound is on the length of an alternating set, not on the number of upper or lower points. In the following function, the number of upper points is infinite, as is the number of lower points. But an alternating set cannot be longer than 2.

Let `f` be continuous on
[`a`, `b`],
and let `p` be a polynomial approximation, and suppose that
`f` ≠ `p`.
Then any alternating set can be extended to an alternating set with sections.

Let
`x`_{0}, ..., `x`_{n − 1}
be the alternating set. If
`n` = 0,
we can always start an alternating set with a single point, the global maximum/minimum. So we may assume that
`n` ≥ 1.

We present an algorithm for building sections for an alternating set, and enlarging the alternating set when necessary. The applet below walks through the steps of the algorithm for a randomized error function.

The algorithms builds left half-sections: intervals of the form
[`y`, `x`_{i}] where
`y` < `x`_{i},
and right half-sections: intervals of the form
[`x`_{i}, `y`]
where
`x`_{i} < `y`.
If
`x`_{i}
is an upper point, then no point in the left or right half-section is a lower point; and if
`x`_{i}
is a lower point, then no point in the left or right half-section is an upper point.

Suppose that
`x`_{0} > `a` and
`x`_{0}
is an upper point. If there are no lower points in
[`a`, `x`_{0}],
then
[`a`, `x`_{0}]
is the left half-section for
`x`_{0}. If there are lower points, let `y` be the first one, and add it to the alternating set. Repeat Step 1 with the enlarged alternating set that begins with `y`.

Similarly, suppose that
`x`_{0} > `a`
and
`x`_{0}
is a lower point. If there are no upper points in
[`a`, `x`_{0}],
then
[`a`, `x`_{0}]
is the left half-section for
`x`_{0}.
If there are upper points, let `y` be the first one, and add it to the alternating set. Repeat Step 1 with the enlarged alternating set that begins with `y`.

We can repeat step 1 only a bounded number of times, and eventually we have an extended alternating set (which we will relabel as
`x`_{0}, ..., `x`_{n − 1})
where either
`a` = `x`_{0}
or
[`a`, `x`_{0}]
is a half-section for
`x`_{0}.

Suppose now that
`x`_{i}, `x`_{i + 1}
are adjacent alternating points. Suppose also that
`x`_{i}
is an upper point, and
`x`_{i + 1}
is a lower point. [The case when
`x`_{i}
is a lower point and
`x`_{i + 1}
is an upper point is completely analogous, and is omitted.]

Let `c` be the last upper point on
[`x`_{i}, `x`_{i + 1}]
and let `d` be the first lower point on
[`x`_{i}, `x`_{i + 1}].
(So
`x`_{i} ≤ `c` < `x`_{i + 1}
and
`x`_{i} < `d` ≤ `x`_{i + 1}.)

If
`c` < `d`,
then let `y` be any point strictly between `c` and `d`. Then
[`x`_{i}, `y`]
is a valid upper right half-section for
`x`_{i},
since there are no lower points between
`x`_{i}
and
`d` > `y`.
Also,
[y, `x`_{i + 1}]
is a lower left half-section for
`x`_{i + 1},
since there are no upper points between
`y` > `c`
and
`x`_{i + 1}.
Continue Step 2 for the next pair of points in the alternating set.

If
`c` > `d`,
then we have from left to right: an upper point
`x`_{i},
a lower point `d`, an upper point `c`, and a lower point
`x`_{i + 1}.
Add the points `d`, `c` to the alternating set, and repeat this step for the pair of alternating points
`x`_{i}, `d`.
Repeat Step 2 for the alternating points
`x`_{i}, `d`.

In either case, continue Step 2 for successive pair of points in the alternating set, until all the half-sections before
`x`_{n − 1}
have been defined.

If
`x`_{n − 1} = `b`,
then we are done. If not, let us suppose that
`x`_{n − 1}
is an upper point. [The case when
`x`_{n − 1}
is a lower point is similar, and is omitted.]

If there are no lower points in
[`x`_{n − 1}, `b`],
then we can make
[`x`_{n − 1}, `b`]
a right half-section for
`x`_{n − 1},
and we are through. If there are lower points, let `c` be the first lower point, and add it to the alternating set. Continue with Step 2 on the interval
[`x`_{n − 1}, `c`].

The algorithm terminates with half sections defined for every alternating point.

The following applet steps through the algorithm to generate a sectioned alternating set. A randomized example of a function
`f` − `p`
is generated for the interval
[−1, 1]
and with
`E` = 1.
Initially, the alternating set has length two and has no sections. (There will usually be other upper points and lower points, and the final alternating set is usually longer than two.)

The upper sections are drawn in blue as they are defined, and the lower sections are drawn in red. By pressing **Next Step**, the applet will display every step of the above algorithm, adding alternating points and half-sections as needed.

After all the sections are completed, you may press **New Func** to begin again with a new example.