插值法第一次(new)

数值逼近

(NUMERICALAPPROXIMATION)插值法（第2章）函数逼近与曲线拟合（第3章）数值积分与数值微分（第4章）2016.3.10第二章插值（INTERPOLATION）法

了解插值的概念。掌握拉格朗日(Lagrange)插值法及其余项公式。了解均差的概念及基本性质，掌握牛顿插值法。了解差分的概念，会牛顿前插公式、后插公式。会埃尔米特(Hermite)插值及其余项公式。知道高次插值的病态性质,会分段线性插值和分段埃尔米特插值及其误差和收敛性。会三次样条插值,知道其误差和收敛性。条件

已知计算sin50的近似值

并估计误差。需求问题实例更一般情况问题：需要计算函数的近似关系表达式、在未知点的函数值条件：一组有函数关系的自变量和因变量的测量数据本节课主要内容插值问题的描述Lagrange插值多项式的存在唯一性，构造形式，基函数性质误差分析应用

描述事物之间的数量关系：函数。有两种情况：一是表格形式——一组离散的数据来表示函数关系；另一种是函数虽然有明显的表达式，但很复杂，不便于研究和使用。从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式来代替，从而使问题得到简化。一般地，构造某种简单函数代替原来函数。插值法就是一种基本方法§0引言(1)(2)(2)在x为特殊值时,是好计算的,则(2)可转化为(1)当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn

处测得函数值y0

=f(x0),…yn

=f(xn)，由此构造一个简单易算的近似函数g(x)

f(x)，满足条件g(xi)=f(xi)(i=0,…n)。这里的g(x)

称为f(x)的插值函数。x0x1x2x3x4xg(x)

f(x)（1.1）

设函数在区间上有定义，且已知在点上的值，若存在一简单函数，使成立，就称为的插值函数，点称为插值节点，包含节点的区间称为插值区间，求插值函数的方法称为插值法.

2.1.1插值问题的提出（1.2）

若是次数不超过的代数多项式，其中为实数，就称为插值多项式，相应的插值法称为多项式插值.本章只讨论多项式插值与分段插值.

若为分段的多项式，就称为分段插值.

若为三角多项式，就称为三角插值.即插值函数：Lagrange,Newton,Hermite,Spline由此可以得到关于系数的元线性方程组上的函数值,求次数不超过的多项式，使

2.1.2多项式插值（1.3）

设在区间上给定个点（1.4）此方程组的系数矩阵为称为范德蒙德（Vandermonde）矩阵,由于互异，故（1.5）因此线性方程组（1.4）的解存在且唯一.

