当前位置:首页 >> 理学 >>

函数逼近(多项式插值)


函数逼近(多项式插值)?

1.

数学问题

Lagrange 插 值 问 题 : 已 知 在 一 组 互 异 节 点 a ? x 0 ? x1 ? .... ? x n ? b 上 的 函 数 值

y0 ? y1 ? .... ? yn ,求一个尽可能低的多项式 p( x) ,使得: p ( xi ) ? y i (i ? 0,1,2,?, n)
即:

Lagrangre 插值共有 n+1 个约束条件。 广 义 Hermite 插 值 问 题 : 设 a ? x 0 ? x1 ? .... ? x n ? b 是 一 组 互 异 节 点 ,

ki (i ? 0,1, 2......n) 是一组正整数。给定一组二维锯齿数组 (cij ) 0 ? i ? n ,0 ? j ? k i ,求 一个尽可能低的多项式 p ( x) ,使得: p ( j ) ( xi ) ? cij 0 ? i ? n ,0 ? j ? k i


设N ?

?k
i ?0

n

i

? 1 ,则共有 N+1 个约束条件。在上图中, k 0 ? 3 , k1 ? 2 , k n ? 1 。

当 ki ? 1 时 , i ? 0,1,...n , Hermite 插 值 问 题 退 化 为 Lagrange 插 值 问 题 。 当

k i ? 2 i ? 0,1, ......n ,问题变成经典的 Hermite 插值问题,即求一个满足下表的插值多项 式 y ? p ( x) :

2.

数学理论结果

定理 在所有次数不大于 N 的多项式中,广义 Hermite 插值问题存在唯一解。 (非构造性的证明, 对于设计计算方法无益)

证明 Hermite 插值问题,共有 N+1 个约束条件, 其中 N ? 个 N 次 Hermite 插值多项式:

?k
i ?0

n

i

? 1 。我们希望找到一

p ( x) ? a N x N ? ..........a1 x ? a0
满足 N+1 个约束条件。 N+1 个约束条件对应于一个关于 a0 , a1.......aN 的线形方程组: Ha ? c 。存在唯一性等 价于矩阵 H 非奇异, 也等价于齐次线形方程 Ha ? 0 仅有唯一的平凡解 0。 考虑 Ha ? 0 所对 应的任意一个多项式 p(x)。显然 xi 是 p(x)的 ki 阶零点,于是 N 阶多项式 p(x)共有 N+1 个的 零点。根据代数基本定理,p(x)只能为 0,即 Ha ? 0 仅有唯一的平凡解 0。 误差估计 定 理 : 设 f ( x) ? C
N ?1

[a, b] , ki (i ? 0,1, 2.....n) 是 一 组 正 整 数 , N ? ? k i ? 1 ,
i ?0

n

cij ? f

( j)

( xi ) , p(x)是在节点 a ? x 0 ? x 1 ? .... ? x n ? b 上阶分别为 k 0 , k1 ,...k n 的

Hermite 插值, 则对于任意 x ? [a, b] , 插值余项为:

R N ( x) ? f ( x) ? p ( x) ?
式中 ? ? (a, b) 依赖于 x,
n
i

f N ?1 (? ) ? N ?1 ( x) ( N ? 1)!

? N ?1 ( x) ? ? ( x ? xi ) k 。
i ?0

证明:当 x 为插值点时, ? 可以取 (a, b) 中的任意点。现设 x 是固定的非插值点。由于

? N ?1 ( x) ? 0 ,可以选择一个与 x 相关的数 K(x),使 x 是以下函数的零点: g (t ) ? f (t ) ? p(t ) ? K ( x)? N ?1 (t )
即:

g ( x) ? f ( x) ? p( x) ? K ( x)? N ?1 ( x) ? 0
于是,当多重零点要重复计算时 g(t)共有 N+2 个零点。 反复应用 Roll 定理, 并根据多重零点的重数的知识, 可以判断 g 特别 g
( N ?1) (k )

(t ) 有 N-k+2 个零点。

(t ) 有一个零点,设之为 ? ? (a, b) 。于是:
( N ?1) f ( N ?1) (? ) ? K ( x)?N ?1 (? ) ? 0

