数值分析 第2章 插值法part-1

计算方法南京大学计算机科学与技术系第二章插值法

(Interpolation)2023/1/31§2.0为什么要研究插值法

插值法是广泛应用于理论和实践的重要数值方法,它是用简单函数为离散数组建立连续模型；为非有理函数提供好的数值逼近。反映自然规律数量关系的函数主要有三种方法：

解析表达式

图象法

数表法§2.0为什么要研究插值法

许多函数关系数据是用数表法给出(如观测和实验得到的数据)。但用离散的函数值进行理论分析和设计，是不方便或是不可能的。因此需要寻找与已知函数值相符，并且形式简单的插值函数(或近似函数)。另外一情况是，函数表达式给定，但其形式不适宜计算机使用，一些涉及连续变量问题的计算需经过离散化后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法。2023/1/31

插值函数p(x)作为f(x)的近似，可以选不同类型的函数,如多项式、三角多项式、有理分式；其函数性态为光滑或分段光滑。其中多项式插值占有重要地位：

(a)

结构简单、计算机容易处理、任何多项式的导数和积分也易确定。(b)

Weierstrass逼近定理：定义在闭区间上的任何连续函数f(x),存在多项式p(x)一致逼近f(x),并达到所要求的精度。本章主要考虑多项式插值问题。内容§2.1引言插值问题的一般提法§2.2

拉格朗日(Lagrange)插值§2.3

均差与Newton插值公式§2.4

差分与等距节点插值公式

§2.5

埃尔米特插值§2.6

分段低次插值§2.7三次样条插值2023/1/31§2.1插值问题的一般提法

当函数y=f(x)复杂或未知，在区间[a,b]内的节点

a=x0<…<

xn=b

处得函数值y0,…,

yn

其中

y0

=f(x0

),…,yn

=f(xn)，

由此构造一个简单的近似函数P(x)f(x)，满足条件:P(xi)=f(xi)(i=0,…n)。

这里的P(x)称为f(x)的插值函数。2023/1/31

插值的几何意义

从几何上看，插值就是求一条曲线使其通过给定的个点，并且与已知曲线有一定的近似度。从几何上看x

0y

y=p(x)a=x0x1x2x3xn=b

•(xi,yi)y=f(x)曲线P

(

x)

近似f

(

x)

x0,x1,…,xn插值节点,

函数P(x)称为函数y=f(x)的插值函数，区间[a,b]称为插值区间。

[a,b]内任一点x处,P(x)可作为f(x)的近似.插值法的适用■1.求函数表上两值之间未列出的函数值.

x1.51.61.7ln(x)0.4054650.4700040.530628需要求出ln(1.64)如已知f(x)=ln(x)的函数表:■2.已知y=f(x)在若干点的函数值,求经过各点(xi,yi)的简单函数P(x).

xi00.51

yi1

0.606530.36788例如,已知可求2次多项式P(x)=1-0.941757x+0.309636x2满足P(0)=1,P(0.5)=0.606531,P(1)=0.367879(yi=f(xi))■3.函数f(x)难以计算,希望在区间[a,b]找到简单函数P(x)代替f(x),以便计算.yx0aby=f(x)y=P(x)例子:f(x)=arctan(x),在[-1,1]区间上,可用简单函数多项式P(x)=0.987733x-0.202335x3

代替f(x)例.(插值问题的一般解法)已知函数f(x)有如下数据:求f(x)的插值多项式p(x)，并求f(x)在x=0.5处的近似值。插值问题是否可解.若有解,是否唯一.如何求插值函数P(x).P(x)与f(x)的误差如何估计.当插值节点无限加密时,P(x)是否收敛于f(x).插值法的研究内容存在唯一性定理：y＝f(x)在[a,b]有定义,设a=x0<x1<x2<···<xn=b已知f(x)在xi处的函数值yi=f(xi),(i=0,1,···,n)则存在唯一的多项式P(x),

使得:

P(xi)=yi,

(i=0,1,···,n)证明:

设P(x)=a0+a1x+a2x2+.....+anxn条件P(xi)=yi

代入,得:这是关于未知系数a0,a1,....,an的n+1阶线性方程组插值条件其系数行列式为Vandermonde行列式

因此,关于a0

