第1节课-第一章-插值法-拉格朗日插值-分段插课件

第一章插值方法李书杰合肥工业大学计算机学院第一章插值方法李书杰提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念插值的基本概念例.某地区某年夏季时节间隔30天的日出日落时间为

5月1日5月31日 6月30日日出5：51 5：17 5：10日落19：04 19：38 19：50任意一天的日照时间？插值的基本概念例.某地区某年夏季时节间隔30天的日出日日照时间的变化设为

y(x)=a0+a1x+a2x2,求出a0，a1，a2，即可得到5、6月份的日照时间的变化规律。根据三组数据:(1,13.21)，(31,14.35)，(61,14.66)导出关于a0，a1，a2的线性方程组日照时间的变化设为y(x)=a0+a1x+a2x2,什么是插值?

插值法是函数逼近的一种简单但又十分重要的方法，实际中，f(x)是复杂多样的，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数

φ(x)来逼近f(x)。

自然地，希望φ(x)通过所有的离散点x3x4xφ(x)

f(x)x0x1x2什么是插值?插值法是函数逼近的一种简单但又十分重要定义1:函数y=f(x)给出一组函数值

x:x0x1x2……xny:y0y1y2……yn其中x0

,x1,x2,…,xn是区间[a,b]上的互异点,要在函数类Φ中求一个简单的函数φ(x)作为f(x)的近似表达式。使满足

(插值原则、插值条件)

这类问题称为插值问题。-----f(x)的插值函数;

f(x)-----被插值函数;x0,x1,x2,…,xn-----插值节点;

求插值函数的方法称为插值法。

若x∈[a,b],需要计算f(x)的近似值φ(x),则称x为插值点。

函数类Φ-----插值函数类;一、定义：定义1:函数y=f(x)给出一组函数值x:x0x当选择代数多项式作为插值函数类时，称为代数多项式插值问题:代数多项式插值问题:设函数y=f(x)在[a,b]有定义,且已知在n+1个点a≤x0<x1<……<xn≤b上的函数值y0,y1,……,yn.,要求一个次数不高于n的多项式

使满足插值原则称Pn(x)为f(x)的n次插值多项式。这样的插值多项式是否存在、唯一？

当选择代数多项式作为插值函数类时，称为代数多项式插值问题:设 Pn

(x)=a0+a1x+a2x2+……+anxn是y=f(x)在[a,b]上的n+1个互异节点x0,x1,…,xn的插值多项式，则求Pn(x)问题归结为求系数a0,a1,…,an。定理

n次插值问题的解是存在而且唯一的。证明：由插值条件：

Pn

(xk)=yk(k=0,1,…,n)得关于a0,a1,…,an的n+1阶线性方程组设 Pn(x)=a0+a1x+a2x2故Pn(x)存在且唯一。因故上式不为0。据Cramer法则，方程组解存在且唯一。是Vandermonde行列式.其系数行列式故Pn(x)存在且唯一。因故上式不为0。据Cramer法则提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念拉格朗日插值线性插值抛物插值一般情形拉格朗日插值线性插值给定插值节点

x0,x1，

y0=f(x0)，y1=f(x1).求线性插值多项式L1(x)=a0+a1x，使满足:

L1(x0)=y0,L1(x1)=y1.线性插值y=L1(x)的几何意义就是过点(x0,y0)，(x1,y1)的直线。给定插值节点x0,x1，y0=f(x0)，y1=f(xL1(x)的表达式：点斜式:变换可得:可以看到，L1(x)是由两个线性函数的线性组合得到，其系数分别为y0，y1。即L1(x)的表达式：点斜式:变换可得:可以看到，L1(l0(x)及l1(x)在节点x0,x1上满足条件：

l0(x0)=1,l0(x1)=0. l1(x0)=0,l1(x1)=1. 称l0(x)及l1(x)为线性插值基函数。(j,k=0,1)即l0(x)及l1(x)在节点x0,x1上满足条件：称l

n=1时的一次基函数为:y1O

xy1Oxn=1时的一次基函数为:yO抛物插值假定插值节点为x0,x1,x2

，求二次插值多项式

L2(x)，使 L2(xj)=yj (j=0,1,2)y=L2(x)的几何意义就是过(x0,y0)，(x1,y1)，(x2,y2)三点的抛物线。采用基函数方法，设 L2(x)=l0(x)y0+l1(x)y1+l2(x)y2此时基函数l0(x),l1(x),l2(x)是二次函数.抛物插值假定插值节点为x0,x1,x2，求二次插值多项l0(x0)=1,l0(x1)=0,l0(x2)=0.l1(x0)=0,l1(x1)=1,l1(x2)=0.l2(x0)=0,l2(x1)=0,l2(x2)=1.基函数l0(x),l1(x),l2(x)在节点上满足：满足上式的插值基函数很容易求出。即(j,k=0,1,2)l0(x0)=1,l0(x1)=0,l0(x2)=0故其中C为待定系数，由l0(x0)=1,得如求l0(x):因x1,x2为其零点，故可表为同理故其中C为待定系数，由l0(x0)=1,得如求l0(x)显然 L2(x)=l0(x)y0+l1(x)y1+l2(x)y2

满足条件 L2(xj)=yj (j=0,1,2)将l0(x),l1(x),l2(x)代入得显然 L2(x)=l0(x)y0+l1(x)y1+l2(x)n=2时的二次基函数为:n=2时的二次基函数为:设有n+1个互异节点x0<x1<…<xn，且

yi=f(xi) (i=0,1,2…,n)构造Ln(x)，使 Ln(xj)=yj

(j=0,1,2,…,n)一般情形定义若n次多项式lj(x)(j=0,1,…,n)在n+1个节点x0<x1<…<xn上满足条件(j,k=0,1,…,n)则称这n+1个n次多项式l0(x),l1(x),…,ln(x)为节点x0,x1,…,xn上的n次插值基函数。设有n+1个互异节点x0<x1<…<xn，且一般情形定义若由条件lk(xj)=0(j≠k)知x0,x1,

…,xk-1,xk+1…,xn都是n次多项式lk(x)的零点，故可设lk(x)=Ak(x-x0)(x-x1)…(x-xk-1)(x-xk+1)…(x-xn)

其中Ak为待定系数。再由lk(xk)=1有1=Ak(xk-x0)(xk-x1)…(xk-xk-1)(xk-xk+1)…(xk-xn)由x0,x1,

…,xk-1,xk+1…,xn互异，解出Ak由条件lk(xj)=0(j≠k)知x0,x1,…,从而得 (k=0,1,2,…,n)或记为(k=0,1,2,…n)次数不高于n的多项式在x0,x1,…,xn上的值分别为y0,y1,…,yn从而得 (k=0,1,2,…,n)或记为(k=0,1,n次插值基函数

(k=0,1,2,…,n)Lagrange插值多项式n=1时,线性插值n=2时,二次插值或抛物插值n次插值基函数 (k=0,1,2,…,n)Lagrang

取x0=4,y0=2，x1=9,y1=3，x2=16,y2=4.例1已知 求解（1）线性插值：取x0=4,x1=9 取x0=4,y0=2，x1=9,y1=3，x2=16取x0=4,x1=9,x2=16（2）抛物插值：取x0=4,x1=9,x2=16（2）抛物插值：例2

求过点(-1,-2),(1,0),(3,-6),(4,3)的三次插值多项式解以以为节点的基函数分别为:例2求过点(-1,-2),(1,0),(3,-6),则拉格朗日的三次插值多项式为则拉格朗日的三次插值多项式为使其满足利用拉格朗日基函数li(x),构造次数不超过n的多项式称为拉格朗日插值多项式。由插值多项式的唯一性,得

特别地,当n=1时又叫线性插值,其几何意义为过两点的直线.当n=2时又叫抛物（线）插值,其几何意义为过三点的抛物线.使其满足利用拉格朗日基函数li(x),构造次数不超过n的注意:对于插值节点,只要求它们互异,与大小次序无关;(2)插值基函数li(x)仅由插值节点xi(i=0,1,…,n)确定,

与被插函数f(x)无关;(3)插值基函数li(x)的顺序与插值节点xi(i=0,1,…,n)

的顺序一致.注意:(2)插值基函数li(x)仅由插值节点xi(提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念逐步插值拉格朗日插值公式计算函数的近似值若对原先选定的n+1个节点所得结果精度不够，

需要增加节点怎么办？给定区间[a,b]上一组插值节点x0,x1,

…,xn,…及对应的函数值y0,y1,

…,yn,…把k+1个节点，，…，所确定的不高于k

次插值多项式记作，则

1）(r=0,1,…,k)

2）逐步插值拉格朗日插值公式计算函数的近似值Neville算法算法步骤如下表例如

K=0123x0

y0=p0

(x)x1y0=p1

(x)p01

(x)x2y0=p2

(x)p12

(x)p012

(x)x3y0=p3

(x)p23

(x)p123(x)p0123

(x)……………Neville算法算法步骤如下表K=01Aitken算法算法步骤如下表计算公式

x0

y0=p0(x)X1y0=p1(x)p01(x)X2y0=p2(x)p02(x)p012(x)x3y0=p3(x)p03(x)p013(x)p0123(x)x4y0=p4(x)p04(x)p014(x)p0124(x)p01234(x)………………Aitken算法算法步骤如下表x0y0=p0(x)X1y0提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念定理

设f(x)在[a,b]上具有n阶连续导数,且

f(n+1)(x)存在,节点a≤x0<x1<…<xn≤b，

Ln(x)是满足条件Ln(xj)=yj(j=0,1,2,…,n)的插值多项式，则对任何x

∈

[a,b]，插值余项插值余项定义

若在[a,b]上用Ln(x)近似f(x)，则其截断误差 Rn(x)＝f(x)-Ln(x)

称插值多项式的余项。其中定理设f(x)在[a,b]上具有n阶连续导数,且证明：因为设其中证明：因为设其中第1节课-第一章-插值法--拉格朗日插值-分段插课件根据Rolle定理,再由Rolle定理,依此类推，由于因此根据Rolle定理,再由Rolle定理,依此类推，由于因此所以注：余项表达式只有在f(x)的高阶导数存在时才能使用，ξ通常不能具体给出，可求出故Ln(x)逼近f(x)的截断误差限是所以注：余项表达式只有在f(x)的高阶导数存在时才能使用，ξ当f(x)是n次的多项式时,Ln(x)=f(x)。即n次多项式的n次插值函数即为该n次多项式本身。说明：n=1时，n=2时，当f(x)是n次的多项式时,Ln(x)=f(x)。即例:解:例:解:第1节课-第一章-插值法--拉格朗日插值-分段插课件的抛物插值多项式,且计算f(3)的近似值并估计误差。例2

设解插值多项式为的抛物插值多项式,且计算f(3)的近似值并估计误差。例2因为故于是因为故于是用二次插值计算ln11.25的近似值,并估计误差.例3

给定函数表x10111213lnx2.3025852.3978952.4849072.564949解

取节点x0=10,x1=11,x2=12,作二次插值有ln11.25L2(11.25)用二次插值计算ln11.25的近似值,并估计误差.例3在区间[10,12]上lnx的三阶导数的上限M3=0.002,可得误差估计式实际上,ln11.25=2.420368,|R2(11.25)|=0.000058.在区间[10,12]上lnx的三阶导数的上限M3=0.00事后误差估计一般直接应用余项公式来估计误差是困难的，常采用一种事后估计法。设x0<x<x1<x2,且f(xi)(i=0,1,2)已知，若将用x0,x1两点作线性插值所求得y的近似值记为y1，将用x0,x2两点作线性插值所求得y的近似值记为y2，则由余项公式知：事后误差估计一般直接应用余项公式来估计误差是困难的，常采用一得：假设

这表明可以通过两个结果的偏差y2-y1来估计插值误差y-y1。这种直接利用计算结果来估计误差的方法，称为事后估计法。得：假设这表明可以通过两个结果的偏差y2-y1来事后估计法算例分析为节点,求得近似值为:用为节点,求得近似值为:按照估计式有用用用例：求的近似值。事后估计法算例分析为节点,求得近似值为:用提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值提纲插值的基本概念分段插值高次插值的病态性质：对于一个确定的区间，如果插值节点之间的距离较小，自然插值节点就增多，如果用一个多项式插值，自然次数就会升高，也就是说要用高次多项式插值。但是否次数越高，插值多项式的逼近效果越好呢？20世纪初，Runge就给出了一个等距节点插值多项式不收敛的例子。分段插值高次插值的病态性质：对于一个确定的区间，如果插值节点Runge反例:(-5≤x≤5)它在[-5,5]上各阶导数均存在，在该区间上取n+1个等距节点：构造拉格朗日插值多项式为：Runge反例:(-5≤x≤5)它在[-5,5]上各阶导数均n20.1379310.759615-0.62168440.066390-0.3568260.42321660.0544630.607879-0.55341680.049651-0.8310170.880668100.0470591.578721-1.531662120.045440-2.7550002.800440140.0443345.332743-5.288409160.043530-10.17386710.217397180.04292020.123671-20.080751200.042440-39.95244939.994889下表列出了n=2,4,…,20的Ln(xn-1/2)和R(xn-1/2)的值：n20.1379310.759615-0.62168440取xk=-5+k

计算:f(xk)(k=0,1,…,10)构造L10(x).取:tk=-5+0.05k(k=0,1,…,200),计算:L10(tk)L10(t)

f(t)

f(x)取xk=-5+k计算:f(xk)(k=0,一、分段线性Lagrange插值构造Lagrange线性插值1.分段线性插值的构造设插值节点为xi，函数值为yi，i=0,1,2,……,nhi=xi+1-xi，i=0,1,2,……,n-1，任取两个相邻的节点xk，xk+1，形成一个插值区间[xk，xk+