A Numerical Study of the Xu Polynomial I nterp olation F ormula in T w o V ariab les

Digital Object Identifier (DOI) 10.1007/s00607-005-0137-z

A Numerical Study of the Xu Polynomial I nterp olation F ormula in T w o V ariab les

L . B os , C algary , M . C aliari, S. D e M archi, V ero na and M . V ianello, P ado v a

R eceiv ed S ep tem ber 21, 2004 ; rev ised J u ne 6, 2005 P u blish ed o nline: N o v em ber 3, 2005

© S p ringer-V erlag 2005

Ab s tract

In h is p ap er “ L agrange interp o latio n o n C h eby sh ev p o ints o f tw o v ariables” (J. A p p ro x . T h eo r. 8 7, 220– 238 , 19 9 6), Y . X u p ro p o sed a set o f C h eby sh ev lik e p o ints fo r p o ly no m ial interp o latio n in th e sq u are [−1, 1] ² , and deriv ed a co m p act fo rm o f th e co rresp o nding L agrange interp o latio n fo rm u la. W e inv es- tigate co m p u tatio nal asp ects o f th e X u p o ly no m ial interp o latio n fo rm u la lik e nu m erical stability and efficiency , th e beh av io r o f th e L ebesgu e co nstant, and its ap p licatio n to th e reco nstru ctio n o f v ario u s test fu nctio ns.

AMS Subject Classifications: 65D05.

K ey w ord s: B iv ariate p o ly no m ial interp o latio n, X u p o ints, L agrange interp o latio n fo rm u la, L ebesgu e co nstant.

1 . I ntroduction

T h e p ro blem o f ch o o sing g ood no des o n a giv en co m p act set is a central o ne in p o ly no m ial interp o latio n. A s is w ell-k no w n, th e p ro blem is essentially so lv ed in o ne dim ensio n (all go o d no dal seq u ences fo r th e su p -no rm are asy m p to tically eq u idis- tribu ted w ith resp ect to th e arc-co sine m etric), w h ile in sev eral v ariables it is still su bstantially o p en. E v en th e basic q u estio n o f u niso lv ence o f a giv en set o f interp o - latio n p o ints is by no m eans sim p le, and receiv ed sp ecial attentio n in th e literatu re o f th e last tw enty y ears, cf., e.g. [1], [16], and th e su rv ey p ap er [6]. T h e sam e co u ld be said co ncerning th eo retical analy sis o f th e L ebesgu e co nstant, also in th e case o f th e im m ediate biv ariate generalizatio n o f o ne dim ensio nal co m p act interv als, i.e., sq u ares and rectangles. A no th er w eak p o int in no n tenso r-p ro du ct interp o latio n is giv en by a su bstantial lack o f co m p u tatio nal efficiency o f th e interp o latio n fo rm u las.

Im p ro v em ents h av e been recently m ade o n general p u rp o se L agrange and N ew to n lik e fo rm u las, cf., e.g. [10], [11], bu t th e p ro blem is still no t co m p letely so lv ed.

R ecently [3], w e stu died nu m erically v ario u s no dal sets fo r p o ly no m ial interp o la-

tio n o f degree n (n ev en) in [−1, 1] ² , w h ich are eq u idistribu ted w ith resp ect to th e

D ubiner m etr ic (a m u ltiv ariate analo g to th e arc-co sine m etric, cf. [5]). T h e m o st

p ro m ising set, term ed P ad ua p oints, ex p erim entally tu rned o u t to be u niso lv ent

and gav e a L ebesgu e co nstant gro w ing lik e lo g ² (n). H o w ev er, th e interp o latio n w as

c on str u c ted b y solv in g th e c or r esp on d in g V an d er m on d e sy stem , w h ic h m ean s a O(N ³ ) c om p lex ity (N b ein g th e d im en sion of th e u n d er ly in g fu ll p oly n om ial sp ac e, i.e., N = (n + 1)(n + 2)/2), p lu s a O(N ) c om p lex ity for eac h p oin tw ise ev alu ation of th e in ter p olan t.

A v er y ap p ealin g alter n ativ e is g iv en b y th e c om p ac t in ter p olation for m u la at C h eb y sh ev lik e p oin ts of tw o v ar iab les, p r op osed som e y ear s ag o b y Y . X u [15 ].

E v en th ou g h th e n od al set r eq u ir es to w or k in a su b sp ac e V _n ² of th e fu ll p oly n om ial sp ac e P ² n , w ith P ² _n−1 ⊂ V _n ² ⊂ P ² n , th er e is th eor etic al u n isolv en c e, an d th e Leb esg u e c on stan t g r ow s (ex p er im en tally ) ag ain lik e log ² (n). M or eov er, th e c om p u tation al c om p lex ity of th e stabilized formula c an b e b ou n d ed b etw een c ₁ N ∼ c ₁ n ² /2 an d c ₂ N ^3/2 ∼ c ₂ n ³ /2 fl op s (N b ein g h er e th e d im en sion of V _n ² , N = d im V _n ² = n(n+2)/2), for eac h p oin tw ise c on str u c tion an d ev alu ation of th e in ter p olan t, an d in p r ac tic e r em ain s c lose to th e low er b ou n d (lin ear in th e d im en sion , i.e., q u ad r atic in th e d eg r ee).

I n th e n ex t sec tion , w e d isc u ss h ow to im p lem en t in an effi c ien t an d stab le w ay th e X u in ter p olation for m u la. I n S ec t. 3, w e sh ow n u m er ic ally th at th e Leb esg u e c on stan t of th e X u in ter p olation op er ator g r ow s lik e (2/π log (n + 1)) ² , w h ic h c or r esp on d s to th e g r ow th of th e Leb esg u e c on stan t of ten sor -p r od u c t C h eb y sh ev in ter p olation an d of in ter p olation at P ad u a p oin ts [3]. F in ally , in S ec t. 4 , w e ap p ly th e X u in ter p o- lation for m u la to th e r ec on str u c tion of som e test fu n c tion s w ith d iffer en t d eg r ees of r eg u lar ity , c om p ar in g th e in ter p olation er r or s w ith th ose of p oly n om ial in ter p ola- tion at ten sor -p r od u c t C h eb y sh ev , (ex ten d ed ) M or r ow -P atter son an d P ad u a p oin ts (c f. [7 ], [14 ], [3]).

