一類廣義Birkhoff插值問題的適定插值基

崔 凱

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

一類廣義Birkhoff插值問題的適定插值基

崔 凱

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

Birkhoff插值在應用密碼學,逼近論以及PDE求解等領域有著重要應用。由于微商插值條件的不連續性,使得該問題比Lagrange和Hermite插值要復雜的多。提出了基于多項式微分條件的廣義Birkhoff 插值格式。探究廣義Birkhoff插值問題的適定插值基,使得對任意給定的型值,在該組基張成的空間中插值時總存在唯一滿足插值條件的多項式。采用代數幾何的方法,通過對多樣性的插值條件分析,證明了當定義插值格式的關聯矩陣滿足較好的性質時,適定的插值基無需繁瑣的計算,可以由微分插值條件直接獲得。最后通過算例驗證了該方法的有效性。

Birkhoff插值; 適定插值基; 關聯矩陣; 正則鏈

0 引 言

繼Newton, Lagrange和Hermite之后,Birkhoff[1]于1906年提出了微商條件不連續的插值問題,即Birkhoff插值。1966年Schoenberg[2]首次給出了經典的一元Birkhoff插值格式,由關聯矩陣,插值結點集和插值空間3部分組成,并提出插值問題的可解性可由關聯矩陣的性質刻畫。Lorentz等[3]于1992年在其專著中將Schoenberg提出的一元Birkhoff插值格式推廣到了單項微分插值條件的多元情形,并且給出了插值格式正則性的若干判定條件。此后的20多年,一方面,一些學者對具有不同特征的插值格式進行研究,得到了關于Birkhoff插值正則性的若干判定結論[4-8];另一方面,一些學者根據給定的插值結點集和插值條件,尋找合適的插值基。Wang等[9]針對插值條件為連通集的情形構造了插值問題的Newton基。Lei基于MB算法[10],提出了計算量較低的B-MB算法[11]求解多元Birkhoff插值問題字典序下的極小單項基。考慮結點集的攝動情形,Cui等修正了SOI算法[12],提出了計算多項式微分條件下的Birkhoff插值問題的穩定單項基算法[13]。2016年,Zheng等[14]研究了單項微分插值條件下的唯一極小單項基問題。

本文將Lorentz的多元Birkhoff插值格式推廣到了多項式微分插值條件的情形,證明了一類具有較好性質的插值問題可以直接由插值條件得到其適定的插值基。

1 廣義Birkhoff插值格式

αi1+αi2+…+αin<αj1+αj2+…+αjn;

αi1+αi2+…+αin=αj1+αj2+…+αjnαi1=αj1,…,αim=αjm,且αi(m+1)<αj(m+1)。

定義3 廣義Birkhoff插值格式包含3個部分:

定義4 給定廣義Birkhoff插值格式(S,Z,E),與之對應的插值問題可以描述為求一組插值基,使得對任意給定的一組實數cij,在該組基張成的空間中都存在唯一的多項式f滿足插值條件:

這樣的插值基稱之為適定的插值基。

2 主要結果

注：乘積序不是單項序,因為并不是任意2個單項都可以在乘積序下比較大小,比如根據定義5,既不能得到x2y3>x3y2,也不能得到x3y2>x2y3,此時稱這2個單項在乘積序下是不可比較大小的。若ti>tj或ti與tj不可比較,則稱ti不小于tj.

定義6 設S是按分次字典序排列的單項序列,稱[S1,S2,…,Sm]為序列S的正則鏈,若滿足

1)Si?S,i=1,…,m;

2) 子序列Si中的單項在乘積序下是不可比較大小的,i=1,…,m;

1) 關聯矩陣的每一列中至多有一個非零元素;

例2 給定廣義Birkhoff插值格式(S,Z,E),S=[1,y,x,y2,xy,x2,y3],Z={(x1,y1),(x2,y2),(x3,y3)}。關聯矩陣

顯然關聯矩陣的每1列至多有1個非零元素,符合定理中的第1個條件。以下檢驗定理中的第2個條件。

1)S1=[1]?S,S2=[xy,y3]?S,S3=[y,x2]?S;

2) 在乘積序下,S2中的單項xy和y3不能比較大小,S3中的單項y和x2也不能比較大小;

3 結 論

