The Study Of Several Problems On Multivariate Birkhoff Interpolation

In 1906, Birkhoff introduced a general interpolation scheme, in which the orders of the derivatives at some nodes are noncontinuous. Given its noncontinuity, the problem becomes more complicated and is then called the "Birkhoff interpolation". There are many applications for Birkhoff interpolation problem such as solving a boundary value problem, construction of the finite element, and solving a secret image sharing scheme. The theory of Birkhoff interpolation is far from systematic and complete as the well known Lagrange interpolation and Hermite interpolation. In fact there are many univari-ate problems unsolved, people know less for multivariate Birkhoff interpolation problem. Though many researchers have studied this area deeply, the problems they studied are mostly limited to the case that the nodes distribute specially or the interpolation condi-tions are uniform. In 1992, Lorentz gave a multivariate Birkhoff interpolation scheme, of which every interpolation condition is defined by a monomial differential operator. In this paper, we study the generalized multivariate Birkhoff interpolation problem, i.e., every interpolation condition is defined by a polynomial differential operator and we discuss the problem from three points:1 Given an interpolation space and interpolation conditions on the nodes, deduce whether the interpolation scheme is regular or singular;2 Given a node set and interpolation conditions on the nodes, finding a proper interpo-lation basis;3 Given a node set and interpolation conditions on the nodes, finding a stable monomial basis when considering the pertubation of nodes.An outline of this paper is as follows:In chapter 2 we propose a generalized multivariate Birkhoff interpolation scheme, in which every interpolation condition is defined by a polynomial differential operator. Deducing the regularity of an interpolation scheme is a key problem that many researchers focus on. We will give two results about the regularity of an interpolation scheme just from the given incidence matrix:a necessary condition for almost regularity and a sufficient condition for regularity.Definition 1. A multivariate Birkhoff interpolation scheme (Z,E,PS) consists of three-components:(1) A set of notes Z,(2) An interpolation space Ps, where S S={t1,…,ti} is a monomial sequence ordered by the graded lex order, tk= x1αk1x2αk2…xnαkn ,1≤k≤l.(3) An incidence matrix E, which consists of m sub-matrices, where Ei= (ejh(i)), does not contain zero row,1≤i≤m, j= 1,…,ji,h= 1,…,1, ejh(i)∈R.Problem 1. For any given data values Cij∈R, the problem associated to the interpolation scheme (Z, E, PS) is to find a polynomial f ∈ PS satisfying the interpolation conditions:D= [D1,…,Dl] is the differential operator sequence associated to the monomial sequence S, where Every row of matrix Ei corresponds to an inter-polation condition on node zi. Lji is an interpolation condition functional decided by the j - th row of Ei and the node zi.Denote by |E| the number of row in the matrix E, i.e., the number of interpolation conditions. If |E|= dimPs, then we say the interpolation Problem 1 is normal. In this paper we always assume interpolation problems are normal.For any given data values, whether the Problem 1 has a unique solution depends on the choices of sets of nodes. If there exists a unique solution for Problem 1 for all choices of sets of nodes, we say the interpolation scheme (Z, E, PS) is regular; If there exists a unique solution for Problem 1 for almost all choices of sets of nodes (in the Lebesgue measure of Rmn), we say the interpolation scheme (Z, E, Ps) is almost regular; If there exists no a solution for Problem 1 for all choices of sets of nodes, we say the interpolation scheme (Z,E,Ps) is singular.The key problem we discuss in this chapter is to obtain some messages about the regularity of a given interpolation scheme just from the property of incidence matrix and we obtain two mam results:Theorem 1. Let S= [t1,…,tl] be a monomial sequence ordered by the graded lex order (?)griex and E be an incidence matrix. If the interpolation scheme (Z, E, PS) is almost regular, then E satisfies the generalized Poly a condition.Theorem 2.If the incidence matrix E can be reduced to an upper triangular matrix E by performing the permitted elementary row operations, of which the diagonal elements are nonzero constants, then the interpolation scheme (Z, E, Ps) is regular.In chapter 3, we discuss the proper problem of a generalized Birkhoff interpolation problem and two special interpolation problems.Problem 2. Let S= [t1,…,ti] be a monomial sequence ordered by the graded lex order. D= [D1,…,Di] is the differential operator sequence associated to the monomial is an incidence matrix, where Ei= (ejh (i)), does not contain zero row,1≤i≤m, j= 1,…,ji, h= 1, …, l, ejh(i) ∈ K. Denote by Lji an interpolation condition functional decided by a row of matrix Ei. The problem is to find a basis such that for any given data values cij ∈ R,1≤ i≤ m, j= 1,…, ji there exists a unique polynomial f in the space F spanned by the basis, satisfying the following interpolation conditions:The basis satisfying the above properties is called proper interpolation basis and accordingly the interpolation space F is called proper interpolation space.Interpolation functionals decided by the incidence matrix are not always linearly independent. So we discuss the condition for the existence of a solution for the given interpolation problem and generalize the BM algorithm to compute a minimal interpola-tion monomial basis with respect to a given graded order.Then we define a regular chain of the given monomial sequence and prove that when an interpolation scheme satisfies some good properties, the proper interpolation basis can be directly obtained from the given interpolation scheme instead of tedious computations.Theorem 3. Given an interpolation problem (Z, E, S), where S= [t1,…,ti) is a mono-mial sequence ordered by the graded lex order (?)griex.Given a set of nodes Z={zi}i=1 m and i.e., Ei= (e1(i),e2(i),…el(i)) eh(i)∈R,h= 1,…, l. The nonzero elements of every row in the matrix E correspond to a monomial sequence, denoted by Si, i= 1, …, m. Poly- nomial set {fi,=∑eh(i)th^}i=1 m is a proper interpolation basis if the following conditions hold,(1) there is at most one nonzero element in every column of the matrix E;(2) [Si, S2, …, Sm] is a regular chain of the sequence S.In the end of chapter 3, we study the Birkhoff interpolation problem of which the interpolation conditions are uniform and proposee a sufficient and necessary condition for a proper interpolation space.Theorem 4. Given the uniform Birkhoff interpolation problem,F=SpanR{g1, …, gm} is the uniform differentia subspace of F=SpanR{f1,…,fm} ∈R[X], where gi=D(fi), then F is a proper interpolation space if and only if the polynomials gi,g2,…,gm are linearly independent and the nodes Z={Zi}i=1 m do not lie on any algebraic manifold of F.In chapter 4, considering the perturbation of nodes, we propose the concept of stable monomial basis for multivariate Birkhoff interpolation problem. In practice, given that the measured values are inexact, the monomial basis obtained by the minimal monomi-al basis is unstable. Therefore, slight perturbations of the nodes may cause structural changes in the interpolation polynomial. Therefore, finding the stable interpolation basis for the given limited precision nodes and data values is necessary. Abbot et al. presented the Stable Order Ideal (SOI) algorithm to determine the stable border basis for the van-ishing ideal of limited precision points. In this chapter we develop a numerical algorithm to solve the Birkhoff interpolation problem on basis of the SOI algorithm.