当前位置:首页 >> 数学 >> 高二竞赛讲义 多项式的插值与差分3

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


高二数学竞赛班二试讲义 第 3 讲 多项式的插值与差分
班级 姓名

一、知识点金
1.拉格朗日插值公式:存在唯一的一个次数不超过 n ? 1 的多项式 f ( x ) 满足
f ( x i ) ? y i , i ? 1, 2, ? ? ?, n ( f ( x ) 的图象经过 n 个不同点 ( x i , y i ) ) ;并

且 f ( x ) 可表示为
f ( x ) ? f ( x1 ) ? f ( x n ?1 ) ( x ? x 2 )( x ? x 3 ) ? ? ? ( x ? x n ) ( x1 ? x 2 )( x1 ? x 3 ) ? ? ? ( x1 ? x n ) ( x ? x1 ) ? ? ? ( x ? x n ? 2 )( x ? x n ) ( x n ? 1 ? x1 ) ? ? ? ( x n ? 1 ? x n ? 2 )( x n ? 1 ? x n ) ? f ( x2 ) ( x ? x1 )( x ? x 3 ) ? ? ? ( x ? x n ) ( x 2 ? x1 )( x 2 ? x 3 ) ? ? ? ( x 2 ? x n ) ? ???

? f ( xn )

( x ? x1 ) ? ? ? ( x ? x n ? 2 )( x ? x n ? 1 ) ( x n ? x1 ) ? ? ? ( x n ? x n ? 2 )( x n ? x n ? 1 )

2.对于函数 f ( x ) 及固定的 h ? 0 , f ( x ? h ) ? f ( x ) 称为 f ( x ) 的步长为 h 的一阶差分,记 作 ? h f (x) 。
1

? h f ( x ? h ) ? ? h f ( x ) ? f ( x ? 2 h ) ? 2 f ( x ? h ) ? f ( x ) ,称为 f ( x ) 的步长为 h 的二阶差
1 1

分。记作 ? h f ( x ) ? ? h f ( x ? h ) ? ? h f ( x ) 。
2 1 1

一般地, f ( x ) 的步长为 h 的 n 阶差分定义为 ? h f ( x ) ? ? h ( ? h f ( x )) 。
n 1

n ?1

3.对于函数 f ( x ) ,有 ? h f ( x ) ?
n

? ( ? 1)
i?0

n

n?i

C n f ( x ? ih )
i n

数学归纳法证明: n ? 1 时结论显然成立。假设 ? h f ( x ) ? 则 ? h f (x) ?
?
n ?1

? ( ? 1)
i?0

n

n?i

C n f ( x ? ih ) ,
i

? ( ? 1)
i?0

n

n?i

C n f ( x ? h ? ih ) ?
i

? ( ? 1)
i?0

n

n?i

C n f ( x ? ih )
i
n

?

n ?1

( ? 1)

n ? i ?1

Cn

i ?1

f ( x ? ih ) ?

i ?1

?

n

( ? 1)

n?i

i?0

C n f ( x ? ih ) ( i ? 1 代替上式 ?
i

中 i 的位置)

i?0

? ?

? ( ? 1)
i?0

n ?1

n ? i ?1

(C n
i

i ?1

? C n ) f ( x ? ih )
i

(注意:定义 C n ? 0 , C n

?1

n ?1

?0)

? ( ? 1)
i?0 n

n ?1

n ? i ?1

C n ? 1 f ( x ? ih )

因此 ? h f ( x ) ?

? ( ? 1)
i?0
m
n

n

n?i

C n f ( x ? ih ) 对一切正整数 n 成立。
i
m ?1

4. f ( x ) ? a m x ? a m ?1 x 设
1

? ? ? ? ? a1 x ? a 0 , n ? m 时,? h f ( x ) 是一个 m ? n 次多项式; 当
n

而对于 n ? m , ? h f ( x ) 恒为零。 证明:由定义可知, ? h f ( x ) ? f ( x ? h ) ? f ( x ) ? [ a m ( x ? h ) ? ? ? ? ? a 0 ] ? [ a m x ? ? ? ? ? a 0 ]
m m

? m ham x
?h
m ?1

m ?1

? 低 次 项 , 这 是 一 个 m ? 1 次 多 项 式 , 首 项 为 m ham x
m ?1 m m

m ?1

,依此类推,
n

f ( x) ? m !h

a m x ? 常数项, ? h f ( x ) ? m ! h a m ,从而当 n ? m 时, ? h f ( x ) ? 0 。
n