2. Implementation of the Xu Interpolation Formula

W e star t b y r ec allin g b r iefl y th e c on str u c tion of th e X u in ter p olation for m u la of d eg r ee n on th e sq u ar e [−1, 1] ² . I n w h at follow s w e r estr ic t to ev en d eg r ees n, in or d er to c om p ar e th e p r esen t w ith ou r p r ev iou s r esu lts (for m or e d etails, see [15 ], [3]). C on sid er in g th e C h eb y sh ev -Lob atto p oin ts on th e in ter v al [−1, 1]

z _k = z _k,n = c os kπ

n , k = 0, . . . , n, n = 2m , (1)

th e X u in ter p olation p oin ts on th e sq u ar e ar e d efi n ed as th e tw o-d im en sion al C h eb y sh ev ar r ay X _N = {x r,s } of d im en sion N = n(n + 2)/2

x _{2i,2j +1} = (z _2i , z _{2j +1} ), 0 ≤ i ≤ m, 0 ≤ j ≤ m − 1 ,

x _2i+1,2j = (z _2i+1 , z _2j ), 0 ≤ i ≤ m − 1, 0 ≤ j ≤ m . (2)

T h e X u in ter p olan t in Lag r an g e for m of a g iv en fu n c tion f on th e sq u ar e [−1, 1] ² is

L ^{X u} _n f (x) = 

x r,s ∈X _N

f (x r,s ) _n (x, x r,s ),  _n (x, x r,s ) := K _n ^∗ (x, x r,s )

K _n ^∗ (x r,s , x r,s ) , (3)

w here the polynomials K _n ^∗ (·, x _r,s ) are g iv en b y K _n ^∗ (x, x r,s ) := 1

2 K n (x, x r,s ) + K _n+1 (x, x r,s ) +

− 1

2 (−1) ^r (T _n (x ₁ ) − T _n (x ₂ )) ; (4 ) here x ₁ , x ₂ are the coordinates of the g eneric point x = (x ₁ , x ₂ ) and T _n is the C heb ys hev polynomial of the fi rs t k ind of deg ree n, T n (x) = cos (n arccos x). In particular w hen x = x r,s (cf. [15 , formula (2.18 )])

K _n ^∗ (x _r,s , x _r,s ) = 1

2 K _n (x _r,s , x _r,s ) + K _n+1 (x _r,s , x _r,s ) − 1 . (5 ) It is w orth noticing that in formulas (4 ) and (5 ) w e corrected tw o mis prints appearing in [15 , formula (2.15 )] and [15 , formula (2.18 )], res pectiv ely: the correct index es in the s um on the rig ht hand s ides are n and n + 1 ins tead of n and n − 1, and moreov er the C heb ys hev polynomials of the fi rs t k ind in (4 ) are not s caled.

T he polynomials K _n (x, y) can b e repres ented in the form

K _n (x, y) = D _n (θ ₁ + φ ₁ , θ ₂ + φ ₂ ) + D _n (θ ₁ + φ ₁ , θ ₂ − φ ₂ ) +D _n (θ ₁ − φ ₁ , θ ₂ + φ ₂ ) + D _n (θ ₁ − φ ₁ , θ ₂ − φ ₂ ) ,

x = (cos θ ₁ , cos θ ₂ ), y = (cos φ ₁ , cos φ ₂ ) , (6 ) w here the function D _n is defi ned b y

D n (α, β) = 1 2

cos ((n − 1/2)α) cos (α/2) − cos ((n − 1/2)β) cos (β/2)

cos α − cos β . (7 )

As s how n in [15 ], the v alues K _n ^∗ (x r,s , x r,s ) are ex plicitly k now n in terms of the deg ree n, that is

K _n ^∗ (x _r,s , x _r,s ) =



 

  n ²

r = 0 or r = n, s odd s = 0 or s = n, r odd n ² /2 in all other cas es .

(8 )

It is w orth s aying that the prev ious formula for K _n ^∗ (x r,s , x r,s ) corrects a mis print in [15 , formula (2.16 )], concerning the cas es r = n and s = n.

O b s erv e that this constructive approach yields immediately unisolvence of the inter- polation prob lem, s ince for any g iv en b as is of the underlying polynomial s pace V _n ² the corres ponding V andermonde s ys tem has a s olution for ev ery N -dimens ional v ector {f (x _r,s )}, and thus the V andermonde matrix is inv ertib le.

R earrang ing (7 ) in the cas e that cos (α) = cos (β), w e v irtually hav e at hand an

interpolation formula w ith pointw is e ev aluation cos t O(N ). H ow ev er, formula (7 ) is

num erica lly ill-cond itioned w hen cos (α) ≈ cos (β), b eing lik e a fi rs t div ided difference,

an d th u s h as to b e stab iliz ed (see T ab le 1). A stab le for m u la to c om p u te D _n c an b e ob tain ed b y sim p le tr ig on om etr ic m an ip u lation s. I n fac t, w e c an w r ite

D _n (α, β) = 1 4

c os nα − c os nβ

c os α − c os β + c os(n − 1)α − c os(n − 1)β c os α − c os β

= 1 4

sin nφ sin nψ

sin φ sin ψ + sin (n − 1)φ sin (n − 1)ψ sin φ sin ψ

= 1

4 U _n−1 (c os φ)U _n−1 (c os ψ) + U _n−2 (c os φ)U _n−2 (c os ψ) , (9 ) w h er e

φ = α − β

2 , ψ = α + β

2

an d U _n d en otes th e u su al C h eb y sh ev p oly n om ial of th e sec on d k in d . F or m u la (9 ) is a stabilized v er sion of (7 ) for th e c om p u tation of D n (α, β), w h er e th e r atio of d iffer en c es d oes n ot ap p ear ex p lic itly . T h e C h eb y sh ev p oly n om ial of th e sec on d k in d U _n h as th e tr ig on om etr ic r ep r esen tation U _n (c os θ ) = sin (n + 1)θ/ sin θ , w h ic h is h ow ev er n u m er ic ally ill-c on d ition ed at in teg er m u ltip les of π , θ = k π, k = 0.

