Studies On The Discrete Approximation Of Ideal Interpolation Operators

Interpolation by polynomials is a classic and old subject that is commonly used in function approximation. With the development of science and tech-nology, the theory of polynomial interpolation has been widely used in image processing, electronic communication, cybernetics, mechanical engineering and many other application fields. In this thesis, we are only interested in the so-called ideal interpolation, whose space of interpolation conditions contains a finite number of interpolation sites, and the interpolation conditions at each site consist of the evaluation functional at this site and some differential op-erators. Note that the polynomials that induce the corresponding differential operators form a finite dimensional D-invariant linear subspace. In the follow-ing, the linear functional space spanned by interpolation conditions is called the functional space of interpolation conditions. Let F be a field with charac-teristic zero. Let F[x]:= F[x1,...,xd] be the polynomial ring in d variables over F. A projector P on F[x] is called an ideal projector if its kernel is an ideal. Ideal interpolation can be defined by an ideal projector in the following way:the functional space of interpolation conditions is exactly the range of the dual of P, and the interpolation space is the range of P.Lagrange interpolant is a standard example of polynomial interpolants, its corresponding ideal projector is called Lagrange projector. Every univariate ideal projector over complex field can be viewed as a limiting case of Lagrange projectors, and it is still true for some multivariate cases. Thus de Boor define Hermite projector as the pointwise limit of Lagrange projectors, de Boor conjectured that every multivariate ideal projector over complex field is Hermite. However, Shekhtman provided counterexamples for d≥3 afterwards. So one is interested in studying what ideal projectors are Hermite projectors; and if a given projector is Hermite, how to find Lagrange projectors that converge to it. Namely, we will consider the following problem:given an ideal projector, how to find a sequence of Lagrange projectors (if any) converge to it. We call this problem the discrete approximation problem for ideal interpolation operators. For simplicity, we also call it the discrete approximation for ideal interpolation or just the discretization problem. In this thesis, we will discuss this problem with the aid of algebraic geometry and the analyzation of the structure of D-invariant subspaces. The main results are as follows.1. We present a discrete approximation algorithm for a general ideal projector. Since the convergence of an interpolation problem is equal to the convergence of its corresponding interpolation conditions, and the interpola-tion conditions can be described by D-invariant subspaces, it follows that in order to solve the discrete approximation problem, we only need to discrete the differential operators in the D-invariant subspace of each site. We call the latter the discrete approximation problem for D-invariant subspace for simplic-ity. For an ideal interpolant, if every differential operator in every functional space of interpolation conditions can be discretized, then so can the original ideal projector. Thus in the discussion that follows, we only need to consider the discrete approximation problem for one site. Specifically, given an inter-polation site z with its corresponding D-invariant s+1-dimensional subspace Qz(?)F[x], we will consider how to compute s+1 points z0(h),...,z8(h), such that where δz is the evaluation functional at z, q(D):= q(D1,...,Dd) is the dif-ferential operator induced by q, Dj:=(?)/(?)xj is the differentiation with respect to the jth variable, j=1,..., d. We call z0(h),..., zs(h) the discrete points. The algorithm computes each site with its corresponding D-invariant subspace separately, and converts the discretization problem into polynomial system solving. If the obtained nonlinear system has a solution, then we can have dis-crete points as the output. Moreover, we prove that for a given ideal projector, if the algorithm computes discrete points for all sites and their corresponding interpolation conditions, then the given projector is Hermite.2. We solve the discrete approximation problem for the second-degree D-invariant subspace Q2. For an arbitrary polynomial subspace, the polynomials in a given basis can be written in matrix form with respect to some monomial order. Using Gauss-Jordan elimination, we can obtain the reduced row echelon form of this matrix, which gives another basis. We call this new basis the reduced basis. In the discussion that follows, by a basis of some subspace we always mean the reduced basis. First, we analyze the structure of a special second-degree D-invariant subspace Q2:= span{1,p1(1),...,pm1(1),p(2)}, where the superscript indicates the total degree of the polynomial. After a suitable permutation of variables, we can get a general form of all the polynomials of total degree one in the basis of Q2, thus the structure of p(2) can be obtained. Next we study the general case of Q2 similarly. Then we give a set of discrete points for all polynomials of total degree 1 in Q2. Finally, with the discrete points of degree one in hand, a sufficient condition for solving the discrete approximation problem for δzQ2(D) is investigated.3. We solve the discrete approximation problem for the breadth-one D-invariant subspace. We first discuss another equivalent representation of the breadth-one D-invariant subspace. Then we give two sets of discrete points for this special class of D-invariant subspaces with the new representation, which indicates that the corresponding projector is an Hermite projector.4. We discuss the discrete approximation problem for the general bivariate case over complex filed. With the aid of algebraic geometry, Shekhtman proved that all bivariate ideal projectors are Hermite projectors. Based on his theory, we present a constructive algorithm for the bivariate discrete approximation problem under general interpolation conditions on each site. First we propose an algorithm for computing the Grobner bases of the ideal determined by interpolation conditions on a single site, thus the multiplication matrices can be computed. Then we compute the discrete points with the aid of Jordan normal form and univariate rational interpolation. Finally, we give a set of discrete points directly for bivariate breadth-one D-invariant subspace.5. We analyze the structure of a D-invariant polynomial subspace Qn in terms of Cartesian tensors, where Qn C(?){f∈F:deg(f)≤n} and there exist at least one polynomial of total degree n in Qn. Let Q<n(?)Qn denote the subset that contains all polynomials of total degree less than n. Similar to the case when n= 2, we know that all n-th degree polynomials share the same form if Q<n is given, thus we can assume that there is only one polynomial of total degree one in Qn. We first analyze the structure of p(3) in Q3= span{1,p1(1),...,Pm1(1),P1(2),...,Pm2(2),p(3)}, where the polynomials in the basis are all homogeneous. Since the space of symmetric tensors of order n on Rd is naturally isomorphic to the space of homogeneous polynomials of total degree n in d variables, it follows that we can use a symmetric tensor to represent a homogeneous polynomial. Namely, an arbitrary homogeneous polynomial p(3) of degree 3 can be determined by a third order symmetric Cartesian tensor B(3)∈Rd(?)Rd(?)Rd. We first prove that B(3) can be written as an inner product of the tensor constructed by the so-called "relational matrices" and the coefficient matrix of all linear polynomials in a basis of Q3. Then we discuss the degrees of freedom of B(6).Finally, we discuss the correspondence between the n-th degree polynomial and all linear polynomials in Qn, n> 3, in the same way.