Optimal cubic Lagrange interpolation:
Extremal node systems with minimal Lebesgue constant
Heinz-Joachim Rack and Robert Vajda
Abstract. In the theory of interpolation of continuous functions by algebraic poly- nomials of degree at mostn−1≥2, the search for explicit analytic expressions of extremal node systems which lead to the minimal Lebesgue constant is still an intriguing topic in mathematics today [33]. The first non-trivial casen−1 = 2 (quadratic interpolation) has been completely resolved, even in two alternative fashions, see [25], [27]. In the present paper we proceed to completely resolve the cubic case (n−1 = 3) of optimal polynomial Lagrange interpolation on the unit interval [−1,1]. We will provide two explicit analytic expressions for the uncount- able infinitely many extremal node systemsx∗1 < x∗2 < x∗3< x∗4 in [−1,1] which all lead to the (known) minimal Lebesgue constant of cubic Lagrange interpola- tion on [−1,1]. The descriptions of the extremal node systems (which need not be zero-symmetric) resemble the solutions for the quadratic case and incorporate two intrinsic constants expressed by radicals, of which one constant looks partic- ularly intricate. Our results encompass earlier related work provided in [17], [23], [24], [29], [30] and are guided by symbolic computation.
Mathematics Subject Classification (2010):05C35, 33F10, 41A05, 41A44, 65D05, 68W30.
Keywords: Constant, cubic, extremal, interpolation, Lagrange interpolation, Lebesgue constant, minimal, node, node system, optimal, point, polynomial, sym- bolic computation.
1. Introduction
Lagrange polynomial interpolation on node systemsx1< x2<· · ·< xn−1< xn
in some intervalIis a classical and feasible method to approximate (continuous) func- tions on I by algebraic polynomials of maximal degreen−1, see e.g. [9], [18], [21],
This paper was presented at the third edition of the International Conference on Numerical Analysis and Approximation Theory (NAAT 2014), Cluj-Napoca, Romania, September 17-20, 2014.
[26] or [28] for details. The goodness of this approximation method, as compared with the best possible approximation in Chebyshev’s sense, is measured by means of the Lebesgue constants which can be viewed as operator norms or condition numbers, see also [33]. They depend, for a givenn, solely on the chosen configuration of in- terpolation points, and Lebesgue’s lemma suggests that we choose them in such a manner that the corresponding Lebesgue constant becomes least. Such extremal (or:
optimal) node systems are in a sense the opposite to the equidistant interpolation points which may yield disastrous approximation results, see e.g. Runge’s example in [18]. Although near-optimal node systems are known, and algorithms exist to nu- merically compute optimal (canonical) node systems, see [1] and [18], the search for explicit analytic formulas characterizing optimal node systems remains an intriguing and challenging topic in mathematics today. Here are three quotations in this regard, see also [6], [7], [13], [14], [17], [33]:
• The nature of the optimal setX∗ remains a mystery [15, p. xlvii]
• The problem of analytical description of the optimal matrix of nodes is considered by pure mathematicians as a great challenge.[4]
• To this day there is no explicit representation for the nth row of the optimal array, and in all likelihood there never will be.[16]
It suffices to restrict the search for optimal node systems to the unit interval I = [−1,1]. The first non-trivial casen−1 = 2 of quadratic Lagrange interpolation on Ihas been completely resolved: All optimal node systems x∗1< x∗2 < x∗3 in I can be explicitly described in two alternative fashions, see [25], [27]. In the present paper we proceed to completely resolve the cubic casen−1 = 3. Similarly to the quadratic case we will provide two alternative, but equivalent, explicit analytic (i.e., non-numeric) descriptions of all extremal node systems x∗1 < x∗2 < x∗3 < x∗4 (with −1 ≤ x∗1 and x∗4 ≤1) which, by their definition, lead to the (known) minimal Lebesgue constant of cubic Lagrange interpolation on I. Amplifying Theorem 2 in [17] which states that optimal node systems are not unique, we will furthermore show that actually there exist, for each n−1 ≥ 2, uncountable infinitely many such node systems in I. Generally, they are zero-asymmetrically distributed in I; however, the subset of optimal zero-symmetric node systems deserves special attention: The investigation, in the cubic case, of optimal node systems−x∗4<−x∗3< x∗3< x∗4 produces two intrinsic constants (bandt, as defined below, of whichbis particularly intricate) which are key in describing the general distribution of all optimal node systemsx∗1< x∗2< x∗3< x∗4. These can be geometrically visualized by a 2D-region in the plane spanned by the two outer optimal nodes.
Historically, the first investigation into optimal node systems for the cubic case seems to be [29, p. 229], [30, Problem 6.43], where an analytic, but implicit (i.e., not by radicals) formula for the optimal zero-symmetric node systems as well as for the minimal Lebesgue constant has been provided. However, the reader of [29], [30]
might be left with the impression that actually all optimal node systems had been determined in this way, since optimal zero-asymmetric ones are not mentioned there.
A particular case of a zero-symmetric node system inI(forn−1 = 3) is a canonical node distribution −1 <−x3 < x3 < 1. The unique nodex3 = x∗3 =t which turns
it to the optimal canonical node configuration has been explicitly determined in [23], [24], where also the minimal Lebesgue constant for the cubic Lagrange interpolation on I has been determined in an explicit form. Both quantities can be expressed, using Cardan’s formula, by means of roots of certain cubic polynomials with integer coefficients.
The manuscript is organized as follows: After providing some necessary notations and definitions, we will consider, in an ascending order of generalization, first canon- ical node systems, then zero-symmetric node systems, and finally arbitrary (zero- symmetric and zero-asymmetric) node systems and will establish corresponding opti- mal node configurations. The proofs are postponed to section 6.
We hope that this paper, along with [25], [27] and our dedicated web repository www.math.u-szeged.hu/~vajda/Leb/ will add to the dissemination of computer- aided optimal quadratic and cubic Lagrange interpolation and may stimulate research of the higher-degree polynomial cases, see Remark 7.5.
2. Definitions and basic theoretical background
LetC(I) denote the Banach space of continuous real functions f onI, equipped with the uniform norm:
||f||= max
x∈I |f(x)|. (2.1)
We wish to approximatef by an algebraic polynomial of degree at mostn−1, where n≥3. An old idea, named after Lagrange, see [19], is to samplef atndistinct points inI,
Xn: −1≤x1< x2< . . . < xn−1< xn≤1, (2.2) and to construct an interpolating polynomial of degree at mostn−1 as follows:
Ln−1(x) =Ln−1(f, Xn, x) =
n
X
j=1
f(xj)ℓn−1,j(Xn, x) (2.3) where
ℓn−1,j(x) =ℓn−1,j(Xn, x) =
n
Y
i=1,i6=j
x−xi
xj−xi, (2.4)
so that
ℓn−1,j(Xn, xi) =δj,i (Kronecker delta) (2.5) and hence
Ln−1(xi) =f(xi), 1≤i≤n(interpolatory condition) (2.6) If||f|| ≤1 then (2.3) implies that |Ln−1(x)| can be estimated from above by
n
X
j=1
|ℓn−1,j(Xn, x)|=λn(x) =λn(Xn, x). (2.7) Definition 2.1. We call the xi’s in (2.2) theinterpolation nodes and the gridXn the node system, the unique Ln−1 the Lagrange interpolation polynomial, the ℓn−1,j’s (of exact degreen−1) theLagrange fundamental polynomials, andλn the Lebesgue function (named after Lebesgue, see [34]).
Three properties ofλn are summarized in the following statement, see [4], [17], [28, p. 95]:
Proposition 2.2.
i) λn is a piecewise polynomial satisfying λn(x) ≥1 with equality only if x=xi
(1≤i≤n).
ii) λn has precisely one local maximum, which we will denote by µi =µi(Xn), in each open sub-interval(xi, xi+1)ofXn (1≤i≤n−1). The extremum point in (xi, xi+1), at which the maximum µi is attained, we will denote by ξi =ξi(Xn) so that λn(ξi) =µi holds.
iii) λn is strictly decreasing and convex in (−∞, x1) and strictly increasing and convex in (xn,∞).
Definition 2.3. The largest value of λn in I, denoted by Λn = Λn(Xn), is called the Lebesgue constant:
Λn= max
x∈I λn(x). (2.8)
The importance of Λnin interpolation theory stems from the following inequality (“Er- ror Comparison Theorem”) which can be viewed as a version of Lebesgue’s lemma, but can also be proved directly [26, Theorem 4.1]:
||f−Ln−1|| ≤(1 + Λn)||f−Pn∗−1||, (2.9) where f ∈ C(I), and Pn∗−1 denotes the polynomial of best uniform approximation to f out of the linear space of all algebraic polynomials of degree at most n−1.
Usually, Pn∗−1 is much harder to determine than Ln−1, and of course there always holds||f−Pn∗−1|| ≤ ||f−Ln−1||. The estimate (2.9), which is sharp for somef, tells us that a small Lebesgue constant implies that the approximation tofby the Lagrange interpolation polynomial is nearly as good as the best uniform approximation tof by means ofPn∗−1. Therefore, it is desirable to minimize Λn which can be achieved by a strategic placement of the interpolation nodes.
It is known [26, p. 100] that for eachn≥3 there exists, inI, an extremal (or optimal) node systemXn=Xn∗:−1≤x∗1< x∗2<· · ·< x∗n−1< x∗n≤1 such that there holds
Λ∗n= Λn(Xn∗)≤Λn= Λn(Xn) for all possible choices of node systemsXn. (2.10) Definition 2.4. The Lebesgue constant Λ∗n is calledminimal .
It is furthermore known that for a givenn≥3 an extremal node system is not unique, see [17, Theorem 2], and there in particular exists an extremal node system which includes the endpoints of I as interpolation nodes, see [26, p. 100]. Obviously, all extremal node systems, for a givenn, generate the same minimal Lebesgue constant.
We take the opportunity to amplify [17, Theorem 2] in the following way:
Theorem 2.5. For eachn ≥3 there exist uncountable infinitely many optimal node systemsXn∗:x∗1< x∗2<· · ·< x∗n−1< x∗n inIwhich all yield (2.10).
Definition 2.6. The construction of Ln−1(f, Xn∗, x) is called optimal Lagrange poly- nomial interpolation on Isince it furnishes, for a givenn, the minimal interpolation error in the sense of (2.9).
Definition 2.7. A node system which includes the endpoints ofIas interpolation nodes (that is,x1=−1 and xn= 1) is called acanonical node system (abbreviated CNS).
In answering a conjecture which goes back to [3], it was proved in [8] and in [14] that the following deep result holds true:
Proposition 2.8. If a Lebesgue function corresponding to a CNSXn satisfies the so- called equioscillation property
µ1=µ2=. . .=µn−2=µn−1, (2.11) thenXn is an extremal node system, i.e.Xn=Xn∗ with Λn(Xn∗) = Λ∗n.
Thus, the fulfillment of (2.11) is a sufficient condition for a CNS to be extremal.
Actually, it was additionally proved that a CNS which satisfies (2.11) is unique and zero-symmetric, i.e.,x∗i =−x∗n−i+1 for 1≤i≤n.
To the best of our knowledge, currently the optimal CNSXn =Xn∗ : −1 =−x∗n <
−x∗n−1 < · · · < x∗n−1 < x∗n = 1 and the associated minimal Lebesgue constant Λ∗n = Λ(Xn∗) are explicitly known only ifn= 3 (X3∗:−1<0<1 and Λ∗3= 1.25, see [3], [25], [27] or [33]), or ifn= 4 (see next section).
In the next three sections we will focus on cubic interpolation onI by the Lagrange interpolation polynomialL3, i.e., we setn= 4.
3. The optimal canonical node system and the minimal Lebesgue constant for cubic Lagrange interpolation
We consider first optimal cubic Lagrange interpolation on a CNS. It must be zero-symmetric if it has to be extremal, so that the goal is to find, analytically and explicitly, the unique node x3 =x∗3 = t in X4 : −1 =−x4 < −x3 < x3 < x4 = 1 which turns X4 into the unique extremal node system X4∗ : −1 < −t < t < 1 and to determine the associated minimal Lebesgue constant Λ∗4 = Λ4(X4∗) for cubic Lagrange interpolation on I. This problem, which is also addressed in [21, Example 2.5.3] and [22, Exercise 4.10], has been solved in [23], [24] by means of roots of certain cubic polynomials with integer coefficients: The minimal Lebesgue constant, Λ∗4, is the unique real root of the polynomial
P3∗(x) =−11 + 53x−93x2+ 43x3. (3.1) This root can be explicitly expressed, with the aid of Cardan’s formula, as
Λ∗4 = 1 129
93+3
q
125172+11868√ 69+ 3
q
125172−11868√ 69
(3.2)
= 1.4229195732. . . . (3.3)
The square of the (unique positive) optimal nodex∗3=t is the unique real root of the polynomial
Q∗3(x) =−1 + 2x+ 17x2+ 25x3. (3.4)
Hence t itself can be explicitly expressed, with the aid of Cardan’s formula, as
t = 1
5√ 3
v u u
t−17 + 3 s
14699 + 1725√ 69
2 + 3
s
14699−1725√ 69
2 (3.5)
= 0.4177913013. . . , (3.6)
so that
X4∗:−1<−t < t <1, withtfrom (3.5), (3.7) is the (unique and zero-symmetric) optimal CNS inI.
Furthermore, also the three extremum pointsξi=ξi∗, withξ∗1 =−ξ3∗< ξ2∗= 0 < ξ3∗, of the cubic Lebesgue functionλ∗4(x) =λ∗4(X4∗, x) are expressed in an analogous way in [24], but we only provide here the numerical value ξ3∗ = 0.7331726239. . . , see Figure 1.
Figure 1
An analytical, but implicit, solution for t and Λ∗4 had been provided earlier in [29, p. 229], [30, Problem 6.43], see also [23]: t is the unique positive root of the polynomial
S6(x) =Q∗3(x2) (3.8)
and
Λ∗4= 1 +t2
1−t2. (3.9)
The polynomial (3.1) and the explicit expressions (3.2), (3.5) were not given there.
Numerical values fortand/or Λ∗4 are given, for example, in [1], [2], [4], [11], [20], [21]
and [33].
4. Optimal zero-symmetric node systems for cubic Lagrange interpolation
We consider next optimal cubic Lagrange interpolation on zero-symmetric node systems inI.
Problem 4.1. Find, analytically and explicitly, all optimal zero-symmetric node sys- temsX4∗:−x∗4<−x∗3< x∗3< x∗4 in I!
Our solution to this problem will be expressed by means of the already deployed explicit constant t according to (3.5) and by means of a real parameter β ∈ [1, b]
where the right-hand endpoint b >1 of that interval has still to be determined. We will first state our solution to Problem 4.1 and then turn to the task of determining the constantb.
Theorem 4.2. All optimal zero-symmetric node systems for the cubic Lagrange inter- polation onI are given byX4∗:−x∗4 <−x∗3 < x∗3< x∗4, where
−x∗4=−1
β,−x∗3=−t
β, x∗3= t
β, x∗4= 1
β. (4.1)
Here, t is given by (3.5) and β is an arbitrary number from the interval [1, b]. The right-hand endpoint b >1 of that interval will be specified implicitly and numerically in Lemma4.3, and explicitly in Lemma4.4.
Note that the choiceβ= 1 takes us back to the optimal CNS as given in (3.7). For the constantb in Theorem 4.2 we will now provide an implicit and an explicit analytical description. However, both of them are intricate.
Lemma 4.3. The constantbin Theorem4.2 can be expressed implicitly as the unique positive root of the following polynomial of degree 18 with integer coefficients:
P18(x) =−121 + 220x−1014x2+ 1344x3+ 3283x4−5166x5+ 4502x6 (4.2) + 15692x7−84178x8+ 7868x9+ 210676x10−25694x11−310732x12 + 34154x13+ 255377x14−8450x15−124700x16+ 26875x18.
The numerical evaluation of this root by computer algebra systems yields
b= 1.0433133411. . . . (4.3)
However, the computer algebra systems we have checked do not render the real root bofP18 by means of radicals. But such an explicit representation ofbis possible:
Lemma 4.4. The constant b in Theorem 4.2 can be expressed explicitly in terms of radicals as follows:
b=b(t) = t+t3 2 + 2t−
s
−1 27
(1 + (−1 +t)t)3+ (t+t3)2 4(1 +t)2
!1/3
+ t+t3 2 + 2t +
s
−1 27
(1 + (−1 +t)t)3+ (t+t3)2 4(1 +t)2
!1/3
, (4.4) wheret denotes the constant in(3.5), so thatbstill depends ont. Upon inserting the value(3.5)fort, one obtains in place of(4.4)a non-parametric explicit expression for
b which, however, is quite intricate:
b=
58 + 1
2
14699−1725√
691/3
+ 1
2
14699 + 1725√
691/3!
(4.5) .(150+ 750√
6.
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699+1725√
691/3
−√
58 21/3+ 14699−1725√ 691/3
+ 14699 + 1725√
691/32 3750 22/3√
6 + 30.√
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√
691/32
−
1 91125000
116 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√ 691/3
− 5√
6
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√
691/331/3
+ 58 + 12 14699−1725√
691/3
+ 12 14699 + 1725√
691/3. (150+ 750√
6.
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699+1725√
691/3 +
√
58 21/3+ 14699−1725√ 691/3
+ 14699 + 1725√
691/32 3750 22/3√
6 + 30.√
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√
691/32
−
1 91125000
116 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√ 691/3
− 5√
6
−34 + 22/3 14699−1725√ 691/3
+ 22/3 14699 + 1725√
691/331/3
The first few decimal digits ofb read, more precisely as in(4.3), as follows:
b= 1.043313341111592913631086831954493674798479469403995. . . . (4.6) To give an example, we consider the shortest sub-interval [−x∗4, x∗4] of Iwhich allows optimal cubic Lagrange interpolation. According to Theorem 4.2 we have to choose β=b, so that we get, as a kind of counterpart to the CNS,
Example 4.5. The configuration
−x∗4=−1
b, −x∗3=−t
b, x∗3= t
b, x∗4= 1
b (4.7)
is the unique optimal zero-symmetric node system in I with the shortest interval lengthx∗4−(−x∗4) = 2b. The corresponding numerical values are:
−0.9584848200. . .<−0.4004466202. . .<0.4004466202. . .<0.9584848200. . . (4.8)
and 2
b = 1.9169696400. . . . (4.9)
We note that (4.7) is also unique in having the property that the corresponding Lebesgue function λ4(x) equioscillates on I most, that is, five (= n+ 1) times, see Figure 2.
Figure 2
It is interesting to remark that the analogous configuration for the quadratic case (n = 3) is −2√32 < 0 < 2√32, and the corresponding Lebesgue function λ3(x) equioscillates on I most, that is, four (= n+ 1) times. The extremum points−1 <
−√32 < √32 <1 inI of that particularλ3(x) were considered by Bernstein in [3] and motivated him to state his famous equioscillation conjecture. We therefore call (4.7) the Bernstein-type node system (BNS).
An analytical, but implicit, solution similar to (4.1) had been provided earlier in [29, p. 229] (misprinted) and [30, Problem 6.43]: The optimal zero-symmetric nodes in I are −a < −at < at < 1, where a ∈ [a0,1] and t is, as before, the unique positive root of the polynomial S6(x) = Q∗3(x2) and a0 is the unique positive root of the (parameterized) polynomial
S3(x) =−(t+ 1) + (t3+ 1)x2+ (t3+t)x3. (4.10) However, Tureckii did not expresst anda0 by radicals, and in [29, p. 229] the term (t3+1)x2ofS3(x) was misprinted as (t3+1)x. We observe that the left-hand endpoint a0of the interval [a0,1] coincides with 1b, where the constantbis given in Lemma 4.3 and 4.4. After all, we point out that optimal zero-asymmetric node systems are not mentioned in [29], [30], [31].
5. Optimal arbitrary node systems for cubic Lagrange interpolation
Finally we consider optimal cubic Lagrange interpolation on arbitrary (zero- symmetric and zero-asymmetric) node systems inI.
Problem 5.1. Find, analytically and explicitly, all optimal node systems X4∗ : x∗1 <
x∗2 < x∗3< x∗4 in I!
Our solution to this problem is twofold: Building on the already deployed constantsb in (4.4) andtin (3.5), the first solution describes all four optimal nodes by means of two parameters,α∈[−b,−1] and β ∈[1, b], whereas the second equivalent solution gives only the selection range for the outer optimal nodes x∗1 and x∗4 and expresses the inner optimal nodes x∗2 andx∗3 as functions of them. The first solution is similar to the one given in [25], whereas the second solution is similar to the one given in [27], for the quadratic case.
Theorem 5.2. All optimal node systems for the cubic Lagrange interpolation on Iare given byX4∗:x∗1< x∗2< x∗3 < x∗4, where
x∗1=−2−α−β
−α+β , x∗2=−2t−α−β
−α+β , x∗3=2t−α−β
−α+β , x∗4=2−α−β
−α+β , (5.1) in whichα∈[−b,−1]andβ ∈[1, b]are arbitrary numbers, and the constantsb andt are defined in(4.4)respectively(3.5).
Note that the choice α = −β takes us back to the zero-symmetric case (4.1). To illustrate Theorem 5.2, we give an analytic example:
Example 5.3. Choose α=−1.04∈[−b,−1] and β = 1.03∈[1, b], say. According to (5.1) we get
X4∗:x∗1=−199
207< x∗2=100 207
1 100−2t
< x∗3=100 207
1 100+2t
< x∗4=201
207 (5.2)
which is an optimal (zero-asymmetric) node system inI. A little computation reveals that indeed
maxx∈I λ4(X4∗, x) = Λ∗4= 1 129
93+3
q
125172+11868√ 69+3
q
125172−11868√ 69
holds, e.g.,λ4(X4∗,2071 ) = Λ∗4 andλ′4(X4∗, x)|x=2071 = 0. The numerical values in (5.2) read, after insertingt from (3.6):
x∗1=−0.9613526570· · ·< x∗2=−0.3988321752· · ·<
< x∗3= 0.4084940109· · ·< x∗4= 0.9710144927. . . . (5.3) The corresponding Lebesgue functionλ4(x) =λ4(X4∗, x) is depicted in Figure 3.
Figure 3
Our second solution to Problem 5.1 likewise builds on the deployed constants b in (4.4) andt in (3.5). The two parametersαandβ and their selection ranges are now superseded by selection ranges for the two outer optimal nodes which, once fixed, uniquely determine the corresponding two inner optimal nodes.
Theorem 5.4. (Alternative solution to Problem5.1) All optimal node systems for the cubic Lagrange interpolation on Iare given by X4∗:x∗1< x∗2< x∗3< x∗4, where either
−1≤x∗1≤−1
b=−0.9584848200. . .and b−1
b+ 1
x∗1+ 2
b+ 1≤x∗4≤1 (5.4) or
−1
b< x∗1≤b−3
b+ 1=−0.9576047978. . .and b+ 1
b−1
x∗1+ 2
b−1≤x∗4≤1 (5.5) with
x∗2 = 1 +t
2
x∗1+ 1−t
2
x∗4, (5.6)
and with
x∗3 = 1−t
2
x∗1+ 1 +t
2
x∗4. (5.7)
When the outer optimal nodes x∗1 and x∗4 vary in their respective ranges (5.4) and (5.5), then also the ranges of the inner optimal nodesx∗2andx∗3 are exhausted. That ranges are substantiated in the next statement.
Theorem 5.5. The two inner optimal nodesx∗2andx∗3 in Theorem5.4may vary within the ranges
−1
b+ 1(2t+b−1) =−0.4301327291. . .≤x∗2≤ −1
b+ 1(2t−b+1) =−0.3877375269. . . (5.8) and
1
b+ 1(2t−b+ 1) = 0.3877375269· · · ≤x∗3≤ 1
b+ 1(2t+b−1) = 0.4301327291. . . (5.9)
To illustrate Theorems 5.4 and 5.5 we give a numerical example which can be turned into an analytical one:
Example 5.6. Choose x∗1 = −0.99, say. Then one gets, according to (5.4), 0.9578167738· · · ≤ x∗4 ≤ 1. Choose now x∗4 = 0.96, say. This implies, according to (5.6) and (5.7), x∗2 =−0.4223465188. . . and x∗3 = 0.3923465188. . .. Hence these four numerical values constitute a zero-asymmetric optimal node system for the cubic Lagrange interpolation on I. The associated Lebesgue function is depicted in Figure 4. It is readily verified that this specific optimal node system corresponds to (5.1) if we insert thereα=−197195 =−1.0102564102. . . and β = 203195 = 1.0410256410. . . . In particular, the two inner nodes can thus be expressed explicitly asx∗2=2001 (−195t−3) andx∗3=2001 (195t−3).
Figure 4
The somewhat curious description of the ranges of the two outer optimal nodesx∗1and x∗4 in Theorem 5.4 can be given a geometric visualization by a 2D-quadrilateral whose one 1D-diagonal represents the zero-symmetric node systems (ZSNS) (4.1). The two endpoints of that diagonal are represented by the CNS (3.7) and by the BNS (4.7).
The quadrilateral itself is not quite a square, rather two of its sides (the lower one and the right one) can be expressed as line segments of linear functionsg (flat) and h(steep) of the variablex∗1, see (5.4) and (5.5):
g(x∗1) = b−1
b+ 1
x∗1+ 2
b+ 1 = 0.0211976010. . . x∗1+ 0.9788023989. . . (5.10) and
h(x∗1) = b+ 1
b−1
x∗1+ 2
b−1 = 47.1751494729. . . x∗1+ 46.1751494729. . . . (5.11) The graphical representation is given in Figure 5.
Figure 5
We are not aware of any published studies that provide explicit analytical solutions to the problem of determining all optimal node systems in the frame of optimal polynomial Lagrange interpolation onIwith polynomials of degree≥4 (i.e.,n≥5), notwithstanding that this large project is vibrant, see [5], and also Remark 7.5 below.
The results for the polynomial degree = 3 as obtained in [23], [24], and [30, Problem 6.43] do not cover zero-asymmetric node systems. Thus the present paper seems to be the first one where, for the polynomial degree = 3,all optimal node systems in I have been determined, explicitly and analytically. For the polynomial degree = 2 this has been achieved in [25] and in [27].
6. Proofs
6.1. Proof of Theorem2.5
Proof. Let λ∗n(x) = λ∗n(Xn∗, x) denote the Lebesgue function corresponding to the optimal CNS Xn∗ : −1 =−x∗n = x∗1 < −x∗n−1 = x∗2 < · · · < x∗n−1 < x∗n = 1 in I. We know that λ∗n(±1) = 1 and that λ∗n(x) is strictly decreasing resp. increasing in (−∞,−1) and (1,∞), see Proposition 2.2. As Λ∗n >1, there exist unique values x = cn < −1 resp. x = bn > 1 with the property λ∗n(cn) = λ∗n(bn) = Λ∗n. Hence, maxx∈[cn,bn]λ∗n(x) = Λ∗n and in particular maxx∈[α,β]λ∗n(x) = Λ∗n for any subinterval [α, β] of [cn, bn] which coversI. Choose now an arbitraryα∈[cn,−1] and an arbitrary β∈[1, bn] and consider the linear transformation
S(x) = 1
−α+β(2x−α−β) (6.1)
which maps [α, β] ontoI, becauseS(α) =−1 andS(β) = 1. In particular, the nodes of the optimal CNSXn∗ (which is contained in [α, β]) will be mapped as follows:
S(−1) =y∗1= 1
−α+β(−2−α−β) S(−x∗n−1) =y∗2= 1
−α+β(−2x∗n−1−α−β) . . . S(x∗n−1) =yn∗−1= 1
−α+β(2x∗n−1−α−β) S(1) =y∗n= 1
−α+β(2−α−β). (6.2) AsS(x) has the positive slope −α+β2 , these images are ordered ascendingly inI:
Yn∗=Yn,α,β∗ :y1∗< y∗2· · ·< yn∗−1< yn∗. (6.3) We proceed to show that Yn∗ is an extremal node system (with minimal Lebesgue constant) inI. To this end, we observe that, for y∈Iand x∈[α, β], we have
λn(Yn∗, y) =
n
X
j=1 n
Y
i=1 i6=j
|y−yi∗|
|y∗j −y∗i| =
n
X
j=1 n
Y
i=1 i6=j
|S(x)−S(x∗i)|
|S(x∗j)−S(x∗i)| =
=
n
X
j=1 n
Y
i=1 i6=j
|−α+β1 (2x−α−β)−−α+β1 (2x∗i−α−β)|
|−α+β1 (2x∗j−α−β)−−α+β1 (2x∗i−α−β)|=
n
X
j=1 n
Y
i=1 i6=j
|x−x∗i|
|x∗j−x∗i| =
=λ∗n(x), (6.4)
and hence
maxy∈I λn(Yn∗, y) = max
x∈[α,β]λ∗n(x) = Λ∗n,
see also [21, Theorem 2.5.3] and [6, Problem 1, p. 22]. Thus, Yn∗ =Yn,α,β∗ is indeed an optimal node system in I, and since αand β were chosen arbitrarily, there exist
uncountable infinitely many suchYn∗’s.
6.2. Proof of Theorem4.2
Proof. The statement is a corollary to Theorem 5.2: insert thereα=−β.
6.3. Proof of Theorem5.2
Proof. The Lebesgue function λ∗4(x) = λ∗4(X4∗, x) which corresponds to the optimal CNSX4∗ in (3.7) is readily found to be given by
λ∗4(x) =|ℓ31(x)|+|ℓ32(x)|+|ℓ33(x)|+|ℓ34(x)|= (6.5)
= |(−t−x)(−1 +x)(−t+x)/(2(−1−t)(−1 +t))|+
|(−1 +x)(1 +x)(−t+x)/(2(−1−t)(1−t)t)|+
|(−1 +x)(1 +x)(t+x)/(2(−1 +t)t(1 +t))|+
|(1 +x)(−t+x)(t+x)/(2(1−t)(1 +t))|, wheret is defined in (3.5).
Forx∈(1,∞),λ∗4(x) is strictly increasing and is representable there as λ∗4(x) =−ℓ31(x) +ℓ32(x)−ℓ33(x) +ℓ34(x) = x(1−t+t2−x2)
(−1 +t)t . (6.6) Letx=b >1 denote the unique point on thex-axis whereλ∗4(x) intercepts with the constant functionf(x) = Λ∗4, see (3.2). A numerical solution of the equationλ∗4(x)− Λ∗4= 0 is the valuebgiven in (4.3). The expression ofbas explicit analytical solution we will provide below (see the proof of Lemma 4.4). Similarly, for x ∈ (−∞,−1), λ∗4(x) is strictly decreasing and is representable there as
λ∗4(x) =ℓ31(x)−ℓ32(x) +ℓ33(x)−ℓ34(x) =x(−1 +t−t2+x2)
(−1 +t)t , (6.7) so that x = −b < −1 denotes the unique point on the x-axis where λ∗4(x) inter- cepts with the constant function f(x) = Λ∗4. Thus we have, on the interval [−b, b]
as well as on any subinterval [α, β] thereof which coversI, maxx∈[−b,b]λ∗4(x) = Λ∗4= maxx∈Iλ∗4(x). We now apply the linear transformation (6.1) toX4∗ in (3.7) with ar- bitraryα∈[−b,−1] and arbitraryβ ∈[1, b], and thus get (5.1), after renamingyi∗ to x∗i, i= 1,2,3,4 (see the proof of Theorem 2.5). In this way we generate uncountable infinitely many extremal node systems x∗1 < x∗2 < x∗3 < x∗4 in I, and in fact we so obtainall extremal node systems inI.
For letX40:x01< x02< x03< x04be an arbitrary extremal node system inI. The linear transformationT(x) = 2x−x
0 1−x04
−x01+x04 maps X40 ontoIsinceT(x01) =−1 andT(x04) = 1.
Since its slope 2
−x01+x04 is positive, the mapped values are ordered ascendingly, that is X4,T0 : −1 =T(x01)< T(x02)< T(x03) < T(x04) = 1, and hence X4,T0 is a CNS in I. The Lebesgue constant corresponding toX40(which equals Λ∗4as given in (3.2)) is identical with the one corresponding to X4,T0 , see the proof of Theorem 2.5 or [21, Theorem 2.5.3] or [6, Problem 1, p. 22]. But this implies thatX4,T0 is necessarily the unique CNSX4∗ on I, as given in (3.7). In particular we thus haveT(x02) =−t and T(x03) =t, and this implies, by the definition of T(x),x02= 1+t2
x01+ 1−2t x04 and x03= 1−2t
x01+ 1+t2
x04, wheret is from (3.5).
With this information at hand we proceed as follows: The linear transformationSfrom (6.1) withα=α0= −2−x
0 4−x01
x04−x01 andβ=β0=2−x
0 4−x01
x04−x01 maps the optimal CNSX4∗onto x01 < x02 < x03 < x04. Indeed, S(−1) = x01 and S(1) = x04 as is immediately verified.
Furthermore we getS(−t) = 1+t2
x01+ 1−2t
x04andS(t) = 1−2t
x01+ 1+t2 x04, and these values are identical withx02 andx03 as shown above.
It remains to show that α0 ∈[−b,−1] andβ0 ∈[1, b]. We will prove it by symbolic computation employing the built-in language symbols InterpolatingPolynomial and Resolvein MathematicaR as well as MathematicaR-specific notation. Furthermore, we will use the fact thatλn(±1)≤Λ∗n, see Proposition 2.2. Assume that the variable LF contains the Lebesgue function corresponding to the node system in (5.1). This can be defined e.g. in MathematicaR as follows:
LF=
Abs[InterpolatingPolynomial[
{{x1[α, β],1},{x2[α, β],0},{x3[α, β],0},{x4[α, β],0}}, x]] + Abs[InterpolatingPolynomial[
{{x1[α, β],0},{x2[α, β],1},{x3[α, β],0},{x4[α, β],0}}, x]] + Abs[InterpolatingPolynomial[
{{x1[α, β],0},{x2[α, β],0},{x3[α, β],1},{x4[α, β],0}}, x]] + Abs[InterpolatingPolynomial[
{{x1[α, β],0},{x2[α, β],0},{x3[α, β],0},{x4[α, β],1}}, x]].
Denote the the specific parameter valuesα0 andβ0 by α0 = −2−x4−x1
x4−x1 β0 = 2−x4−x1
x4−x1 . (6.8)
Then one gets, with Λ = Λ∗4 as given in (3.2) and (3.9) andb as given in (4.2) and (4.5),
[in:]
Resolve[ForAll[{x1, x4},(−1≤x1< x4≤1∧
(LF/.x→ −1)≤Λ∧(LF/.x→1)≤Λ/.{α→α0, β→β0})
⇒
(−b≤α0≤ −1 ∧ 1≤β0≤b)],Reals] (6.9)
[out:] True.
6.4. Proof of Lemma4.3
Proof. We want to determine the pointx=b >1 on thex-axis whereλ∗4(x) intercepts with the constant function f(x) = Λ∗4 (see the proof of Theorem 5.2). To this end, we employ a computer algebra system. The built-in language symbol RootReduce of MathematicaR immediately gives, in view of (3.1), (3.4) and (6.6), the claimed polynomial of degree 18:
[in:]
RootReduce[x/.Solve[x(1−t+t2−x2)/((−1 +t)t) ==
Root[−11 + 53#1−93#12+ 43#13&,1]
/.t→Root[−1 + 2#12+ 17#14+ 25#16&,2], x,Reals]] (6.10) [out:]
{Root[−121 + 220#1−1014#12+ 1344#13+ 3283#14−5166#15+ 4502#16+ 15692#17−84178#18+ 7868#19+ 210676#110− 25694#111−310732#112+ 34154#113+ 255377#114−
8450#115−124700#116+ 26875#118&,2]}. (6.11) This polynomial P18 can also be deduced in a reverse way: If one employs in MathematicaR the built-in language symbol FullSimplify to the explicit expression
(4.5), then one gets (6.11).
6.5. Proof of Lemma4.4 Proof. The equation
x(1−t+t2−x2)/((−1 +t)t) =1 +t2
1−t2 (6.12)
see (3.9) and (6.6), amounts to the following cubic algebraic equation inx:
(t+t3) + (1 +t3)x+ (−1−t)x3= 0. (6.13) Solving (6.13) with the aid of Cardan’s formula yields the (parametric) solution x=b=b(t) as given in (4.4). Inserting then into (4.4) the value for the constantt according to (3.5) and simplifying eventually gives (4.5). The said algebraic manipu- lations can be executed by pencil and paper, but it is more convenient to guide them
by a computer algebra system.
6.6. Proof of Theorem5.4
Proof. To prove (5.4) and (5.5), we use quantifier elimination to eliminate the existen- tially quantified variablesαandβfrom the parametric representation ofx∗1 =x∗1(α, β) andx∗4=x∗4(α, β), taking into account the range ofαand β, see Theorem 5.2. This elimination can be executed by means of the built-in language symbol Resolve in MathematicaR:
[in :]
Resolve[Exists[{α, β}, b >1∧ −b≤α≤ −1∧1≤β≤b∧ x∗1(β−α) ==−2−α−β∧x∗4(β−α) == 2−α−β
],{x∗1, x∗4},Reals]
[out :]
b >1∧ (−1≤x∗1 ≤ −1
b ∧2−x∗1+bx∗1
1 +b ≤x∗4≤1)∨ (−1
b < x∗1≤−3 +b
1 +b ∧2 +x∗1+bx∗1
−1 +b ≤x∗4≤1)
, (6.14)
which coincides with (5.4) and (5.5). To prove (5.6) and (5.7), consider the parametric representation of the optimal nodesx∗i =x∗i(α, β), i= 1,2,3,4 in (5.1). Computing now 1+t2
x∗1(α, β) + 1−2t
x∗4(α, β) and 1−2t
x∗1(α, β) + 1+t2
x∗4(α, β) gives imme-
diately (5.6) and (5.7).
6.7. Proof of Theorem5.5
Proof. According to (5.7), the node x∗3 =x∗3(x∗1, x∗4) = 1−2t
x∗1+ 1+t2
x∗4 is a bi- variate polynomial which is linear in both variablesx∗1 andx∗4. Hencex∗3(x∗1, x∗4) will attain its extreme values on the boundary of the ranges ofx∗1andx∗4, so that it suffices to investigate the values ofx∗3(x∗1, x∗4) at five points, see (5.4), (5.5) and also Figure 5:
x∗3
−1,3−b b+ 1
=2t−b+ 1
b+ 1 = 0.3877375269. . . (6.15) x∗3(−1,1) =t= 0.4177913013. . . (6.16) x∗3
−1 b ,1
b
= t
b = 0.4004466202. . . (6.17)
x∗3 −1
b ,1
= −1 +b+bt+t
2b = 0.4298765508. . . (6.18) x∗3
b−3 b−1,1
= 2t+b−1
b+ 1 = 0.4301327291. . . . (6.19) Obviously, (6.15) is the minimum and (6.19) is the maximum of x∗3 =x∗3(x∗1, x∗4) as claimed in (5.9). The verification of (5.8) follows similar lines and will be left to the
reader.
7. Concluding remarks
Remark 7.1. Let n = 4. According to (4.7), the largest possible value for the first optimal interpolation node inIisx∗1=−1b =−0.9584848200. . ., if we consider zero- symmetric node systems. But if we allow arbitrary node configurations, then we can get beyond this number: the largest possible value for the first optimal interpolation node inIis in factx∗1= bb+1−3 =−0.9576047978. . ., see (5.5).
Remark 7.2. According to section 6.6, Schurer’s description in [27, Theorem 1] of the optimal arbitrary node systems X3∗ : x∗1 < x∗2 < x∗3 for quadratic Lagrange interpolation onIcan be restated almost verbatim in the form as given in our Theorem 5.4, if we replace in (5.4) and (5.5) x∗4 by x∗3 and if we replace the constant b = 1.0433133411. . . by the corresponding constantb◦ = 2√3
2 = 1.0606601717. . . . For example, (5.4) would then read
−1≤x∗1≤ −1
b◦(≈−0.9428) ∧
b◦−1 b◦+ 1
x∗1+ 2
b◦+ 1 ≤x∗3≤1 (7.1) which is identical with
−1≤x∗1≤ −2√ 2
3 (≈−0.9428)∧ (17−12√
2)x∗1+ 12√
2−16≤x∗3≤1 (7.2) as given in [27]. Note that in the quadratic case we havex∗2= x∗1+x2 ∗3.
Remark 7.3. The proof of Theorem 5.4 rests on Theorem 5.2. We have also found an alternative, computer-aided proof of Theorem 5.4 which avoids Theorem 5.2. It uses quantifier elimination and can be compared with section 3.5 in [25]. However, to reduce computational complexity, this automated proof requires a reduction of the variables by means of
x∗2=x∗1+x∗4−x∗3. (7.3) This equation, which is of some interest in itself, follows readily from Theorem 5.2, but, to stay independent of that theorem, we had to establish an alternative new proof for (7.3).
Remark 7.4. Suppose one choosesx∗1=c (constant) andx∗4=d(constant) from the indicated ranges (5.4) respectively (5.5) in Theorem 5.4. Then one gets, in generalizing Example 5.6, α = −2d−−cc−d and β = 2−d−c−cd, and hence x∗2 = c+d+t(c2 −d) and x∗3 =
c+d+t(d−c)
2 , according to Theorem 5.2, or directly from (5.6) and (5.7).
Remark 7.5. The natural question arises: How to determine the minimal Lebesgue constant Λ∗nand all optimal node systemsXn∗in Ifor the next casesn= 5,6,7, . . . ? We have achieved some progress forn= 5 andn= 6. For example, we have implicitly determined the Lebesgue constants Λ∗5 and Λ∗6 by symbolic computation as roots of certain high-degree polynomials with integer coefficients. To be more specific, for n= 5 (quartic case) we have obtained
Λ∗5= 1.5594902098. . . (7.4)
as a root of a polynomial of degree 73 with integer coefficients. This polynomial has the contour
P73∗(x) = (7.5)
491920844066918518676932058679834515105631225977247880376611328125 +. . . +14156651510438131445849849962417864414147142283963792181670336004096x73.
We intend to expose our findings in a separate manuscript, see also [32].
Remark 7.6. That the topic of optimal cubic Lagrange interpolation awakens interest in the reader may be deduced from the fact that the online-version of [23] on the publishers website has received more than 60 article views subject to charge, see http://www.tandfonline.com/doi/abs/10.1080/0020739840150312
Remark 7.7. The desire to precisely determine the values of interesting constants (here:b,t, Λ∗4) is reflected on in [12, p. 79].
Remark 7.8. In [10, p. 70] it is erroneously claimed that an optimal node system in Imust necessarily be a CNS.
References
[1] Angelos, J.A., Kaufman, E.H. Jr., Henry, M.S., Lenker, T.D.,Optimal nodes for poly- nomial interpolation, in: Approximation Theory VI, Vol. I, C.K. Chui, L.L. Schumaker, J.D. Ward (Eds.), (College Station, TX, 1989), 17-20, Academic Press, Boston, MA, 1989.
[2] Babu˘ska, I., Strouboulis, Th.,The finite element method and its reliability, Oxford Uni- versity Press, Oxford, UK, 2001.
[3] Bernstein, S., Sur la limitation des valeurs d’un polynˆome Pn(x) de degr´e n sur tout un segment par ses valeurs en(n+ 1)points du segment, (in French), Izv. Akad. Nauk.
SSSR,7(1931), 1025-1050.
[4] Brutman, L.,Lebesgue functions for polynomial interpolation – a survey, Ann. Numer.
Math.,4(1997), 111-127.
[5] Chen, D., Generalization of polynomial interpolation at Chebyshev nodes, in: Approx- imation Theory XIII, M. Neamtu, L.L. Schumaker (Eds.), (San Antonio, TX, 2010), 17-35, Springer Proc. Math. 13, Springer, New York, 2012.
[6] Cheney, E.W., Light, W.A.,A course in approximation theory, AMS Publishing, Prov- idence, RI, 2000.
[7] Cheney, E.W., Xu, Y.,A set of research problems in approximation theory, in: Topics in polynomials of one and several variables and their applications, Th. M. Rassias, H.M.
Srivastava, A. Yanushauskas (Eds.), 109-123, World Sci. Publ., River Edge, NJ, 1993.
