崔 凱

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

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

崔 凱

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

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

Birkhoff插值; 適定插值基; 關(guān)聯(lián)矩陣; 正則鏈

0 引 言

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

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

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個(gè)部分:

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

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

2 主要結(jié)果

注：乘積序不是單項(xiàng)序,因?yàn)椴⒉皇侨我?個(gè)單項(xiàng)都可以在乘積序下比較大小,比如根據(jù)定義5,既不能得到x2y3>x3y2,也不能得到x3y2>x2y3,此時(shí)稱這2個(gè)單項(xiàng)在乘積序下是不可比較大小的。若ti>tj或ti與tj不可比較,則稱ti不小于tj.

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

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

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

1) 關(guān)聯(lián)矩陣的每一列中至多有一個(gè)非零元素;

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

顯然關(guān)聯(lián)矩陣的每1列至多有1個(gè)非零元素,符合定理中的第1個(gè)條件。以下檢驗(yàn)定理中的第2個(gè)條件。

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

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

3 結(jié) 論

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

[ 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]張樹功,雷娜,劉停戰(zhàn). 計(jì)算機(jī)代數(shù)基礎(chǔ)[M]. 北京:科學(xué)出版社, 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。

遼寧省科技廳自然科學(xué)基金資助項(xiàng)目(20170540821)。

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

1673-5862(2017)04-0441-04

O241.3

A

10.3969/ j.issn.1673-5862.2017.04.012