数值分析插值法

数值分析课件插值法1第1页，课件共93页，创作于2023年2月2插值法

许多实际问题都用函数来表示某种内在规律的数量关系

但函数表达式无法给出，只有通过实验或观测得到的数据表函数表达式已知，但较复杂，计算函数值或积分比较困难如何根据这些数据推测或估计其它点的函数值？例：已测得在某处海洋不同深度处的水温如下：

深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500、600、800米…）处的水温。问题的提出

第2页，课件共93页，创作于2023年2月3问题的数学提法已知[a,b]上的函数y=f(x)在n+1个互异点处的函数值:fnf2f1f0f(x)xnx2x1x0x求简单函数Pn(x)，使得x0x1x2x3x4xP(x)

第3页，课件共93页，创作于2023年2月4插值基本概念已知函数y=f(x)

在[a,b]

上有定义，且已经测得在点

a

x0

<x1

<···

<xn

b处的函数值为

y0

=f(x0)，…，yn

=f(xn)如果存在一个简单易算的函数P(x)，使得

P(xi)=f(xi)，i=0,1,...,n则称P(x)为f(x)的插值函数插值区间插值节点求插值函数P(x)

的方法就称为插值法插值节点无需递增排列，但必须确保互不相同！插值条件第4页，课件共93页，创作于2023年2月5其插值函数的图象如图第5页，课件共93页，创作于2023年2月6常用插值法

多项式插值：P(x)为多项式函数---最常用的插值函数

分段插值：P(x)为分段多项式函数

三角插值：P(x)为三角函数……

多项式插值

polynomialinterpolationWeierstrass定理对于在[a,b]上的连续函数f以及,总存在多项式P(x)满足第6页，课件共93页，创作于2023年2月7多项式插值

对于多项式插值，我们主要讨论以下几个问题：

满足插值条件的多项式P(x)是否存在且唯一？若满足插值条件的P(x)存在,又如何构造出P(x);即插值多项式的常用构造方法有哪些？用P(x)代替f(x)的误差估计当插值节点无限加密时，插值函数是否收敛于f(x)。第7页，课件共93页，创作于2023年2月8插值多项式的存在唯一性ExistenceandUniquenessofinterpolationpolynomials?且满足第8页，课件共93页，创作于2023年2月9上述方程组的系数行列式为n+1阶Vandermond行列式插值多项式的存在唯一性定理已知函数y=f(x)

在[a,b]

上n

+1

个点

a

x0

<x1

<···

<xn

b处的函数值为

y0

=f(x0)，…，yn

=f(xn)求次数不超过

n

的多项式P(x)=c0+c1x+···+cnxn，使得P(xi)=yi，i=0,1,...,n

存在且唯一第9页，课件共93页，创作于2023年2月10关于唯一性证明的几点说明

插值多项式的唯一性表明，对同一组节点，它们的插值多项式是唯一的，可能由不同的方法，会得到不同形式的插值多项式，但它们之间一定可以相互转化，一定会相同，当然误差也一样。

上述证明是构造性的（给出解决问题的方法）即以通过解线性方程组来确定插值多项式，但这种方法的计算量偏大，计算步骤较多，容易使舍入误差增大。因此实际计算中不采用这种方法，而用下面介绍的几种常用的方法。第10页，课件共93页，创作于2023年2月11基函数插值法通过基函数来构造插值多项式的方法就称为基函数插值法Zn(x)

=

{次数不超过n

的多项式的全体}记n+1维线性空间设z0(x),z1(x),...,zn(x)

构成Zn(x)

的一组基，则插值多项式P(x)=a0z0(x)+a1z1(x)

+···+anzn(x)寻找合适的基函数确定插值多项式在这组基下的表示系数基函数法基本步骤

若通过前述方法来求解插值多项式，不但计算工作量较大,且难于得到简单表达式第11页，课件共93页，创作于2023年2月12Lagrange插值

十八世纪法国数学家Lagrange提出了易于掌握和计算的统一公式称为Lagrange插值公式

线性插值已知两个插值点及其函数值：xx0x1f(x)f0f1求一次多项式

first-degreepolynomial使得：第12页，课件共93页，创作于2023年2月13线性插值所以，按Cramer法则，有唯一解点斜式两点式第13页，课件共93页，创作于2023年2月14线性插值的线性组合得到，即：注意到：称，为线性插值基函数由两点式看出，是由两个线性函数第14页，课件共93页，创作于2023年2月15

抛物线插值