O n th e oth er h an d , as it is w ell-k n ow n , th e p oly n om ials U _n c an b e c om p u ted b y th e th r ee-ter m r ec u r r en c e r elation

U ₀ (c os θ ) = 1, U ₁ (c os θ ) = 2 c os θ,

U _n (c os θ ) = 2 c os θ U _n−1 (c os θ ) − U _n−2 (c os θ ), n ≥ 2 . (10) S u c h a r ec u r r en c e is stable for an y θ , b y p ay in g th e p r ic e of a O(n) in stead of O(1) c ost for eac h ev alu ation of D n (α, β).

Table 1. C om p u tation of D n (0, β), as β → 0, for n = 4, 8 w ith for m u lae (7 ) an d (9 ) (N A N = n ot a n u m b er = 0/0)

β D ₄ u n stab le D ₄ stab le D ₈ u n stab le D ₈ stab le

0.1E + 01 0.19 815 4E + 01 0.19 815 4E + 01 0.7 5 6 801E + 00 0.7 5 6 801E + 00 0.1E + 00 0.6 185 28E + 01 0.6 185 28E + 01 0.26 9 45 0E + 02 0.26 9 45 0E + 02 0.1E − 01 0.6 249 35 E + 01 0.6 249 35 E + 01 0.28236 7 E + 02 0.28236 7 E + 02 0.1E − 02 0.6 249 9 9 E + 01 0.6 249 9 9 E + 01 0.28249 9 E + 02 0.28249 9 E + 02 0.1E − 03 0.6 25 000E + 01 0.6 25 000E + 01 0.2825 00E + 02 0.2825 00E + 02 0.1E − 04 0.6 25 000E + 01 0.6 25 000E + 01 0.2825 00E + 02 0.2825 00E + 02 0.1E − 05 0.6 249 9 9 E + 01 0.6 25 000E + 01 0.28249 9 E + 02 0.2825 00E + 02 0.1E − 06 0.6 25 341E + 01 0.6 25 000E + 01 0.28246 9 E + 02 0.2825 00E + 02 0.1E − 07 0.6 7 89 05 E + 01 0.6 25 000E + 01 0.27 89 10E + 02 0.2825 00E + 02 0.1E − 08 0.111111E + 00 0.6 25 000E + 01 0.111111E + 00 0.2825 00E + 02

0.1E − 09 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 10 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 11 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 12 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 13 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 14 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 15 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

0.1E − 16 N A N 0.6 25 000E + 01 N A N 0.2825 00E + 02

At this point, w e can compute the complex ity of the pointw is e ev aluation of the Xu interpolation formula (3) v ia (9 )– (10). Firs t, the ev aluation of K _n ^∗ (x, x _r,s ), w hich inv olv es four ev aluations of D _n and of D _n+1 v ia K _n and K _n+1 , res pectiv ely (cf. (4) and (6 )), cos ts ab out 2n × 4 = 8n fl ops, s ince D n and D _n+1 w ith the s ame arg u- ments can b e computed tog ether us ing the recurrence (10) once. Since this has to b e done for ev ery interpolation point, the dominant term in the fi nal complex ity for the ev aluation of L ^Xu _n f (x) is 8nN ∼ 4n ³ fl ops.

In order to reduce the ev aluation cos t of the interpolant, one mig ht think to apply a hyb rid s trateg y in the computation of D n (α, β), that is formula (7 ) w hen |cos α − cos β| is not too s mall, s ay ab ov e a g iv en thres hold δ, and the s tab iliz ed formula (9 ) along w ith the recurrence (10) otherw is e. H ow ev er, w e hav e numerical ev idence that choos ing δ < 2, w hich implies that als o formula (7 ) is us ed, then the interpolation method fails. T his can b e s een in T ab le 2, w here w e s how the interpolation errors and the us e percentag e of s tab iliz ed formula (9 )– (10) for n = 20 on a uniform 100 × 100 g rid for the s mooth function f (x ₁ , x ₂ ) = cos (x ₁ + x ₂ ), corres ponding to different choices of δ. T he percentag es in the las t column hav e b een rounded, ex cept for the fi rs t and the las t w hich are ex act. Notice that w hen only the s tab iliz ed formula is applied (i.e., δ = 2) the error is clos e to machine precis ion, w hile in all other cas es w e hav e a dramatic los s of accuracy.

An effectiv e w ay to reduce the computational cos t of the s tab iliz ed formula (9 ), s till pres erv ing hig h accuracy, is computing the C heb ys hev polynomials of the s econd k ind U _n b y the three-term recurrence relation (10) only w hen the repres entation U _n (cos θ ) = s in(n + 1)θ/ s in θ (w hos e cos t is O(1) in n and θ ) is ill-conditioned, s ay for |θ − k π | ≤ ε.

In T ab le 3, w e compare the interpolation errors for the s ame ex ample ab ov e w ith different choices of ε. W e can s ee that w ith ε = 0.01, w hich inv olv es the recur- rence (10) for les s than 1% , w e hav e in practice no los s of accuracy, w hile for ε = 10 ⁻⁵ , w here the recurrence is not us ed at all, w e hav e an error of ab out 10 ⁻¹¹ . In this ex am- ple, for ε ≤ 0.01, the alg orithm us es almos t only the trig onometric repres entation of U n (cos θ ) and thus its computational cos t is, in practice, linear in the dimens ion N, i.e., q uadratic in the deg ree n.

It is w orth ob s erv ing that this b ehav ior is not peculiar to the ex ample jus t des crib ed.

Indeed, in practice w e hav e computed the av erag e of the us e percentag e of the

T a b le 2 . Interpolation errors of f (x ₁ , x ₂ ) = cos (x ₁ + x ₂ ) on a uniform 100 × 100 g rid at deg ree n = 20 (las t column: us e percentag e of s tab iliz ed formula (9 )– (10))

δ L ^Xu ₂₀ f − f _∞ % s tab .

1.0E − 10 1.9 E + 00 0

1.0E − 05 1.9 E + 00 0.003

1.0E + 00 1.9 E − 02 6 3.50

1.5E + 00 1.2E − 02 83.51

1.8E + 00 1.1E − 02 9 3.81

2.0E + 00 6 .0E − 15 100