定理1满足条件（1.3）的插值多项式是存在唯一的.(证明)§1拉格朗日多项式niyxPiin,...,0,)(==求n

次多项式使得条件：无重合节点，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0,y0

)和(x1,y1

)两点的直线。)(1xP101xxxx--010xxxx--=y0

+y11.1线性插值两点式)()(0010101xxxxyyyxP---+=点斜式)(001010xxxxxxy---+=(())ff（解的存在唯一性）1.2二次插值n=2已知x0

,x1

,x2;

y0

,

y1

,y2,求使得002,)(yxP112)(yxP==222)(yxP=,

为求P2(x),将三点代入其表达式,即可得到三个方程式,从而联立方程组解出系数a0,a1,a2即可:方程组的解是否存在?若存在解,是否唯一?!当x0

,x1

,x2互异时,方程组的解存在且唯一.注：显然有,求n次插值时,由n+1个点可有n+1个方程,联立方程组即可求出插值多项式的n+1个系数.

然而,方程组的求解也并不是一件容易的事。1.2.1待定系数法

对于线性插值的两种形式解进行适当的分析,从中寻求规律而得到启发,就有了所谓的拉格朗日插值法(公式)和牛顿插值(公式).

我们先来看看如何得到二次拉格朗日插值公式（和牛顿插值公式（为讨论方便，留待后述））.

首先,线性插值的两点式可看作是两个特殊的一次式的一种线性组合.101xxxx--010xxxx--)(1xP=y0

+y1==10)(iiiyxl两点式l0(x)l1(x)实质上（）和（）即是满足函数表的一次插值多项式,称l0(x)和l1(x)为以x0,x1为节点的基本插值多项式，也称为线性插值的插值基函数。

于是，线性插值即是用基函数的线性组合来构造的.1.2.2基函数法称为拉氏基函数，满足li(xj)=ij

显然有l0(x)+l0(x)≡1.这里，l0(x)和l1(x)具有如下性质：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,

由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合:这时，l0(x),l1(x),l2(x)都是二次多项式，且应满足满足(2.1)式的

li(x)是否存在?若存在，具有什么形式呢?（2.1）同理可得

l1(x)＝1(x－x0)(x－x2),

l2(x)＝2(x－x0)(x－x1),1＝(x1－x0)(x1－x2)12＝(x2－x0)(x2－x1)1此即二次拉格朗日插值公式,其中,l0(x),l1(x),l2(x)是满足(2.1)的特殊(基本)二次插值多项式;称为二次插值基函数.P2(x)=y0+y1+y2(x-x0)(x-x2)(x1-x0)(x1-x2)(x-x1)(x-x2)(x0-x1)(x0-x2)(x-x0)(x-x1)(x2-x0)(x2-x1)

先考虑l0(x)。因l0(x)是以x1,x2

为零点的二次多项式,所以它可写成l0(x)＝0(x－x1)(x－x2),

其中0

是待定系数。又因为l0(x0)=1，所以0(x0－x1)(x0－x2)＝1，则可有0＝(x0－x1)(x0－x2)1

l0(x)＝0(x－x1)(x－x2),

n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li有n

个根x0…

xi…xn=-=---=njjijiniiixxCxxxxxxCxl00)())...()...(()(-==jijiiiixxCxl)(11)(

拉格朗日多项式与有关，而与无关节点f1.3n

次插值定理(唯一性)满足的n

阶插值多项式是唯一存在的。证明：(存在性可利用Vandermonde

行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n

阶多项式Pn(x)满足Pn(xi)=yi

。考察则Qn

的阶数n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n

，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。设节点在[a,b]内存在,考察截断误差，且f

满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。推广：若使得使得存在使得Rn(x)至少有个根n+1=-=niinxxxKxR0)()()(任意固定x

xi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2

个不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意这里是对t求导=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx

1.4插值余项

(Remainder)注：

通常不能确定x

,而是估计,x(a,b)

将作为误差估计上限。当

f(x)为任一个次数n

的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。例1

求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式.解：三个插值节点及对应的函数值为由抛物插值公式得n+1个节点的Lagrange插值多项式不超过n次例2：已知分别利用sinx的1次、2次Lagrange插值计算sin50

并估计误差。解：n=1分别利用x0,x1

以及x1,x2

计算利用这里而sin50=0.7660444…)185(50sin10pL0.77614外推

(extrapolation)

的实际误差0.01010利用sin500.76008,内插

(interpolation)

的实际误差0.00596内插通常优于外推。选择要计算的x

所在的区间的端点，插值效果较好。n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……

例3

考虑下述的插值法问题：求二次多项式P(x)，满足P(x0)=y0,其中是已给的数据并给出使这一问题的解存在且唯一的条件.解：设则由已知条件有即所以故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为这就是P（x）存在且唯一的条件。HW:p.481,2,4,5(1)1.5拉格朗日插值公式的优缺点课堂练习证明？？本节主要内容Newton插值等距差分公式

Lagrange插值公式(利用插值基函数很容易得到):

含义直观,结构紧凑,在理论分析中非常方便;

计算机上实现也很容易.也有一些缺点：

一是计算量大，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，全部插值基函数均要随之变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要增加一项计算。

为克服上述两个缺点,

努力：把插值多项式变形为便于计算的形式。希望：计算改变的过程中,尽可能能利用已有的计算结果.

下面我们将看到,这是可能的。我们可以有具有“承袭性”的所谓牛顿公式。)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]

二次牛顿插值多项式

我们再看线性插值的点斜式:)(00xxy-+=f[x0,x1]常数(差商)

由此启发，我们希望二次插值也能类似地有有规律的组合表达式:P2(x)=0+1(x-x0)+2(x-x0)(x-x1)利用P2(x0)=y0有:0=y0,利用P2(x1)=y1有:1=0101xxxx--(())ff=f[x0,x1],利用P2(x2)=y2有:2=f[x0,x1]

(x2-x0)(x2-x1)

(x2-x0)(x2-x1)0xx2-(())ff

(x2-x0)-f[x0,x2]f[x0,x1]

x2-x1

=-=f[x0,x1,x2];P2(x)=f(x0)

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

x=x0时0注:1.事实上,从上述可看出二次牛顿插值公式是用待定系数法求得的;2.它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0)

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

1,(x-x0),(x-x0)(x-x1)即函数的线性组合,组合系数为本质上还是基函数法.

更一般地，n+1个节点的插值多项式，我们希望由上述类似的一组特殊函数：来线性组合为：1,(x-x0),(x-x0)(x-x1)，……，(x-x0)(x-x1)…(x-xn)那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法.容易发现,计算a0,a1,a2,…,an

是很有规律的.

定义2

称为函数f(x)关于点x0,xk的一阶均差.称为f(x)的二阶均差.一般地,称为f(x)的k阶均差(差商).f[x0,xk]=f(xk)-f(x0)xk-x0f[x0,x1,xk]=f[x0,xk]-f[x0,x1]xk-x1f[x0,x1,…,xk]=f[x0,…,xk-2,xk]-f[x0,x1,…,xk-1]xk-xk-1均差有如下的基本性质:1ºk阶均差可表示为函数值f(x0),f(x1),…,f(xk)的线性组合,即f[x0,x1,…,xk]=f(xj)(xj-xj+1)…(xj-xk)…(xj-xj+1)(xj-x0)∑

kj=0这个性质可用归纳法证明.这个性质也表明均差与节点的排列次序无关,称为均差的对称性,即f[x0,x1,…,xk]=f[x1,x0,x2,…,xk]=…=f[x1,…,xk,x0]f[x0,x1,…,xk]=f[x1,…,xk-1,xk]-f[x0,x1,…,xk-1]xk-x02º由性质1º可得:f(n)(ξ)n!3º若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn[a,b],则n阶均差与导数关系如下:（证明推后到余项分析）12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)Rn(x)ai=

f[x0,…,xi]二、牛顿插值公式Rn(x)Nn(x)ωn+1(x)

多项式Nn(x)显然满足插值条件,即Nn(xj)=f(xj),(j=1,…,n),且次数不超过n,由唯一性定理它就是前述的Ln(x),其系数为

Nn(x)称为牛顿均差插值多项式,它比拉格朗日插值多项式计算量省,且便于程序设计.注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]均差计算可列均差表如下：

例1

依据如下函数值表建立不超过3次的拉格朗日插值多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性.