5.综合第 3、4 条,取步长 h ? 1 ,可得出 (1)设 f ( x ) 是 m 次多项式,首项系数为 a m ,则 ? ( ? 1)
i?0
m

n ?i

若 m ? n, ? 0, i C n f ( x ? i) ? ? ? m ! a m , 若 m ? n,

(2)特别地,取 f ( x ) ? x ,并在上面等式中取 x ? 0 ,得欧拉恒等式
1

? ( ? 1) C
i i?0

n

i n

?i

m

若 m ? n, ? 0, ? ? n ? ( ? 1) n !, 若 m ? n ,

6.整值多项式:如果当 x 取整数时,复系数多项式 f ( x ) 为整数,则称 f ( x ) 为整值多项式。 整系数多项式当然都是整值多项式。 但组合数 C x ?
k

x ( x ? 1) ? ? ? ( x ? k ? 1) k!

是非整系数的整值

多项式。 7. n 次复系数多项式 f ( x ) 为整值多项式的充分必要条件是,它可表示成
a n C x ? a n ? 1C x
n n ?1

? ? ? ? ? a1C x ? a 0 ,其中 a i ( i ? 0,1, 2, ? ? ?, n ) 均为整数,且 a n ? 0
1
n n ?1

证明:充分条件是显然的。现证明必要性。以 C x 除 f ( x ) ,商必为常数,设为 a n ,则
f ( x ) ? a n C n ? f 1 ( x ) , f 1 ( x ) 或者为零, 或者次数小于 n ; 在用 n ? 1 次多项式 C x
x

除 f1 ( x ) ,

如此进行,便得到 f ( x ) ? a n C x ? a n ?1C x
n

n ?1

? ? ? ? ? a1C x ? a 0 ,这种表示显然是惟一的。
1

二、例题分析
例 1.设 n 次多项式 f ( x ) 满足 f ( k ) ?
1 C n ?1
k

( k ? 0,1, ? ? ?, n ) 。求 f ( n ? 1) 。
n

例 1.法一:由多项式插值公式得, f ( x ) ?
n

?
?

k ?0

f (k ) ?
n

x?i k ?i

,对于 m ? n ,有

i? k 0?i? n

f (m ) ?

?

f ( k )( ? 1)
n

n?k

m ( m ? 1) ? ? ? ( m ? n ) ( m ? k ) k !( n ? k ) !

k ?0

? ( ? 1)
k ?0

n?k

f ( k ) C m C m ? k ?1

k

n?k

所以 f ( n ? 1) ?

? ( ? 1)
k ?0

n?k

? 0, 若 n 为 奇 数 , ? ? ?1 , 若 n 为 偶 数
n ?1 n ?1? i

法二:因为 n 次多项式 f ( x ) 的 n ? 1 阶差分为零,所以 ? ( ? 1)
i?0

C n ?1 f ( x ? i ) ? 0
i

令 x ? 0 ,并以 f ( i ) ? 所以 f ( n ? 1) ?

1 C n ?1
i

( i ? 0,1, ? ? ?, n ) 代人,得 f ( n ? 1) ?
? 0, 若 n 为 奇 数 , ? ? ?1 , 若 n 为 偶 数

? ( ? 1)
i?0

n

n ?1? i

C n ?1 f ( i ) ? 0
i

? ( ? 1)
i?0

n

n?i

例 2.设 n 次多项式 f ( x ) 满足 f ( k ) ? 例 1.法一由多项式插值公式得。略

1 k

( k ? 1, 2, ? ? ?, n ? 1) 。求 f ( n ? 2) 。

法二:因为 n 次多项式 f ( x ) 的 n ? 1 阶差分为零,所以 ? ( ? 1)
i?0

n ?1

n ?1? i

C n ?1 f ( x ? i ) ? 0
i

令 x ? 1 ,并以 f ( i ) ?
n

1 i

( i ? 0,1, ? ? ?, n ) 代人,得 f ( n ? 2 ) ?

? ( ? 1)
i?0
n ?1

n

n ?1? i

C n ?1 ?
i

1 1? i

?0

f (n ? 2) ?

?

( ? 1)

n?i

C n?2 ?

i ?1

1 n?2

?

1 n?2

[( ? 1 ? 1)

n ?1

? ( ? 1)

i?0

? 0, n 为 奇 数 , ? ? 1] ? ? 2 , n为 偶 数 ? ?n ? 2

2

法三:对于本题还有更好的做法,考虑 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) ( ? 1) ( n ? 1) !
n

,因此 g ( n ? 2 ) ?

