计算方法第四章插值法

第4章插值法§1插值问题§2线性插值与二次插值§3代数多项式插值的存在唯一性§4代数多项式的余项§5拉格朗日插值多项式§6牛顿均差插值多项式§7牛顿前差和后差插值多项式§8三次样条插值§9数值微分§10曲线拟合法?7=xi4916yi234479164320应用背景造函数表：三角函数、对数预测：鸡蛋价格、城市用水量数控加工：造船、飞机机翼骨架、服装样片、模具加工、刀具计算机辅助设计：潜水艇、汽车造型服装样片实际问题中，f(x)多样，复杂，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数φ(x)来逼近f(x)。自然地，希望φ(x)通过所有的离散点。x0x1x2x3x4xφ(x)f(x)已知{xi，yi}，i=0,1,…,n是函数y=f(x)的离散点，φ(x)∈φ为y=f(x)的近似函数。满足φ(xi)=yi，i=0,1,…,n称这个问题为曲线插值问题。φ(x)为插值函数；xi,i=0,1,…,n为插值节点；f被插值函数；φ(xi)=yi插值条件或插值原则。(x)求§1插值问题数学模型：已知{xi，yi}，求一条光滑曲线满足φ(xi)=yi。理论问题：1数学描述；2误差估计；取前n+1项的部分和Pn(x)作为f(x)的近似式，也即：若仅限于求函数在x=x0的近似函数，一个熟知的办法就是将f(x)在x=x0处展成泰勒级数，即多项式插值（待定系数法）多项式插值（待定系数法）代数多项式形式简单，便于计算，且在某些情况下与给定的函数有较好的逼近的特性1个点插值φ(x)=y0x0y0（，）xy§2线性插值与二次插值

2.1线性插值线性插值是代数多项式插值的最简单的形式。假设给定了函数f(x)在两个互异点x0，x1的值,即xx0x1yy0y1（2点插值）x0x1y0y1xy现要用一线性函数

φ(x)=P1(x)=ax+b

近似地代替f(x)。按照插值原则，有：因为x0≠x1,所以a，b可唯一确定，且有

2.2二次插值二次插值又称为抛物线插值,也是常用的代数多项式插值之一。设已知函数f(x)的三个互异插值基点x0，x1，x2的函数值分别为y0，y1，y2,见下表所示:xx0x1x2yy0y1y2（3点插值）现要构造一个二次函数

φ(x)=P2(x)=ax2+bx+c

近似地代替f(x)，并满足插值原则

P2(xi)=yi，i=0，1，2，…x0，x1，x2互异，a，b，c可唯一地确定。二次函数P2(x)也唯一地被确定。§3代数多项式插值的存在唯一性对于一般的代数插值问题，就是寻求一个n次的代数多项式：

Pn(x)=a0+a1x+a2x2+…+anxn

使其在给定的n+1个互异的插值基点上满足插值原则

Pn(xi)=yi，i=0，1，…，n根据插值原则式，代数多项式中的各个系数a0，a1，…，an应满足下列n+1阶线性方程组系数行列式为范德蒙特(VanderMonde)行列式由于插值基点xi(I=0，1，…，n)为互异,故

V(x0，x1，…，xn)≠0

方程组有唯一的一组解a0，a1，…，an

Pn(x)存在且唯一。§4代数多项式的余项一般说来,对插值区间［a，b］上插值基点xi(i=0，1，2，…，n)以外的点，Pn(x)≠f(x)。若令：

Rn(x)=f(x)–Pn(x)

则：

f(x)=Pn(x)+Rn(x)x0x1x2x3x4xφ(x)f(x)插值多项式Pn(x)的余项定理:

设Pn(x)是过点x0，x1，x2，…，xn的f(x)的n次插值多项式，f(x)

∈Cn+1[a,b]，其中[a，b]是包含点x0，x1，x2，…，xn的区间，则对任意给定的x[a，b]，总存在一点

（a，b）（依赖于x）使：

插值的截断误差其中： 证明见书P145

插值的绝对误差限为:由上面定理有一下几点结论:(1)插值多项式只与插值基点及基点上的函数值有关，与函数f(x)没有关系。但余项Rn(x)却与f(x)联系很紧。

(2)若f(x)即为次数不超过n的多项式，那么以n+1个点为基点的插值多项式就一定是其本身，即Pn

(x)≡f(x)。

(3)当点x位于x0，x1，…，xn的中部时，|ωn+1(x)|比较小，误差小些，而位于两端时，误差要更大些。nkkiiknyxlyxP==å)()(i=0构造li(x)为n次多项式，满足：说明：满足插值条件φn(xi)=yi，i=0，1，…,n于是：§5拉格朗日插值多项式kiinknxlyxP=å)()(i=0li(xj)=j≠i1j=i0关键是:li(x)=？注意到li(xj)=0j≠i说明li(x)中定有因子：(x–x0)(x–x1)…(x–xi-1)(x–xi+1)…(x–xn)即：xj，j≠i是li(x)的根再注意到li(xi)=1，说明li(x)的分母中有因子(xi–x0)(xi–x1)…(xi–xi-1)(xi–xi+1)…(xi–xn)故有称为Lagerange插值基但是将xi代入，此式不等于nixxxxxljijnijji,,1,0,)(0L=--P=¹=当n=1,Lagerange插值10100101)(yxxxxyxxxxxy--+--=x0x1y0y1xy010110)(,)(xxxxxlxxxxxl--=--=1022当n=2时，Lagerange插值为：满足插值条件：例：已知函数y=f(x)的观测数据为x1234y0-5-63试求拉格朗日插值多项式。解：已知函数y=f(x)的观测数据为x012y123试求拉格朗日插值多项式。解：例：解：图4.3图4.3想法：

Lagrange插值每增加一个节点，所有的系数必须重新计算。能否有一种方法，增加节点时，先前的计算仍然可以利用，只增加很少的工作量就能得到新的高次插值多项式。做法：§6牛顿均差插值多项式?将插值多项式Pn(x)表示成下列形式:依据条件，根据插值原则，可以依次确定系数a0，a1，…，an，例如：取x=x0，得取x=x1,得

为了得到计算系数ai的一般方法,下面引进差商的概念.取x=x2,得二差商的定义

给定[a,b]中互不相同的点x0，x1，x2，…，以及f(x)在这些点处相应的函数值f(x0)，f(x1)，f(x2)，…，用记号表示f(x)在x0及x1两点的一阶差商。x0，x1，x2三点的二阶差商为：一般地，有了k-1阶差商之后，可以定义f(x)在x0，x1，..，xk的k阶差商：三Newton插值公式由差商定义,有

f(x)=f[x0]+(x-x0)f[x,x0]

f[x,x0]=f[x0,x1]+(x-x1)f[x,x0,x1]

f[x,x0,x1]=f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2]………..

f[x,x0,…xn-1]=f[x0,…,xn]+(x-xn)f[x,x0,….,xn]将以上各式，由下而上逐步代入，得到

f(x)=f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1,x2]+…+(x-x0)…(x-xn-1)f[x0,…,xn]+(x-x0)…(x-xn-1)(x-xn)f[x,x0,…xn](5)],,,,[))(())((],,,,[)())((],,[))((],[)()()(10110210110210101000nnnnnxxxxfxxxxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfLLLLL----+---++--+-+=--=Pn(x)称为Newton插值公式=Rn(x)Newton插值余项0x牛顿差商表例3已知数据表，构造f(x)的牛顿均差插值多项式。x1234y0-5-63

解：作均差表P3(x)=0+(-5)(x-1)+2(x-1)(x-2)+(x-1)(x-2)(x-3)=x3-4x2+3x

12356F(x)

0262090试求牛顿均差插值多项式。

例4已知数据表解:§7牛顿前差和后差插值多项式当插值基点x0,x1,…,xn分布等距时,也即

h=xk+1-xk,k=0,1,2,…,n-1

牛顿均差插值多项式的表达形式可以简化。为此先引进有限差概念。

7.1有限差我们分别称为一阶前差、一阶后差和一阶中心差,又统称为一阶有限差。这里符号Δ、、δ分别表示前差、后差和中心差算子。由一阶有限差算子的定义,用递推方法可定义高阶有限差。二阶前、后差分别定义为依此类推,n阶前差定义为n阶后差定义为并规定零阶前、后差为同样可定义n阶中心差根据有限差的定义,可得到它的几个简单性质:=(1)若函数f(x)为m次多项式,则m-k次多项式,0≤k≤mk＞m（即常数的有限差为零）(4―31)

(2)均差与前、后差的关系可表示为(4―32)(4―33)式(4―32)和(4―33)可用归纳法证明。

7.2牛顿前差和后差插值多项式

1.牛顿前差插值多项式在牛顿均差插值多项式(4―24)中,按式(4―32)将均差换成前差,即得到牛顿前差插值多项式(4―34)令

x=x0+sh(s未必是整数)

则

xi=x0+ih

x-xi=(s-i)h,i=0,1,2,…,n

这样牛顿前差插值多项式可改写成(4―35)或记为且其余项为(4―36)

2.牛顿后差插值多项式若将n+1个插值基点依xn,xn-1,…,x0的次序排列,则牛顿均差插值多项式为

Pn(x)=f(xn)+f［xn,xn-1］(x-xn)+f［xn,x

n-1,…,x0］(x-xn)(x-xn-1)…(x-x1)

根据公式(4―33)易得用后差代替均差,可得牛顿后差插值多项式令

x=xn+th（t不一定是整数）则

xn-k=xn-khx-xn-k=(t+k)h,k=0,1,2,…,n于是牛顿后差插值多项式又可写成(4―37)或记为其余项为(4―38)这里

ωn+1(x)=t(t+1)(t+2)…(t+n)hn+1表4―5表4―6例5分别作出

f(x)=x2+x+1

的前差和后差表。解前差表见表4―7;后差表见表4―8。表4―7表4―8例6给出正弦函数sinx由x=0.4到0.7的值(h=0.1),试分别用牛顿前差和后差公式计算sin0.57891的近似值。解作差分表4―9。表4―９利用牛顿前差公式利用牛顿后差公式§8三次样条插值

8.1三次样条插值函数的定义设给定区间［a,b］上n+1个点

a=x0＜x1＜x2＜…＜xn=b

如果函数s(x)满足:(1)在每一个子区间［xk,xk+1］(k=0,1,…,n-1)上,s(x)是一个不超过三次的多项式,且

s(xi)=f(xi),i=0,1,2,…,n(4―39)

(2)函数s(x)在［a,b］上具有直到二阶的连续导数,则称s(x)是f(x)以x1,x2,…,xn-1为内部基点的三次样条插值函数,并称(xi,yi)(i=0,1,2,…,n)为样条插值函数的样点。

8.2三次样条插值法按照三次样条插值函数的定义,s(x)在每一个子区间［xk,xk+1］上是一个不超过三次的多项式,故s″(x)是线性函数。令

mk=s″(xk),k=0,1,2,…,n(4―40)

设x∈［xk,xk+1］,则过两点(xk,mk)与(xk+1,mk+1)的直线所表示的线性函数为(4―41)其中

hk=xk+1-xk

对(4―41)式两端连续求两次积分得(4―42)(4―43)其中Ak、Bk为积分常数。根据插值原则由式(4―43)得到方程(4―44)从而解出Ak和Bk,即(4―45)(4―46)由式(4―43)可看出三次样条插值函数s(x)仅与mk、mk+1有关系,因此只要求得各个mk,则各个子区间［xk,x

k+1］上的三次样条函数也就确定了。下面介绍求mk的方法。当x∈［xk-1,xk］时,(4―47)式应表示为当x∈［xk,x

k+1］时,(4―48)(4―49)根据三次样条插值函数的定义,应有整理后得到(4―50)那么于是(4―50)式可简写成(4―51)也即(4―52)

此是含有n+1个未知量m0,m1,…,mn的n-1个方程的方程组,我们可根据实际问题的具体要求补充两个附加条件,就可求出各个mk。在区间［a,b］的端点a和b(即x0和xn)处对样条插值函数加以限制,称为端点条件。常用的端点条件有以下几种:①函数y=f(x)在两端点x0及xn处的导数y′0和y′n为已知。此时要求由式(4―48)和(4―49)得到也即(4―53)其中(4―54)式(4―52)与式(4―53)两个方程组联立成

其几何解释为曲线在两端点的斜率。②函数y=f(x)在两端点x0,xn处的二阶导数为零。此时要求其几何解释为曲线在两端点的曲率为零。③函数y=f(x)是一个以b-a=xn-x0为周期的周期函数。此时

y0=yn

相应也要求样条插值函数s(x)也具有周期性,故在端点要求满足条件由于hn=h0,mn=m0,yn=y0利用式(4―48)和式(4―49)可得到于是有(4―57)例7给出四个样点(1,1)、(2,3)、(4,4)、(5,2),求其各个子区间上的样条插值函数s(x)(设m0=m3=0),并求f(3)。解给定样点的函数表为x1234y1342于是求mk的方程组为则关于m1,m2的方程组为解得在［1,2］上的样条插值函数为在［2,4］上的样条插值函数为在［4,5］上的样条插值函数为并且§9数值微分

9.1用插值法求数值微分用插值多项式Pn(x)近似地表示函数f(x),即

f(x)≈Pn(x)

于是有

f(k)(x)≈P(k)n(x)

其余项相应地为R(k)n(x)。设插值基点为等距分布,由牛顿前差插值多项式其中由于于是即因为而当x=xi时,s=i,此时(4―59)(4―60)特别当x=x0时,s=0,则(4―61)

1.两点公式(n=1)于是在区间［x0,x2］上有(4―62)

2.三点公式(n=2)于是在区间［x0,x2］上有

9.2用三次样条函数求数值微分设s(x)是f(x)在各区间［xk,xk+1］上的三次样条插值函数,则在区间［xk,xk+1

］上可通过三次样条函数来求f(x)的数值微分。

1.一阶数值微分公式(4―65)若只求基点xk(k=0,1,…,n-1)上的一阶导数值,则(4―66)

2.二阶数值微分公式特别,若只求基点上的二阶导数值,则(4―67)

(4―68)§10曲线拟合法设一组观测数据为xx0x1x2x3…xnyy0y1y2y3…yn能否找到一个简单易算的p(x)

，使得f(x)

p(x)已知f(x)

在某些点的函数值：xx0x1…xm

f(x)y0y1…ym

m

通常很大

yi

本身是测量值，不准确，即yi

f(xi)不要求f(xi)通过所给的数据点，但能表述（xi，yi）的趋势已知f(xi)的基本形式这时不要求p(xi)=yi,而只要

p(xi)

yi

总体上尽可能小

曲线拟合

使最小

使最小

p(xi)

yi

总体上尽可能小

常见做法不可导，求解困难，分析困难最小二乘法：目前最好的多项式曲线拟合算法设函数关系y=f(x)的一组观测数据为(xi,yi)(i=0,1,2,…,n),欲求一个m(m＜n)次多项式

Pm(x)=α0+α1x+…+αmxm的平方和最小最小二乘法R称为用Pm(x)拟合f(x)的总偏差根据极值理论，要使得R

达到极小，必有：称此方程组为正则方程组。通过它可求出a0,a1,…,am。下面对m=2的情形作具体讨论。

拟合函数基本形式为：

总偏差为：正则方程为：写成矩阵形式：例8设有一组数据表x1345678910y2781011111098试用二次