已知三个插值节点及其函数值：f2f1f0f(x)x2x1x0x求一个二次多项式使得：抛物线插值第15页，课件共93页，创作于2023年2月16抛物线插值

（B-2）令：第16页，课件共93页，创作于2023年2月17抛物线插值所以为二次插值基函数第17页，课件共93页，创作于2023年2月18Lagrange插值设lk(x)是n次多项式，在插值节点x0,x1,…,xn上满足则称lk(x)

为节点x0,x1,…,xn

上的拉格朗日插值基函数

n次Lagrange插值第18页，课件共93页，创作于2023年2月19P(x)=y0l0(x)+y1l1(x)

+···+ynln(x)Lagrange插值多项式

Lagrange插值

Lagrange插值公式的标准型公式:第19页，课件共93页，创作于2023年2月20插值举例例：已知函数y=lnx

的函数值如下解：x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试分别用线性插值和抛物线插值计算

ln0.54的近似值线性插值：取x0=0.5,x1=0.6得将x=0.54

代入可得：ln0.54L1(0.54)=-0.6202为了减小截断误差，通常选取插值点x

邻接的插值节点第20页，课件共93页，创作于2023年2月21插值举例抛物线插值：取x0=0.4,x1=0.5,x2=0.6,可得ln0.54L2(0.54)=-0.6153在实际计算中，不需要给出插值多项式的表达式

ln0.54

的精确值为：-0.616186···可见，抛物线插值的精度比线性插值要高Lagrange插值多项式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。第21页，课件共93页，创作于2023年2月22matlabprogramfunctions=Lagrange(x0,y0)n=length(x0);%取长度s=0;forj=0:(n-1)t=1;

fori=0:(n-1)ifi~=jt=t*(x-x0(i+1))/(x0(j+1)-x0(i+1));endends=s+t*y0(j+1);ends第22页，课件共93页，创作于2023年2月23误差估计插值余项定理设f(x)

Cn[a,b](

n

阶连续可微)，且f(n+1)(x)在(a,b)

内存在，则对x[a,b]，有其中x(a,b)

且与x

有关,证明：如何误差估计:第23页，课件共93页，创作于2023年2月24插值余项由插值条件可知：Rn(xi)=0,

i=0,1,…,nRn(x)在[a,b]上至少有n+1个零点对任意给定的x[a,b](xxi,i=0,1,...,n)，构造辅助函数则在[a,b]

中有n+2

个互不相同的零点：x,

x0,

…,xnRn(x)可写成罗尔定理第24页，课件共93页，创作于2023年2月25插值余项由Rolle定理可知在(a,b)

内至少有n+1个不同的零点；同理可知在(a,b)

内至少有n

个零点；又f(x)

Cn[a,b]，且f(n+1)(x)在(a,b)

内存在以此类推，可知在(a,b)

内至少有一个零点，设为x

，即，x

(a,b)。第25页，课件共93页，创作于2023年2月26注余项公式只有当f(x)

的高阶导数存在时才能使用

从余项Rn(x)中的n+1(x)知，当点x位于x0,x1,…,xn的中部时，比较小，精度要高一些；而位于两端时，精度要差一点；若x位于x0,x1,…,xn的外部，一般称为外插，此时精度一般不理想，使用时必须注意。如果，则

x

与x

有关，通常无法确定,实际使用中通常是估计其上界第26页，课件共93页，创作于2023年2月27Lagrange基函数性质

当f(x)为一个次数n

的多项式时，有

故即n

次插值多项式对于次数n

的多项式是精确的

若f(x)=xk，kn，则有

特别地，当k=0时有Lagrange基函数的两个重要性质第27页，课件共93页，创作于2023年2月28插值误差举例例：已知函数y=lnx

的函数值如下x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试估计线性插值和抛物线插值计算

ln0.54的误差解：线性插值

x0=0.5,x1=0.6,(0.5,0.6)第28页，课件共93页，创作于2023年2月29插值误差举例抛物线插值：x0=0.4,x1=0.5,x2=0.6,(0.4,0.6)高次插值通常优于低次插值但绝对不是次

数越高就越好，嘿嘿…第29页，课件共93页，创作于2023年2月30Lagrange插值优点和缺点优点

公式简洁,理论分析方便容易编程上机缺点

基函数计算复杂，计算量大，计算量为每增加一个节点，插值多项式的所有系数都得重算；第30页，课件共93页，创作于2023年2月31第二章

插值法——Newton插值法第31页，课件共93页，创作于2023年2月32Newton插值为什么Newton插值Lagrange插值简单易用，但若要增加一个节点时，全部基函数lk(x)

都需重新计算，不太方便。设计一个可以逐次生成插值多项式的算法，即

pn(x)=

pn-1(x)+un(x)其中pn(x)和

pn-1(x)分别为n

次和n-1

次插值多项式解决办法

第32页，课件共93页，创作于2023年2月33新的基函数

设插值节点为

x0,…,xn

，考虑插值基函数组当增加一个节点xn+1时，只需加上基函数第33页，课件共93页，创作于2023年2月34Newton插值

此时

f(x)

的n

次插值多项式为问题如何从pn-1(x)得到pn(x)?怎样确定参数a0,…,an?

第34页，课件共93页，创作于2023年2月35Newton插值

再继续下去待定系数的形式将更复杂为此引入差商的概念

第35页，课件共93页，创作于2023年2月36差商什么是差商设函数f(x)，节点x0,…,xn

f(x)

关于点xi

,xj

的一阶差商f(x)

关于点xi

,xj,xk的二阶差商k

阶差商差商的一般定义

第36页，课件共93页，创作于2023年2月37差商的性质

差商可以表示为函数值的线性组合：用归纳法可以证明差商与节点的排序无关，即差商具有对称性其中i0,i1,…,ik

是0

,1,…,k

的任一排列第37页，课件共93页，创作于2023年2月38差商的性质

k阶差商与k阶导数之间的关系：若f(x)在[a,b]上

具有k阶导数，则至少存在一点(a,b)，使得若h(x)=cf(x)，则若h(x)=f(x)+g(x)，则若f(x)是n次多项式，则一阶差商f[x,xi]是n1次多项式。

第38页，课件共93页，创作于2023年2月39差商的计算第39页，课件共93页，创作于2023年2月40差商举例例：已知y=(x)

的函数值表，试计算其各阶差商i0123xi-2-112f(xi)531721解：差商表如下xiƒ(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-1第40页，课件共93页，创作于2023年2月41Newton插值公式Newton插值公式由差商的定义可得12……n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)Rn(x)第41页，课件共93页，创作于2023年2月42Newton插值公式f

(x)=Nn(x)+Rn(x)

其中Nn(x)

是n次多项式第42页，课件共93页，创作于2023年2月43注f

(x)

在x0,x1,…,xn

上的n次插值多项式是唯一的！Nn(x)Ln(x)且余项相同

第43页，课件共93页，创作于2023年2月44注

牛顿插值公式利用差商可简单地表为

因此,每增加一个结点,Newton插值多项式只增加一项,克服了Lagrange插值的缺点。第44页，课件共93页，创作于2023年2月45注

在实际计算中，特别是在函数f(x)的高阶导数比较复杂或

f(x)的表达式没有给出时，我们可以用差商表示的余项公式来估计误差。

实际计算中，当n+1阶差商变化不激烈时，可用近似代替

Newton插值多项式需要除法次,及2n次乘法,大约比Lagrange公式节省3到4倍工作量.

第45页，课件共93页，创作于2023年2月46插值举例例

给出的函数表（见表2-2），求4次牛顿插值多项式，并由此计算的近似值.

首先根据给定函数表造出均差表.

第46页，课件共93页，创作于2023年2月47插值举例

按牛顿插值公式，将数据代入于是

截断误差这说明截断误差很小，可忽略不计.第47页，课件共93页，创作于2023年2月48第二章

插值法——Hermite插值法第48页，课件共93页，创作于2023年2月49Hermite插值在许多实际应用中，不仅要求函数值相等，而且要求若干阶导数也相等，如机翼设计等。（i=0,1,…,n）满足函数值相等且导数也相等的插值方法成为Hermite插值

第49页，课件共93页，创作于2023年2月50Hermite插值

典型的Hermite插值两点三次Hermite插值插值节点：x0,x1插值条件：P(xi)=f(xi)，P’(xi)=f’(xi)，i=

0,1考虑插值问题

插值条件2n+2个，确定2n+2个待定系数。因此插值多项式最高次为2n+1第50页，课件共93页，创作于2023年2月51两点三次Hermite插值插值节点：x0,x1插值条件：P(xi)=f(xi)=yi，P’(xi)=f’(xi)=mi，i=

0,1模仿Lagrange多项式的思想，设其中均为3次多项式，且满足i,j=0,1

