高二竞赛讲义多项式的插值与差分

第3讲 多项式的插值与差分

一、知识点金

班级 姓名

1．拉格朗日插值公式：存在唯一的一个次数不超过n1的多项式f(x)满足

f(xi)yi,i1,2,,n（f(x)的图象经过n个不同点(xi,yi)）；并且f(x)可表示为

(xx2)(xx3)(xxn)(xx1)(xx3)(xxn)f(x)f(x1)f(x2)

(x1x2)(x1x3)(x1xn)(x2x1)(x2x3)(x2xn)(xx1)(xxn2)(xxn)(xx1)(xxn2)(xxn1)f(xn1)f(xn)

(xn1x1)(xn1xn2)(xn1xn)(xnx1)(xnxn2)(xnxn1)2．对于函数f(x)及固定的h0，f(xh)f(x)称为f(x)的步长为h的一阶差分，记

作1hf(x)。

11 hf(xh)hf(x)f(x2h)2f(xh)f(x)，称为f(x)的步长为h的二阶差

分。记作hf(x)hf(xh)hf(x)。

n1n1一般地，f(x)的步长为h的n阶差分定义为hf(x)h(hf(x))。

2113．对于函数f(x)，有f(x)nh(1)i0nniiCnf(xih)

数学归纳法证明：n1时结论显然成立。假设f(x)则n1hnniinnnh(1)i0nniiCnf(xih)，

if(x)(1)Cf(xhih)(1)niCnf(xih)

i0i0(1)i1n1ni1Ci1nf(xih)(1)Cf(xih)（i1代替上式中i的位置）

niini0i0nn

i1i1n1(1)ni1(CnCn)f(xih) （注意：定义Cn0，Cn0） i0i(1)ni1Cn1f(xih) i0nhn1n1因此f(x)(1)i0nniiCnf(xih)对一切正整数n成立。

mm1mn次多项式；4．设f(x)amxam1xa1xa0，当nm时，nhf(x)是一个

而对于nm，nhf(x)恒为零。

1mm证明：由定义可知，hf(x)f(xh)f(x)[am(xh)a0][amxa0]

mhamxm1低次项，这是一个m1次多项式，首项为mhamxm1，依此类推，

1mnmf(x)m!hm1amx常数项，mhhf(x)m!ham，从而当nm时，hf(x)0。 5．综合第3、4条，取步长h1，可得出

n若mn,0,nii（1）设f(x)是m次多项式，首项系数为am，则(1)Cnf(xi)

m!a,若mn,i0mm（2）特别地，取f(x)x，并在上面等式中取x0，得欧拉恒等式

若mn,0, (1)Cini0(1)n!,若mn,

6．整值多项式：如果当x取整数时，复系数多项式f(x)为整数，则称f(x)为整值多项式。

x(x1)(xk1)k整系数多项式当然都是整值多项式。但组合数Cx是非整系数的整值

k!niinm多项式。

7．n次复系数多项式f(x)为整值多项式的充分必要条件是，它可表示成

nn11 anCxan1Cxa1Cxa0，其中ai(i0,1,2,,n)均为整数，且an0

n证明：充分条件是显然的。现证明必要性。以Cx除f(x)，商必为常数，设为an，则 n1f(x)anCnxf1(x)，f1(x)或者为零，或者次数小于n；在用n1次多项式Cx除f1(x)，nn11如此进行，便得到f(x)anCxan1Cxa1Cxa0，这种表示显然是惟一的。

二、例题分析

例1．设n次多项式f(x)满足f(k)1(k0,1,,n)。求f(n1)。 kCn1例1．法一：由多项式插值公式得，f(x)nf(k)k0nik0inxi，对于mn，有 kif(m)f(k)(1)k0nkm(m1)(mn)nknk(1)nkf(k)CmCmk1

(mk)k!(nk)!k0所以f(n1)0,若n为奇数，nk (1)k01，若n为偶数n法二：因为n次多项式f(x)的n1阶差分为零，所以

(1)i0n1n1iiCn1f(xi)0

n1n1iiCn1f(i)0 令x0，并以f(i)i(i0,1,,n)代人，得f(n1)(1)Cn1i0所以f(n1)

0,若n为奇数，ni (1)i01，若n为偶数n例2．设n次多项式f(x)满足f(k)例1．法一由多项式插值公式得。略

1(k1,2,,n1)。求f(n2)。 kn1i0

法二：因为n次多项式f(x)的n1阶差分为零，所以

(1)n1iiCn1f(xi)0

n11n1iiCn10 令x1，并以f(i)(i0,1,,n)代人，得f(n2)(1)1iii00,n为奇数，11i1n1n1 f(n2)(1)niCn[(11)(1)1]22n2n2，n为偶数i0n2n法三：对于本题还有更好的做法，考虑n1次多项式g(x)xf(x)1。有已知条件，g(x)有n1个不同的零点x1,2,,n1，又g(0)1， 于是g(x)(x1)(x2)(xn1)1g(n2)，因此，进而

(1)n(n1)!(1)n0,n为奇数，1(1)n f(n2)2n2，n为偶数n2k例3．设f(x)是一个n次多项式，满足f(k)2(k1,2,,n1)，求f(n3)的值。

例3．因为n次多项式f(x)的n1阶差分为零，所以取x1，f(n2)n1i0(1)i0n1n1iiCn1f(xi)0 ①

