                          UNIVERSITY OF AUCKLAND
                         DEPARTMENT OF MATHEMATICS

On Bernstein’s comparison theorem, Peano kernels of constant sign and near–minimax approximation

Shayne Waldron^{∗} (waldron@math.auckland.ac.nz)

                             Technical Report
                                 May 1997

ABSTRACT

Some basic properties of what are called ‘B(ernstein)–monotone’ seminorms are investigated. These lie between the classes of monotone and sign–monotone seminorms. It is seen that these seminorms arise naturally in Bernstein’s comparison theorem, the description of Peano kernels of constant sign, and in near–minimax approximations. A number of new results are obtained including some sufficient conditions for a projection to be near–minimax which are easily seen to be satisfied by all the known examples, and a characterisation of the Peano kernels of constant sign where derivatives are replaced by divided differences.

Key Words: monotone seminorm, B–monotone seminorm, sign–monotone seminorm, property B of order k, Bernstein’s comparison theorem, Peano kernel, divided difference, Hermite interpolation, Steffensen’s differentiation formula, positive linear operator, Bernstein operator, variation diminishing splines, near–minimax approximation, Chebyshev polynomial

AMS (MOS) Subject Classifications: primary 41A10, 41A65, 41A80, secondary 41A05, 41A55, 46E99, 65J05

∗ This work was supported by the Israel Council for Higher Education.

1. Introduction

In this section we give some basic properties of what are called ‘B(ernstein)–monotone’ seminorms. These lie between the classes of monotone and sign–monotone seminorms. In the rest of this paper it is shown how these seminorms arise naturally in Bernstein’s comparison theorem, the description of Peano kernels of constant sign, and in near–minimax approximations. In Section 2 we give a characterisation of the Peano kernels of constant sign. The analoguous result where divided differences at distinct points replace derivatives is obtained in Section 4. In Section 3 sufficient conditions for a projection to be near minimax which are easily seen to be satisfied by all known examples are given.

B–monotone seminorms

Here we consider seminorms defined on C(T), where T is some topological space. This covers the cases of interest in this paper, namely T = [a, b], and to deal with divided differences (at distinct points)

T = {(t_{0}, …, t_{k+1}) : a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b}.  (1.1)

Definition 1.2. A seminorm E : C(T) → IR^{+} is said to be monotone if

|f| ≤ |g| ⟹ E(f) ≤ E(g),

more generally B–monotone if it satisfies (the weaker condition)

|f| ≤ g ⟹ E(f) ≤ E(g),

and even more generally sign–monotone if

0 ≤ f ≤ g ⟹ E(f) ≤ E(g).

Further, E is said to be strictly B–monotone if

|f| < g ⟹ E(f) < E(g),

and strictly sign–monotone if

0 ≤ f < g ⟹ E(f) < E(g).

A strictly B–monotone seminorm is B–monotone, since

\begin{aligned}|f| ≤ g & ⟹ |f| < g + ε, ∀ε > 0 ⟹ E(f) < E(g) + εE(1), ∀ε > 0 \\ & ⟹ E(f) ≤ E(g), \end{aligned} (1.3)

and similarly a strictly sign–monotone seminorm is sign–monotone. If T is compact, which (1.1) isn’t, then the classes of strictly B–monotone and B–monotone seminorms coincide, since if E is B–monotone

|f| < g ⟹ |f| ≤ θg, θ := sup \frac{|f|}{g} < 1 ⟹ E(f) ≤ θE(g) < E(g).  (1.4)

Similarly, the classes of strictly sign–monotone and sign–monotone seminorms are the same when T is compact.

It immediately follows that if E is B–monotone, then

E(f) ≤ E(|f|),  (1.5)

and if E is monotone, then

E(f) = E(|f|).

If E is sign–monotone, then f ↦ E(|f|) is a monotone seminorm, and so a sign–monotone seminorm is monotone if and only if E(f) = E(|f|). From this observation it is easily seen that there are B–monotone seminorms which are not monotone, e.g.,

E : C[a, b] → IR^{+} : f ↦ |∫_{a}^{b} f(t) dt| ,

or, more generally, see Lemma 1.9. Further, from (1.5) it follows that there are sign– monotone seminorms which are not B–monotone. For example (as in Kimchi and Dyn [KD79] where sign–monotone norms were introduced), let N : C[a, b] → IR^{+} be the sign– monotone norm given by

N(f) := ∥f^{+}∥_{∞} + ∥f^{−}∥_{∞},  (1.6)

where f^{+}, f^{−} are the positive and negative parts of f. If ∥f^{+}∥_{∞}, ∥f^{−}∥_{∞} ≠ 0, then

N(f) = ∥f^{+}∥_{∞} + ∥f^{−}∥_{∞} > ∥f∥_{∞} = N(|f|),

and so N is not B–monotone.

B–monotone seminorms arise in connection with Peano kernels of constant sign and near–minimax approximations because of the following consequence of the intermediate value theorem.

Lemma 1.7. Suppose that E is a strictly B–monotone seminorm defined on a subspace of C(T), where T is a connected topological space. Then it satisfies the equivalent conditions (a) For ∀f, ∃t ∈ T with

E(f) = |f(t)|E(1).

(b) There ∃A such that ∀f, ∃t ∈ T with

E(f) = |f(t)|A.

Proof: Choosing f = 1 in the second equation gives E(1) = A, which proves the equivalence of (a) and (b). Let

m := inf_{ξ∈[a,b]} |f(ξ)|, M := sup_{ξ∈[a,b]} |f(ξ)|.

Case 1. Suppose that f has a zero. If M is attained, then

|f| ≤ M ⟹ mE(1) = 0 ≤ E(f) ≤ ME(1),

and by the intermediate value theorem there is t ∈ T with E(f) = |f(t)|E(1). If M is not attained, then

|f| < M ⟹ mE(1) = 0 ≤ E(f) < ME(1),

