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

6. Sectioned Alternating Sets

Alternating sets with sections

Suppose that f is continuous on [a, b], and p is a polynomial approximation, and that x0, ..., xn − 1 is an alternating set for f, p. Let E = ||fp||. By definition, the values of f(xi) − p(xi) 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 x0, ..., xn − 1, together with nontrivial closed intervals I0, ..., In − 1, called sections, with the following properties:

• The intervals partition [a, b]: every point in [a, b] belongs to some Ii, and the intersection of two different sections is either empty or contains just the common endpoint.
• For every i, xi is in Ii.
• If xi is an upper point, then Ii contains no lower points. If xi is an lower point, then Ii 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(π ex) 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.

Your browser does not support the applet tag.

Lemma 4

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

Proof

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 |xy| < δ. 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.

Your browser does not support the applet tag.

Adding sections to an alternating set

Theorem 5

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

Proof

Let x0, ..., xn − 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, xi] where y < xi, and right half-sections: intervals of the form [xi, y] where xi < y. If xi is an upper point, then no point in the left or right half-section is a lower point; and if xi is a lower point, then no point in the left or right half-section is an upper point.

Step 1

Suppose that x0 > a and x0 is an upper point. If there are no lower points in [a, x0], then [a, x0] is the left half-section for x0. 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 x0 > a and x0 is a lower point. If there are no upper points in [a, x0], then [a, x0] is the left half-section for x0. 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 x0, ..., xn − 1) where either a = x0 or [a, x0] is a half-section for x0.

Step 2

Suppose now that xi, xi + 1 are adjacent alternating points. Suppose also that xi is an upper point, and xi + 1 is a lower point. [The case when xi is a lower point and xi + 1 is an upper point is completely analogous, and is omitted.]

Let c be the last upper point on [xi, xi + 1] and let d be the first lower point on [xi, xi + 1]. (So xic < xi + 1 and xi < dxi + 1.)

If c < d, then let y be any point strictly between c and d. Then [xi, y] is a valid upper right half-section for xi, since there are no lower points between xi and d > y. Also, [y, xi + 1] is a lower left half-section for xi + 1, since there are no upper points between y > c and xi + 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 xi, a lower point d, an upper point c, and a lower point xi + 1. Add the points d, c to the alternating set, and repeat this step for the pair of alternating points xi, d. Repeat Step 2 for the alternating points xi, d.

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

Step 3

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

If there are no lower points in [xn − 1, b], then we can make [xn − 1, b] a right half-section for xn − 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 [xn − 1, c].

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

Demonstration of the algorithm

The following applet steps through the algorithm to generate a sectioned alternating set. A randomized example of a function fp 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.