Table 3. I n ter p olation er r or s of f (x ₁ , x ₂ ) = c os (x ₁ + x ₂ ) on a u n ifor m 100 × 100 g r id at d eg r ee n = 20 (last c olu m n : u se p er c en tag e of r ec u r r en c e r elation (10))

ε L ^{X u} ₂₀ f − f _∞ % r ec u r r.

1.0E − 05 7 .0E − 12 0

1.0E − 04 8.6E − 13 0.004

1.0E − 03 1.6E − 13 0.05

1.0E − 02 1.6E − 14 0.64

1.0E − 01 7 .1E − 15 6.37

1.0E + 00 6.4E − 15 63.65

1.0E + 01 6.0E − 15 100

r ec u r r en c e in ev alu atin g all th e Lag r an g e b asis p oly n om ials on a c er tain u n ifor m g r id . I f w e tak e r an d om , u n ifor m ly d istr ib u ted ev alu ation p oin ts, su c h a p er c en t- ag e b ec om es a r an d om v ar iab le (fu n c tion of th e u n ifor m r an d om v ar iab le), w h ose ex p ec tation , say η, d ep en d s on th e th r esh old ε b u t n ot on th e d eg r ee n. T h is is c lear ly seen in T ab les 4 an d 5 , w h er e it is sh ow n th at th e av er ag es u p to on e m illion r an d om p oin ts c on v er g e to v alu es c lose to th ose ob tain ed ab ov e on a u n ifor m 100 × 100 g r id , an d th at th ese v alu es d o n ot d ep en d on d eg r ee n.

N ow , th e ev alu ation of K _n ^∗ (x, x r,s ) u sin g on ly th e tr ig on om etr ic r ep r esen tation of U _n (c os θ ) c osts ab ou t 8 × 4 = 32 ev alu ation s of th e sin e fu n c tion , r ec allin g th at D _n an d D _n+1 ap p ear w ith th e sam e ar g u m en ts in (4), (6). D en otin g b y c _sin th e average ev alu ation c o s t of th e s in e fu n c tion (w h ic h ac tu ally d ep en d s on its in ter n al im p le- m en tation ), th e av er ag e c om p lex ity for th e ev alu ation of th e X u in ter p olan t for m u la L ^{X u} _n f (x) is of th e or d er of

C (n, ε) := 8nτ N + 32c _sin (1 − τ )N ∼ 4n ³ τ + 16c _sin (1 − τ )n ² fl op s , (11)

Table 4 . A v er ag es of th e u se p er c en tag e of r ec u r r en c e r elation (10), u p to on e m illion u n ifor m r an d om p oin ts, in ev alu atin g all th e Lag r an g e b asis p oly n om ials at d eg r ee n = 20

# of r an d om p oin ts % r ec u r r. (av er ag es)

ε = 0.01 ε = 0.1

1.0E + 01 0.5 0 7 .00

1.0E + 02 0.7 5 6.25

1.0E + 03 0.69 6.27

1.0E + 04 0.63 6.34

1.0E + 05 0.64 6.36

1.0E + 06 0.64 6.37

Table 5 . A v er ag e u se p er c en tag e η of r ec u r r en c e r elation (10), in ev alu atin g all th e Lag r an g e b asis p oly n om ials at d iffer en t d eg r ees

d eg r ee n p er c en tag e η

ε = 0.01 ε = 0.1

20 0.64 6.37

40 0.64 6.37

80 0.64 6.37

Table 6. C PU times (s econds ) for the ev aluation of all the L ag rang e b as is polynomials on a uniform 100 × 100 g rid

% recurr. n = 20 n = 30 n = 40 n = 5 0 n = 6 0

0.6 4 (ε = 0.01) 5 .43 11.8 1 20.6 4 31.9 9 45 .8 2

100 (ε = 10) 3.79 9 .72 20.38 36 .5 3 5 9 .33

w here τ = η / 100. C ons idering the ex perimental v alue c _{s in} = 10 (ob tained w ith G NU Fortran, s ee als o [13]), w e can conclude that, for ε ≤ 0.01 (i.e., τ ≤ 0.006 4), the s iz e of the ratio C (n, ε)/ N remains cons tant up to deg rees of the order of hun- dreds, that is in practical applications the computational cost can b e cons idered lin e a r in the numb er N of points.

A more s ophis ticated implementation may tak e into account that, for low deg rees, the recurrence relation cos ts les s than the trig onometric repres entation in ev aluating U n (cos θ ). C omparing the dominant cos ts, the alg orithm s hould us e only the former w hen 4n ³ < 16 c _{s in} n ² , i.e., n < 4c _{s in} .

O ur Fortran implementation of the Xu interpolation formula res orts to all the trick s jus t des crib ed, in particular the las t w ith the ex perimental v alue c _{s in} = 10, i.e., a thres hold deg ree n = 40 (as confi rmed b y the numerical tes t reported in T ab le 6 , performed on an AM D Athlon 28 00+ proces s or). T he corres ponding Fortran77 code is av ailab le at the w eb s ite h ttp ://w w w .m a th .u n ip d .it/∼m a rcov /softw a r e .h tm l.

3 . N u m er ic al S tu d y o f th e L ebes g u e C o n s tan t

In this s ection w e dis cus s another k ey feature of the Xu interpolation formula, that is the b ehav ior of its L eb es g ue cons tant. Firs t it comes eas y to b ound the L eb es g ue cons tant linearly in the dimens ion of the polynomial s pace V _n ² , w hich already s how s that the Xu points are g ood candidates for interpolation purpos es. Indeed, from the w ell-k now n b ound for C heb ys hev polynomials of the s econd k ind |U n (cos θ )| ≤ n+1 (cf. [4, p. 306 ]), w e immediately hav e

|D n (α , β )| ≤ 1

4 (n ² + (n − 1) ² ) (12)

w hich implies b y (6 )

|K n (x, y)| ≤ n ² + (n − 1) ² . (13)

H ence, b y means of the ex plicit repres entation (8 ) w e g et

| _n (x, x r,s )| =    

K _n ^∗ (x, x r,s ) K _n ^∗ (x r,s , x r,s )

≤ (n + 1) ² + 2n ² + (n − 1) ²

n ² = 4 + 2