and since f(T) = [m, M) there is t ∈ T with E(f) = |f(t)|E(1) (the intermediate value theorem). Case 2. Suppose that f has no zeroes. Since E(f) = E(−f) we may assume wlog that f > 0. Depending on whether m, M are attained or not, we have either

0 < m ≤ f ≤ M ⟹ mE(1) ≤ E(f) ≤ ME(1),
0 ≤ m < f ≤ M ⟹ mE(1) < E(f) ≤ ME(1),
0 < m ≤ f < M ⟹ mE(1) ≤ E(f) < ME(1),
0 ≤ m < f < M ⟹ mE(1) < E(f) < ME(1),

and the intermediate value theorem can be applied in each case.

A similar result for T = [a, b] is given in Holland, Phillips and Taylor [HPT80:Th.1]. The sign–monotone norm given by (1.6) does not satisfy the conditions (a),(b) of Lemma 1.7. The author does not know whether the conditions (a),(b) are sufficient to characterise the class of B–monotone seminorms. We now show that for certain seminorms at least, this is the case.

Definition 1.8. A linear functional L : C(T) → IR is said to be positive if

f ≥ 0 ⟹ L(f) ≥ 0,

strictly positive if

f > 0 ⟹ L(f) > 0,

and is negative, strictly negative if −L is positive, strictly positive, respectively.

It can easily be shown that strictly positive linear functionals are positive, and that if T is compact then the classes of strictly positive and positive linear functionals coincide (with the same results holding for negative linear functionals).

Lemma 1.9. Suppose that L is a nonzero linear functional defined on a subspace of C(T), where T is a connected topological space. Let E be the seminorm given by

E : f ↦ |Lf|.

Then the following are equivalent

(a) E is strictly B–monotone.

(b) E is strictly sign–monotone.

(c) L is strictly positive or strictly negative.

(d) For ∀f, ∃t ∈ T with

E(f) = |f(t)|E(1).

(e) There ∃A such that ∀f, ∃t ∈ T with

E(f) = |f(t)|A.

(f) For ∀f, ∃t ∈ T with

L(f) = f(t)L(1).

(g) There ∃B such that ∀f, ∃t ∈ T with

L(f) = f(t)B.

Furthermore, if T is a subset of IR^{n}, then E is monotone if and only if the support of L consists of exactly one point, i.e., E is of the form

E : f ↦ c|f(t)|, c > 0, t ∈ T.

Proof: (a)⟹(b) Immediate.

(b)⟹(c) By contraposition. Suppose L is not strictly positive or strictly negative, and (by considering −L if necessary) choose f, g > 0 with L(f) ≥ 0 and L(g) < 0. If L(f) = 0, then E is not strictly sign–monotone, so suppose L(f) > 0 and choose β > 0 such that L(f + βg) = L(f) + βL(g) = 0. Since

0 ≤ f < f + βg, E(f) > E(f + βg) = 0,

the seminorm E is again not strictly sign–monotone.

(a)⟸(c) Since |Lf| = | − Lf|, assume wlog that L is strictly positive. Then |f| < g ⟹ L(|f|) < L(g),

±f ≤ |f| ⟹ ±Lf ≤ L(|f|),

giving

E(f) = |Lf| ≤ L(|f|) < L(g) = E(g),

and so E is strictly B–monotone.

(a)⟹(d)⟺(e) Follows from Lemma 1.7.

(c)⟸(d) By contraposition. Suppose L is not strictly positive or strictly negative, and (by considering −L if necessary) choose f, g > 0 with L(f) ≥ 0 and L(g) < 0. If L(f) = 0, then (d) implies E(1) = 0 ⟹ E = 0, a contradiction. If on the otherhand L(f) > 0, choose β > 0 such that L(f + βg) = 0, then using the function f + βg > 0 obtain the same contradiction as before.

(c)⟹(f) Suppose wlog that L is strictly positive, then L is a strictly B–monotone seminorm and Lemma 1.7 can be applied.

(c)⟸(f) Since L is nonzero, L(f) = f(t)L(1) implies that L(1) ≠ 0, and so if ±L(1) > 0, then ±L is strictly positive.

(f)⟺(g) Choose f = 1 in L(f) = f(t)B to obtain L(1) = B.

Finally, suppose E is monotone, and the support of L contains two points. Then it is possible to choose f, g with disjoint supports and L(f), L(g) ≠ 0. Let β ≠ 0 be such that L(f + βg) = Lf + βLg = 0. Since

|f| ≤ |f + βg|, E(f) > E(f + βg) = 0,

this contradicts E being monotone, and so E is monotone if and only if the support of L is empty (L = 0), or consists of one point (L is a scalar multiple of point evaluation at that point, which clearly gives a monotone seminorm).

This result forms the basis for the characterisation of Peano kernels of constant sign given next.

2. Peano kernels of constant sign

In this section quotient theorems for seminorms and linear functionals (Peano’s kernel theorem) are used to translate the properties of B–monotone seminorms into results about seminorms that satisfy ‘property B of order k’ and Peano kernels of constant sign.

Definition 2.1. A seminorm E : C^{k}[a, b] → IR^{+} is said to satisfy property B of order k (cf Holland, Phillips and Taylor [HPT80]) if

|D^{k}f| ≤ D^{k}g ⟹ E(f) ≤ E(g).  (2.2)

The term ‘property B’ was used because of the connection with Bernstein’s comparison theorem [B26:p8] which states that the seminorm

E(f) := inf_{p∈Π_{k}} ∥f − p∥_{∞}  (Π_{k} the polynomials of degree ≤ k)  (2.3)

satisfies property B of order k + 1. Our use of the term property B differs slightly from the definition given in [HPT80], where for k ≥ 1 the E of (2.2) would be said to satisfy property B of order k − 1. The seminorms that satisfy property B of order 0 (in our sense) are precisely the B–monotone seminorms, hence our choice of the term B(ernstein)– monotone.

