Newton Bases For Multivariate Polynomial Interpolation

In this paper, we first consider the problem of Birkhoff interpolation .Definition 1. Let and , be as above. If for any, and then iscalled connected. Moreover, if connected,then the problem is called connected.Similarly, we can define ?? ? ?? connected for the problem .In this paper, we only discuss the ?? ? ?? connected interpolations. The resultsof connected cases can be obtained likewise.Let be an Hermite system with ?? its index set. If for some interpolationfunctional i0, there exists a functional ,, defined as [27], such that , then we say that theinterpolation functional is constructible w.r.t. . Moreover, if every, is constructible w.r.t., we say that the problem is constructibleLet , andthen we say that ??1 is equivalent to Q₂, denoted by Q₁～Q₂. It is easy to checkthat～is an equivalence relation. We denote all the equivalence classes of ??by . Next, we will prescribe an order 1 on set . We saythat if for any , we haveAlgorithm 1 (Construction of Hermite system)From now on, without loss of generality, we may assume that the elementsof are in ascending order w.r.t. (?)1.Output: Hermite systemIf the problem connected, it is constructible w.r.t.. The set with defined as [27] is a Newton Basis forthe connected problem , and we denote by P the space spannedby .Theorem 1 If the problem is x-y connected, it has aunique solution in , i.e., it is regular.Now we discuss the unconnected case. Definition 2 Let and , be as above. The setis called the x-y connected closure of .When the interpolation problem is not x-y connected, we consider theassociated x-y connected interpolation problem de?ned bywhere p is the interpolant and . We denote the problem by .Since it is x-y connected, we can get the Hermite system ?? and its index set with Algorithm 1. Therefore,It implies that there exists a subset x-y such thatThe set is a Newton basis for the unconnected problem, and we denote by the interpolation space spanned by it.Theorem 2 The problem has a unique solution in , i.e.,it is regular.We can generalize the results above to multivariate cases without anyeffort. Next, we talk about how to get the minimal degree interpolation mono-mial basis and Newton basis for the bivariate Lagrange interpolation.Let P be a set of distinct points, S be a lower set, then they produce abivariate Lagrange scheme (,S), where S determines a unique polynomialspaceIf for every given data, the interpolation problem has a unique solution, we saythat the interpolation scheme ((?),S) is regular, and we call ???? the interpola-tion space for the interpolation problem. Moreover, let ??0 = min{?? : ???? ? Π_M}. If there does not exist an interpolation space inΠ_M0-1, we say that is a minimal degree interpolation space.According to [51], we can get two special sets, denoted by which re?ect the geometric distribution of the set of points .Proposition 3 There must exist at least one cartesian subset for anynon-empty set of points in ??2.Theorem 4 Let be a set of distinct points in , is anS′-cartesian subset, i.e. . If the monomial basis forthe interpolation problem w.r.t. , thenCorollary 5 Let be a set of distinct points in is an′-cartesian subset, then Definition 3 Let be a lower set, define its degreeTheorem 6 Let P be a set of distinct points in 2. Assumed that, if there exists an cartesian subset′of such that deg(′) = then the space is a minimal degree interpolation space forthe Lagrange interpolation.Proposition 7 Let P be a set of distinct points . The points give rise to polynomials, and the empty productsare taken as 1. Then we have Proposition 8 Let P be a set of distinct points . We define the polynomialswhere . The empty products aretaken as 1. Then,When the space is a minimal degree interpolation spacefor the Lagrange interpolation, the set isthe minimal degree interpolation monomial basis, and is theminimal degree interpolation Newton basis.For general Lagrange interpolation, we can get degree reducing interpola-tion monomial or Newton basis by the BM algorithm. But the complexity ofthe BM algorithm is higher. We now discuss how to improve the BM algorithm.Theorem 9 The Lagrange interpolation schemes (P,(?)(?)(?)(?)(P)) and (P,(?)(?)(?)(?)(P))are regular. Furthermore,(i) the set is the DRIMB as well as : is a DRINB w.r.t. (?)lex for the interpolation problem .(ii) the set is the DRIMB as well as is a DRINB w.r.t. (?)rlex.Algorithm 2 (SPBM)This algorithm is an improved version of BM algorithm for bivariate casesunder (?)lex or (?)rlex.Input: A set of distinct affine points (?)2 and a fixed term ordering(?)lex or (?)rlex.Output: The 3-tuple (G,N,Q), where G is the reduced Gr¨obner basis of, N and Q are DRIMB and DRINB for the Lagrange interpolation on, respectively. SPBM1. Construct lowerSPBM2. Compute the sets and by Theorem 9;SPBM3. Compute the border set ;SPBM4. Goto BM2 of BM algorithm for the reduced Gr¨obner basis ??.For other monomial orderings, we can improve the BM algorithm using amaximal cartesian subset of the set of points.Definition 4 Let(?)be a set of points in ??2, and (?)′be a cartesian subsetof (?). We say that (?)′is a maximal cartesian subset of(?)if any cartesianproper subset (?)′′of(?)containing (?)′is such that (?)′′= (?)′. In addition, amaximal row subset of(?)is a non-empty subset that equals the intersectionof(?)and a horizontal line.We can present an algorithm to get a special maximal cartesian subset.Algorithm 3 (Maximal Cartesian Subset Construction Algorithm)Input: A set of distinct affine pointsOutput: A maximal cartesian subsetMCS1. Start with an empty listMCS2. If(?)= [ ], return the set (?)′and stop. Otherwise, computelower sets andMCS3. If , then replace (?)′by (?)′∪P, return the set(?)′and stop;MCS4. Otherwise, we ?rst choose a maximal row subset of(?)withmaximal cardinal number, denoted by A. Next, delete from(?)the pointseither in A or have di?erent abscissae from the points in ??. Finally, replace(?)′by (?)′∪A and continue with MCS2.Now, we can provide an algorithm to improve the BM algorithm for anymonomial ordering.Algorithm 4 (GPBM)Input: A set of affine points(?) and a term ordering . Output: The 3-tuple (??,??,??).GPBM1: Get a maximal cartesian subset P′of P by Algorithm 3;GPBM2: Compute the lower set and setGPBM3: Goto BM2 of the BM algorithm to complete the computationand get the whole output.