n ² . (14) D efi ning , in the us ual w ay, the L e b e sg u e fu n ction for the Xu interpolation points

λ ^Xu _n (x) := 

x r,s ∈X _N

| n (x, x r,s )| , (15 )

1 0.5

0 0.5

1

1 0.5 0 0.5 1

1 1.5

2 2.5

3 3.5

4 4.5

1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1 1

0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1

−

−

−

−

−

− − − − −

−

− −

−

Fig. 1. T h e N = 24 X u p oin ts for n = 6 an d th e c or r esp on d in g Leb esg u e fu n c tion λ ^{X u} ₆ (x)

w e fi n ally ob tain th e follow in g b ou n d of th e Leb esg u e c on stan t ^{X u} _n := m ax

x∈[−1,1] ²

λ ^{X u} _n (x) ≤

4 + 2 n ²

N ∼ 4N ∼ 2n ² . (16)

H ow ev er, (16) is an ov er estim ate of th e ac tu al Leb esg u e c on stan t. I n fac t, th e Leb esg u e fu n c tion tu r n s ou t to b e sy m m etr ic an d seem s to attain its m ax im u m at th e fou r v er tic es of th e sq u ar e (see F ig . 1 for d eg r ee n = 6). T h is fac t h as b een c on fi r m ed b y a w id e set of n u m er ic al ex p er im en ts, w h er e w e h av e m ax im iz ed th e Leb esg u e fu n c tion λ ^{X u} _n (x) u p to d eg r ee n = 100 on a u n ifor m 1000 × 1000 g r id . I n F ig . 2, w e c om p ar e th e Leb esg u e c on stan t of X u p oin ts u p to d eg r ee n = 100 c om - p u ted as λ ^{X u} _n (1, 1), w ith th e least-sq u ar e fi ttin g fu n c tion (0.9 5 + 2/ π log (n + 1)) ² an d th e th eor etic al b ou n d for ten sor -p r od u c t in ter p olation of d eg r ee n (c f. [2]), i.e., (1 + 2/ π log (n + 1)) ² . T h ese c om p u tation s g iv e a sou n d b asis for th e follow in g

0 10 20 30 40 5 0 60 7 0 80 9 0 100

0 2 4 6 8 10 12 14 16

L e b e s g u e c o n s ta n t o f X u p o in ts (0.9 5 + 2/π lo g (n + 1))²

(1+ 2/π* lo g (n + 1))²

Fig. 2 . T h e Leb esg u e c on stan t of X u p oin ts u p to d eg r ee 100

Conjecture: The Lebesgue function λ ^Xu _n of X u inter p ola tion p oints ca n be bound ed a s max

x∈[−1,1] ²

λ ^Xu _n (x) = ^Xu _n
(2/π log (n + 1)) ² , n → ∞ . (17) M or eov er, the m a x im um is a tta ined a t the four v er tices of the sq ua r e.

W e s tres s fi nally that the Xu points are ex actly eq ually s paced w ith res pect to the D ub iner metric [5], w hich, on the s q uare  = [−1, 1] ² , turns out to b e µ _ (x, y) = max {|arccos x ₁ − arccos y ₁ |, |arccos x ₂ − arccos y ₂ |}. T his fact confi rms once more the conjecture s tated in [3]: “ nearly optimal interpolation points on a compact  are as ymptotically eq uidis trib uted w ith res pect to the D ub iner metric on ” .

4 . T es ts on F unctions I nterp ola tion

In this s ection w e compare interpolation at Xu points (XU ) w ith tens or-product C heb ys hev (T PC ) interpolation, and interpolation at M orrow -Patters on (M P), ex tended M orrow -Patters on (E M P) and Padua (PD ) (cf. [3]) points on three tes t functions w ith different deg ree of reg ularity, namely the Frank e function

f ₁ (x ₁ , x ₂ ) = 3

4 e ^{− 1 4 ((9x 1 −2) 2 +(9x 2 −2) 2 )} + 3

4 e ^{− 49 1 (9x 1 +1) 2 − 10 1 (9x 2 +1)} + 1

2 e ^{− 1 4 ((9x 1 −7) 2 +(9x 2 −3) 2 )} − 1

5 e ^{−((9x 1 −4) 2 +(9x 2 −7) 2 )} ,

f ₂ (x ₁ , x ₂ ) = (x ₁ ² + x ₂ ² ) ^5/2 and f ₃ (x ₁ , x ₂ ) = (x ₁ ² + x ₂ ² ) ^1/2 . T he ab ov e mentioned s et of points for n = 16 , that is M P, E M P, PD points, are dis played in Fig . 3 on the left and for comparis on on the rig ht w e dis play the corres ponding Xu points.

For M P, E M P and PD points, the interpolant w as cons tructed b y s olv ing the corre- s ponding V andermonde s ys tem, w hereas the Xu interpolant has b een implemented as des crib ed in Sect. 2 w ith ε = 0.01 (cf. T ab les 3– 5). T o ob tain an es timate of how the

1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1 1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1

1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1

1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 M P 1 E M P P D

X U

−

−

−

−

−

−

−

−

−

−

− − − − −

− − − − −

F ig . 3 . Left: the N = 153 M orrow -Patters on (M P), ex tended M orrow -Patters on (E M P) and Padua (PD )

points for n = 16 . R ight: the N = 144 Xu points for n = 16

in ter p olation er r or s g r ow , th ey h av e b een c om p u ted , in in fi n ity n or m , on a u n ifor m c on tr ol g r id of 100 × 100 p oin ts. T h e r esu lts ar e c ollec ted in T ab les 8 – 12. F or T P C p oin ts w e h av e c h osen as in [3] th e seq u en c e of d eg r ees n = 24 , 34 , 4 4 , 5 4 an d , for th e oth er sets of p oin ts, th e in ter p olation d eg r ees h av e b een c h osen in su c h a w ay th at th e d im en sion N of p oly n om ial sp ac es, an d th u s th e n u m b er of fu n c tion ev al- u ation s, is as c lose as p ossib le to th e d im en sion of th e ten sor -p r od u c t p oly n om ial sp ac es. T h e r esu ltin g seq u en c e of d eg r ee is n = 34 , 4 8 , 6 2, 7 6 .