1 ( ? 1)
n

,进而

f (n ? 2) ?

1 ? ( ? 1) n?2

n

? 0, n 为 奇 数 , ? ? ? 2 , n为 偶 数 ? ?n ? 2
k

例 3.设 f ( x ) 是一个 n 次多项式,满足 f ( k ) ? 2 ( k ? 1, 2, ? ? ?, n ? 1) ,求 f ( n ? 3) 的值。 例 3.因为 n 次多项式 f ( x ) 的 n ? 1 阶差分为零,所以 ? ( ? 1)
i?0 n ?1 n ?1? i

C n ?1 f ( x ? i ) ? 0
i


n?2

取 x ? 1 , f (n ? 2) ?
f ( n ? 2 ) ? 2 ? ( ? 1)
i?0 n ?1

?

n

( ? 1)
i

n ?1? i

C n ?1 2
n?2

i

i ?1

? 0 , f (n ? 2) ?

i?0

? ( ? 1)
i?0

n ?1

n ?1? i

C n ?1 2

i

i ?1

?2

?0

n ?1? i

C n ?1 2 ? 2
i

? 0 , f ( n ? 2) ? 2(2 ? 1)

n ?1

?2

n?2

?0,

所以 f ( n ? 2 ) ? 2

n?2

?2
n

再用 ①取 x ? 2 , f ( n ? 3) ? C n ? 1 f ( n ? 2 ) ?
f ( n ? 3) ? C n ? 1 f ( n ? 2 ) ?
n n

? ( ? 1)
i?0

n ?1

n ?1? i

C n ?1 2
n

i

i? 2

?0

? ( ? 1)
i?0 n ?1 i?0

n ?1

n ?1? i

C n ?1 2
i

i

i? 2

?2

n?3

? C n ?1 2 ? C n ?1 2
n
n?2

n?2

?0 ?0

f ( n ? 3) ? C n ? 1 f ( n ? 2 ) ? 4 ? ( ? 1)
n

n ?1? i

C n ?1 2 ? 2
i
n?3

n?3

n?2

f ( n ? 3) ? C n ? 1 f ( n ? 2 ) ? 4 ( ? 1 ? 2 )

n ?1

?2

? C n ?1 2
n

?0

所以 f ( n ? 3) ? 2

n?3

? 2n ? 6

例 4.设 x1 , x 2 , ? ? ?, x n ? 1 是任意 n ? 1 个互不相同的整数。则任意 n 次多项式
x ? a1 x
n n ?1

? ? ? ? ? a n 在点 x1 , x 2 , ? ? ?, x n ? 1 处所取得的 n ? 1 个值中,至少有一个的绝对值 ?
n ?1

n! 2
n

例 4.记所说的多项式为 f ( x ) ,由多项式插值公式得, f ( x ) ?
n ?1

?
?1

? (x ? x
f (i )
k ?i

k

)

i ?1

? (x
k ?i

i

? xk )

由于 f ( x ) 的首项系数为 1,故由上式得出 ? f ( i )
i ?1

1

?

( xi ? x k )

k ?i

记 M 是 f ( i ) ( i ? 1, 2, ? ? ?, n ) 的最大值,则有 M ? ?

n ?1

1

?1 ? xk )

i ?1

