Polynomial interpolation in several variables

AdvancesinComputationalMathematics0(2001)?–?1PolynomialinterpolationinseveralvariablesMarianoGasca,a,∗ThomasSauerb,∗∗aDepartmentofAppliedMathematics,UniversityofZaragoza,50009Zaragoza,Spain,E-mail:[e-mail]t,Universit¨atErlangen–N¨urnberg,Bismarckstr112,D–91054Erlangen,GermanyE-mail:[e-mail]resultsonmultivariatepolynomialinterpolationinthelasttwentyfiveyears,aperiodoftimewhenthesubjectexperienceditsmostrapiddevelopment.Theproblemisconsideredfromtwodifferentpointsofview:theconstructionofdatapointswhichallowuniqueinterpolationforgiveninterpolationspacesaswellastheconverse.Inaddition,onesectionisdevotedtoerrorformulasandanotheronetoconnectionswithComputerAlgebra.Anextensivelistofreferencesisalsoincluded.Keywords:Interpolation,multivariatepolynomials,Newtonapproach,divideddifferences,Gr¨obnerbases,H–bases1.IntroductionInterpolationistheproblemofconstructingafunctionpbelongingtoa(simple)finitedimensionallinearspacefromagivensetofdata.Usually,thein-terpolationdataareobtainedbysamplinganother(moredifficult)functionand,inthatcase,itissaidthatpinterpolatesf,inthesensethatbothfunctionscoincideonthatdataset.Thesimplestcontexttostudyhereisinterpolationbyunivariatepolynomials.Thereforeitisnosurprisethatinterpolationbyunivari-atepolynomialsisaveryclassicaltopic.However,interpolationbypolynomialsofseveralvariablesismuchmoreintricateandisasubjectwhichiscurrentlyanactiveareaofresearch.Inthispaperwewanttodescribesomerecentdevelop-mentsinpolynomialinterpolation,especiallythosewhichleadtotheconstruction∗PartiallysupportedbyDGESSpain,PB96-0730∗∗PartiallysupportedbyDGESSpain,PB96-0730andProgramaEuropaCAI-DGA,Zaragoza,Spain2M.GascaandT.Sauer/Polynomialinterpolationoftheinterpolatingpolynomial,ratherthanverificationofitsmereexistence.Letusdenotebyx=(ξ1,...,ξd)anypointofRdandbyΠdthespaceofalld–variatepolynomialswithrealcoefficients.Thesubspaceofpolynomialsoftotaldegreeatmostn,denotedbyΠdn,isformedbypolynomialsp(x)=Xα∈Nd,n0aαxα,(1.1)whereNd,n0isthesetofall(integerlattice)pointsα=(α1,...,αd),αi≥0,i=1,...,d,with|α|=α1+···+αd≤n.Inaddition,thecoefficientsaα,α∈Nd,n0,arerealconstantsandxα=ξα11···ξαdd.WealsousethenotationHd,n:=Nd,n0\Nd,n−10.Thissurveywillbemainlyconcernedwiththeproblemoffindingapolyno-mialp∈Πdsuchthatthevaluesofpand/orsomeofitsderivativesareprescribedrealnumbersatpointsx1,...,xNofRd.Whenderivativesarenotinterpolated,theproblemisreferredtoastheLagrangeinterpolationproblemandcanbestatedinthefollowingform:Givenafinitenumberofpointsx1,...,xN,somerealconstantsy1,...,yNandasubspaceVofΠd,findapolynomialp∈V,suchthatp(xj)=yj,j=1,...,N.(1.2)TheinterpolationpointsxiarealsocallednodesandVistheinterpolationspace.1.1.TheunivariatecaseThereisawell–developedandextensiveclassicaltheoryofunivariateLa-grangepolynomialinterpolation.InthiscontexttheHermiteinterpolationprob-lemarisesasalimitingcasewhensomeoftheinterpolationpointscoalesce,givingrisetoderivativesofconsecutiveorders.TheLagrangeproblemwithNdifferentnodesxi∈RortheHermiteproblem,withmiderivativesofconsecutiveorders0,1,...,mi−1ateachnodexiandN=Pimi,havealwaysauniquesolutioninthespaceΠ1N−1ofunivariatepolynomialsofdegreenotgreaterthanN−1.Iftherearesome“gaps”intheorderofthederivativesatsomeinterpolationpoint,theproblemiscalledaBirkhoffinterpolationproblem.Intheunivariatecase,thisproblemhasawelldevelopedtheory,see[77]forconditionsensuringitssolvability.MultivariateBirkhoffinterpolationwillenterourdiscussiononlyM.GascaandT.Sauer/Polynomialinterpolation3inaperipheralmanner.Thebook[78]isthebestsourceofinformationaboutthissubject.ReturningtotheunivariateLagrangeinterpolationproblem,werecallthattheLagrangeformulap(x)=NXi=1yi`i(x),(1.3)where`i(x)=NYj=1j6=ix−xjxi−xj,i=1,...,N,(1.4)explicitlyprovidesthesolutionoftheproblem.Alternatively,arecursiveformisobtainedfromtheNewtonformula,whichmakesuseofdivideddifferences.Specifically,wehavethatp(x)=NXi=1f[x1,...,xi]i−1Yj=1(x−xj),(1.5)wherethedivideddifferencef[xj,...,xk],j≤k,isrecursivelydefinedbytheequationsf[xj]=f(xj)f[xj,...,xk]=f[xj,...,xk−1]−f[xj+1,...,xk]xj−xk.(1.6)AnimportantadvantageoftheNewtonformulaisthatitcanbeeasilyextendedtoincludetheHermitecase.LetusalsomentiontheNeville–Aitkenformulap(x)=(x−x1)p1(x)−(x−xN)p2(x)xN−x1,(1.7)wherep1,p2solvetheinterpolationproblemsatthenodesx2,...,xNandx1,...,xN−1,respectively.Theseformulassuggestastrategyofconstructingtheinterpolatingpolyno-mialatNnodesfromthesolutionsofsomeinterpolationproblemsdependingonlessdata.TheLagrangeformulausesthesolutionsofNinterpolationproblems,4M.GascaandT.Sauer/Polynomialinterpolationeachofthemwithonlyoneinterpolationpoint.TheNewtonformula,writtenintheformp(x)=N−1Xi=1f[x1,...,xi]i−1Yj=1(x−xj)+f[x1,...,xN]N−1Yj=1(x−xj),(1.8)tellsuswhathastobeaddedtothesolutionoftheproblemwiththeN−1pointsx1,...,xN−1togetthesolutionoftheproblemwiththeNpointsx1,...,xN.Finally,theNeville–Aitkenformulatellsushowthissolutioncanbeobtainedbycombiningthesolutionsofthetwoproblemscorrespondingtothedatapointsx2,...,xNandx1,...,xN−1.Ageneralinterpolationformul