f ( N ?1) (? ) ? ( N ? 1)!? K ( x) ? 0 K ( x) ?
定义 如果 f
(i )

f ( N ?1) (? ) ( N ? 1)!

(0 ? i ? n) , 则称 ? 为 f 的 n 重零点。 (k ) 根据定义,如果 ? 为 f 的 n 重零点, 则当 k ? n 时, ? 为 f 的 n-k 重零点。 (? ) ? 0
收敛性 例 1 f(x)=sin(x)

| RN ( x) |?

| ? ( x) | (b ? a ) N ?1 | f N ?1 (? ) | | ? N ?1 ( x) |? N ?1 ? ?0 ( N ? 1)! ( N ? 1)! ( N ? 1)!

例 2 f(z)=1/z, 在单位圆 | z |? 1 上插值。 选择插值点为 e
i 2 k? n

(k ? 0,1,2...n ? 1) ,显然插值函数是 z n ?1 ,因为当 z ? e

i

2 k? n



R( z ) ?
另外,当 z ? e
i (2 k ?1)? n

1 1 ? z n ?1 ? (1 ? z n ) ? 0 z z 1 n ?1 1 ? z ? (1 ? z n ) ? 2 z z

时,

R( z ) ?
| z | ?1

于是不难看出 max | R ( z ) |? 2 ,当 n 趋于无穷时,插值多项式不一致收敛于被插值的函数。 Runge 给出了在实数域上一个非常著名的高次插值函数不收敛的例子。 例 3(Runge) 高阶 Lagrangre 插值不一致收敛于函数。

f(x)=1/(1+x 2 )

x ? [-5, 5]

Faber 定理 对任意给定的节点组
(n) ( n) a ? x0 ? x1( n ) ? .... ? x n ?b

(n ? 0)

存在一个函数 f ? C[a, b] , 使得在这组点上 f 的插值多项式不能一致收敛于 f。 插值法收敛性定理 设 f ? C[a, b] ,则存在一个节点组 a ? x0
(n) ( n) ? x1( n ) ? .... ? x n ?b

(n ? 0) ,使得 f

在这组节点上的 Lagrange 插值多项式 p n 一致收敛于 f。 证明 对于任意给定的正整数 n,分别按照 Weierstrass 定理和 Chebyshev 最佳一致逼近 定理构造两个次数不大于 n 次多项式 g n 和 p n ,则它们满足

pn ? f ? g n ? f ? 0
由于 Chebyshev 最佳一致逼近多项式必定是插值型多项式,这样我们就可以根据 p n 选 择 与 之 对 应 的 插 值 节 点 a ? x0
(n) (n) ? x1( n ) ? .... ? x n ?b

(n ? 0) 。 每 个 插 值 节 点 位 于

pn ? f 的两个相临的交错点之间。
3. 数值计算方法

Lagrange 插值基法

Lagrange 问题的插值基 l k ( x) (k ? 0,1,2, ? , n) :

lk ( x) ?
插值多项式:

i ? 0 ,i ? k n i ? 0 ,i ? k

? (x ? x
k

n

i

) ?

? (x

? xi )

? n? ( x) ( x ? x k )? ' n ? 1 ( x k )

n n ? ? ?n ?1 ( x) Ln ( x) ? ? ? yk ? lk ( x) ? ? ? ? yk ? ? ( x ? xk )? 'n ?1 ( xk ) ? k ?0 k ?0 ?

广义 Hermite 插值问题,插值基 lij ( x) (i ? 0,1,2, ? , n,0 ? j ? k i ) :

?1 if (i, j ) ? (k , l ) (k ) lij ( xl ) ? ? otherwise ?0
插值多项式:

p( x) ? ?? cij l ij ( x)
i ?0 j ?0

n

ki

当 k i ? 2 , i ? 0,1,...n 时,插值基的计算公式为可以计算如下。设 ? i ( x) 满足如下插值 约束条件,



? i ( x) ? ? ? 1 ? 2( x ? x j )
同样,设 ? i ( x) 满足如下插值约束条件,

? ?

1 k ?0,k ?i xi ? x k

?

n

? 2 ? ?li ( x) ?



? i ( x) ? ( x ? xi )li2 ( x)
其中 l i ( x) 是 Lagrange 插值基, i ? 0,1,2, ?, n 。