I n T ab le 7 , w e d isp lay th e Leb esg u e c on stan ts (r ou n d ed to th e n ear est in teg er ) of M P , E M P , P D an d X u p oin ts c or r esp on d in g to th e c h osen d eg r ees. A s alr ead y ob ser v ed , P D an d X u p oin ts h av e th e sm allest Leb esg u e c on stan ts, w h ic h ar e v er y c lose to (1 + 2/ π log (n + 1)) ² ; see F ig . 2 an d [3]. W e r ec all th at, d en otin g b y L _n f th e in ter - p olation p oly n om ial of d eg r ee n on M P , or E M P or P D p oin ts, th e in ter p olation er r or c an b e estim ated b y

f − L _n f _∞, ≤ (1 + _n )E _n (f ),  = [−1, 1] ² , (18 ) w h er e E _n (f ) d en otes, as u su al, th e b est u n ifor m ap p r ox im ation er r or to f on  b y p oly n om ials in P ² n . A s for th e X u p oin ts, th e c or r esp on d in g p oly n om ial sp ac e V _n ² is a su b sp ac e of P ² n w ith P ² _n−1 ⊂ V _n ² ⊂ P ² n , fr om w h ic h w e h av e E _n (f ) ≤ in f _{p∈ V} 2

n f −

p _∞, ≤ E _n−1 (f ) an d th u s th e estim ate f − L ^{X u} _n f _∞, ≤ (1 + ^{X u} _n ) in f

p∈ V _n ²

f − p _∞, ≤ (1 + ^{X u} _n )E _n−1 (f ) . (19 ) T h e r ate of d ec ay of E n (f ) as n → ∞ d ep en d s on th e d eg r ee of sm ooth n ess of f , in v iew of m u ltiv ar iate g en er aliz ation s of J ac k son ’s th eor em (c f. [8 ]).

S om e c om m en ts on th e r esu lts in T ab les 8 – 12 ar e n ow in or d er. F ir st, w e ob ser v e th at in th ese ex am p les, X u in ter p olation er r or s ar e alm ost alw ay s v er y c lose to th ose

Table 7. Leb esg u e c on stan ts (r ou n d ed to th e n ear est in teg er )

in ter p . p ts. _{34 4 8 6 2 7 6}

M P 6 4 9 126 4 208 2 3102

E M P 237 4 5 6 7 4 6 1106

P D 11 13 14 15

X U 10 12 13 14

Table 8 . I n ter p olation er r or s on [0, 1] ² for th e F r an k e fu n c tion

T P C 1.3E -03 2.6 E -06 1.1E -09 2.0E -13

n, N = (n + 1) ² 24 , 6 25 34 , 1225 4 4 , 2025 5 4 , 3025

M P 1.3E -03 2.6 E -06 1.1E -09 2.0E -13

n, N = (n + 1)(n + 2)/ 2 34 , 6 30 4 8 , 1225 6 2, 2016 7 6 , 3003

E M P 6 .3E -04 1.3E -06 5 .0E -10 5 .4 E -14

n, N = (n + 1)(n + 2)/ 2 34 , 6 30 4 8 , 1225 6 2, 2016 7 6 , 3003

P D 4 .3E -05 3.3E -08 5 .4 E -12 1.9 E -14

n, N = (n + 1)(n + 2)/ 2 34 , 6 30 4 8 , 1225 6 2, 2016 7 6 , 3003

X U 3.2E -05 4 .7 E -08 7 .8 E -12 1.9 E -13

n, N = n(n + 2)/ 2 34 , 6 12 4 8 , 1200 6 2, 19 8 4 7 6 , 29 6 4

Table 9. Interpolation errors on [−1, 1] ² for the function f ₂ (x ₁ , x ₂ ) = (x ₁ ² + x ₂ ² ) ^5/2

T PC 6 .0 E -0 5 8 .2E -0 6 1.8 E -0 6 5.4 E -0 7

n , N = (n + 1) ² 24 , 6 25 34 , 1225 4 4 , 20 25 54 , 30 25

M P 1.8 E -0 4 5.1E -0 5 1.9 E -0 5 8 .8 E -0 6

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

E M P 6 .5E -0 5 1.8 E -0 5 6 .7 E -0 6 3.0 E -0 6

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

PD 3.6 E -0 6 6 .5E -0 7 1.8 E -0 7 6 .5E -0 8

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

XU 7 .1E -0 6 1.2E -0 6 3.4 E -0 7 1.2E -0 7

n , N = n (n + 2)/2 34 , 6 12 4 8 , 120 0 6 2, 19 8 4 7 6 , 29 6 4

Table 1 0 . Interpolation errors on [0 , 2] ² for the function in T ab le 9

T PC 8 .5E -0 9 1.7 E -10 1.4 E -11 1.1E -11

n , N = (n + 1) ² 24 , 6 25 34 , 1225 4 4 , 20 25 54 , 30 25

M P 1.0 E -0 8 3.8 E -10 3.7 E -11 2.3E -11

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

E M P 7 .2E -0 9 2.6 E -10 2.4 E -11 8 .6 E -12

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

PD 2.8 E -0 9 9 .3E -11 9 .4 E -12 6 .4 E -12

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

XU 3.2E -0 9 1.1E -10 1.6 E -11 4 .5E -12

n , N = n (n + 2)/2 34 , 6 12 4 8 , 120 0 6 2, 19 8 4 7 6 , 29 6 4

Table 1 1 . Interpolation errors on [−1, 1] ² for the function f ₃ (x ₁ , x ₂ ) = (x ² ₁ + x ₂ ² ) ^1/2

T PC 2.1E -0 1 1.1E -0 1 6 .8 E -0 2 4 .6 e-0 2

n , N = (n + 1) ² 24 , 6 25 34 , 1225 4 4 , 20 25 54 , 30 25

M P 4 .4 E -0 1 4 .4 E -0 1 4 .4 E -0 1 4 .4 E -0 1

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

E M P 1.4 E -0 1 1.4 E -0 1 1.4 E -0 1 1.4 E -0 1

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

PD 3.7 E -0 2 2.7 E -0 2 2.1E -0 2 1.7 E -0 2

n , N = (n + 1)(n + 2)/2 34 , 6 30 4 8 , 1225 6 2, 20 16 7 6 , 30 0 3

