The Minimal Newton Bases Of Multivariate Interpolation

Polynomial interpolation is a basic method for approxima-tion. The theory of univariate polynomial interpolation has beenconstructed completely. But Di?er to the univariate polynomialinterpolation problems, the multivariate interpolation has manyproblems to solve. Of the multivariate interpolation problems,people pay more attention to constructing the multivariate inter-polation polynomials under the given interpolation conditions.To the given interpolation problems, the multivariate interpo-lation polynomials would be constructed easy if we have theNewton bases. So in this thesis, we study the construction ofNewton bases of the classical multivariate interpolation prob-lems. We discuss the given nodes and the given di?erential con-ditions minimal degree Newton bases w.r.t. grlex which relatedto a listed functional set mainly. First, we give some note anddefinition.Letα₁,...,α_d∈N, and supposethen we call the R(α₁,α₂,...,α_d) is a(in the space Nd)tensorproduct set.Letκ= (m1,m2,...,md)∈N0d, we call X is tensor productgrid in Rd if where x_iαi,1≤i≤d are distinct.Let , if to the all (α₁,α₂,...,α_d)∈L, we havethen we call the L is a (of N0d) lower set, and we call the subsetXL of R^d is a lower grids subsets, whereGenerally, the n dimension Hermite interpolation problem aredefined as hereafter. Supposedefine the differential operators:the point x|ˉ∈R^d and the related di?erential operators can definethe linear functional onΠ^d :Next, we would give the definitions of the Hermite interpolationproblem and the Lagrange interpolation problem.Definition 1 Given a set of N distinct points x⁽¹⁾,...,x^(N)∈Rd, for the prescribed values lower di?erential operators sets , then we callis a Hermite interpolation problem.When the set B1,...,BN have only 0, we call the upper in-terpolation problem is a Lagrange interpolation problem. First,we study the Newton bases of Lagrange interpolation on lowerset. So we give the definition of the list of point evaluation func-tionals defining Lagrange interpolation on lower set next. Definition 2 Let andΘbe the set of point evaluationfunctionals defining Lagrange interpolation on Y. Fixed a mono-mial order in N^d. For ,we write . Therefore, we cangiveΘan enumeration, sayθ₁,...,θ_#Y, satisfyingNote that the set Y also has a list, then,Θand Y are called -ordered.The following theorem tells us that we can give the minimaldegree Newton bases , the theorem is only about 3Dcondition, and the same bases in the d dimension.Theorem 1 Let be a lower subset of a tensor productgrid, andΘbe the set of point evaluation functionals definingLagrange interpolation on XL. Fix a monomial order . M = . Suppose is ordered, whereA minimal degree interpolation Newton basis P w.r.t. grlexconsists of polynomials:where and .Definition 3 Given a set of N distinct points'a tensor productgrid set is the lower di?erential set definingHermite interpolation on the related points, let graded is thegrade degree order, that is graded lexicographic order or gradedreverse lexicographic order. Suppose are graded -ordered. Letand M = #A, then A have the form:if the element of A: , where , satisfy one ofthe conditions:then we call . So we define the list of set A, where have the form:Then the set A are called -ordered.Next, we study the multivariate dimension identical Hermiteinterpolation Newton bases on the tensor product grids. Weonly give the results of 3D condition, and the same bases in thed dimension. Supposeis the linear functionals set defining the identical Hermite inter-polation on the tensor product grid set X and it is a list ordered by . The number k,1≤k≤M element of A : where .First, letwhere1≤k≤M,(μ_k,ν_k,ω_k)∈B, andWe study the monomial bases w.r.t. grlex of the upper Hermiteinterpolation problem. LetNext, we would think about the Newton bases of identicalHermite interpolation. We have the results underside: the def-inition of the linear evaluation functionals A on tensor productgrid set, the Newton bases of the interpolation problem definedby the list A , the proof of minimal Newton bases .Theorem 2 Suppose X is a tensor product grid set, B,A aredefined upper, then the kernel of the linear evaluation functionalsA defining a identical Hermite interpolation defined on X is anideal I.Then the reduced Gr¨obner Bases of I is: so, the minimal term bases set w.r.t. grlex of the interpolationproblem is:Theorem 3 Suppose X is a tensor product grid set, B',A aredefined upper, then the identical Hermite interpolation Newtonbases defined by B on X are the set:and A_l(p_k) =δ_lk,1≤l≤k≤M.Then we give the definition of point evaluation functionals setlist w.r.t. lex defining Lagrange interpolation on a tower gridset. The 2D lower set can also be the form: . Define the towersubset of X:where .Definition 4 Given a tower set ,Θ^T are point evalua-tion functionals set defining the Lagrange interpolation on X^T ,for all , ifthen we call . So we defined the elementslist ofΘ^T . After changed marks of the elements, we write: , and satisfy:thenΘ^T and X^T are -ordered. Then we can give the minimal degree Newton bases on tower set.Theorem 4 Given a tower set X^T ,Θ^T is defined as upper. Let , suppose ordered, wherethen the minimal degree Newton bases on towerset X^T is the hereafter polynomial set:whereθ_l and p_k satisfyθ_l(p_k) =δ_lk,1≤l≤k≤M.Next, we give the definition of n dimensional tower set, wealso think about 3 dimensions. Suppose the grid subset ,and Cover X^T by 2 sets of planes that are {H₀,...,H_h} and{J₀,...,J_j} which parallel to the XY and XZ planes respec-tively. If the planes set {H₀,...,H_h} have z₀,...,z_h as theircoordinate value of Z axes, and {J₀,...,J_j} have the y₀,...,y_jas Y axes. Under the related suppose, note: Let points set Hh has th distinct values of y- axes, and J_j has r_jdistinct values of z? axes. Define as:Definition 5 Given a grid set , H_h,J_j are the gridson the related plane. If we changed the marks of these planes:{H₀,H₁,···,H_h} so that Hh,0≤h≤h is the 2 dimensionaltower set, the related lower set are: L_y(s₀+1,...,s_th+1),L_z(s'₀+1,...,s'_tj + 1). No lose the general, suppose , and:then the set XT are called the 3 dimensional tower set.Next we will give the definition of point evaluation functionalsset list defining Lagrange interpolation on a tower gridset.Definition 6 Given a tower set ,Θ^T are definedupper, let M = #T , for , if satisfyone of conditions underside: then we called . So we defined thelist of elements in , and satisfythen the setΘ^T and X^T are called lex-ordered.Then we can give the minimal degree Newton bases w.r.t. grlexonthe multivariate dimensional tower set.Theorem 5 Suppose is a tower set,Θ^T is definedupper, let M = #T . SupposeΘ^T = {θ₁,...,θ_M} is ordered, wherethen the minimal degree Newton bases P w.r.t. grlex on towerset X^T is the hereafter polynomial set:where 1≤k≤M,also the minimal degree monomial bases of Lagrange interpola- tion on X^T is:As the corollary of the upper theorem, we can give a quick algo-rithm to solve out the reduced Gr(o|¨)bner bases of the vanish idealof tower set.Algorithm 1 Algorithm to solve the reduced Gr(o|¨)bner basesof the vanish ideal of tower set.Input: X^T = {X₁,X₂,···,X_M}, the tower set.θ₁,θ₂,···,θ_M is valuate functional list w.r.t. lex of pointsX^T ;P := {p₁,p₂,···,p_M} is the Newton bases about the listθ₁,θ₂,···,θ_M which defined the Lagrange interpo-lation problem on X^T ;forWhile B(N) = ? do Output: The reduced Gr(o|¨)bner bases G of the vanish idealof the tower set X^T .Theorem 6 The algorithm 1 are terminated in finite steps, andthe output: G are The reduced Gr(o|¨)bner bases G w.r.t. grlex ofthe vanish ideal of the tower set X^T .