Quotient theorem (for seminorms). There is a 1–1 correspondence between the seminorms E : C^{k+1}[a, b] → IR^{+} that vanish on Π_{k} and the seminorms Q : C[a, b] → IR^{+} which is given by

E(f) = Q(D^{k+1}f), ∀f.

In particular, the seminorms that satisfy property B of order k + 1 vanish on Π_{k}, and correspond to the B–monotone seminorms.

Proof: Since D^{k+1} : C^{k+1}[a, b] → C[a, b] is onto, with Π_{k} in its kernel, the function

Q : C[a, b] → IR^{+} : D^{k+1}f ↦ E(f), ∀f ∈ C^{k+1}[a, b]

is well defined and is a seminorm. Conversely for a given seminorm Q : C[a, b] → IR^{+} the map E := Q ∘ D^{k+1} : C^{k+1}[a, b] → IR^{+} is a seminorm which vanishes on Π_{k}. This establishes the 1–1 correspondence.

If E satisfies property B of order k + 1, then

|D^{k+1}p| ≤ D^{k+1}0, ∀p ∈ Π_{k} ⟹ E(p) ≤ E(0) = 0,

so E vanishes on Π_{k}, and the corresponding Q is B–monotone. Conversely, if Q is B– monotone then E := Q ∘ D^{k+1} satisfies property B of order k + 1.

Thus, the seminorms satifying property B of order k + 1 are precisely those of the form E(f) = D^{k+1}f , ∀f, where · is a B–monotone seminorm.

Peano kernel theorem (cf Sard [S63:p.314]). There is a 1–1 (linear) correspondence between the linear functionals λ : C^{k+1}[a, b] → IR that vanish on Π_{k} and the linear functionals L : C[a, b] → IR which is given by

λ(f) = L(D^{k+1}f), ∀f.

In particular, the continuous linear functionals λ ∈ (C^{k+1}[a, b])^{∗} correspond to the continuous linear functionals L ∈ (C[a, b])^{∗}.

Let (·)^{k} denote the monomial x ↦ x^{k}.

Theorem 2.4 (Peano kernels of constant sign). Suppose that λ : C^{k+1}[a, b] → IR is a linear functional. Let E be the seminorm given by

E : C^{k+1}[a, b] → IR^{+} : f ↦ |λf|.

Then the following are equivalent

(a) λ vanishes on Π_{k}, and the linear functional L : C[a, b] → IR defined by λ = L ∘ D^{k+1} is positive or negative.

(b) E satisfies property B of order k + 1.

(c) For ∀f, ∃ξ ∈ [a, b] with

λ(f) = \frac{D^{k+1}f(ξ)}{(k + 1)!}λ ((·)^{k+1}) .

(d) For ∀f, ∃ξ ∈ [a, b] with

E(f) = \frac{|D^{k+1}f(ξ)|}{(k + 1)!}E ((·)^{k+1}) .

(e) There ∃A such that ∀f, ∃ξ ∈ [a, b] with

λ(f) = \frac{D^{k+1}f(ξ)}{(k + 1)!}A.

(f) There ∃B such that ∀f, ∃ξ ∈ [a, b] with

E(f) = \frac{|D^{k+1}f(ξ)|}{(k + 1)!}B.

(g) There is a positive or negative linear map L : C[a, b] → IR for which λ = L ∘ D^{k+1}.

(h) There is a B–monotone seminorm · for which E(f) = D^{k+1}f , ∀f.

(i) There is a sign–monotone seminorm · for which E(f) = D^{k+1}f , ∀f.

(j) The map f ↦ λ(f) does not change sign on the set

{f ∈ C^{k+1}[a, b] : D^{k+1}f ≥ 0}.

Further, if E : C^{k+1}[a, b] → IR^{+} is any seminorm (not necessarily of the form f ↦ |λf|), then the implications

(i) ⟸ (h) ⟺ (b) ⟹ (d) ⟺ (f)  (2.5)

remain valid.

Proof: Recall that since T = [a, b] is compact the strict and nonstrict versions of B–montone, positive, etc are equivalent. Since f ∈ Π_{k} ⟹ D^{k+1}f = 0, each of (c),(d),(e),(f),(g),(h),(i) implies that λ and E vanish on Π_{k}. Thus, in view of the quotient and Peano kernel theorems, Lemma 1.9 gives the equivalence of all conditions except (j), and Lemma 1.7 gives the implications (2.5). The equivalence of (j). The implication (a) ⟹ (j) is immediate. Suppose (j) holds, then

f ∈ Π_{k} ⟹ ±D^{k+1}f ≥ 0 ⟹ ±λ(f) ≥ 0, or ±λ(f) ≤ 0 ⟹ λ(f) = 0,

so λ vanishes on Π_{k}. Since λ does not change sign on {f : D^{k+1}f ≥ 0}, the linear functional L defined by λ = L ∘ D^{k+1} is either positive or negative, which gives (a).

In [HPT84] the implications (a) ⟺ (b) ⟺ (c) were proved for linear functionals λ from a subspace of (C^{k+1}[a, b])^{∗} called the ‘Peano functionals on C^{k+1}[a, b]’.

Suppose that any one of (a), (b), …, (j) in Theorem 2.4 holds. If λ ∈ (C^{k+1}[a, b])^{∗}, then the L for which λ = L ∘ D^{k+1} belongs to (C[a, b])^{∗}, and hence can be represented as integration against a Riemann–Stieltjes measure dw given by a w ∈ NBV[a, b]. For such an L the condition that it be positive or negative is equivalent to dw being a positive or negative measure, which is equivalent to w being a monotone function. Further, if λ ∈ (C^{k}[a, b])^{∗} ⊂ (C^{k+1}[a, b])^{∗}, then L can be represented as integration against a Peano kernel K ∈ L_{∞}[a, b], i.e.,

λ(f) = L(D^{k+1}f) = ∫_{a}^{b} D^{k+1}f(t)K(t) dt,  ∀f,  (2.6)