Newton 插值法 均差 定义:设 x0 , x1 ,...., x n 互不相同的节点,称

? f [ xi ] ? f ( xi ) ? f [ x1 ,..xn ] ? f [ x0 , x1 ,..xn ?1 ] ? ? f [ x0 , x1 ,..xn ] ? xn ? x0 ?
为 f(x)的 n 阶均差。 均差的性质: 1、 设 x0 , x1 ,...., x n 互不相同的节点,则:

f [ x0 , x1 ,..x n ] ? ?
k ?0

n

f ( xk )
i ? 0 ,i ? k

? (x

n

k

? xi )
n

2、 Hermite-Genocchi 公式:设 x0 , x1 ,...., x n 是 n 个节点, f ? C [ a, b] , S n 是如下的 单纯形:
n ? ? S n ? ?u ? (u0 , u1 ,...., un ) ? R n ?1 : ui ? 0, ? ui ? 1, i ? 0,1, 2,..., n ? i ?0 ? ?



f [ x0 , x1 ,..x n ] ? ??? f ( n ) (u 0 x0 ? u1 x1 ? .... ? u n x n )du
Sn

如果节点 x0 , x1 ,...., x n 中有重复,则仍可把这个重积分作为均差的定义,则能避免均差 定义中节点互不相同的要求。当然,当 f ? C [a, b] ,不能采用这个公式作为均差的定义。
n

定义:设 x0 , x1 ,...., x n ? [a, b] , f ? C [a, b] ,f 的 n 阶均差定义为:
n

f [ x0 , x1 ,..x n ] ? ??? f ( n ) (u 0 x0 ? u1 x1 ? .... ? u n x n )du
Sn

当节点相同时,均差有如下性质: 3、 设 x0 , x1 ,...., x n ? [a, b] , 做适当置换,可以假设 x0 ? x1 ? .... ? xn ,则定义