(1)i0nn1iCin12i1ii1n20，f(n2)(1)n1iCn220 1i0n1iin2f(n2)2(1)n1iCn0，f(n2)2(21)n12n20， 122所以f(n2)2n22

nn1ii2f(n2)(1)n1iCn0 12i0n1再用 ①取x2，f(n3)Cf(n3)Cf(n3)Cnn1ii2nn2f(n2)(1)n1iCn2n3Cn0 1212i0iin3nn2f(n2)4(1)n1iCnCn0 12212i0n1n1nn1nn1nn2f(n3)Cn2n3Cn0 1f(n2)4(12)12所以f(n3)22n6

例4．设x1,x2,,xn1是任意n1个互不相同的整数。则任意n次多项式

xna1xn1an在点x1,x2,,xn1处所取得的n1个值中，至少有一个的绝对值n3n! n2(xx)例4．记所说的多项式为f(x)，由多项式插值公式得，f(x)f(i)

(xx)n1i1kkiikki由于f(x)的首项系数为1，故由上式得出

f(i)i1n1记M是f(i)(i1,2,,n)的最大值，则有Mi1kin111

(xx)ik1ik1

(xx)ki但x1,x2,,xn1是任意n1个互不相同的整数，可设x1x2xn1，我们有

(xx)(xx)(xxiki1ikii1)(xixi1)(xixn1)

(i1)(i2)12(n1i)(i1)!(n1i)!于是Mn! i1Cn1i1n11k(xx)iki1n!n! i101nnn1CnCnCnCn2i1n!例5．设k3是奇数。证明：存在一个次数为k的非整系数的整值多项式f(x)，具有下面

的性质：

（1）f(0)0,f(1)1；

（2）有无穷多个正整数n，使得对s21，方程 nf(x1)f(x2)f(xs)

没有整数解x1,x2,,xs。

例5．先证明一个引理：存在一个首项系数为正的k次整值多项式f(x)，系数不全是整数，

k0(mod2),若x为偶数，满足f(0)0,f(1)1，以及f(x) k1(mod2),若x为奇数。引理证明：满足f(0)0,f(1)1的首项系数为正的k次整值多项式f(x)可以表示为：

1f(x)akCxkak1Cxk1a1Cx，其中ak0，a11 iii1i2因为Cx2Cx2CxCx，所以

kf(x2)f(x)2akCk1xi1(2aiai1)Cx i1k1k2ak2,现在我们去ak,ak1,,a2满足

2aiai10,1ik1i1kk1则易解得（注意a11）ai(2)，1ik，从而f(x2)f(x)2Cx

由此即知，对每一个整数x，有f(x2)f(x)0(mod2) 由于f(0)00(mod2)，所以x为偶数时，f(x)0(mod2)， 由于f(1)11(mod2)，所以x为奇数时，f(x)1(mod2)，

k0(mod2),若x为偶数，即有f(x) k1(mod2),若x为奇数。kkkkk这时多项式f(x)2k1C2kxk2Ck1x2CC2x1x，

2k1x的系数是在k3时为非整

k!k数。满足引理中的要求。

回到原问题：取正整数n1(mod2)，假设有整数x1,x2,,xs，使得

knf(x1)f(x2)f(xs)，则更有f(x1)f(x2)f(xs)1(mod2k)

kk但由引理可知，上式左边每一项模2是0或1，因此在s21时，左边模2决不可能为

k2k1，矛盾！从而本题结论成立。

三、同步检测

1．求一个次数小于4的多项式f(x)，满足f(1)2i2,f(0)1,f(1)0,f(2)2i1， 这里i1。

1．利用拉格朗日插值公式得f(x)ix(1i)x1

2141325211xxxx1是整值多项式。 241224121413252114322．设xxxx1aCxbCxcCxdC1xe，取x0,1,2,3,4，可

241224122．证明多项式

求得ab1,c1,d0,e1，因此所说的多项式是整值多项式。

3．设f(x)是n次多项式，在连续n1个整数处取值为整数，则f(x)是整值多项式。 3．对任意整数a，f(x)是整值多项式，等价于g(x)f(xa)是整值多项式。因此可设

nn11连续n1个整数是0,1,2,,n。先将f(x)表示为f(x)anCxan1Cxa1Cxa0，

再由f(k)(k0,1,2,,n)是整数，可推出诸系数都是整数。 4．设f(x)是2n次多项式，f(0)f(2)f(2n)0，

f(1)f(3)f(2n1)2，且f(2n1)30，求n的值。

2n14．因为2n次多项式f(x)的2n1阶差分为零，所以

2n1(1)i02n1i2n1iiC2n1f(xi)0

取x0，并以f(i)(i0,1,,2n1)代人，得

2n(1)i0iC2n1f(i)0

122n1if(2n1)2(CCCf(2n1)(1)2n1iC2f(i)0，2n12n12n1)0 n1i0所以302(2

2n1)0，解得n2

5．设f(x)为一个n次多项式，满足f(k)k(k0,1,,n)，求f(n1)的值。 k15．考虑g(x)(x1)f(x)x，它在x0,1,2,,n处的值是0，又g(1)1。

(1)n1(1)n1x(x1)(xn)，所以g(n1)x(x1)(xn)(1)n1 故g(x)(n1)!(n1)!n为奇数，1,(1)n1(n1) f(n1)nn2，n为偶数.n2