and the condition that L be positive or negative is equivalent to K being positive or negative. In this situation K is usually referred to as a Peano kernel of constant sign (or as one that does not change sign), and by some authors as definite of order k + 1.

Example 1: The error in quadrature rules exact for Π_{k}. The error in many quadrature rules that are exact for Π_{k} (including the Gauss and Newton–Cotes rules) have Peano kernels of constant sign. This can be seen from the error estimates of the forms (c) and (d) that are given in many numerical analysis texts.

Example 2: The (k + 1)–th order divided differences of f at a multiset of k + 1 points in [a, b]

λ : f ↦ [θ_{0}, …, θ_{k+1}]f

satisfies the conditions (a),(c),(e),(g),(j). This is easily seen from the Hermite–Genocchi formula

λ(f) = ∫_{0}^{1} ∫_{0}^{s_{1}} ⋯ ∫_{0}^{s_{k}} D^{k+1}f(θ_{0} + s_{1}(θ_{1} − θ_{0}) + ⋯ + s_{k+1}(θ_{k+1} − θ_{k})) ds_{k+1} ⋯ ds_{2} ds_{1}, which shows that L is positive. The Peano kernel K representing L (cf (2.6)) is the (normalised) B–spline of order k + 1 with knots {θ_{0}, …, θ_{k+1}} (provided not all of the knots are the same).

Example 3: The error in Hermite interpolation from Π_{k}. Let H_{Θ} : C^{k+1}[a, b] → Π_{k} be the operator of Hermite interpolation to the multiset Θ := {θ_{0}, …, θ_{k}} of points in [a, b], and ω_{Θ}(x) := ∏_{j=0}^{k}(x − θ_{j}). Since the pointwise error at x ∈ [a, b]

λ : f ↦ f(x) − H_{Θ}f(x) = ω_{Θ}(x)[θ_{0}, …, θ_{k}, x]f

is a scalar multiple of a (k + 1)–th order divided difference, it satisfies (a),(c),(e),(g),(j), and so

|D^{k+1}f| ≤ D^{k+1}g ⟹ |f − H_{Θ}f| ≤ |g − H_{Θ}g|

(see, e.g., Kimichi and Dyn [KD78:Lem.2.2]). Thus, if ∥ · ∥ is any monotone seminorm, then

|D^{k+1}f| ≤ D^{k+1}g ⟹ ∥f − H_{Θ}f∥ ≤ ∥g − H_{Θ}g∥.  (2.7)

Example 4: The Steffensen differentiation formula. Let H_{Θ} be the Hermite interpolation operator as above. In Steffenson [St27:p64] it is shown that if x ∈ [a, min Θ] ∪ [max Θ, b], and j = 0, …, k + 1, then ∀f, ∃ξ ∈ [a, b] with

D^{j}f(x) = D^{j}(H_{Θ}f)(x) + \frac{D^{k+1}f(ξ)}{(k + 1)!}D^{j}ω_{Θ}(x).

Thus, the linear functional

λ : f ↦ D^{j}(f − H_{Θ}f)(x)

satisfies (e), and so the seminorm

E : f ↦ |D^{j}(f − H_{Θ}f)(x)|  (2.8)

satisfies property B of order k + 1, etc. A complete description of when (2.8) satisfies property B of order k + 1 (in terms of the sign of the Peano kernel) was recently given in Shadrin [Sh95].

Example 5: The error in best approximation from Π_{k} in a monotone norm. Let ∥ · ∥ be a monotone norm, e.g., any of the L_{p}[a, b]–norms, and P g be a best approximation from Π_{k} to g in this norm, i.e.,

E(g) := E_{k,∥·∥}(g) := inf_{p∈Π_{k}} ∥g − p∥ = ∥g − P g∥.

Since the error g − P g has at least k + 1 zeroes counting multiplicities (this was proved in Kimichi and Dyn [KD79:Th.2.2] for any sign–monotone norm), i.e., P g = H_{Θ}g for some multiset Θ := {θ_{0}, …, θ_{k}} (depending on g), we have by (2.7) the following generalisation of Bernstein’s comparison theorem

|D^{k+1}f| ≤ D^{k+1}g ⟹ E(f) ≤ ∥f − H_{Θ}f∥ ≤ ∥g − H_{Θ}g∥ = ∥g − P g∥ = E(g). (2.9)

In other words, as proved in [KD78:Th.2.2], E_{k,∥·∥} satisfies property B of order k + 1.

Example 6: The error in approximation by a positive linear operator which reproduces the linear polynomials, e.g., the Bernstein operators, or more generally Schoenberg’s variation diminishing spline operators. An operator L is positive (monotone) if

f ≥ 0 ⟹ Lf ≥ 0.

If L : C[a, b] → C[a, b] is a positive linear operator which reproduces the linear polynomials, then

f − Lf = −Q(D^{2}f),  ∀f ∈ C^{2}[a, b],  (2.10)

where Q : C[a, b] → C[a, b] is a positive linear operator.

The existence of a Q satisfying (2.10) follows (pointwise) by applying the Peano kernel theorem to the error functionals f ↦ f(x) − Lf(x), x ∈ [a, b]. That Q is positive, i.e., the Peano kernel of each error functional has constant (negative) sign, can be proved as follows. Suppose that D^{2}f ≥ 0. Then f is convex, and so p the tangent line to f at x lies below f, i.e., p ≤ f. Since L is positive and reproduces the linear polynomials (such as p)

p ≤ f ⟹ p = Lp ≤ f.

Evaluating this at x gives f(x) = p(x) ≤ Lf(x), so that Q(D^{2}f) = Lf − f ≥ 0, i.e., Q is positive.

Though the representation (2.10) (with Q positive) is not mentioned in the literature, the corresponding sharp error bounds

E(f, x) := |f(x) − Lf(x)| ≤ α^{2}(x) ∥D^{2}f∥_{∞},  ∀f ∈ C^{2}[a, b],  (2.11)

where