第51页，课件共93页，创作于2023年2月52两点三次Hermite插值将插值条件代入立即可得0(x),1(x),0(x),1(x)的表达式？

第52页，课件共93页，创作于2023年2月53两点三次Hermite插值0(x)第53页，课件共93页，创作于2023年2月54两点三次Hermite插值同理可得第54页，课件共93页，创作于2023年2月55两点三次Hermite插值满足插值条件P(x0)=f(x0)=y0，P’(x0)=f’(x0)=m0P(x1)=f(x1)=y1，P’(x1)=f’(x1)=m1的三次Hermite插值多项式为余项第55页，课件共93页，创作于2023年2月56非标准型Hermite插值

给(xi,yi)i=0,1,2,…,n及某些节点上的导数值（而不是全部导数值）Hermite插值问题的非标准型是：

例如求满足下列条件的Ｈermite插值多项式。12324123

基本方法为待定系数法

利用重节点差商构造Hermite插值第56页，课件共93页，创作于2023年2月57三点三次Hermite插值插值节点：x0,x1,x2插值条件：P(xi)=f(xi)，i=

0,1,2，P’(x1)=f’(x1)设将P’(x1)=f’(x1)代入可得

第57页，课件共93页，创作于2023年2月58三点三次Hermite插值由于x0,x1,x2是R(x)的零点，且x1是二重零点，故可设余项公式与Lagrange插值余项公式的推导过程类似，可得其中x

位于由x0,x1,x2和x所界定的区间内

第58页，课件共93页，创作于2023年2月59利用重节点差商构造Hermite插值定理设f(x)Cn[a,b]，

x0,…,xn为[a,b]

上的互异节点，则f[x0,…,xn]

是其变量的连续函数重节点差商一般地，n

阶重节点差商定义为第59页，课件共93页，创作于2023年2月60重节点Newton插值

在节点x0处的n次Hermite插值多项式

在Newton插值公式中，令xix0,i=

1,…,n,则Taylor插值多项式余项启示：将同时具有函数值和导数值条件的节点视为重节点处理第60页，课件共93页，创作于2023年2月61重节点Newton插值举例第61页，课件共93页，创作于2023年2月62重节点Newton插值举例第62页，课件共93页，创作于2023年2月63第二章

插值法——分段低次插值第63页，课件共93页，创作于2023年2月64多项式插值的缺陷n时Ln(x)不一定收敛于f(x)例：Runge现象

在插值方法中，为了提高插值多项式的逼近程度，常常提高多项式的次数，当插值节点增多，插值多项式的次数逐步提高时，是否逼近程度也越来越好呢？一般总认为Ln(x)的次数n越高，逼近f(x)的程度越好，实际上并非如此。

高次多项式插值的病态性质：

从计算的含入误差看，高次插值可能会产生严重的误差积累，即稳定性得不到保证。第64页，课件共93页，创作于2023年2月65Runge现象

Runge函数第65页，课件共93页，创作于2023年2月66Runge现象-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次数的Lagrange插值多项式的比较图第66页，课件共93页，创作于2023年2月67

在-2,2上L10(x)对f(x)逼近较好,但在端点附近很差.可以证明

即随着n的增长Ln(x)在两端点附近的振荡会越来越大.高次代数插值所发生的这种现象称为Runge现象.在上个世纪初由Runge发现.

增加节点并不一定能保证在两节点之间插值函数Ln(x)能很好地逼近f(x)，即高次插值（如7，8次上）在实际应用中很少被采用。常用的方法就是分段低次插值结论第67页，课件共93页，创作于2023年2月68分段插值用分段低次多项式函数来逼近原函数f(x)分段低次插值常见的分段低次插值分段线性插值分段三次Hermite插值每个小区间上用线性多项式来逼近f(x)

每个小区间上用三次Hermite多项式来逼近f(x)

第68页，课件共93页，创作于2023年2月69分段线性插值分段线性插值设a

x0

<x1

<···

<xn

b

为[a,b]

上的互异节点f(x)在这些节点上的函数值为y0,y1,…,yn记，

求分段函数Ih(x)

满足

Ih(x)

在每个小区间[xk,xk+1]上是线性函数第69页，课件共93页，创作于2023年2月70分段线性插值由以上条件直接可得Ih(x)在小区间[xk,xk+1]上的表达式x[xk,xk+1]，k=

0,1,…,n-1第70页，课件共93页，创作于2023年2月71误差估计误差估计在小区间[xk,xk+1]上有当h0