XU 5.1E 0 -2 3.6 E -0 2 2.8 -0 2 2.3E -0 2

n , N = n (n + 2)/2 34 , 6 12 4 8 , 120 0 6 2, 19 8 4 7 6 , 29 6 4

of interpolations at PD points, and s maller than the errors g iv en b y the other s ets of

points. Notice that on the functions f ₂ and f ₃ , w hich hav e a s ing ularity at the orig in,

interpolation performs alw ays b etter w hen the s ing ularity is located at the corner of

the s q uare, w here all the fi v e s ets of points clus ter b y cons truction. Xu points ex hib it

the w ors t b ehav ior only in the tes t of T ab le 12, es pecially for hig h deg rees : this may

b e as crib ed to the pres ence of a s trong s ing ularity (dis continuity of the g radient) at

the orig in, around w hich more points of the other s ets clus ter.

Table 12. I n ter p olation er r or s on [0 , 2] ² for th e fu n c tion in T ab le 11

T P C 2.8 E -0 3 5 .8 E -0 4 1.1E -0 4 8 .9 E -0 5

n, N = (n + 1) ² 24, 6 25 34, 1225 44, 20 25 5 4, 30 25

M P 8 .8 E -0 4 2.8 E -0 4 2.6 E -0 4 1.7 E -0 5

n, N = (n + 1)(n + 2)/ 2 34, 6 30 48 , 1225 6 2, 20 16 7 6 , 30 0 3

E M P 8 .3E -0 4 2.6 E -0 4 2.1E -0 4 2.1E -0 5

n, N = (n + 1)(n + 2)/ 2 34, 6 30 48 , 1225 6 2, 20 16 7 6 , 30 0 3

P D 7 .3E -0 4 3.7 E -0 4 7 .0 E -0 6 4.6 E -0 6

n, N = (n + 1)(n + 2)/ 2 34, 6 30 48 , 1225 6 2, 20 16 7 6 , 30 0 3

X U 9 .4E -0 4 4.7 E -0 4 2.8 E -0 4 1.9 E -0 4

n, N = n(n + 2)/ 2 34, 6 12 48 , 120 0 6 2, 19 8 4 7 6 , 29 6 4

4.1. Efficiency and Robustness

T o su p p or t th e effi c ien c y an d r ob u stn ess of ou r im p lem en tation of th e X u in ter - p olation for m u la, w e d id som e c om p ar ison s w ith th e MPI software b y T . S au er (c f. [10 ], [11]). T h e M P I softw ar e is on e of th e m ost effi c ien t an d r ob u st im p lem en ta- tion s of m u ltiv ar iate in ter p olation b y p oly n om ials v ia fi n ite d iffer en c es an d is b ased on th e n otion of block w ise inter p olation. C allin g X U ou r im p lem en tation of th e X u in ter p olation for m u la, w e c om p ar ed th e C P U tim es n ec essar y to b u ild th e in ter p o- lan t an d th e in ter p olation er r or s for b oth X U an d M P I on all ou r tests fu n c tion s.

T h e tests w er e p er for m ed , as ex p lain ed ab ov e, on a A M D A th lon 28 0 0 + p r oc essor m ac h in e, w ith b oth c od es c om p iled u sin g th e op tim iz ation op tion -O3. T h e r esu lts ar e c ollec ted in T ab les 13– 16 . F u r th er m or e, all tests w ith M P I , w er e d on e m od ify in g on ly th e tem p late fi le demo.cc to w or k w ith tw o-d im en sion al p oin t sets. T h e tar g et

Table 13 . C P U tim es (in sec on d s) an d in ter p olation er r or s on [0 , 1] ² of X U an d M P I for th e F r an k e fu n c tion

n 20 30 40 5 0 6 0

X U 2.1 5 .2 10 .3 17 .8 28 .4

7 .3E -0 3 3.6 E -0 4 3.1E -0 6 1.8 E -0 8 2.5 E -11

M P I 0 .6 U n solv . U n solv . U n solv . U n solv .

3.8 E -0 2 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

Table 14 . C P U tim es (in sec on d s) an d in ter p olation er r or s of M P I for th e F r an k e fu n c tion on d iffer en t d om ain s b y a c h an g e of v ar iab les an d r eor d er in g th e X u p oin ts as Leja seq u en c es

n 20 30 40 5 0 6 0

M P I 0 .6 4.3 21.0 7 5 .6 U n solv .

[−1, 1] ² 6 .3E -0 3 3.5 E -0 4 2.0 E -0 1 3.8 E -0 2 ∗ ∗ ∗

M P I 0 .5 3.7 17 .4 6 2.3 18 3.4

[−2, 2] ² 6 .4E -0 3 1.0 E -0 2 2.7 E + 0 2 1.3E + 14 1.9 E + 35

M P I -Leja 0 .6 4.3 21.0 7 5 .6 U n solv .

[−1, 1] ² 6 .4E -0 3 3.5 E -0 4 1.1E -0 4 2.0 E -0 3 ∗ ∗ ∗

Table 15. C PU times (in s econds ) and interpolation errors on [−1, 1] ² of XU and M PI for the function f ₂ (x ₁ , x ₂ ) = (x ₁ ² + x ₂ ² ) ^1/2

n 20 30 40 50 6 0

XU 2.1 5.2 10 .3 17 .8 28 .4

8 .7 E -0 2 5.8 E -0 2 4.3E -0 2 3.5E -0 2 2.9 E -0 2

M PI 0 .6 4.3 20 .8 7 4.8 U ns olv .

8 .7 E -0 2 5.8 E -0 2 2.8 E + 0 0 4.7 E + 0 0 ∗ ∗ ∗

Table 16 . C PU times (in s econds ) and interpolation errors on [−1, 1] ² of XU and M PI for the function f ₃ (x ₁ , x ₂ ) = (x ₁ ² + x ₂ ² ) ^5/2

n 20 30 40 50 6 0

XU 2.1 5.2 10 .3 17 .8 28 .4

1.1E -0 4 1.3E -0 5 3.1E -0 6 1.0 E -0 6 4.0 E -0 7

M PI 0 .6 4.3 21.0 7 5.3 U ns olv .