α(x) := \frac{1}{2}L((· − x)^{2})(x) = \frac{1}{2}E((·)^{2}, x)

are well known (see, e.g., DeVore [De72:Theorem 2.5, p. 39]). Other positive linear operators reproducing the linear polynomials for which (2.10), (2.11) and

E(f, x) := |f(x) − Lf(x)| = α^{2}(x) |D^{2}f(ξ)|, ∃ξ ∈ [a, b],

etc hold include (see, e.g., Păltănea [Pa88]) the Meyer–König and Zeller operators on C[0, 1], and the Szasz–Mirakjan and Baskakov operators on C[0, ∞) (with [0, ∞) replacing [a, b] in the natural way).

3. Near–minimax approximations

In this section we give examples which are related to ‘near–minimax’ approximations.

Definition 3.1. A linear projector P from C[−1, 1] (or C^{k+1}[−1, 1]) onto Π_{k} is said to be near–minimax if for ∀f ∈ C^{k+1}[−1, 1], ∃ξ ∈ [−1, 1] with

∥f − P f∥_{∞} := ∥f − P f∥_{L_{∞}[−1,1]} = \frac{|D^{k+1}f(ξ)|}{2^{k}(k + 1)!}.  (3.2)

This definition is due to Phillips [P92], whose motivation was that the ‘minimax’ error satisfies: ∀f, ∃ξ with

inf_{g∈Π_{k}} ∥f − g∥_{∞} = \frac{|D^{k+1}f(ξ)|}{2^{k}(k + 1)!}

(which follows from Bernstein’s comparison theorem and (b) ⟹ (f) of Theorem 2.4). There are a number of other notions of ‘near–minimax’ approximation in the literature, see, e.g., Mason [M73].

Example 7: In Phillips [P92] it is shown that Lagrange interpolation at the zeroes of T_{k+1} the Chebyshev polynomial of degree k + 1 is a near–minimax approximation. Recall that the infimum

inf_{p∈Π_{k}} ∥(·)^{k+1} − p∥_{∞} = \frac{1}{2^{k}}

is achieved if and only if

(·)^{k+1} − p = 2^{−k}T_{k+1},  (3.3)

and that

∥T_{k+1}∥_{∞} = 1.  (3.4)

In view of (2.7), the seminorm E given by

E(f) := ∥f − H_{Θ}f∥_{∞}

satifies property B of order k + 1, and so, by (b) ⟹ (d) of Theorem 2.4, the Hermite interpolation operator H_{Θ} (see Example 3) is near–minimax if and only if

∥(·)^{k+1} − H_{Θ} ((·)^{k+1}) ∥_{∞} = ∥ω_{Θ}∥_{∞} = \frac{1}{2^{k}} ,

which, by (3.3), holds if and only if ω_{Θ} = 2^{−k}T_{k+1}. Thus, Lagrange interpolation at the zeroes of the Chebyshev polynomial of degree k + 1 is the only Hermite interpolation operator which is near–minimax. Even more generally, this shows the following:

Theorem 3.5 (sufficient conditions for near–minimax approximation). Let P be any projector of C^{k+1}[−1, 1] onto Π_{k} (possibly nonlinear like the ∥·∥_{∞}–best approximation operator) for which E : f ↦ ∥f − P f∥_{∞} is a seminorm. If

(·)^{k+1} − P ((·)^{k+1}) = 2^{−k}T_{k+1},  (3.6)

and f − P f has (at least) k + 1 zeroes counting multiplicities for all f, then P is near– minimax (in the sense of Phillips [P92]). Notice that if P is linear, then

(3.6) ⟹ P (T_{k+1}) = 0.

Proof: Suppose f − P f has k + 1 zeroes Θ, then P f = H_{Θ}f, and by (2.7) the seminorm E satisfies property B of order k + 1. Thus, by (b) ⟺ (d), (e) of Theorem 2.4, P is near–minimax if and only if

E ((·)^{k+1}) = ∥(·)^{k+1} − P ((·)^{k+1}) ∥_{∞} = \frac{1}{2^{k}} ,

which, by (3.3), holds only if (·)^{k+1} − P ((·)^{k+1}) = 2^{−k}T_{k+1}.

If P is a linear projector, then applying P to both sides of (3.6) gives 0 = 2^{−k}P (T_{k+1}).

Example 8: The paper of Brass [Br84] shows the truncated Chebyshev series is near– minimax. An alternative proof of this fact was given independently by Elliot, Paget, Phillips and Taylor [EPPT87]. Since the error in the best approximation from Π_{k} in a weighted L_{2}–norm vanishes k + 1 times, it is easily seen that the truncated Chebyshev series satisfies the conditions of Theorem 3.5.

Example 9: In Phillips and Taylor [PT82] it is shown that the projector f ↦ p ∈ Π_{k} obtained by choosing the unique p ∈ Π_{k} for which the error f − p equioscillates on the point set consisting of the k + 2 extrema of T_{k+1} is near–minimax. Again it is easily seen that this (nonlinear) projector satisfies the conditions of Theorem 3.5.

Example 10: In the paper of Chalmers, Phillips and Taylor [CPT88] two necessary conditions for a continuous linear projector P : C[−1, 1] → Π_{k} to be near–minimax are given. The first of these is that

P (T_{k+1}) = 0.  (3.7)

In our next result we show that infact the stronger condition (3.6) of Theorem 3.5 is necessary for all projectors P : C^{k+1}[−1, 1] → Π_{k} (these need not be linear or continuous). It is also shown that a stronger form of the second condition given is necessary.

Theorem 3.8 (necessary conditions for near–minimax approximation). For a (possibly nonlinear) projector P : C^{k+1}[−1, 1] → Π_{k} to be near–minimax it is necessary that

(·)^{k+1} − P ((·)^{k+1}) = 2^{−k}T_{k+1}.  (3.9)

Further, if P is a continuous linear projector, then for P to be near–minimax each of the (continuous) linear functionals