? (x
k ?i

i

但 x1 , x 2 , ? ? ?, x n ? 1 是任意 n ? 1 个互不相同的整数,可设 x1 ? x 2 ? ? ? ? ? x n ? 1 ,我们有

? (x
k ?i

i

? x k ) ? ( x i ? x1 ) ? ? ? ( x i ? x i ? 1 )( x i ? x i ? 1 ) ? ? ? ( x i ? x n ? 1 )

3

? ( i ? 1)( i ? 2 ) ? ? ? 1 ? 2 ? ? ? ( n ? 1 ? i ) ? ( i ? 1) !( n ? 1 ? i ) ! ?

n! Cn
i ?1

于是 M ?

1

?

n ?1

1

?

1

i ?1

?
k ?i

?

n ?1

Cn

i ?1

?

n! Cn ? Cn ? ??? ? Cn
0 1 n

?

n! 2
n

( xi ? x k )

i ?1

n!

例 5.设 k ? 3 是奇数。证明:存在一个次数为 k 的非整系数的整值多项式 f ( x ) ,具有下面 的性质: (1) f (0 ) ? 0, f (1) ? 1 ; (2)有无穷多个正整数 n ,使得对 s ? 2 ? 1 ,方程
k

n ? f ( x1 ) ? f ( x 2 ) ? ? ? ? ? f ( x s )

没有整数解 x1 , x 2 , ? ? ?, x s 。 例 5.先证明一个引理:存在一个首项系数为正的 k 次整值多项式 f ( x ) ,系数不全是整数,
? 0 (m o d 2 k ), 若 x 为 偶 数 , ? 满足 f (0 ) ? 0, f (1) ? 1 ,以及 f ( x ) ? ? k ?1(m o d 2 ), 若 x 为 奇 数 。 ?

引理证明:满足 f (0 ) ? 0, f (1) ? 1 的首项系数为正的 k 次整值多项式 f ( x ) 可以表示为:
f ( x ) ? a k C x ? a k ? 1C x
k i i k ?1

? ? ? ? ? a1C x ,其中 a k ? 0 , a1 ? 1
1 i?2

因为 C x ? 2 ? C x ? 2 C x ? C x ,所以
f ( x ? 2) ? f ( x) ? 2akC x
k ?1

i ?1

?

? (2a
i ?1

k ?1

i

? a i ? 1 )C x

i ?1

? 2ak ? 2 k , ? 现在我们去 a k , a k ?1 , ? ? ?, a 2 满足 ? ? 2 a i ? a i ? 1 ? 0,1 ? i ? k ? 1 ?

则易解得(注意 a1 ? 1 ) a i ? ( ? 2)
k

i ?1

, 1 ? i ? k ,从而 f ( x ? 2) ? f ( x ) ? 2 C x
k

k ?1

由此即知,对每一个整数 x ,有 f ( x ? 2) ? f ( x ) ? 0(m od 2 )
k

由于 f (0) ? 0 ? 0(m od 2 ) ,所以 x 为偶数时, f ( x ) ? 0 (m o d 2 ) ,
k

由于 f (1) ? 1 ? 1(m o d 2 ) ,所以 x 为奇数时, f ( x ) ? 1(m o d 2 ) ,
k k

? 0 (m o d 2 k ), 若 x 为 偶 数 , ? 即有 f ( x ) ? ? k ?1(m o d 2 ), 若 x 为 奇 数 。 ?

这时多项式 f ( x ) ? 2

k ?1

Cx ? 2
k

k ?2

Cx

k ?1

? ? ? ? ? 2 C x ? C x , x 的系数是
2 1
k

2

k ?1

在 k ? 3 时为非整

k!

数。满足引理中的要求。 回到原问题:取正整数 n ? ? 1(m o d 2 ) ,假设有整数 x1 , x 2 , ? ? ?, x s ,使得
k

n ? f ( x1 ) ? f ( x 2 ) ? ? ? ? ? f ( x s ) ,则更有 f ( x1 ) ? f ( x 2 ) ? ? ? ? ? f ( x s ) ? ? 1(m o d 2 )
k

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

k

2 ? 1 ,矛盾!从而本题结论成立。
k

三、同步检测
1. 求一个次数小于 4 的多项式 f ( x ) , 满足 f ( ? 1) ? 2 i ? 2, f (0) ? 1, f (1) ? 0, f (2) ? 2 i ? 1 , 这里 i ?
?1 。
4

1.利用拉格朗日插值公式得 f ( x ) ? ix ? (1 ? i ) x ? 1
2

x ? 1 是整值多项式。 24 12 24 12 1 4 1 3 25 2 11 4 3 2 1 x ? x ? x ? x ? 1 ? a C x ? b C x ? cC x ? d C x ? e ,取 x ? 0,1,2,3,4 2.设 24 12 24 12

2.证明多项式

1

x ?
4

1

x ?
3

25

x ?
2

11

,可

求得 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 ) 是整值多项式。因此可设 连续 n ? 1 个整数是 0,1, 2, ? ? ?, n 。 先将 f ( x ) 表示为 f ( x ) ? a n C x ? a n ?1C x
n n ?1

? ? ? ? ? a1C x ? a 0 ,
1

再由 f ( k )( k ? 0,1, 2, ? ? ?, n ) 是整数,可推出诸系数都是整数。 4.设 f ( x ) 是 2 n 次多项式, f (0) ? f (2) ? ? ? ? ? f (2 n ) ? 0 ,
f ( 1 )? f ( 3?) ? ? ? ?f (n2 ? 1 )? 2 f (2 n ? 1) ? ? 30 ,求 n 的值。 ,且
2 n ?1 2 n ?1? i

4.因为 2 n 次多项式 f ( x ) 的 2 n ? 1 阶差分为零,所以 ? ( ? 1)
i?0