? f [ x1 ,..xn ] ? f [ x0 , x1 ,..xn ?1 ] 当xn ? x0时 ? xn ? x0 ? f [ x0 , x1 ,..xn ] ? ? f ( n ) ( x0 ) ? 当x0 ? x1 ? ... ? xn时 ? n! ? ' ' ' 4、 设 x0 , x1 ,...., x n 是 x0 , x1 ,...., x n 的一个置换,则
' ' f [ x0 , x1 ,..x n ] ? f [ x0 , x1' ,...., x n ]

5、 设 f ? C [ a, b] ,且 x0 , x1 ,...., x n ? [ a, b] , 则存在 ? ? [ a, b] ,使
n

f [ x0 , x1 ,..x n ] ?
6、 设 x0 , x1 ,...., x n 互不相同的节点,则

f ( n ) (? ) n!

f ( x) ? f ( x 0 ) ? f [ x 0 , x1 ]( x ? x0 ) ? f [ x 0 , x1 , x 2 ]( x ? x0 )( x ? x1 ) ? ...... ? f [ x0 , x1 ,..x n ]( x ? x0 )( x ? x1 ).....( x ? x n ?1 ) ? f [ x, x0 , x1 ........x n ]( x ? x0 )( x ? x1 )....( x ? x n )
7、如果 f ? C [ a, b] ,则对于可能相同的节点 x0 , x1 ,...., x n ,性质 6 仍然正确。
n

性质 1 可以用数学归纳法证明。 将重积分花为累次积分, 再用数学归纳法可以证明性质

1 ,根据积分中值 n! n 定理性质 5 得证。在 f ? C [ a, b] 的假设下,牛顿公式关于变量 x0 , x1 ,...., x n 连续,假设性
2。性质 3、4 是性质 2 的直接推论。在单纯形 S n 上,常数 1 的积分等于 质 6 得证,则取极限立刻可知性质 7 也正确。以下仅证明性质 3 和性质 6。 性质 3 的证明: 当x0 ? x1 ? ... ? x n时

f [ x0 , x1 ,..x n ] ? ??? f ( n ) (u 0 x0 ? u1 x1 ? .... ? u n x n )du
Sn

? f ( n ) ( x0 ) ??? du ?
Sn

f ( n) ( x0 ) n!

当 x0 ? x n 时,
(n) f [ x0 , x1 ,..xn ] ? ? ??? f (u0 x0 ? u1 x1 ? .... ? un xn )du Sn

??

1 1?u1

0 0 1 1?u1

?

......?

1?u1 ?...un?1

0 1?u1 ?...un?2

f ( n ) ( x0 ? u1 ( x1 ? x0 ) ? .... ? un ( xn ? x0 ))dun .....du2 du1
un ?1?u1 ?...?un?1 1 f ( n ?1) ( x0 ? u1 ( x1 ? x0 ) ? .... ? un ( xn ? x0 )) dun ?1.....du2 du1 un ? 0 xn ? x0

?? ?? ?

0 0 1 1?u1

? ?

......? ......?

0 1?u1 ?...un?2

0 0

0

1 xn ? x0

? f ( n ?1) ( xn ? u1 ( x1 ? xn ) ? .... ? un ?1 ( xn ?1 ? xn )) ? ? ( n ?1) ?dun ?1.....du2 du1 ? ? ? ? ? ? f ( x u ( x x ) .... u ( x x )) ? n ?1 n ?1 0 1 1 0 0 ? ? ?

1 ? f [ x1 ,..xn ] ? f [ x0 , x1 ,..xn?1 ]? xn ? x0

性质 6 的证明:证明采用数学归纳法。 1、当 n=0 时,公式显然成立。事实上, 当 x ? x 0 时,显然

f ( x) ? f ( x0 ) ? f ' ( x 0 )( x ? x0 ) 当 x ? x 0 时,按均差的定义: f ( x) ? f ( x0 ) f [ x, x 0 ] ? x ? x0
于是

f ( x) ? f ( x0 ) ? f [ x, x0 ]( x ? x 0 )
所以性质 6 在 n=0 时正确。 2、假设对 n=k-1 性质 6 正确,现在来讨论 n=k 的情况。由归纳法假设,

f ( x) ? f ( x0 ) ? f [ x0 , x1 ]( x ? x 0 ) ? f [ x 0 , x1 , x 2 ]( x ? x 0 )( x ? x1 ) ? ..... ? f [ x0 , x1 ,..x k ?1 ]( x ? x0 )( x ? x1 ).....( x ? x k ? 2 ) ? f [ x, x0 , x1 ,..x k ?1 ]( x ? x0 )( x ? x1 ).....( x ? x k ?1 ) 当 x 不等于 x0 , x1 ,...., x k ?1 , x k 中的任意一点时,由性质 3:

f [ x, x0 , x1 ,....., x k ] ?
代入上式,可知

f [ x, x0 , x1 ,....., x k ?1 ] ? f [ x 0 , x1 ,....., x k ] x ? xk

f ( x) ? f ( x0 ) ? f [ x0 , x1 ]( x ? x 0 ) ? f [ x 0 , x1 , x 2 ]( x ? x 0 )( x ? x1 ) ? ..... ? f [ x0 , x1 ,..x k ?1 ]( x ? x0 )( x ? x1 ).....( x ? x k ? 2 ) ? f [ x0 , x1 ,..x k ?1 , x k ]( x ? x0 )( x ? x1 ).....( x ? x k ?1 ) ? f [ x, x0 , x1 ,..x k ]( x ? x0 )( x ? x1 ).....( x ? x k ) 即当 x 不等于 x0 , x1 ,...., x k ?1 , x k 时,性质 6 正确。
另外,再以 x ? xi 代入,我们有:

f ( xi ) ? f ( x0 ) ? f [ x0 , x1 ]( xi ? x0 ) ? f [ x0 , x1 , x 2 ]( xi ? x0 )( xi ? x1 ) ? ..... ? f [ x0 , x1 ,..x k ?1 ]( xi ? x0 )( xi ? x1 ).....( xi ? x k ? 2 ) ? f [ xi , x0 , x1 ,..x k ?1 ]( xi ? x0 )( xi ? x1 ).....( xi ? x k ?1 ) 于是,直接验证,如果 x 为 x0 , x1 ,...., x k ?1 , x k 中的任意一点,性质 6 仍然成立。
根据数学归纳法,性质 6 得证。

定理 1:设 x0 , x1 ,...., x n 互不相同的节点,

p ( x) ? f ( x0 ) ? f [ x0 , x1 ]( x ? x 0 ) ? f [ x 0 , x1 , x 2 ]( x ? x 0 )( x ? x1 ) ? ...... ? f [ x 0 , x1 ,..x n ]( x ? x 0 )( x ? x1 ).....( x ? x n ?1 )


p ( x i ) ? f ( xi )

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

证明:证明采用数学归纳法。当 n=1 时,定理显然成立。假设定理对 n-1 时正确,我们 来看 n 的情形。 按归纳法假设, p n ?1 ( x) 是在 x0 , x1 , x 2 ....x n ?1 的插值函数,即:

p n ?1 ( x) ? f ( x0 ) ? f [ x0 , x1 ]( x ? x0 ) ? f [ x0 , x1 ,...., x n ? 2 ]( x ? x0 )( x ? x1 )...( x ? x n ?3 ) ? ...... ? f [ x 0 , x1 ,..x n ?1 ]( x ? x0 ).....( x ? x n ? 2 ) 再设 q n ?1 ( x) 是在 x0 , x1 ....x n ? 2 , x n 的插值函数: qn ?1 ( x) ?? f ( x0 ) ? f [ x0 , x1 ]( x ? x0 ) ? .... ? f [ x0 , x1 ,...., xn ? 2 ]( x ? x0 )( x ? x1 )...( x ? xn ?3 ) ? f [ x0 , x1 ,..xn ? 2 , xn ]( x ? x0 ).....( x ? xn ? 2 )
首先,直接验证

p n ( x) ? p n ?1 ?
是 n 次插值函数,而

( x ? x n ?1 ) (q n ?1 ? p n ?1 ) x n ? x n ?1

p n ( x) ? p n ?1 ?

( x ? x n ?1 ) (q n ?1 ? p n ?1 ) x n ? x n ?1

? f ( x0 ) ? f [ x0 , x1 ]( x ? x0 ) ? f [ x0 , x1 ,...., x n ? 2 ]( x ? x0 )( x ? x1 )...( x ? x n ?3 ) ? ...... ? f [ x 0 , x1 ,..x n ?1 ]( x ? x0 ).....( x ? x n ?2 ) ? ( x ? x n ?1 ) ( f [ x0 , x1 ,..x n ? 2 , x n ] ? f [ x0 , x1 ,..x n ?1 ])( x ? x1 ).....( x ? x n ? 2 ) x n ? x n ?1 ? f ( x0 ) ? f [ x0 , x1 ]( x ? x0 ) ? f [ x0 , x1 ,...., x n ? 2 ]( x ? x0 )( x ? x1 )...( x ? x n ?3 ) ? f [ x0 , x1 ,..x n ?1 , x n ]( x ? x0 )( x ? x1 ).....( x ? x n ?1 )
引理 1:设 x0 , x1 ,...., x n 互不相同的节点,则 Newton 插值多项式与节点的顺序无关。 引理 2:设 x0 , x1 ,...., x n 为任意一组节点,且 f ? C [ a, b] ,则 Newton 插值多项式与节
n

点的顺序无关。 定理 2:设 x0 , x1 ,...., x n ? [ a, b] ,且 f ? C [ a, b] 。定义
n

p( x) ? f ( x0 ) ? f [ x0 , x1 ]( x ? x0 ) ? f [ x0 , x1 , x2 ]( x ? x0 )( x ? x1 ) ? ...... ? f [ x0 , x1 ,..xn ]( x ? x0 )( x ? x1 ).....( x ? xn?1 )
如果节点 xi 重复 k 次,则 p
( j)

( xi ) ? f ( j ) ( xi )

(0 ? j ? k ) 。
( j)

证明:我们仅需要证明当节点 x0 重复 k 次时,则 p

( x0 ) ? f ( j ) ( x0 )

(0 ? j ? k ) 。

首先适当置换节点,使所有与 x0 相同的节点全部排在前面。此时,多项式的表示时变形为:

p ( x) ? ?
j ?0

k ?1

f ( j ) ( x0 ) ( x ? x0 ) j ? g ( x)( x ? x0 ) k j!

于是 p ( x) 满足定理中插值各阶约束。

Newton 插值算法:

x i=0 i=1 2

j=0 y

1

2

…….

J

…….

n

x0
x1 x2

y0
y1 y2 y3

d (1,1) d (2,1)

d (2,2) d (i ? 1, j ? 1)
d (i,2) d (i, j ? 1) d (i, j )

d (i ? 1,1)
i i=5 6

xi x5 x6

yi y5 y6

d (i,1)

其中: d [i, j ] ?

d [i, j ? 1] ? d [i ? 1, j ? 1] x[i ] ? x[i ? j ]

例 1、老师的程序输出(P34,例 2)

例 2:求以下 Hermite 插值: f f’ f” 手工计算 i 0 1 2 3 4 x 1 1 2 2 2 y 2 2 6 6 6 x=1 2 3 x=2 6 7 8

3 4 7/1!=7 7

1 3 8/2!=4

2 1

-1

老师的程序输出:

例 3:求以下 Hermite 插值。 我们首先求前 3 个节点的插值,然后再增加一个二重节点 x=7。 f f’ f” x=1 3 4 8 2 2 4 6 4 7 2 5

算法技巧: 1、 空间的节省:二维数组让费太多空间,即使使用下三角矩阵也不好。我使用了两个一维 数组存储对角线和最后一行元素。 2、 Newton 算法允许事后添加新的插值节点,这是其精华所在。于是可知,不宜选择 C 语 言中的数组,它不具有自动缩放功能。我选择了 MFC 中的摸板类 CArray。如果使用 ANSI C++,可以使用 vector 来组织数据。 3、 对于多重节点,有一些项不需要计算。 4、 注意程序的计算复杂性。


赞助商链接
相关文章:
第四章 插值法与函数逼近
第四章 插值法与函数逼近_数学_自然科学_专业资料。第四章 插值法与函数逼近 .../ 2? 上求 1 次和三次伯恩斯坦多项式并画出图形,并与相应的 B 函数逼近 ?...
数值分析作业
(2)选择其他的函数,例如定义在区间[-5,5]上的函数 重复上述的实验看结果如何。 三、 实验结果及分析 图 1 f(x)的拉格朗日插值多项式 结果分析:多项式插值逼近...
数值分析 函数逼近与曲线拟合
插值函数出现的龙格现象表明,非节点处函数和它的插值多项式相差太大。更重要的是, 实际中通过观测得到的节点数据往往有各种误差,此时如果要求逼近函数过全部节点,...
函数的插值与多项式近似计算
函数插值多项式近似计算 1. 实验描述计算机中常常要用到库函数,sin(x),cos(x)和 ex,它们是用多项式逼近来计算的。常见的多项 式逼近方法有泰勒级数、...
插值与多项式逼近的数组计算方法实验
插值多项式逼近的数组计算方法实验 - 《数值方法》实验报告 1 插值多项式逼近的数组计算方法实验 【摘要】计算机软件中经常要用到库函数,如 sin(x) , cos (...
第七讲 MATLAB在插值与逼近中的应用
第七讲 MATLAB 在插值逼近中的应用 1 插值逼近 1.1 为什么要逼近 数学...,xn 上的函数值为 y0,y1,?,yn,求作一 个次数≤n 的多项式 pn ( x) ?...
数值分析作业-三次样条插值
实验要求:(1) 随着节点个数的增加,比较被逼近函数和三样条插值函数的误差变化情 况,分析所得结果并与拉格朗日插值多项式比较; (2) 三次样条插值函数的思想最早...
数值计算方法第七章习题 2013
6.什么是切比雪夫多项式?它有什么重要性质? 7.用切比雪夫多项式零点做插值得到...(x) = 1 的最佳平方逼近二次多项式。 20.求函数 f (x)在指定区间上对于?...
数值代数与数值逼近2014
题目 3:插值法 某气象观测站在 8:00(AM)开始每隔 10 分钟对天气作如下观测, 用多项式插值函数逼近如下曲线,插值节点数据如上表,并求出 9 点 30 分该地区...
数值分析习题集及答案[1]
ln( x ? x 2 ? 1) ,求 f(30)的值.若开平方用六位函数表,问求对数...x ?1,1? 上的插值极小化近似最佳逼近多项式为 Ln ( x) ,若 f ? Ln ...
更多相关标签: