数值分析 数据插值

1、1 1 引引 言言 第二章第二章 插值插值 /* Interpolation */究函数的变化规律，往往需要求不在表上的函数值。因究函数的变化规律，往往需要求不在表上的函数值。因此，我们希望根据给定的函数表做一个既能反映函数此，我们希望根据给定的函数表做一个既能反映函数的特性，又便于计算的的特性，又便于计算的简单函数简单函数 , ,用用 近似近似 。 许多实际问题都用函数许多实际问题都用函数 来表示某种内在规来表示某种内在规 律的数量关系，其中相当一部分函数是通过实验或观测律的数量关系，其中相当一部分函数是通过实验或观测 得到的。得到的只是得到的。得到的只是 上一系列点上一系列点 的函数值的函

2、数值 这只是一张函数表。有的函数虽有解析表达式，但由于这只是一张函数表。有的函数虽有解析表达式，但由于 计算复杂，使用不方便，通常也造一个函数表，比如平计算复杂，使用不方便，通常也造一个函数表，比如平 方根表、立方根表、对数表和三角函数表等等。为了研方根表、立方根表、对数表和三角函数表等等。为了研)(xfy ,ba)(xf), 1 , 0)(nixfyii ix)(xf)(xp)(xp)(xpx0 x1x2x3x4xp(x) f(x)如如：通常用代数多项式或分段代数多项式作为：通常用代数多项式或分段代数多项式作为 , ,并使并使 对对 成立。这样确定的成立。这样确定的 就是我们希望得到的插值函

3、数。就是我们希望得到的插值函数。)()(iixfxp ni,1 ,0 )(xp)(xp)(xf1 Introduction 已知在点已知在点 上的值上的值 nyyy,10nxxx,10bxxxan 10若存在一简单函数若存在一简单函数 ，使，使, iiyxp )(0,1, 2, (2.1)in)(xp设函数设函数 在区间在区间 上有定义，且上有定义，且)(xfy ,ba插值法定义插值法定义成立，就称成立，就称 为为 的插值函数，点的插值函数，点nxxx,10)(xp)(xf插值节点插值节点，包含插值节点的区间，包含插值节点的区间 称为称为插值区间，插值区间，（2.1）称为）称为插值条件，插值条

4、件，求插值函数求插值函数 的方法称为的方法称为插值法插值法。,ba)(xp称为称为若若 为次数不超过为次数不超过 的代数多项式，即的代数多项式，即)(xpn(2.2) nnxaxaaxp 10)(其中其中 为实数，就称为实数，就称 为为插值多项式插值多项式，相应的插值法称，相应的插值法称为为多项式插值多项式插值。若。若 为分段多项式，就是为分段多项式，就是分段插值分段插值。若。若 为三角多项式，就称为为三角多项式，就称为三角插值。三角插值。na)(xp)(xp)(xp1 Introduction由插值条件可得由插值条件可得00202010yxaxaxaann )3 . 2(nnnnnnyxax

5、axaa 2210插值多项式的存在唯一性插值多项式的存在唯一性这是一个关于这是一个关于 的的 元线性方程组。元线性方程组。naaa10,1 n 要证明插值多项式的存在唯一性，只要证明上述方程要证明插值多项式的存在唯一性，只要证明上述方程组存在唯一解，也就是证明方程组的系数行列式的值组存在唯一解，也就是证明方程组的系数行列式的值不为不为零。零。 设设 是形如是形如 的插值多项式，用的插值多项式，用 代表所有次代表所有次 数不超过数不超过 的多项式集合，于是的多项式集合，于是 . .所谓插值所谓插值多项式多项式 存在且唯一，就是指在集合存在且唯一，就是指在集合 中有且只有中有且只有一个一个 满足满

6、足插值条件插值条件 。)(xpnHnnHxP )() 2 . 2 ()(xp)(xpn,iyxpii1 ,0)( , nH1 Introduction式中式中 称为称为Vandermond行列式。行列式。 ),(10nnxxxV故方程组故方程组 存在唯一的一组解。存在唯一的一组解。)3 . 2( ),(10nnxxxV利用行列式性质可得利用行列式性质可得 niijjixx110),(0 jixx, ,故所有因子故所有因子jixxji 时由于由于以上论述可写成下列定理：以上论述可写成下列定理：0),(10 nnxxxV于是于是nnnnnnnnxxxxxxxxxxxxV21211020010111

7、),( 其系数行列式为其系数行列式为1 Introduction1 Introduction定理定理 (唯一性唯一性) 满足满足 次数不超过次数不超过 n的插值多项式是唯一存在的。的插值多项式是唯一存在的。niyxPii,., 0,)( 证明：证明： (另一证法）另一证法）反证：若不唯一，则除了反证：若不唯一，则除了pn(x) 外还有另一外还有另一 n 阶多项阶多项式式 Ln(x) 满足满足 Ln(xi) = yi 。考察考察 则则 Qn 的次数的次数, )()()(xLxPxQnnn nn + 1x0 xn而而 Qn 有有 个不同的零点个不同的零点注：注：若不将多项式次数限制为若不将多项式次

8、数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。niinxxxpxPxP0)()()()()(xp2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */)x(ly)x(ly)x(ly)x(Lnnn 1100求求 n 次多项式次多项式使得使得niyxLiin, 2 , 10,)(， 条件：条件：无重合节点，即无重合节点，即jixx ji 11001y)x(ly)x(l)x(L (0使得使得n = 111L已知已知 x0 , x1 ; y0 , y1 ，求，求y0,

9、( x1L)1y )x 可见可见 L1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)()(0010101xxxxyyyxL 101xxxx 010 xxxx = y0 + y1l0(x)l1(x) 10)(iiiyxl称为称为拉氏基函数拉氏基函数 /* Lagrange Basis */，满足条件满足条件 li(xj)= ij /* Kronecker Delta */2 Lagrange Polynomialn 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 niiinyxlxL0)()(

10、，则显然有，则显然有Ln(xi) = yi 。li(x)每个每个 li 有有 n 个零点个零点 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f i 1注：注：ixl)(（特别的，（特别的，f(x)=1）2120210121012002010212)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 特别地，一点零次插值

11、多项式为特别地，一点零次插值多项式为0)(yxLn 101001011)(yxxxxyxxxxxL 三点二次插值（抛物插值）多项式为三点二次插值（抛物插值）多项式为两点一次插值（线性插值）多项式为两点一次插值（线性插值）多项式为2 Lagrange Polynomial 插值余项插值余项 /* Remainder */设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)(

12、)(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个零点个零点n+1 niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 niixtxKtRnt0)()()()( (t)有有 n+2 个不同的零点个不同的零点 x0 xn x),(, 0)()1(baxxn !=0)1()()()1(nxKRxnn 注意这里是对注意这里是对 t 求导求

13、导 !)1)()()()1()1(nxKLfxnnxn !)1()()()1( nfxKxn niixnnxxnfxR0)1()(! ) 1()()( 当当 时时，1n),)()(21)(1,0101xxxxxxfxR ),)()()(61)(2, 02102xxxxxxxxfxR当当 时，抛物插值余项为时，抛物插值余项为2n注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插

14、值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRn2 Lagrange Polynomial2 Lagrange PolynomialQuiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x)的图像？的图像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 2 Lagrange Polynomial例：

15、例：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin1

16、0 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.010100.010103,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.00596 0.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。2 Lagrange Polynomialn = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL

17、)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.00061 0.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿HW: p.49#2，#3，#4 When you start writing the program, you will find how easy it is to calculate the Lagrange polynomial.Oh yeah? What if I find the