C 2 n ?1 f ( x ? i ) ? 0
i

取 x ? 0 ,并以 f ( i )( i ? 0,1, ? ? ?, 2 n ? 1) 代人,得 ? ( ? 1)
i?0

2 n ?1

2 n ?1? i

C 2 n ?1 f ( i ) ? 0
i
2 2 n ?1

f ( 2 n ? 1) ?

? ( ? 1)
i?0

2n

2 n ?1? i

C 2 n ? 1 f ( i ) ? 0 , f (2 n ? 1) ? 2 ( C 2 n ? 1 ? C 2 n ? 1 ? ? ? ? ? C 2 n ? 1 ) ? 0
i
1

所以 ? 3 0 ? 2 (2

2n

? 1) ? 0 ,解得 n ? 2
k k ?1

5.设 f ( x ) 为一个 n 次多项式,满足 f ( k ) ?

( k ? 0,1, ? ? ?, n ) ,求 f ( n ? 1) 的值。

5.考虑 g ( x ) ? ( x ? 1) f ( x ) ? x ,它在 x ? 0,1, 2, ? ? ?, n 处的值是 0,又 g ( ? 1) ? 1 。
( ? 1)
n ?1

故 g (x) ?

( n ? 1) !

x ( x ? 1) ? ? ? ( x ? n ) ,所以 g ( n ? 1) ?

( ? 1)

n ?1

( n ? 1) !

x ( x ? 1) ? ? ? ( x ? n ) ? ( ? 1)

n ?1

f ( n ? 1) ?

( ? 1)

n ?1

? ( n ? 1)

n?2

n为 奇 数 , ?1, ? ? ? n , n为 偶 数 . ? ?n ? 2

5


更多相关文档:

插值多项式存在唯一性

插值多项式存在唯一性_数学_自然科学_专业资料。插值...如果节点等距的情况下,可用差分构造 Newton 插值,...f ( xi ) . 分段线性插值和分段三次 Hermite ...

用matlab实现多项式插值与三次样条插值

用matlab实现多项式插值与三次样条插值_数学_自然科学_专业资料。用matlab实现多项式插值与三次样条插值的编码及龙格现象的分析!实验一 在区间[-1,1]上分别取 n...

拉格朗日多项式插值

拉格朗日多项式插值_数学_自然科学_专业资料。拉格朗日...式以及构造牛顿多项式的分段差分和系数表等等, 这里...y1 (5) 式(3)中的项 L1,0 ( x) L1,1...

数值分析牛顿插值多项式

数值分析牛顿插值多项式_数学_自然科学_专业资料。数值分析牛顿插值多项式对均分...通过所给出的节点,求得相应的差分; 3. 代入公式求出牛顿插值多项式,并由题目...

多项式插值理论

多项式插值理论_自然科学_专业资料。结构有限元素法 第六章一、区间[a , b]...注意:这里并不是分片插值基函数,而是全域上的;分片插值见下段。 3、误差估计...

高二竞赛讲义 多项式的零点2

高二竞赛讲义 多项式的零点2_理学_高等教育_教育专区...当 3 4 时实根的个 数为 4 个 b 例 4. ...1 已成立, 则由和差化积公式有等式 2 cos( n ...

拉格朗日插值多项式与泰勒多项式的误差分析详全文

拉格朗日插值多项式与泰勒多项式的误差分析详全文_教学...(Turin),從小就極有數學天分,於 18 歲開始 撰寫...clii. 在拉格朗日插值多項式被引入高中數學課綱([3...

Newton插值多项式的C程序实例

Newton插值多项式的C程序实例_数学_自然科学_专业资料。附录(一)等距结点的 Newton...步骤 2 求得各界差分 步骤 3 代入牛顿插值公式,可计算得出结果 (二)等距节点...

拉格朗日插值法理论及误差分析

拉格朗日插值法理论及误差分析_数学_自然科学_专业资料。浅析拉格朗日插值法目录:一、 引言 二、 插值多项式插值的介绍 三、 拉格朗日插值的理论及实验 四、 ...

Lagrange 插值多项式与Newton插值

插值多项式与Newton插值_数学_自然科学_专业资料。大家...3. 观察 Runge 现象的演示。 【程序设计】 执行 ...(n,n); --- % 加标签 % 存差分表(下三角...
更多相关标签:
多项式插值 | 拉格朗日插值多项式 | lagrange插值多项式 | 牛顿插值多项式 | matlab 多项式插值 | 多项式插值法 | 三次多项式插值 | hermite插值多项式 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com