Newton Type Multivariate Interpolation Bases On Lower Sets

Newton's algorithm for constructing univariate interpolation polynomial is well-known. In this paper,we propose theoretically an interpolation basis of Newton type which spans a minimal degree interpolation space for Lagrange interpolation on a lower subset of a tensor product grid. We generalize Newton type Lagrange interpolation bases for bivariate and trivariate case,respectively.Firstly,let us recall the Newton Basis of univariate interpolation.Considering the univariate interpolation,we find a polynomial p satisfyingwhere f_i∈R,i =1, …, m, and p∈ P (?) R[x],the interpolation space,which can be spaned by (?)= {p₁,p₂, … ,p_m} (?) R[x], whereIf so, we will call (?) a Newton basis for this interpolation. Obviously,the main property of Newton basis isSecondly,we propose some definitions:Definition 1 Given a set of m distinct points x^\ ? ? -x^ € Rd.For prescribed values /? € R,i = 1, ? â–  ? , m, find all polynomials p 6 nd, satisfyingp(z? = /<) (2)We call it the problem of Lagrange interpolation.Definition 2 [19] Let Lagrange interpolation be in Definition l.We call a subset V C IT* the minimal degree interpolation space w.r.t. -< for the Lagrange interpolation if(1). V is an interpolation space, i.e., for any /* G R, i = 1, ? ? ? , m, there is a unique p € V such that p satisfies (2);(2). V is -< —minimal with this property,i.e., there exists no interpolation space Q with Q -< V.The latter means that for any q € Q there exists a p EV such that q -< p\(3). T3 is -< -reducing. Let pi,P2> ? ? ? ,pt ï¿¡ IT1. IfWe will call *$ = {pi,P2j ? ? ? )Pi} a minimal degree interpolation basis w.r.t. -< for the Lagrange interpolation.Definition 3 Let Lagrange interpolation be in Definition 1. If V is its minimal degree interpolation basis w.r.t. X, then a Newton basis 71 of V will be called a minimal degree interpolation Newton basis(MDINB) w.r.t. -<.Definition 4 Let C C N(j, C is called lower if, for any (c*i, ? ? ? , ot*d*>d) € e> we write e â– < e'> if (ai? ? ? ? 'ad) â– < (a[, ? ? ? , a'd).Therefore, we can give 0 an enumeration, say 9\, ? ? ? , 0#x, satisfying0i = <5(*i0,-,xdo) -< 02 - ji) >â–  0- From the definition of term order (see [11]), we can deduce easily that at least one of ik > k,jk > ji holds. By (3), we have Q(pk) = 0. Our claim is proved.According to Definition 3,for any -<-ordered set 6,9t is a MDINB w.r.t. - - ?*?) = i.ji'=O fc'=OProof Similar to the proof of Theorem 3.