Optimal Lagrange Interpolation:
Minimal Lebesgue Constants and Extremal Node Systems via Symbolic Computation
(Web Repository)

Research Project Supported by OTKA No. 83219, OMAA 87öu15 and IPA HUSRB/1203/221/024
Description. The goal of this project to systematically investigate and characterize the canonical forms of computational problems related to the optimal Lagrangre polynomial interpolation.

In the current form it is a web repository which contains a list of Benchmark Problems for symbolic computation.
This page is also thought as a web supplement of published researh articles.

[1] H.-J. Rack, An example of optimal nodes for interpolation. Int. J. Math. Educ. Sci. Technol., 15 (1984), 355-357
[2] H.-J. Rack, An example of optimal nodes for interpolation revisited. In: Advances in applied mathematics and approximation theory, Contributions from AMAT 2012 (Eds G. A. Anastassiou, O. Duman), Springer Proceedings in Mathematics and Statistics, 41, (2013), Springer, New York, 117-120.
[3] R. Vajda, Lebesgue constants and optimal node systems via symbolic computations (short paper). In: L. Kovacs, T. Kutsia (eds.), Fifth International Symposium on Symbolic Computation (SCSS 2013), RISC-Linz Report Series No. 13-06, 2013, 125-125
[4] H.-J. Rack, R. Vajda, On optimal quadratic Lagrange interpolation: Extremal node systems with minimal Lebesgue constant via symbolic computation, Serdica J. of Comput., Vol. 8(1), 2014, pp. 71-96.
[5] H.-J. Rack, R. Vajda: Optimal Cubic Lagrange Interpolation: Extremal Node Systems with Minimal Lebesgue Constant, Stud. Univ. Babes-Bolyai Math. 60(2015), No. 2, pp. 151-171.

Tools: Quantifier Elimination(QE), Groebner Basis(GB), Resultants(R).
Results 1: (QE)
deg2:
2.1 [-1,0,1]--m  [input]
p212=x2-x+(m-1)
c2=0< x≤1
Input:
(Ax)(c2⇒p212≥0)
Output: m≥5/4.
2.2 [-1,x2,1]--m  [input]
p221=x2+(-x2+1)x+(-mx2+m-1)
p222=x2+(-x2-1)x+(mx2+m-1)
c=-1< x2 <1
c1=-1≤ x< x2
c2=x2 < x≤1
Input:
(Ex2)(c /\ (Ax)((c1⇒p221≥0)/\(c2⇒p222≥0)))
Output: m≥5/4.
2.3 [-1,x2,1]--Λ  [input]
p231=4x2+(-4x2+4)x+(-5x2+1)
p232=4x2+(-4x2-4)x+(5x2+1)
c=-1< x2 <1
c1=-1≤ x< x2
c2=x2 < x≤1
Input:
(c /\ (Ax)((c1⇒p231≥0)/\(c2⇒p232≥0)))
Output: x2=0.
2.4 [-x3,0,x3]--m  [input]
p242=x2+(-x3)x+(x32(m-1))
p243=-2x2+(x32(m+1))
c=0< x3 <1
c1=0≤ x< x3
c2=x3 < x≤1
Input:
(Ex3)(c /\ (Ax)((c1⇒p242≥0)/\(c2⇒p243≥0)))
Output: m≥5/4.
2.5 [-x3,0,x3]--Λ  [input]
p253=-8x2+9x32
c=0< x3 <1
c3=x3 < x≤1
Input:
(c /\ (Ax)(c3⇒p253≥0))
Output: 2/3 21/2≤x3< 1.
2.6 [-x3,x2,x3]--m
p261=x2+(-x2+x3)x+(x32(m-1))-mx2x3
p262=x2+(-x2-x3)x+(x32(m-1))+mx2x3
p263=-2x2+(x22(1-m))+(x32(m+1))
c=-1< -x3< x2< x3 <1
c1=-x3< x< x2
c2=x2 < x< x3
c3=x3 < x≤1
Input:
(Ex2)(Ex3)(c /\ (Ax)((c1⇒p261≥0)/\(c2⇒p262≥0)/\ (c3⇒p263≥0)))
Output: m≥5/4.
2.7 [-x3,x2,x3]--Λ
p271=4x2+(-4x2+4x3)x+x32-5x2x3
p272=4x2+(-4x2-4x3)x+x32+5x2x3
p273=-8x2-x22+9x32
c=-1< -x3< x2< x3 <1
c1=-x3< x< x2
c2=x2 < x< x3
c3=x3 < x≤1
Input:
(c /\ (Ax)((c1⇒p271≥0)/\(c2⇒p272≥0)/\ (c3⇒p273≥0)))
Output: 2/3 21/2≤x3< 1/\ x2=0.
2.8 [-1,x2,x3]--Λ  [input]
p281=8x2+(-8x2+8)x+x32-9x2-x2x3+x3
p282=8x2+(-8x2-8x3)x+x2+x3+9x2x3+1
p283=-8x2+(8x3-8)x-x22+9x3+x2x3-x2
c=-1< x2< x3 <1
c1=-1≤ x< x2
c2=x2 < x< x3
c3=x3 < x≤1
Input:
(c /\ (Ax)((c1⇒p281≥0)/\(c2⇒p282≥0)/\ (c3⇒p283≥0)))
Output: 3(-11+8 21/2)≤x3< 1/\ x2=(-1+x3)/2.
2.9 [x1,x2,1]--Λ  [input]
p290=-8x2+(8x1+8)x-x22-9x1+x1x2+x2
p291=8x2+(-8x1-8x2)x-x1-x2+9x1x2+1
p292=8x2+(-8x2-8)x+x12+9x2-x1x2-x1
c=-1< x1< x2 <1
c0=-1≤ x< x1
c1=x1 < x< x2
c2=x2 < x≤1
Input:
(c /\ (Ax)((c0⇒p290≥0)/\(c1⇒p291≥0)/\ (c2⇒p292≥0)))
Output: -1< x1≤ 3(11-8 21/2)/\ x2=(1+x1)/2.
2.10 [x1,x2,x3]--Λ  [input]
p2100=-8x2+(8x1+8x3)x-x22-9x1x3+x1x2+x2x3
p2101=8x2+(-8x1-8x2)x-x1x3-x2x3+9x1x2+x32
p2102=8x2+(-8x2-8x3)x-x1x2-x1x3+9x2x3+x12
p2103=-8x2+(8x1+8x3)x-x22-9x1x3+x1x2+x2x3
c=-1< x1< x2< x3 <1
c0=-1≤ x< x1
c1=x1 < x< x2
c2=x2 < x< x3
c3=x3 < x≤1
Input:
(c /\ (Ax)((c0⇒p2100≥0)/\(c1⇒p2101≥0)/\ (c2⇒p2102≥0))/\(c3⇒p2103≥0)))
Output: (-1< x1≤ -2/3 21/2/\ (17-12 21/2)x1+12 21/2-16≤x3< 1/\ x2=(x1+x3)/2)) \/ (-2/3 21/2< x1<3(11-8 21/2 )/\ (17+12 21/2)x1+12 21/2+16≤x3< 1/\ x2=(x1+x3)/2) .