λ : C^{k+1}[−1, 1] → IR : f ↦ f(z_{i}) − P f(z_{i}), z_{0} < z_{1} < ⋯ < z_{k+1} the extrema of T_{k+1}

must satisfy the (equivalent) conditions of Theorem 2.4 (with the corresponding L changing between being positive/negative for consecutive extrema z_{i} and z_{i+1}). This implies, for example, that f − P f must have k + 1 zeroes (counting multiplicities) for all f from the set {f : D^{k+1}f ≥ 0}.

Proof: Suppose that P is near–minimax. Substituting f = (·)^{k+1} into (3.2) gives

∥(·)^{k+1} − P ((·)^{k+1}) ∥_{∞} = \frac{1}{2^{k}} ,

which, by (3.3), implies (3.9).

Now suppose P is also a continuous linear map, and so each of

λ_{x} : C^{k+1}[−1, 1] → IR : f ↦ f(x) − P f(x),  x ∈ [−1, 1]  (3.10)

is a continuous linear functional (which vanishes on Π_{k}). By the Peano kernel theorem of Section 2, each λ_{x} has a (unique) representation of the form

λ_{x}(f) = L_{x}(D^{k+1}f), ∀f,

where L_{x} : C[−1, 1] → IR is a continuous linear functional, which can therefore be represented by a Riemann–Stieltjes integral

L_{x}(f) = ∫_{−1}^{1} f(t) dw_{x}(t),  ∀f,  w_{x} ∈ BV[−1, 1]

with

∥L_{x}∥ = Var(w_{x}) (the total variation of w_{x}).

Since |λ_{x}(f)| ≤ ∥f − P f∥_{∞}, the near–minimax condition (3.2) implies that

Var(w_{x}) = ∥L_{x}∥ ≤ \frac{1}{2^{k}(k + 1)!}.  (3.11)

Also, by (3.9),

∥L_{x}∥ ≥ \frac{|λ_{x} ((·)^{k+1}) |}{∥D^{k+1}(·)^{k+1}∥_{∞}} = \frac{2^{−k}|T_{k+1}(x)|}{(k + 1)!},  (3.12)

and

\frac{|λ_{x} ((·)^{k+1}) |}{∥D^{k+1}(·)^{k+1}∥_{∞}} = |∫_{−1}^{1} dw_{x}(t)| = |w_{x}(b) − w_{x}(a)| = |Var^{+}(w_{x}) − Var^{−}(w_{x})|. (3.13)

Here Var^{+}(w_{x}), Var^{−}(w_{x}) denote the positive and negative variations of w_{x}. Since (3.4) implies that |T_{k+1}(z_{i})| = 1, it follows from (3.11),(3.12),(3.13) that

Var(w_{x}) = Var^{+}(w_{x}) + Var^{−}(w_{x}) = |Var^{+}(w_{x}) − Var^{−}(w_{x})| = \frac{1}{2^{k}(k + 1)!}, ∀x ∈ \{z_{i}\}.

Thus, when x ∈ {z_{i}}_{i=0}^{k+1} either the positive or negative variation of w_{x} must be zero, i.e., w_{x} is monotone, and so L_{x} is either a positive or negative linear functional. This shows that λ : f ↦ f(z_{i}) − P f(z_{i}) satisfies condition (a) of Theorem 2.4, with L_{z_{i}} being positive when T_{k+1}(z_{i}) = 1, and negative otherwise.

Finally, suppose that D^{k+1}f ≥ 0. By condition (d) of Theorem 2.4 and (3.9), for each z_{i}

f(z_{i}) − P f(z_{i}) = \frac{D^{k+1}f(ξ)}{(k + 1)!}2^{−k}T_{k+1}(z_{i}), ∃ξ ∈ [−1, 1],

which (since T_{k+1}(z_{i}) = (−1)^{k+1−i}) implies

(−1)^{k+1−i} (f(z_{i}) − P f(z_{i})) ≥ 0,  i = 0, …, k + 1,  (3.14)

and so f − P f must have at least k + 1 zeroes counting multiplicities (including at least one zero in each of the intervals [z_{i}, z_{i+1}], i = 0, …, k, with any zero at z_{1}, …, z_{k} being of double multiplicity).

In Chalmers, Phillips and Taylor [CPT88] the second necessary condition for a continuous linear projector P : C[−1, 1] → Π_{k} to be near–minimax is given as:

(ii) For each t ∈ [−1, 1], with f := g_{t} := (· − t)_{+}^{k}/k!, the error f − P f must have k + 1 zeroes x_{i} ∈ [z_{i}, z_{i+1}] (counting multiplicities).

By Theorem 3.8, the Peano kernel for λ_{x} of (3.10) which is given by

K_{x} : t ↦ g_{t}(x) − P g_{t}(x)

is of constant sign for x ∈ {z_{i}} (and this sign changes for consecutive extrema z_{i} and z_{i+1}). Thus, with f := g_{t}, the error f − P f satisfies (3.14), and (as in the proof of Theorem 3.8) it must therefore have k + 1 zeroes of the form given in (ii) above.

4. Divided difference formulation

In this section we give a variation of Theorem 2.4 which uses divided differences of order k + 1 instead of derivatives of order k + 1. This generalises a number of results in the literature including a classical theorem of Popoviciu [Po59] and recent work of Elliott and Taylor [ET91].

Let T be the collection of (ordered) sequences of k + 2 distinct points in [a, b],

T := T (k + 1, [a, b]) := {(t_{0}, …, t_{k+1}) : a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b},

and let D^{k+1} : C[a, b] → IR^{T} be the linear operator which associates with each f ∈ C[a, b] the collection of its divided differences of order k + 1

D^{k+1}f : T → IR : (t_{0}, …, t_{k+1}) ↦ [t_{0}, …, t_{k+1}]f.

This will replace the linear operator D^{k+1} : C^{k+1}[a, b] → C[a, b] in Theorem 2.4 which associates with each f ∈ C^{k+1}[a, b] its k + 1 order derivative D^{k+1}f ∈ C[a, b]. Notice that the range of D^{k+1} consists of continuous functions on T (with the Euclidean metric), i.e.,