,a1,....,an的线性方程组有唯一解.即存在唯一的多项式P(x)=a0+a1x+a2x2+.....+anxn满足插值条件.n=1已知x0,x1;

y0,

y1，求使得111001)(,)(y1x1Ly0x0L==可见L1(x)是过(x0,y0)和(x1,y1)两点的直线。§2.2拉格朗日多项式

LagrangePolynomial

l0(x)l1(x)线性插值基函数1.线性插值与抛物插值:2023/1/31线性插值与其基函数示意图2023/1/31显然,是过、、三点的一条抛物线。已知,求，n=2使得2023/1/31显然,是过、、三点的一条抛物线。已知,求，n=2使得仿照线性插值基函数的构造方法，令抛物线基函数称其为抛物线插值基函数(如上右图所示)。

抛物线插值基函数于是抛物线基函数推导n+1节点的Lagrange插值多项式推导n+1节点的Lagrange插值多项式希望找到li(x)，i=0,…,n

使得

li(xj)=ij

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

。每个li有n

个根x0,…

xi,…xn一般情形，

k=0,1

,⋯,

n

.k=0,1

,⋯,

n

.由得:设函数表则满足插值条件的多项式Lagrange插值多项式其中,2023/1/31x-1

0

1

2f(x)-2

-2

12

已知连续函数f(x)的函数表如下：求方程f(x)=0在(-1,2)内的近似根。例题2023/1/31解：利用Lagrange插值法有

取初值x=0.5，利用牛顿法求解可得f(x)在(-1,2)内的近似根为0.67433。

解方程x-1

0

1

2f(x)-2

-2

12

已知连续函数f(x)的函数表如下：试求方程f(x)=0在(-1,2)内的近似根。例题以下的问题：如何分析插值的余项？

(1)先求插值基函数.

(2)构造插值多项式.构造插值多项式的方法：2023/1/31

，且f

满足条件,

Lagrange插值法插值余项设节点在[a,b]内存在,考察截断误差:2023/1/31Lagrange插值法的插值余项

，且f

满足条件,设节点在[a,b]内存在,截断误差(或插值余项):2023/1/31Lagrange插值法的插值余项

，且f

满足条件,设节点在[a,b]内存在,截断误差(或插值余项):证明：由已知条件得到：于是有：其中是与x

有关的待定函数。2023/1/31任意固定xxi(i=0,…,n),考察根据插值条件及余项定义，可知在点故处均为零，在上有n+2个个零点，根据Roll定理

在的每两个零点间至少有一个零点，故在内至少有n+1个零点，对再用Roll定理，可知在内至少有n

个零点，依此类推，在内至少有一个零点，记为使得:2023/1/31由于不能确定，因此不能确定误差的大小但如能求出，那么用逼近的截断误差限是：2023/1/31当n=2时,当n=1时，当

f(x)为任一个次数n

的多项式时，,可知，即n+1个节点的插值多项式对于次数n的多项式是精确的。注意2023/1/31

给定xi=i+1,i=0,1,2,3,4,5.

下面哪个是l2(x)的图像？问题2023/1/31算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。2023/1/31算例1Lagrange插值法已知，，用线性插值及抛物线插值计算的值并估计截断误差。线性插值时取

解:2023/1/31其截断误差为：其中,因为可取于是：

2023/1/31用抛物线插值时，取所有节点，得到余项讨论：其中：2023/1/31算例2Lagrange插值法利用100，121的开方计算.由于:

解:利用Lagrange插值法有于是,的精确值为10.72380529…,因此,近似值10.71428有3位有效数字.

Return2023/1/31第二章习题P.42第2题第2题改用L二次

插值计算.P.42第3题（线性插值用x=0.5,0.6两点；二次插

值用x=0.5,0.6,0.7三点）,估计误差P.42第4题第6题第8题p.43第19题2023/1/31k=0,1,⋯,n

.上次：Lagrange插值xx0x1….xnyy0y1….yn设y=f(x),已知：Lagrange插值公式：插值余项:2023/1/31x2345y1.43.35.58.0f(x)=x·lnx，已知2次插值多项式求f(4.5)，用余项公式估计误差§2.3差商与Newton插值公式Lagrange插值虽然易算，但若要增加节点时，全部基函数li(x)都需重新计算。2023/1/31增加节点需要重新计算基函数,给计算带来不便看2次和3次L插值公式,在[0,3]求f(x)的插值函数:寻求如下形式的插值多项式：其中为待定系数，由插值条件确定.由线性代数知识可知：任一n次多项式都可以表示成n+1个线性无关多项式的线性组合。那么，可以将这n+1个多项式作为插值基函数.而,线性无关设插值多项式P(x)具有如下形式：

再继续,形式更复杂,为此引入差商和差分的概念.P(x)应满足插值条件：有：§2.3.1差商（也称均差）的及其性质从零阶差商出发，归纳地定义各阶差商:称为函数关于点的一阶差商.

一般地，关于的k

阶差商:记函数在的值，称为关于的零阶差商。

一般，关于的n阶差商:n阶差商的概念2023/1/31或差商的基本性质性质1：差商可表示为函数值的线性组合，即：f[x0,x1,…,xk]=c0

f(x0)+c1f(x1)+…+ckf(xk)其中,因此,差商f[x0,x1,…,xn]与节点x0,x1,…,xn次序无关.从而有:性质2：差商与所含节点次序无关性质3：性质4：设f(x)在[a,b]

存在n阶导数，且

，则

使得:

例.

f(x)=3x4-5x3+4x-8,

则f[0,1,2,3,4]f[1,2,3,4,5,6]=f(4)/4!=3,=f(5)/5!=0差商的计算一阶差商二阶差商三阶差商四阶差商2023/1/31差商表已知计算三阶差商解：列表计算算例2023/1/31§2.3.2牛顿插值公式根据差商的定义，把x看成[a,b]上的一点，可得：2023/1/31

牛顿插值公式把后一式代入前一式根据差商的定义，把x看成[a,b]上的一点，显然Nn(x)满足插值条件，且次数不超过n,它就是插值多项式，第i

次项系数为：

其中我们称为牛顿插值多项式.

已知的函数表，求4次牛顿插值多项式,

并求算例2023/1/31从表中可以看到4阶差商几乎为0，故取4次插值多项式即可，于是：0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表计算

已知f(x)的函数表，求4次牛顿插值多项式,并求f(0.596).算例:0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表计算

已知的函数表，求4次牛顿插值多项式,

并求算例截断误差为：§2.4差分与等距节点插值公式设函数f(x)在等距节点上的值fi=

f(xi)为已知，这里h为常数，称为步长。

下面来讨论差分的定义。2023/1/31在前面的讨论中，节点是任意分布的，但实际上经常遇到等距节点的情况，这时插值公式可以得到简化，为此，我们先介绍差分的概念。差分的定义符号、、分别称为向前差分算子、向后差分算子、中心差分算子.2023/1/31记号称为f(x)在xi

处以h为步长的向前差分、向后差分、中心差分一般地可定义m阶差分：用一阶差分可以定义二阶差分高阶差分中心差分定义为:以此类推.不变算子I、移位算子E由差分的定义及不变算子和移位算子有如下性质:差分的性质性质1：各阶差分均可用函数值表示，如：2023/1/31性质2：某点的函数可用各阶差分来表示：性质3：差商与差分有如下关系：2023/1/31性质4：差分与导数有如下关系：差分的计算Return2023/1/31等距节点的Newton公式等距节点前插公式等距节点后插公式2023/1/31

和均是n次多项式,且均满足插值条件:

由多项式的唯一性,,因而,两个公式的余项是相等的,即当插值多项式从n-1

次增加到n次时,拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值,只需用表格再计算一个n阶差商,然后加上一项即可。牛顿插值公式和Lagrange插值公式比较Return2023/1/31例.已知f(x)=sinx在0.5,0.6,0.7,0.8的值,分别用二次,三次Newton插值求sin0.57891.解:节点等距,先求差分表令

x=x0+th=0.57891,则t=0.7891=0.547139实际误差:sin0.57891-0.547139=-2.713E-51)二次插值取x0=0.5,x1=0.6,x2=0.7h=0.12)三次插值取x0=0.5,x1=0.6,x2=0.7,x3=0.8,h=0.1,t=0.7891实际误差:sin0.57891-0.547112=1.3287E-7§2.5埃尔米特(Hermite)插值拉格朗日和牛顿均只保证函数插值；实际问题有时需要导数也插值；满足这种需要的插值称为埃尔米特插值.2023/1/31埃尔米特插值的一般提法为：设函数在节点的函