Results 1: (GB)
deg3:
p31=2x32+(1-q2)x3+q3-q
p32=-2qx3+3q2-1


Input:
GB[{p31,p32},{q,x3}]
Output: {q31,q32}, where
q31=25x36+17x34+2x32-1
q32=23q+25x35-58x33-31x3
Input:
GB[{p31,p32},{x3,q}]
Output: {q33,q34}, where
q33=25q6-23q4+7q2-1
q34=25q5-23q3+4q+2x3

Interpretation:
x3=Root[q31,2]~.417791
q=Root[q33,2]~.733173
p33=m x33-x33+q2x3-m x3-q3+q
p34=m x32+x32-m+1

Input:
GB[{p32,p33,p34},{x3,q,m}][[1]]
Output: q35, where
q35=43m3-93m2+53m-11

Interpretation:
m=Root[q35,1]~1.42292






Results 2: (QE)
deg3:
3.1 [-1,-x3,x3,1]--m  [input]
p312=-mx32-x32+2x2+m-1
p313=-mx33+x33-x2x3+mx3+x3-x
c=0< x3 <1
c2=-x3 < x< x3
c3=x3 < x ≤1

Input:
(Ex3)(c /\ (Ax)((c2⇒p312≥0)/\(c3⇒p313≥0)))
Output: q35≥0, where q35=43m3-93m2+53m-11

Remarks:
1. Problem type: determining the optimal Leb. Constant Λ4*(~1.42292)
2. No. of vars: 3
3. No. of level-1-projection-factors: 10, among them P1,7=q35.
3.2 [-1,-x3,x3,1]--Λ  
p322=-mx32-x32+2x2+m-1
p323=-mx33+x33-x2x3+mx3+x3-x
cm=43m3-93m2+53m-11=0
c=0< x3 <1
c2=-x3 < x< x3
c3=x3 < x ≤1

Input:
(Em)(cm /\ c /\ (Ax)((c2⇒p322≥0)/\(c3⇒p323≥0)))
Output: x3>0 /\ q31=0, where q31=25x36+17x34+2x32-1

Remarks:
1. Problem type: determining the optimal CNS (x3~.417791)
2. x3=sqrt((Λ4*-1)/(Λ4*+1))
3. No. of vars: 3
4. No. of level-1-projection-factors: 12, among them P1,6=q31.
3.3 [-x4,-x3,x3,x4]--Λ  
p332=m x42-x42-m x32-x32+2x2
p333=mx3 x42-x x42-mx33+x33-x2x3+x3
p334=mx3 x42+x x42-mx32x4-xx3x4+xx32-x3
cm=43m3-93m2+53m-11=0
c=0< x3<x4 <1
c2=-x3 < x < x3
c3=x3< x < x4
c4=x4 < x ≤1

Input:
(Em)(cm /\ c /\ (Ax)((c2⇒p332≥0)/\(c3⇒p333≥0)/\(c4⇒p334≥0)))
Output:
Root[q36,2]≤ x4 < 1 /\ x3=Root[-x46+2x44#12+17x42#14+25#16&,2]
where q36=121x18-220x17+1014x16-1344x15-3283x14+5166x13-4502x12-15692x11+ +84178x10-7868x9-210676x8+25694x7+310732x6-34154x5-255377x4+8450x3+124700x2-26875

Remarks:
1. Problem type: determining all the zero-symmetric optimal NS (except for the CNS)
2. The smallest value for x4 belongs to the BNS.
3. No. of vars: 4


Robert Vajda