ran(D^{k+1}) ⊂ C(T)

(by the well known property that a divided difference is a continuous function of its distinct arguments). The kernel of D^{k+1} is Π_{k}, since if all the k + 1 order divided differences of the function f ∈ C[a, b] vanish, then p ∈ Π_{k} its Lagrange interpolant at the k + 1 points a ≤ t_{0} < ⋯ < t_{k} ≤ b satisfies

f(t) − p(t) = (t − t_{0})(t − t_{1}) ⋯ (t − t_{k}) [t_{0}, t_{1}, …, t_{k}, t]f = 0, ∀t ∉ {t_{0}, …, t_{k}},

and so f = p ∈ Π_{k}. Since the kernel of D^{k+1} is Π_{k}, similarly to the case of D^{k+1}, we obtain the following factorisation theorems.

Peano kernel theorem (for D^{k+1}). There is a 1–1 (linear) correspondence between the linear functionals λ : C[a, b] → IR that vanish on Π_{k} and the linear functionals L : ran(D^{k+1}) → IR which is given by λ = L ∘ D^{k+1}. (cf Sard [S63:p.311])

Seminorm quotient theorem (for D^{k+1}). There is a 1–1 correspondence between the seminorms E : C[a, b] → IR^{+} that vanish on Π_{k} and the seminorms Q : ran(D^{k+1}) → IR^{+} which is given by E = Q ∘ D^{k+1}. In particular, the seminorms that satisfy the strict property B of order k + 1, i.e.,

|[t_{0}, …, t_{k+1}]f| < [t_{0}, …, t_{k+1}]g, ∀a ≤ t_{0} < ⋯ < t_{k+1} ≤ b ⟹ E(f) < E(g),

vanish on Π_{k}, and correspond to the strictly B–monotone seminorms.

Though T is bounded and connnected, it is not closed (e.g., the points (t_{0}, …, t_{0}), t_{0} ∈ [a, b] lie on its boundary). It is for this reason the “strict” forms of Lemmas 1.7 and 1.9 were proved, which allows the relevant functionals

L : ran(D^{k+1}) → IR

to be handled.

Theorem 4.1. Suppose that λ : C[a, b] → IR is a linear functional. Let E be the seminorm given by

E : C[a, b] → IR^{+} : f ↦ |λf|.

Then the following are equivalent (a) λ vanishes on Π_{k}, and the linear functional L : ran(D^{k+1}) → IR defined by λ =

L ∘ D^{k+1} is strictly positive or strictly negative.

(b) E satisfies

|[t_{0}, …, t_{k+1}]f| < [t_{0}, …, t_{k+1}]g, ∀a ≤ t_{0} < ⋯ < t_{k+1} ≤ b ⟹ E(f) < E(g).

(c) For ∀f ∈ C[a, b], ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

λ(f) = [t_{0}, …, t_{k+1}]f λ ((·)^{k+1}) .

(d) For ∀f ∈ C[a, b], ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

E(f) = |[t_{0}, …, t_{k+1}]f| E ((·)^{k+1}) .

(e) There ∃A such that ∀f ∈ C[a, b], ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

λ(f) = [t_{0}, …, t_{k+1}]f A.

(f) There ∃B such that ∀f ∈ C[a, b], ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

E(f) = |[t_{0}, …, t_{k+1}]f| B.

(g) There is a strictly positive or strictly negative linear map L : ran(D^{k+1}) → IR for which λ = L ∘ D^{k+1}.

(h) There is a strictly B–monotone seminorm · : ran(D^{k+1}) → IR^{+} for which E(f) = D^{k+1}f , ∀f ∈ C[a, b].

(i) There is a strictly sign–monotone seminorm · : ran(D^{k+1}) → IR^{+} for which E(f) = D^{k+1}f , ∀f ∈ C[a, b].

(j) The map f ↦ λ(f) is of one sign on the set

{f ∈ C[a, b] : [t_{0}, …, t_{k+1}]f > 0, ∀a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b}.

The conditions above imply the (equivalent) conditions (a), …, (j) of Theorem 2.4. Further, if E : C[a, b] → IR^{+} is any seminorm (not necessarily of the form f ↦ |λf|), then the implications

(i) ⟸ (h) ⟺ (b) ⟹ (d) ⟺ (f)  (4.2)

remain valid.

Proof: Since f ∈ Π_{k} ⟹ D^{k+1}f = 0, each of (c),(d),(e),(f),(g),(h),(i) implies that λ and E vanish on Π_{k}. Thus, in view of the quotient and Peano kernel theorems for D^{k+1}, Lemma 1.9 gives the equivalence of all conditions except (j), and Lemma 1.7 gives the implications (4.2).

The equivalence of (j). The implication (a) ⟹ (j) is immediate. Suppose (j) holds, then

f ∈ Π_{k} ⟹ ±D^{k+1}f ≥ 0 ⟹ ±λ(f) ≥ 0, or ±λ(f) ≤ 0 ⟹ λ(f) = 0,

so λ vanishes on Π_{k}. Since λ is of one sign on {f : D^{k+1}f ≥ 0}, the linear functional L defined by λ = L ∘ D^{k+1} is either positive or negative, which gives (a).

For f ∈ C^{k+1}f[a, b], it is well known (cf Example 2) that

[t_{0}, …, t_{k+1}]f = \frac{D^{k+1}f(ξ)}{(k + 1)!}, ∃ξ ∈ [t_{0}, t_{k+1}] ⊂ [a, b],

and so, for example, the equivalence (c) above implies (c) of Theorem 2.4.

Example 11: In Popoviciu [Po59] a function f ∈ C[a, b] is said to be convex of order k on [a, b] if D^{k+1}f > 0, i.e.,

[t_{0}, …, t_{k+1}]f > 0, ∀a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b,