1.1E -0 4 1.3E -0 5 1.8 E -0 3 4.8 E -0 3 ∗ ∗ ∗

points on w hich w e ev aluate the interpolation errors w ere chos en as b efore, that is a g rid of 10 0 × 10 0 points on the reference s q uare.

R em ar k s : W e performed many ex periments w ith different functions and s q uare domains, b ut all s how ed the s ame b ehav ior: the M PI s oftw are w ork s q uite w ell, b oth in terms of C PU times and interpolation errors, for s mall deg rees n b ut for hig her deg rees it b ecomes uns tab le (n = 40 , 50 ) or unus ab le (n = 6 0 ). T his has b een v erifi ed als o applying s tab iliz ation techiniq ues for the div ided differences (on w hich the M PI s oftw are is ultimately b as ed) lik e s caling the domain or reordering the interpolation points as Leja sequences (cf. [9 ], [12]). See the details for the Frank e function in T ab les 13 and 14. O n the contrary, XU can s uitab ly manag e interpolation up to v ery hig h deg rees.

5. C o n c lu s io n s an d F u t u r e W o r k s

In this paper, w e inv es tig ated the numerical as pects of Xu interpolation formula and, in particular, w e ob tained an effi cient and s tab le formula for its computation and tig ht numerical b ounds of the g row th of the as s ociated L eb es g ue cons tant. O ur numerical s tudy s how s that Xu interpolation g iv es almos t the b es t one can do w ith polynomials on the s q uare. In fact, b es ides the v ery g ood b ehav ior of its L eb es g ue cons tant (w hich g row s lik e lo g ar ith m squar e of the deg ree), it can b e implemented b y an alg orithm w hich has in practice a linear cos t in the numb er of interpolation points (i.e., in the dimens ion of the underlying polynomial s pace).

H ow ev er, important theoretical as pects hav e s till to b e faced. Supported b y our

res ults, it w ould b e interes ting fi rs t to prov ide analytically a precis e g row th rate

of the L eb es g ue cons tant and, as s ug g es ted b y Fig . 1, prov e theoretically that the

max ima of the Leb esg ue function are tak en at the v ertices of the sq uare [−1, 1] ² ; see the conjecture at the end of Sect. 3. As w e already ob serv ed, in this w ay w e could simply restrict on fi nding an ex plicit formula for λ ^Xu _n (1, 1).

Acknowledgements

W e are g rateful to W alter G autschi and Y uan Xu for v aluab le discussions and sug g estions during their recent v isits at the U niv ersities of Padua and V erona. W e are also g rateful to T omas Sauer w ho k indly prov ided us the M PI softw are. T his w ork has b een supported b y the research project C PD A0 28 29 1

“ E ffi cient approx imation methods for nonlocal discrete transforms” of the U niv ersity of Padov a, the ex -6 0 % funds of the U niv ersity of V erona, and b y the G NC S-INdAM funds.

R efer ences

[1] Bos, L.: O n certain confi g urations of points in R ⁿ w hich are unisolv ent for polynomial interpolation.

J. Approx . T heor. 64(3), 27 1– 28 0 (19 9 1).

[2] Brutman, L.: Leb esg ue functions for polynomial interpolation – a surv ey. Ann. Numer. M ath.

4, 111– 127 (19 9 7 ).

[3] C aliari, M ., D e M archi, S., V ianello, M .: Biv ariate polynomial interpolation on the sq uare at new nodal sets. Appl. M ath. C omput. 1 65 , 26 1– 27 4 (20 0 5 ).

[4] D av is, P. J.: Interpolation and Approx imation. New Y ork : D ov er Pub lications 19 7 5 .

[5 ] D ub iner, M .: T he theory of multi-dimensional polynomial approx imation. J. Anal. M ath. 67 , 39 – 116 (19 9 5 ).

[6 ] G asca, M ., Sauer, T .: Polynomial interpolation in sev eral v ariab les. Adv . C omput. M ath. 1 2 , 37 7 – 410 (20 0 0 ).

[7 ] M orrow , C . R ., Patterson, T . N. L.: C onstruction of alg eb raic cub ature rules using polynomial ideal theory. SIAM J. Numer. Anal. 1 5 (5 ), 9 5 3– 9 7 6 (19 7 8 ).

[8 ] Ple´sniak , W .: R emark s on J ack son’s theorem in R ^N . E ast J. Approx . 2 (3), 30 1– 30 8 (19 9 6 ).

[9 ] R eichel, L.: New ton interpolation at Leja points. BIT 30 , 332– 346 (19 9 0 ).

[10 ] Sauer, T .: C omputational aspects of multiv ariate polynomial interpolation. Adv . C omput. M ath.

3, 219 – 238 (19 9 5 ).

[11] Sauer, T ., Xu, Y .: O n multiv ariate Lag rang e interpolation. M ath. C omp. 64, 1147 – 117 0 (19 9 5 ).

[12] T al-E z er, H .: H ig h deg ree polynomial interpolation in New ton form. SIAM J. Sci. Stat. C omput.

1 2 (3), 6 48 – 6 6 7 (19 9 1).

[13] T ang , P. T . P.: Some softw are implementations of the functions sine and cosine. ANL R eport 9 0 /3, Arg onne National Lab oratory, April 19 9 0 .

[14] Xu, Y .: G aussian cub ature and b iv ariate polynomial interpolation. M ath. C omp. 5 9 , 5 47 – 5 5 5 (19 9 2).

[15 ] Xu, Y .: Lag rang e interpolation on C heb yshev points of tw o v ariab les. J. Approx . T heor. 8 7 , 220 – 238 (19 9 6 ).

[16 ] Xu, Y .: Polynomial interpolation on the unit sphere and on the unit b all. Adv . C omput. M ath. 2 0 , 247 – 26 0 (20 0 4).

L. Bos M . C aliari

25 0 0 U niv ersity D riv e NW D ept. of C omputer Science

C alg ary U niv ersity of V erona

Alb erta T 2N1N4 37 129 V erona

C anada Italy

e-mail: lpb os@ math.ucalg ary.ca

S. D e M archi M . V ianello

D ept. of C omputer Science D ept. of Pure and Applied M athematics U niv ersity of V erona U niv ersity of Padov a

37 129 V erona 35 122 Padov a

Italy Italy