本文刻畫了一類具有較好性質的廣義Birkhoff插值問題,與其他計算適定插值基的算法不同,本文證明了該類問題的適定多項式基無需計算,可由給定的插值格式直接獲得。算例表明,定理提供的方法在解決特定的一類廣義Birkhoff插值問題時具有一定的優越性。

[ 1 ]BIRKHOFF G D. General mean value and remainder theorems with applications to differentiation and quadra-ture[J]. Trans Amer Math Soc, 1906,7(1):107-136.

[ 2 ]SCHOENBERG I J. On Hermite-Birkhoff interpolation[J]. J Math Anal Appl, 1966,16:538-543.

[ 3 ]LORENTZ R A. Multivariate Birkhoff interpolation[M]. Berlin: Springer Verlag, 1992:1-192.

[ 4 ]PALACIOS F,RUBIO P. Generalized Pólya condition for Birkhoff interpolation with lacunary polynomials[J]. Appl Math E-Notes, 2003,3:124-129.

[ 5 ]CRAINIC N. Necessary and sufficient conditions for almost regularity of uniform Birkhoff interpolation sche-mes[J]. Acta Univ Apulensis Math Inform, 2003,5:61-66.

[ 6 ]CRAINIC N. UR Birkhoff interpolation with rectangular sets of derivatives[J]. Comment Math Univ Carolin, 2004,45(4):583-590.

[ 7 ]CRAINIC N. UR Birkhoff interpolation schemes: reduction criterias[J]. J Numer Math, 2005,13(3):197-203.

[ 8 ]CRAINIC M, CRAINIC N. Birkhoff interpolation with rectangular sets of nodes and with few derivatives[J]. East J Approx, 2008,14:423-437.

[ 9 ]WANG Xiaoying, ZHANG Shugong, DONG Tian. Newton basis for multivariate Birkhoff interpolation[J]. J Comput Appl Math, 2009,228(1):466-479.

[10]CERLIENCO L, MUREDDU M. From algebraic sets to monomial linear bases by means of Combinatorial algorithms[J]. Discrete Math, 1995,139(1):73-87.

[11]LEI Na, CHAI Junjie, XIA Peng, et al. A fast algorithm for multivariate Birkhoff interpolation problem[J]. J Comput Appl Math, 2011,236(6):1656-1666.

[12]ABBOTT J, FASSINO C, TORRENTE M L. Stable border bases for ideals of points[J]. J Symbolic Comput, 2008,43(12):883-894.

[13]CUI Kai, LEI Na. Stable monomial basis for multivariate Birkhoff interpolation problems[J]. J Comput Appl Math, 2015,277:162-170.

[14]ZHENG Xiaopeng, CHAI Juejie, SHENG Mengci. On the unique minimal monomial basis of Birkhoff interp-olation problem[J]. J Syst Sci Complex, 2016,29(3):825-841.

[15]張樹功,雷娜,劉停戰. 計算機代數基礎[M]. 北京:科學出版社, 2005:1-222.

[16]COX D A,LITTLE J,O’SHEA D. Ideals,varieties,and algorithms[M]. New York: Spriner-Verlag, 1997:1-541.

ProperinterpolationbasisforaclassofgeneralizedBirkhoffinterpolationproblems

CUIKai

(College of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

Birkhoff interpolation has significant applications in the fields of applied cryptography, approximation theory and PDE theory, etc. The noncontinuity of derivative conditions makes Birkhoff interpolation to be more complicated than Lagrange and Hermite interpolation. A generalized Birkhoff interpolation scheme based on polynomial differential conditions is proposed. Proper interpolation basis of the generalized Birkhoff interpolation problem is studied and a unique polynomial which satisfies interpolation conditions always exists in the space spanned by the basis for any given data values. Applying the method of algebraic geometry to analyze various interpolation conditions, we prove that when the interpolation scheme defined by incidence matrix satisfies some good properties, the proper interpolation basis can be directly obtained from differential interpolation conditions, instead of tedious computations. Finally, an example is given to illustrate the effectiveness of the proposed method.

Birkhoff interpolation; proper interpolation basis; incidence matrix; regular chain

2017-06-05。

遼寧省科技廳自然科學基金資助項目(20170540821)。

崔 凱(1986-),男,吉林遼源人,沈陽師范大學講師,博士。

1673-5862(2017)04-0441-04

O241.3

A

10.3969/ j.issn.1673-5862.2017.04.012