第九章插值与拟合 插值：求过已知有限个数据点的近似函数。 拟合：已知有限个数据点，求近似函数，不要求过已知数据点，只要求在某种意义 下它在这些点上的总偏差最小。 插值和拟合都是要根据 组数据构造 一个函数作为近似，由于近似的要求不同， 的。而面对一个实际问题，究竞应该用插值还是拟合，有的 容 §1插值方法 下面介绍几种基本的、常用的插值：拉格朗日多项式插值、牛顿插值、分段线性插 值、Hermite插值和三 次样条插值。 1.1拉格朗日多项式插值 1.1.1插值多项式 用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数f(x)在 区间[a,b]上n+1个不同点x。,x,.,xn处的函数值y,=f(x)(1=0,1.,n),求一个 至多n次多项式 pn(x)=a+ax+.+anx 使其在给定点处与f(x)同值，即满足插值条件 p.(x)=fx)=y0=0,1.,n p(x)称为插值多项式，x,(i=0,L,.,n)称为插值节点，简称节点，[a,b]称为插值区 间。从几何上看，n次多项式插值就是过n+1个点(x,fx,》=01,n),作一条 多项式曲线y=o(x)近似曲线y=f(x)。 n次多项式(1)有n+1个待定系数，由插值条件(2)恰好给出n+1个方程 do+axo+azxo++axo=yo a+ax+a2x+.+anx=y (3) a+axn+a2x2+.+anx=ya 记此方程组的系数矩阵为A,则 1x。xg.xl 1x。x.x 是范德蒙特(Vandermonde)行列式。当xo,x1,xn互不相同时，此行列式值不为零。因 此方程组(3)有唯一解。这表明，只要+1个节点互不相同，满足插值要求(2)的 插值多项式(1)是唯一的。 插值多项式与被插函数之间的差 R(r)=f（x)-0(x) -175
-175- 第九章 插值与拟合 插值：求过已知有限个数据点的近似函数。 拟合：已知有限个数据点，求近似函数，不要求过已知数据点，只要求在某种意义 下它在这些点上的总偏差最小。 插值和拟合都是要根据一组数据构造一个函数作为近似，由于近似的要求不同，二 者的数学方法上是完全不同的。而面对一个实际问题，究竟应该用插值还是拟合，有时 容易确定，有时则并不明显。 §1 插值方法 下面介绍几种基本的、常用的插值：拉格朗日多项式插值、牛顿插值、分段线性插 值、Hermite 插值和三次样条插值。 1.1 拉格朗日多项式插值 1.1.1 插值多项式 用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数 f (x)在 区间[a,b]上n +1个不同点 n x , x , , x 0 1 L 处的函数值 ( ) i i y = f x (i = 0,1,L,n) ，求一个 至多n 次多项式 n n n x = a + a x +L+ a x 0 1 ϕ ( ) （1） 使其在给定点处与 f (x)同值，即满足插值条件 (x ) f (x ) y (i 0,1, ,n) ϕ n i = i = i = L （2） (x) ϕ n 称为插值多项式，x (i 0,1, ,n) i = L 称为插值节点，简称节点，[a,b]称为插值区 间。从几何上看，n 次多项式插值就是过n +1个点( , ( )) i i x f x (i = 0,1,L,n) ，作一条 多项式曲线 y (x) = ϕ n 近似曲线 y = f (x) 。 n 次多项式（1）有n +1个待定系数，由插值条件（2）恰好给出n +1个方程 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + + + = + + + + = + + + + = n n n n n n n n n n a a x a x a x y a a x a x a x y a a x a x a x y L LLLLLLLLLLLL L L 2 0 1 2 1 1 2 0 1 1 2 1 0 0 2 0 1 0 2 0 （3） 记此方程组的系数矩阵为 A ，则 n n n n n n x x x x x x x x x A L LLLLLLL L L 2 1 2 1 1 0 2 0 0 1 1 1 det( ) = 是范德蒙特(Vandermonde)行列式。当 n x , x , , x 0 1 L 互不相同时，此行列式值不为零。因 此方程组（3）有唯一解。这表明，只要n +1个节点互不相同，满足插值要求（2）的 插值多项式（1）是唯一的。 插值多项式与被插函数之间的差 R (x) f (x) (x) n = −ϕ n
称为截断误差，又称为插值余项。当f八(x)充分光滑时， R国=f-L=f且a,5ea.b (n+1)！ 其中on1(x)=Π(x-x,)。 1.12拉格朗日插值多项式 实际上比较方便的作法不是解方程(3)求待定系数，而是先构造一组基函数 1(x)= (x-x)(x-xx-x）.(x-x） (x,-xo).(x-x-x,-X1.(x,-xn) =7-x X-X ，0=0.L,m） I,(x)是n次多项式，满足 1,(x,)= j*1 1 i=i (4) x-x 上试称为次e插值多项式。由方程(3》解的唯性，n+1个节点的n次 用 ,agrange插值 00输 以黄组个铃久收物数组y为m个精酯.—一个名为cm的网爱 atlat的数组下标从1开交 for k=1:n 0 1： snnpe0g/a-85 if ik ens=p*y0 (k)+s; -176
-176- 称为截断误差，又称为插值余项。当 f (x)充分光滑时， ( ), ( , ) ( 1)! ( ) ( ) ( ) ( ) 1 ( 1) x a b n f R x f x L x n n n n ∈ + = − = + + ω ξ ξ 其中 ∏= + = − n j n j x x x 0 1 ω ( ) ( )。 1.1.2 拉格朗日插值多项式 实际上比较方便的作法不是解方程（3）求待定系数，而是先构造一组基函数 ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) 0 1 1 0 1 1 i i i i i i n i i n i x x x x x x x x x x x x x x x x l x − − − − − − − − = − + − + L L L L , ( 01 ) 0 i , , ,n x x x x n j i j i j j = L − − =∏ ≠ = l (x) i 是n 次多项式，满足 ⎩ ⎨ ⎧ = ≠ = j i j i l x i j 1 0 ( ) 令 ∑ ∑∏ = = ≠ = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − = = n i n i n j i j i j j n i i i x x x x L x y l x y 0 00 ( ) ( ) （4） 上式称为n 次 Lagrange 插值多项式，由方程（3）解的唯一性，n +1个节点的n 次 Lagrange 插值多项式存在唯一。 1.1.3 用 Matlab 作 Lagrange 插值 Matlab 中没有现成的 Lagrange 插值函数，必须编写一个 M 文件实现 Lagrange 插值。 设n 个节点数据以数组 x0, y0输入（注意 Matlat 的数组下标从 1 开始），m 个插值 点以数组 x 输入，输出数组 y 为m 个插值。编写一个名为 lagrange.m 的 M 文件： function y=lagrange(x0,y0,x); n=length(x0);m=length(x); for i=1:m z=x(i); s=0.0; for k=1:n p=1.0; for j=1:n if j~=k p=p*(z-x0(j))/(x0(k)-x0(j)); end end s=p*y0(k)+s; end y(i)=s; end
1.2牛顿(Newton)插值 在导出Newton公式前，先介绍公式表示中所需要用到的差商、差分的概念及性质。 定义设有函数f(x),x0,x,x2,.为一系列互不相等的点，称 f八)-2+》为f)关于点，x,一阶差商（他称均差）记为儿，小即 xi-xi ,=f)-f x,-x, 称一阶差商的差商 f几x,x,]-f几x,x] X。-x 为fx)关于点x,xx的二阶差商，记为fxx,x]。一般地，称 fLxo,x.,x-】-f[x,x2.,x] Xo-Xx 为f(x)关于点x,x,.,x的k阶差商，记为 。,小=小- Xo-Xk 容易证明，差商具有下述性质： f[x,x l=f[x,.x,] f[x.xx]=f[x,xx,x ]=f[xxx] 122 Newton插值公式 线性插值公式可表成 )=x,+(任-阶差商的定义，依次可得】 称为一次N wton插值多项式。 f(x)=f(xo)+(x-x)f几x,x】 f[x,xo]=f[xo.x]+(x-x)f[x.xo.x] f[x,xo,X]=f[xo,x,x2]+(x-x2)f[x,xo,X1.X2] fx,xo,.,x】=fxox1,.,xn】+(x-xn)fx,xo,.,xn] 将以上各式分别乘以1x-x-xx-x人，(x-x-x小.(x-x小然 后相加并消去两边相等的部分，即得 f(x)=f(xo)+(x-xo)f[xo,x]+. +(x-xoX(x-x).(x-x)fxo] +(x-xo(x-x(x-xn)f几x,x0,x,.,xn] 记 -177
-177- 1.2 牛顿（Newton）插值 在导出 Newton 公式前，先介绍公式表示中所需要用到的差商、差分的概念及性质。 1.2.1 差商 定义 设有函数 f (x), x0 , x1, x2 ,L为一系列互不相等的点，称 i j i j x x f x f x − ( ) − ( ) (i ≠ j) 为 f (x)关于点 i j x , x 一阶差商（也称均差）记为 [ , ] i j f x x ，即 i j i j i j x x f x f x f x x − − = ( ) ( ) [ , ] 称一阶差商的差商 i k i j j k x x f x x f x x − [ , ]− [ , ] 为 f (x)关于点 i j k x , x , x 的二阶差商，记为 [ , , ] i j k f x x x 。一般地，称 k k k x x f x x x f x x x − − − 0 0 1 1 1 2 [ , ,L, ] [ , ,L, ] 为 f (x)关于点 k x , x , , x 0 1 L 的k 阶差商，记为 k k k k x x f x x x f x x x f x x x − − = − 0 0 1 1 1 2 0 1 [ , , , ] [ , , , ] [ , , , ] L L L 容易证明，差商具有下述性质： [ , ] [ , ] i j j i f x x = f x x [ , , ] [ , , ] [ , , ] i j k i k j j i k f x x x = f x x x = f x x x 1.2.2 Newton 插值公式 线性插值公式可表成 ( ) ( ) ( ) [ , ] 1 0 0 0 1 ϕ x = f x + x − x f x x 称为一次 Newton 插值多项式。一般地，由各阶差商的定义，依次可得 ( ) ( ) ( ) [ , ] 0 0 0 f x = f x + x − x f x x [ , ] [ , ] ( ) [ , , ] 0 0 1 1 0 1 f x x = f x x + x − x f x x x [ , , ] [ , , ] ( ) [ , , , ] 0 1 0 1 2 2 0 1 2 f x x x = f x x x + x − x f x x x x LL [ , , , ] [ , , , ] ( ) [ , , , ] 0 n 1 0 1 n n 0 n f x x L x = f x x L x + x − x f x x L x − 将以上各式分别乘以1,( ),( )( ), , x − x0 x − x0 x − x1 L ( )( ) ( ) − 0 − 1 − n−1 x x x x L x x ，然 后相加并消去两边相等的部分，即得 ( )( ) ( ) [ , , , , ] ( )( ) ( ) [ , , , ] ( ) ( ) ( ) [ , ] 0 1 0 1 0 1 1 0 1 0 0 0 1 n n n n x x x x x x f x x x x x x x x x x f x x x f x f x x x f x x L L L L L + − − − + − − − = + − + − 记
N(x)=f(xo)+(x-xo)xox ]+. +(x-xo(x-x).(x-xm-i)f几x0,x1,x] R(x)=(x-xox-x).(x-xn)fx,xo,x,.,xn] =0n(x)X,xn,x,.,x 显然，N,(x)是至多n次的多项式，且满足插值条件，因而它是f(x)的n次插值 多项式。这种形式的插值多项式称为Newton插值多项式。R,(x)称为Newton插值余 项。 Newton插值的优点是：每增加一个节点，插值多项式只增加一项，即 N(x)=N (x)+(x-xo)(x)xox 因而使于递推运算。而且Newton插值的计算量小于L 由插值项式的唯性如，插值余项与金项也是相等的，即 R(x)=@(x)fIx.xo.X.x] a+i7o)5∈a.b 了+(5）) 由此可得差商与导数的关系 f,x]=位 其中5e(a,B),a=minx,B=maxx}. 123差分 当节点等距时，即相邻两个节点之差（称为步长）为常数，Newton插值公式的形 式会更简单。此时关于节点间函数的平均变化率（差商）可用函数值之差（差分）来表 示 定义设有等距节点x=x。+hk=0l,n),步长h为常数，=(x) 称相邻两个节点k,x1处的函数值的增量f1一f(欣=0,1，n-1)为函数f(x)在 点x处以h为步长的一阶差分，记为△，即 4=f1-f(k=0l,.,m 类似地，定义差分的差分为高阶差分。如二阶差分为 4=4-4(k=0,1.n-2) 一般地，m阶差分为 △f=△m-f41-△"-f(k=2,3), 上面定义的各阶差分又称为向前差分。常用的差分还有两种： 听=f-f 称为f(x)在x处以h为步长的向后差分： 成=}不剑 称为∫(x)在x处以h为步长的中心差分。一般地，m阶向后差分与m阶中心差分公 式 178
-178- ( ) [ , , , , ] ( ) ( )( ) ( ) [ , , , , ] ( )( ) ( ) [ , , , ] ( ) ( ) ( ) [ , ] 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 n n n n n n n n x f x x x x R x x x x x x x f x x x x x x x x x x f x x x N x f x x x f x x L L L L L L + − = = − − − + − − − = + − + ω 显然，N (x) n 是至多n 次的多项式，且满足插值条件，因而它是 f (x)的n 次插值 多项式。这种形式的插值多项式称为 Newton 插值多项式。 R (x) n 称为 Newton 插值余 项。 Newton 插值的优点是：每增加一个节点，插值多项式只增加一项，即 ( ) ( ) ( ) ( ) [ , , , ] n+1 = n + − 0 − n 0 1 n+1 N x N x x x L x x f x x L x 因而便于递推运算。而且 Newton 插值的计算量小于 Lagrange 插值。 由插值多项式的唯一性可知，Newton 插值余项与 Lagrange 余项也是相等的，即 ( ) ( , ) ( 1)! ( ) ( ) ( ) [ , , , , ] 1 ( 1) 1 0 1 x a b n f R x x f x x x x n n n n n ∈ + = = + + + ω ξ ξ ω L 由此可得差商与导数的关系 ! ( ) [ , , , ] ( ) 0 1 n f f x x x n n ξ L = 其中 ( , ), min{ }, max{ } 0 0 i i n i i n x x ≤ ≤ ≤ ≤ ξ ∈ α β α = β = 。 1.2.3 差分 当节点等距时，即相邻两个节点之差（称为步长）为常数，Newton 插值公式的形 式会更简单。此时关于节点间函数的平均变化率（差商）可用函数值之差（差分）来表 示。 定义 设有等距节点 ( 0,1, , ) xk = x0 + kh k = L n ，步长 h 为常数， ( ) k k f = f x 。 称相邻两个节点 1 , k k + x x 处的函数值的增量 ( 0,1, , 1) f k +1 − f k k = L n − 为函数 f (x) 在 点 k x 处以h 为步长的一阶差分，记为 k Δf ，即 ( 0,1, , ) Δf k = f k +1 − f k k = L n 类似地，定义差分的差分为高阶差分。如二阶差分为 ( 0,1, , 2) 1 2 Δ f k = Δf k + − Δf k k = L n − 一般地，m 阶差分为 ( 2,3, ) 1 1 Δm f k = Δm−1 f k + − Δm− f k k = L ， 上面定义的各阶差分又称为向前差分。常用的差分还有两种： ∇ k = k − k −1 f f f 称为 f (x)在 k x 处以h 为步长的向后差分； ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⎟ − − ⎠ ⎞ ⎜ ⎝ ⎛ = + 2 2 h f x h f f x δ k k k 称为 f (x) 在 k x 处以 h 为步长的中心差分。一般地， m 阶向后差分与 m 阶中心差分公 式为
V"fi =Vm-Ifi-vm-Ifi 6fi=8-6m 差分具有以下性质： ()各阶差分均可表成函数值的线性组合，例如 s1-fn) p-i-y） ()各种差分之间可以互化。向后差分与中心差分化成向前差分的公式如下： V"=△"f-m 8"f=A∫ x=x。+k幼(k=0,12,.,n),则有 N(x)=f(xo)+f[xo,x](x-xo) +.+f几x0,x,.,xn](x-xox-x).(x-xn-) =6+x-)++x-xXx-x)-X-) n!h 若令x=x。+h,则上式又可变形为 N(+h)=+++-小-m+公万 上式称为前插值公式。 13!插值多项式的振荡 用Lagrange插值多项式L.(x)近似fx(a≤x≤b,虽然随着节点个数的增加 L(x)的次数n变大，多数情况下误差|R(x)川会变小。但是n增大时，L(x)的光滑 性变坏，有时会出现很大的振荡.理论上，当n→0，在[a,b]内并不能保证L.(x)处 处收敛于f(x),Runge给出了一个有名的例子： f(x)= 1+x,xe[-55 对于较大的x,随着n的增大，L,(x)振荡越来越大，事实上可以证明，仅当|x上3.63 时，才有1imLn(x)=f(x),而在此区间外，L(x)是发散的。 高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。 1.3.2分段线性插值 简单地说，将每两个相邻的节点用直线连起来，如此形成的一条折线就是分段线性 插值函数，记作I(x),它满足I(x,)=y,且I(x)在每个小区间[x,x,上是线性 179
-179- 1 1 1 − − − ∇ = ∇ − ∇ k m k m k m f f f 2 1 1 2 1 1 − − + − = − k m k m k m δ f δ f δ f 差分具有以下性质： （i）各阶差分均可表成函数值的线性组合，例如 k m j m j j k m f j m f + − = ∑ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ Δ = (−1) 0 k j m j j k m f j m f − = ∑ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∇ = (−1) 0 （ii）各种差分之间可以互化。向后差分与中心差分化成向前差分的公式如下： k m m k m f f ∇ = Δ − 2 m k m k m f f − δ = Δ 1.2.4 等距节点插值公式 如果插值节点是等距的，则插值公式可用差分表示。设已知节点 xk = x0 + kh (k = 0,1,2,L,n)，则有 ( )( ) ( ) ! ( ) [ , , , ]( )( ) ( ) ( ) ( ) [ , ]( ) 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 − − − − − Δ − + + Δ = + + + − − − = + − n n n n n n x x x x x x n h f x x h f f f x x x x x x x x x N x f x f x x x x L L L L L 若令 x = x0 + th ，则上式又可变形为 0 0 0 0 ! ( 1) ( 1) ( ) f n t t t n N x th f t f n n Δ − − + + = + Δ + + L L 上式称为 Newton 向前插值公式。 1.3 分段线性插值 1.3.1 插值多项式的振荡 用 Lagrange 插值多项式 L (x) n 近似 f (x)(a ≤ x ≤ b) ，虽然随着节点个数的增加， L (x) n 的次数n 变大，多数情况下误差| R (x) | n 会变小。但是n 增大时， L (x) n 的光滑 性变坏，有时会出现很大的振荡。理论上，当n → ∞ ，在[a,b]内并不能保证 L (x) n 处 处收敛于 f (x)。Runge 给出了一个有名的例子： , [ 5,5] 1 1 ( ) 2 ∈ − + = x x f x 对于较大的| x |，随着n 的增大，L (x) n 振荡越来越大，事实上可以证明，仅当| x |≤ 3.63 时，才有 lim L (x) f (x) n n = →∞ ，而在此区间外， L (x) n 是发散的。 高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。 1.3.2 分段线性插值 简单地说，将每两个相邻的节点用直线连起来，如此形成的一条折线就是分段线性 插值函数，记作 I (x) n ，它满足 n i i I (x ) = y ，且 I (x) n 在每个小区间[ , ] i i+1 x x 上是线性