时，Ih(x)

在[a,b]

上一致收敛

到f(x)分段线性插值的不足：Ih(x)

在节点不可导第71页，课件共93页，创作于2023年2月72分段三次Hermite插值分段三次Hermite插值设a

x0

<x1

<···

<xn

b

为[a,b]

上的互异节点yk＝f(xk),mk＝f(xk)

，

k=

0,1,…,n

求分段函数Ih(x)

满足

Ih(x)

在每个小区间[xk,xk+1]上是三次多项式第72页，课件共93页，创作于2023年2月73分段三次Hermite插值由以上条件直接可得Ih(x)在小区间[xk,xk+1]上的表达式x[xk,xk+1]，k=

0,1,…,n-1误差估计第73页，课件共93页，创作于2023年2月74第二章

插值法——三次样条插值第74页，课件共93页，创作于2023年2月75分段低次插值具体作法：(1)把整个插值区间分割成多个小区间(2)在每个小区间上作低次插值多项式(3)将所有插值多项式拼接整一个多项式

基本思想：用分段低次多项式来代替单个多项式

优点：公式简单、运算量小、稳定性好、收敛性…

其光滑性较差。前面所介绍的方法只保证函数连续或其一阶导数连续，满足不了许多工程技术提出的对插值函数的光滑性有较高要求的计算问题例如，船体、飞机的机翼外形，内燃机的进、排气门的凸轮曲线，都要求曲线具有较高的光滑程度，不仅要连续，而且要有连续的曲率，即二阶导数连续。为解决这一类问题，导致产生了样条插值。第75页，课件共93页，创作于2023年2月76三次样条插值是分段三次多项式具有二阶连续导数插值条件：S(xi)=f(xi)=yi

给定插值节点

x0,x1,…,xn

[a,b]及函数值

f(xi)=yi

，i=0,1,2,…,n求一个定义在[a,b]上的插值函数S(x)，满足：三次样条插值第76页，课件共93页，创作于2023年2月77三次样条插值设插值节点为

a=

x0<x1<…<xn-1<xn=

b

若函数S(x)C2[a,b]，且在每个小区间[xj,xj+1]上是三次多项式，则称其为三次样条函数如果同时还满足

S(xi)=f(xi)=yi

，i=0,1,2,…,n

则称s(x)为f

(x)在[a,b]上的三次样条插值函数定义第77页，课件共93页，创作于2023年2月78三次样条插值S(x)满足：①S(x)C2[a,b]；②在[xj,xj+1]是三次多项式③

S(xi)=yi

，i=0,1,2,…,n其中sj(x)为[xj,xj+1]上的三次多项式，且满足sj(xj)=yj，sj(xj+1)=yj+1

j=0,1,…,n-1怎样计算三次样条插值函数第78页，课件共93页，创作于2023年2月79边界条件每个sj(x)

均为三次多项式，有4个待定系数，所以共有4n

个待定系数，故需4n

个方程才能确定。前面已经得到2n+2(n-1)=4n-2

个方程，还缺2个方程！实际问题通常对样条函数在两个端点处的状态有要求，即所谓的边界条件第79页，课件共93页，创作于2023年2月80常用的边界条件第一类边界条件：给定函数在端点处的一阶导数，即第二类边界条件：给定函数在端点处的二阶导数，即当S”(x0)=

S”(xn)=0时，称为自然边界条件，此时的样条函数称为自然样条函数第三类边界条件：设f(x)是周期函数，并设xn–x0是一个周期，于是要求S(x)满足第80页，课件共93页，创作于2023年2月81三次样条函数的计算设S”(xj)=Mj，j=0,1,2,…,n由于

sj(x)

是三次多项式，故

sj”(x)

为线性函数，且

sj”(xj)=Mj

,sj”(xj+1)=Mj+1下面计算S(x)在[xj,xj+1]的表达式sj

(x)

由线性插值公式可得求积分，可得第81页，课件共93页，创作于2023年2月82三次样条函数的计算将插值条件sj(xj)=yj，sj(xj+1)=yj+1

代入，即可确定积分常数c1和c2。整理后可得sj(x)

的表达式为只需确定M0,M1,…,Mn的值，即可给出sj(x)的表达式，从而可以得到S(x)的表达式。j=0,1,…,n-1第82页，课件共93页，创作于2023年2月83条件：易知6f[xj-1,xj,xj+1]djjj三次样条函数的计算第83页，课件共93页，创作于2023年2月84或j