and a linear functional λ : C[a, b] → IR is of the simple form if condition (e) holds, i.e., ∃A ≠ 0 (independent of f) for which ∀f, ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

λ(f) = [t_{0}, …, t_{k+1}]f A.

There it is proved [Po59:Theorem 5] that a linear functional is of the simple form if and only if λ does not vanish on the convex functions of order k. This is the implications (e) ⟺ (j) of Theorem 4.1.

Example 12: The error in best approximation from Π_{k} in a monotone norm ∥ · ∥ (see Example 5). As in Example 3,

|[t_{0}, …, t_{k+1}]f| < [t_{0}, …, t_{k+1}]g, ∀a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b
⟹ |f − H_{Θ}f| < |g − H_{Θ}g|
⟹ ∥f − H_{Θ}f∥ < ∥g − H_{Θ}g∥,

and so, with the notation of (2.9)

\begin{matrix}|[t_{0}, … & , t_{k+1}]f| < [t_{0}, …, t_{k+1}]g, ∀a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b \\ ⟹ E(f) ≤ ∥f − H_{Θ}f∥ < ∥g − H_{Θ}g∥ = ∥g − P g∥ = E(g), \end{matrix}  (4.3)

in other words E_{k,∥·∥} satisfies the condition (b) of Theorem 4.1. By (b) ⟹ (d) we conclude that ∀f ∈ C[a, b], ∃a ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ b with

E_{k,∥·∥}(f) = |[t_{0}, …, t_{k+1}]f| E_{k,∥·∥}((·)^{k+1}).

This result was proved in Elliott and Taylor [ET91:Theorem 2.1] for the case when ∥ · ∥ is the uniform norm.

Example 13: The error in near–minimax approximation. If P is a linear projector of C[−1, 1] onto Π_{k} which for all f ∈ C[−1, 1] satisfies the sufficient conditions for near– minimax approximation given by Theorem 3.5, then, using the notation of its proof, it follows using (4.3) that E : f ↦ ∥f − P f∥_{∞} satisfies condition (b). Hence by (b) ⟹ (d) it follows that ∀f ∈ C[−1, 1], ∃ − 1 ≤ t_{0} < t_{1} < ⋯ < t_{k+1} ≤ 1 with

∥f − P f∥_{∞} = 2^{−k}|[t_{0}, …, t_{k+1}]f|.  (4.4)

For P equal to the truncated Chebyshev series operator (see Example 8) it is shown in Elliott and Taylor [ET91:Theorem 4.1] that (4.4) holds for every f ∈ C^{2}[−1, 1] with points −1 ≤ t_{0} ≤ t_{1} ≤ ⋯ ≤ t_{k+1} ≤ 1 of which at least k are distinct.

References

[B26] S. Bernstein, Leçons sur les propriétés extrémales et la meilleure approximation des fonctions analytiques d’une variable réele, Gauthier–Villars, Paris, 1926.

[Br84] H. Brass, Error estimates for least squares approximation by polynomials, J. Approx.

Theory 41(1984), 345–349.

[CPT88] B. L. Chalmers, G. M. Phillips and P. J. Taylor, Polynomial approximation using projections whose kernels contain the Chebyshev polynomials, J. Approx. Theory 53(1988), 321–334.

[De72] R. A. DeVore, The Approximation of Continuous Functions by Positive Linear Operators, Springer–Verlag, Berlin, 1972.

[D79] N. Richter–Dyn, On best nonlinear approximation in sign–monotone norms and in

norms induced by inner products, SIAM J. Numer. Anal. 16(4)(1979), 612–622.

[EPPT87] D. Elliot, D. F. Paget, G. M. Phillips and P. J. Taylor, Error of truncated Chebshev series and other near minimax polynomial approximations, J. Approx. Theory 50(1987), 49–57.

[ET91] D. Elliott and P. J. Taylor, Polynomial approximation errors for functions of low-order continuity, Constr. Approx. 7(1991), 381–387.

[HPT80] A. S. B. Holland, G. M. Phillips and P. J. Taylor, Generalisation of a theorem of Bernstein, In: Approximation Theory III (E. W. Cheney, Ed), pp. 513–516, Academic Press, New York, 1980.

[HPT84] A. S. B. Holland, G. M. Phillips and P. J. Taylor, A relation between Peano kernels and a theorem of Berstein, J. Approx. Theory 41(1984), 386–389.

[KD78] E. Kimchi and N. Richter-Dyn, Restricted range approximation of k-convex functions in monotone norms, SIAM J. Numer. Anal. 15(1978), 1030–1038.

[KD79] E. Kimchi and N. Richter-Dyn, A necessary condition for best approximation in monotone and sign–monotone norms, J. Approx. Theory 25(1979), 169–175.

[M73] J.C. Mason, Some methods of near–minimax approximation using Laguerre polynomials, SIAM J. Numer. Anal. 10(1973), 470–477.

[Pa88] R. Păltănea, Improved estimates with the second order modulus of continuity in approximation by linear positive operators, Anal. Numér. Théor. Approx. 17(2)(1988), 171–179.

[P92] G. M. Phillips, Error estimates for near-minimax approximations, In: Approximation Theory, Spline Functions and Applications (S. P. Singh, Ed), pp. 223–241, Kluwer, Dordrecht, Netherlands, 1992.

[PT82] G. M. Phillips and P. J. Taylor, Polynomial approximation using equioscillation on the extreme points of Chebyshev polynomials, J. Approx. Theory 36(1982), 257– 264.

[Po59] T. Popoviciu, Sur le reste dans certaines formules linéaires d’approximation de l’analyse, Mathematica (Cluj) 1(1959), 95–142.

[S63] A. Sard, Linear approximation, Math. Survey 9, AMS, , 1963.

[Sh95] A. Yu. Shadrin, Error bounds for Lagrange interpolation, J. Approx. Theory 80(1995), 25–49.

[St27] J. F. Steffensen, Interpolation, Williams and Wilkins, Baltimore, 1927.