第二章第二章插值法插值法/* Interpolation */&第一讲第一讲1.1.引言引言2.2.拉格朗日插值拉格朗日插值 许多实际问题都用函数许多实际问题都用函数 来表示某种内在规律的数量关系来表示某种内在规律的数量关系, ,其中相当一部分函其中相当一部分函数是通过实验或观测得到的：数是通过实验或观测得到的： 1 1 引言引言虽然虽然 在某个区间在某个区间 a a, ,b b 上是存在的，有的还是上是存在的，有的还是连续的，但却只能给出连续的，但却只能给出 a a, ,b b 上一系列点上一系列点 有的函数虽然有解析表达式有的函数虽然有解析表达式,但由于计算复杂但由于计算复杂,使用不使用不方便方便,通常也构造一个函数表。如三角函数表、对数表、通常也构造一个函数表。如三角函数表、对数表、平方根表、立方根表等等。平方根表、立方根表等等。由此构造一个简单易算的近似函数由此构造一个简单易算的近似函数 P(x) f(x)，满足条件：，满足条件： P(xi) = f(xi) (i = 0, n)。这里的这里的 P(x) 称为称为f(x) 的的插值函数插值函数。最常用的插值函数是。最常用的插值函数是 ?多项式多项式x0x1x2x3x4xP(x) f(x)设已知设已知f f( (x x) )满足满足1 1 引言引言根据给定的函数表，做一个根据给定的函数表，做一个既能反映函数的特性，又便既能反映函数的特性，又便于计算的简单函数近似于计算的简单函数近似f f( (x x) )。r有关概念有关概念插值函数插值函数插值节点插值节点插值区间插值区间若存在一个简单的函数若存在一个简单的函数P(x)，使得，使得 P(xi)=yi (i=0,1,2,n)成立，就称成立，就称P(x)为为f(x)的插值函数的插值函数点点x x0 0, x, x1 1, x, x2 2, ,x,xn n称为插值节点。称为插值节点。a,b称为插值区间称为插值区间插值法插值法求插值函数求插值函数P(x)的方法称为插值法。的方法称为插值法。 多项式插值多项式插值 分段插值分段插值 三角插值三角插值1 1 引言引言2.1 2.1 拉格朗日插值拉格朗日插值拉格朗日插值拉格朗日插值 2.2.拉格朗日插值拉格朗日插值 2.2 2.2 插值余项及误差估计插值余项及误差估计niyxLiin,., 0,)(= = =求求 n 次多项式次多项式 使使得得条件：条件：无重合节点，即无重合节点，即n = 1已知已知 xk-1 , xk ; yk-1 , yk ，求，求使得使得kk1K-1K-1)(,)(yxLyxL= = =可见可见 L1(x) 是过是过 ( xk-1 , yk-1 ) 和和 ( xk, yk ) 两点的直两点的直线。线。)()(K-1K-1kK-1kK-11xxxxyyyxL + += =kK-1kxxxx K-1kK-1xxxx = yk-1+ yklk-1(x)lk(x) = = =kK-1)(iiiyxl称为称为拉氏基函数拉氏基函数 /* Lagrange Basis */，满足条件满足条件 li(xj)= ij /* Kronecker Delta */2.1 2.1 拉格朗日插值拉格朗日插值拉格朗日插值拉格朗日插值 n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =niiinyxlxL0)()(，则显然有，则显然有Ln(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn = = = = = =njj i jiniiixxCxxxxxxCxl00)().().()( = = =j i jiiiixxCxl)(11)(与与 有关，而与有关，而与 无关无关,称为称为n次插值基函数。次插值基函数。节点节点f2.1 2.1 拉格朗日插值拉格朗日插值拉格朗日插值拉格朗日插值 Lagrange Polynomial若引入记号若引入记号 ，则，则 有：有：定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值阶插值多项式是唯一存在的。多项式是唯一存在的。证明：证明： ( 利用利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶的阶数数 n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n ，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插也是一个插值多项式，其中值多项式，其中 可以是任意多项式。可以是任意多项式。2.1 2.1 拉格朗日插值拉格朗日插值拉格朗日插值拉格朗日插值 插值余项插值余项 /* Remainder */设节点设节点在在a , b内存在内存在, 考察截断误差考察截断误差，且，且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。推广：推广：若若使得使得使得使得存在存在使得使得Rn(x) 至少有至少有 个根个根n+1 = = = =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = = = =niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x!)1()()()1(+-+nxKfxn 注意这里是对注意这里是对 t 求导求导= =+ + + + +!)1)()()()1()1(nxKLfxnnxn !)1()()()1(+ += =+ +nfxKxn 2.2 2.2 2.2 2.2 插值余项及误差估计插值余项及误差估计插值余项及误差估计插值余项及误差估计注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。Quiz: 给定给定 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 例例1：已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算利用利用这里这里而而sin 50 = 0.7660444)185(50sin10 p pL0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.010010.01001利用利用sin 50 0.76008, 内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。n = 2)185(50sin20 p pL0.76543sin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿嘿高就越好，嘿嘿关于关于LangrangeLangrange插值的几点说明插值的几点说明 仅与已知数据仅与已知数据 有关，与有关，与 的原来形式无关，但余式与的原来形式无关，但余式与 密切相关。密切相关。特别地：若特别地：若特别地：若特别地：若若若本身是一个不超过本身是一个不超过n次的多项式，则次的多项式，则，即，即，有，有 关于关于LangrangeLangrange插值的几点说明插值的几点说明从从 角度观察，内插误差要小些，即角度观察，内插误差要小些，即 位于位于 之间，而外插有可能误差之间，而外插有可能误差变大，因此要慎用。变大，因此要慎用。