插值法与最小二乘法

插值法与最小二乘法第1页，课件共77页，创作于2023年2月本章主要内容

插值法Lagrange插值插值误差分段插值法

Newton插值多项式样条函数插值法数据拟合最小二乘法第2页，课件共77页，创作于2023年2月为什么需要插值?

函数表达式复杂,不便于计算和进行理论分析;

没有函数表达式,只给出离散样点，不能计算.

找简单函数近似,即函数逼近.

函数逼近常用方法:插值法,曲线拟合法.插值法:代数多项式插值,三角多项式插值.曲线拟合法：最小二乘法.第3页，课件共77页，创作于2023年2月

给定空间一组有序的控制点（controlpoint），得到一条分段光滑的多项式曲线的方法:

引言(x1,y1)(x2,y2)(x3,y3)(x0,y0)(xn,yn)插值拟合曲线顺序经过所有的控制点，则称为对这些控制点进行插值，得到的曲线称为插值曲线。构造一条在某种意义下最靠近控制点的曲线，这称为对这些控制点进行逼近，得到的曲线称为逼近(拟合)曲线。第4页，课件共77页，创作于2023年2月

本章先讨论插值问题，然后再讨论数据拟合的有关问题。

拟合法就是考虑到数据不一定准确，不要求近似表达式经过所有的点，而只要求在给定的上误差（i=0，1,…,n）按某种标准最小。若记

δ=(δ1,δ2

,…,δn

)T

，就是要求向量δ的范数||δ||

最小。

引言第5页，课件共77页，创作于2023年2月问题１：基于未知函数或复杂函数的某些已知信息，如何构造这些函数的近似表达式?情形１函数f(x)在x0

点的Taylor展开式－－称为函数f(x)的Taylor插值引例1第6页，课件共77页，创作于2023年2月解设例如利用Taylor插值求利用Taylor插值，有引例1第7页，课件共77页，创作于2023年2月y=f(x)x0p(x)Taylor插值的缺陷：①Taylor插值中有导数运算，而计算机实现求导运

算存在困难；②近似区间小,在大的区间上不可行．引例1第8页，课件共77页，创作于2023年2月情形２在区间［a,b］上考虑函数f(x)的近似表达式．y=f(x)a

b

求解：y=f(x)在[a,b]上的近似曲线？引例2第9页，课件共77页，创作于2023年2月

1.利用函数f(x)在区间[a,b]上一系列点的值

yi=f(xi)

（可通过观察、测量、试验等方法得到）xx0x1x2…xnyy0y1y2…yny=f(x)插值法解决思路：引例2第10页，课件共77页，创作于2023年2月2.根据

f

(x)在n+1个已知点的值，求一个足够光滑又比较简单的函数p(x)，作为

f(x)的近似表达式.x0x1x2xn-1xn

xf(x)p(x)从几何上看曲线P

(

x)

近似f

(

x)引例2第11页，课件共77页，创作于2023年2月从代数上看，p(x)满足以下代数条件:p(xi)=yi

(=f(xi))

i=0,1,2,

⋯,n这就是所谓的代数插值问题．然后计算p(x)在[a,b]上其它点x处的函数值作为原来函数f

(x)在此点函数值的近似值.代数多项式、三角多项式、有理函数或样条函数一.代数插值问题§1拉格朗日(Lagrange)插值第12页，课件共77页，创作于2023年2月(2.1)式称为插值条件，x2<⋯<xn≤

b

点上的值y0,y1,⋯,yn.

若存在一简单函数p(x),

使得

p(xi)=yi

i=0,1,2,

⋯,n

(2.1)

定义2.1f(

x

)称为被插值函数，[a,b]称为插值区间，称为插值节点，

求p

(

x

)

的方法就是插值法.设函数f(x)在[a,b]上有定义，且已知在a

≤

x0

<

x1<成立,则称p(x)为

f(x)

的插值函数.近似计算f(x)的值、零点、极值点、导数、积分等.插值点在插值区间内的称为内插,否则称外插.

一.代数插值问题第13页，课件共77页，创作于2023年2月最常用的插值函数是：代数多项式，用代数多项式作插值函数的插值称为多项式插值.本章主要讨论的内容插值函数的类型有很多种.插值问题插值法插值函数分段函数….三角多项式，一.代数插值问题第14页，课件共77页，创作于2023年2月x0x1x2x3x4f(x)p(x)从几何上看曲线P

(

x)

近似f

(

x)研究问题：（1）满足插值条件的p(

x)

是否存在唯一？（2）若满足插值条件的p

(

x)

存在，如何构造p(

x)？（3）如何估计用p

(

x)近似替代f

(

x)产生的误差？一.代数插值问题第15页，课件共77页，创作于2023年2月问题2－插值多项式的构造②可设p

(

x

)=a0

+a1x+

⋯+an

x

n①确定多项式p(x)的次数；方法１：待定系数法要求插值多项式p(x)，可以通过求n+1个方程的解:得到。但这样做不但计算复杂，而且难于得到pn(x)的简单表达式。结论：n+1个插值节点产生的插值多项式至多是n次的．第16页，课件共77页，创作于2023年2月问题１－插值多项式的存在唯一性

设pn(

x

)是f(x)

的插值多项式，Hn表示次数不超过n的所有多项且pn(

x

)∈Hn.称插值多项式存在且唯一，就是指在由(2.1)可得(2.2)方程组(2.2)有唯一解插值多项式的唯一性≠0(xi≠xj)定理1满足条件(2.1)的次数不高于n次的插值多项式存在且唯一。范德蒙行列式a0,a1,a2,⋯,an存在唯一p(xi)=yi

i=0,1,2,

⋯,nHn中有且仅有一个pn(

x

)满足插值条件(2.1)式。式的集合。n+1个节点互异第17页，课件共77页，创作于2023年2月为求得便于使用的简单插值多项式pn(

x

)，我们先讨论n=1的情形（线性插值）。当n=1时，要构造通过两点

(x0

,y0

)和(x1,y1)的不超过1次的多项式p1(x)(后面记作L1(x))，使得二.拉格朗日插值(1次)y

0x

y=f(x)y=L1(x)x0x1

第18页，课件共77页，创作于2023年2月y

0x

y=f(x)y=L1(x)x0x1

——称为线性（一次）插值（两点式）（点斜式）二.拉格朗日插值(1次)第19页，课件共77页，创作于2023年2月或L1(x)是两个线性函数的线性组合称为节点x0,x1上线性插值基函数------线性Lagrange插值多项式形式二.拉格朗日插值(1次)第20页，课件共77页，创作于2023年2月

y10

x0x1

xl0(x)l1(x)

节点上的线性

插值基函数：满足

y10

x0x1

x(2.3)(2.4)x0x1l0(x)10l1(x)01二.拉格朗日插值(1次)第21页，课件共77页，创作于2023年2月lk,lk+1称为节点上线性插值基函数.

y10

xkxk+1

x

y10

xkxk+1

xlk(x)lk+1(x)xkxk+1lk(x)10lk+1(x)01二.拉格朗日插值(1次)满足(2.7)第22页，课件共77页，创作于2023年2月

(2.6)式也称为拉格朗日型插值多项式，其中基函数lk,lk+1与yk,yk+1无关，而由插值节点xk,xk+1决定．

因此，一次拉格朗日插值多项式是插值基函数lk,lk+1的线性组合，相应的组合系数是该点的函数值yk,yk+1．二.拉格朗日插值(1次)第23页，课件共77页，创作于2023年2月例1

已知,,解

这里x0=100，y0=10，x1=121，y1=11,利用线性插值利用线性插值求二.拉格朗日插值(1次)第24页，课件共77页，创作于2023年2月二.拉格朗日插值(2次)第25页，课件共77页，创作于2023年2月

先求

插值基函数l0(x),l1(x),l2(x),它们满足

(1)都是二次函数；

(2)在节点满足(2.8)x0x1x2l0(x)100l1(x)010l2(x)001二.拉格朗日插值(2次)第26页，课件共77页，创作于2023年2月y

1

0

xx0

x1

x2

先求l0(x):待定系数y

1

0

xx0

x1

x2y

1

0

xx0

x1

x2

由l0(x)满足的两个条件类似地,可得知l0(x)中含有两个因子(x-x1)(x-x2)，且是二次的.再由l0(x)满足的条件即得所以有L2(x)=y0l0(x)

+y1

l1(x)

+y2

l2(x)二.拉格朗日插值(2次)第27页，课件共77页，创作于2023年2月L2(

xj)=yj,j=k-1,k,k+1.

L2(x)=yk-1lk–1(x)

+yk

lk(x)

+yk+1lk+1(x)值件插条再构造插值多项式L2(x)是三个二次插值多项式的线性组合，且也满足插值条件．(2.9)-----过三点(xk-1,yk-1),(xk,yk)与(xk+1,

yk+1)的抛物线.Y=L2(x)的几何意义二.拉格朗日插值(2次)第28页，课件共77页，创作于2023年2月例2

已知,,解

这里x0=100，y0=10，x1=121，y1=11,x2=144，y2=12，利用抛物线插值公式利用抛物线插值求二.拉格朗日插值(2次)第29页，课件共77页，创作于2023年2月n次Lagrange插值多项式求通过n+1个节点的n次插值多项式Ln(x)：先求插值基函数然后构造插值多项式设Ln(x)=满足插值条件：Ln(

xj)=yj

,j=0,1,⋯,n定义2.2若n次多项式lk(

x

)(k=0,1,⋯,n)在各节点j,k=0,1,⋯,n上满足条件

则称这n

+1个n次多项式为这n+1个节点上的n次插值基函数。二.拉格朗日插值(n次)第30页，课件共77页，创作于2023年2月先求

插值基函数，k=0,1

,⋯,

n

.k=0,1,⋯,n

.L2(x)=y0l0(x)

+y1

l1(x)

+y2l2(x)（类似于前面讨论n=1,2时的情形）(2.10)二.拉格朗日插值(n次)第31页，课件共77页，创作于2023年2月再构造插值多项式（Ln(x)是n+1个插值基函数的线性组合）定理2（Lagrange）插值多项式(2.11)二.拉格朗日插值(n次)第32页，课件共77页，创作于2023年2月显然，如此构造的L(x)是不超过n次多项式。当n=1时，称为线性插值。当n=2时，称为抛物线插值。二.拉格朗日插值(n次)第33页，课件共77页，创作于2023年2月

设为插值节点，n次多项式满足条件

由此可得称为lagrange插值基函数。Lagrange插值多项式的另一种形式二.拉格朗日插值(n次)第34页，课件共77页，创作于2023年2月于是，lk(x)可以写成容易求得(2.12)二.拉格朗日插值(n次)第35页，课件共77页，创作于2023年2月

由插值条件知,被插值函数和插值函数在节点处的函数值相等,但在节点外的值可能会偏离.即函数插值必然存在误差.x0x1x2xn-1xnxL(x)

f(x)f(x)L(x)三.拉格朗日插值多项式的误差估计第36页，课件共77页，创作于2023年2月3-1插值余项插值多项式存在着误差不会完全成立，即但是，对于引入插值余项的概念，以下分析插值余项的形式…满足插值条件：由上一节可知，y=f(x)的Lagrange插值如何估计这个误差?第37页，课件共77页，创作于2023年2月待定函数即在[a,b]上至少有

n+1个零点，因此可设：假设在区间[a,b]上f(x)的插值多项式为，令显然：因此：

为了求得K(x)，引入辅助函数：视x为区间上的固定点，且x≠xi，则插值余项第38页，课件共77页，创作于2023年2月若

f(x)n+1次可微n+1次可微n+1次可微n+1次可微可知:再由在区间[a,b]上至少有n+2个零点：根据Rolle定理,在区间(a,b)上至少有n+1个零点。再由Rolle定理,在区间(a,b)上至少有n个零点…第39页，课件共77页，创作于2023年2月由于因此依次类推，在区间(a,b)内至少有一个点,使=0=(n+1)!x，第40页，课件共77页，创作于2023年2月定理3（Lagrange插值多项式的余项公式）Lagrange型余项称为插值多项式的余项.不确定，难以估计第41页，课件共77页，创作于2023年2月设，则误差界注：为使误差尽可能小,对于固定的插值点,应选靠近的节点建立，使较小，即较小。第42页，课件共77页，创作于2023年2月当n=1时,线性插值余项为当n=2时,抛物线插值余项为特例第43页，课件共77页，创作于2023年2月第44页，课件共77页，创作于2023年2月

以上结果似乎表明，插值多项式的次数越高，插值精度也越高？但实际并非如此！第45页，课件共77页，创作于2023年2月例3并作图比较.解:3-2高次插值多项式存在的问题一第46页，课件共77页，创作于2023年2月不同次数的Lagrange插值多项式的比较图-5-4-3-2-1012345-1.52-1-0.500.511.5n=2n=4n=6n=8n=10f(x)=1/(1+x2)分段插值第47页，课件共77页，创作于2023年2月

为解决高阶插值多项式产生的Runge现象,可将插值区间分成若干个子区间,而在每个子区间上采用低次多项式插值。Runge现象及解决方法

以上结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,称为Runge(龙格)现象。

所有子区间上的插值多项式构成[a,b]上的分段函数,称为f(x)在[a,b]上的分段插值多项式。第48页，课件共77页，创作于2023年2月注:子区间的分法与子区间上插值多项式的次数和插值点的位置有关,同时区间分点应取在节点上。构造分段低次插值…从第一节可知,若插值多项式次数过高，可能产生Runge现象。将插值区间划分为若干个插值子区间；

各子区间上的插值多项式构成插值区间上的分段函数,称为分段插值多项式。执行步骤：在每个子区间上构造低阶插值多项式。§2分段低次插值第49页，课件共77页，创作于2023年2月2-1分段线性Lagrange插值

给定

f(x)

在[a,b]上的节点及对应函数值,任取两相邻节点，形成一个插值区间，构造Lagrange线性插值多项式：1、分段线性插值多项式的构造第50页，课件共77页，创作于2023年2月显然，

称由(1)、(2)式构成的插值多项式Lh(x)为f(x)在[a,b]上的分段线性插值多项式。整个区间可以分成？个上述子区间：(2)n注：k

为子区间的标号.(1)第51页，课件共77页，创作于2023年2月

由第一节定理3可知，n次插值多项式的余项为：1）插值余项则分段线性插值多项式Lh(x)的余项为：其中:，且与x有关.

2、插值余项及收敛性第52页，课件共77页，创作于2023年2月并且设设相邻两节点之间的距离为：第53页，课件共77页，创作于2023年2月因此,若f(x)在[a,b]上连续,则2）收敛性

曲线的光滑性较差

在节点处有尖点

增加节点数量

减小步长即:分段线性插值的光滑性虽然不好，但可以保证收敛。连接插值节点的一条折线，称

折线插值。分段线性插值曲线实际是第54页，课件共77页，创作于2023年2月

由余项公式知:节点

xk离插值点越近,误差越小,插值效果就越好,因此应尽量

在插值点的邻近选取插值节点.分段插值的关键:恰当挑选插值节点

对于给定的一组数据,设节点按的顺序排列,设插值点x=u,则有：若,就取这两个节点作内插，即①3、插值节点的选取原则如何确定

k？第55页，课件共77页，创作于2023年2月外推内插外推②若,取靠近它的作外推,即若,取靠近它的作外推,即③第56页，课件共77页，创作于2023年2月2-2分段二次Lagrange插值

分段线性插值的光滑性较差,且精度不高.因此,当节点较多时,可根据情况构造分段二次Lagrange插值.将整个区间划分为若干个小的子区间，在子区间上，用三个节点构造二次Lagrange插值多项式.1、分段二次插值多项式的构造

设给定

f(x)在[a,b]上的节点

xi(i

=

0,1,…n)及其对应的函数值

yi

(i

=

0,1,…n)，任取三个相邻节点

,形成一个插值区间,对于插值点x

=

u,构造分段二次

Lagrange

插值多项式:第57页，课件共77页，创作于2023年2月对给定插值点

x=u,取靠近

u

的三个节点作二次插值多项式.①若,显然插值区间和都包含插值点

u,另一个节点取

xi-1

还是

xi+2

取决于

u偏向于区间的哪一侧：如何确定k？第58页，课件共77页，创作于2023年2月内插内插当u靠近

xi+1,即时,补选

xi+2为节点,此时当u靠近

xi,即时,补选

xi-1为节点,此时第59页，课件共77页，创作于2023年2月内插外推内插外推若时(包含外推情况),取为节点②若时(包含外推情况),取为节点③第60页，课件共77页，创作于2023年2月设在各节点的数据为例4用分段二次插值,求在处的近似值.解:因为靠近表头,所以取为插值节点；

且靠近0.40,故补选0.40前面的点为节点,所以仍选为插值节点；则计算和的分段二次插值公式相同，即：第61页，课件共77页，创作于2023年2月代入计算得：第62页，课件共77页，创作于2023年2月代入计算得：则计算和的分段二次插值公式相同，即：因且靠近0.80,所以取为插值节点,而靠近表末,也取为节点第63页，课件共77页，创作于2023年2月分段低次插值法的特点:1）算法简单,计算较容易,且收敛性能够得到保证;2）只要节点间距充分小，分段插值总能获得所要求的精度，而不会像高次多项式插值那样产生Runge现象；4）插值多项式分段，插值曲线在插值节点处会出现尖点，插值多项式在节点处不可导.3）具有局部性，若修改某个数据，插值曲线仅在某个局部范围内受到影响，而不会影响到整个插值区间.第64页，课件共77页，创作于2023年2月Lagrange插值多项式的缺点二：当新增加插值节点时,用Lagrange插值多项式,则需要重新计算所有的插值基函数,计算量大且应用不方便.第65页，课件共77页，创作于2023年2月

由插值多项式存在唯一性的定理说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。类似于拉格朗日插值，我们还可以给出不同形式的便于使用的其它插值多项式。

基本思想：在n次多项式空间Pn中找一组合适的基函数0(x),

1(x),…,

n

(x),使pn(x)=b00(x)

+b11(x)

+…+bnn(x)(bi为常数)不同的基函数的选取导致不同的插值方法.Lagrange插值§3Newton插值多项式第66页，课件共77页，创作于2023年2月将Ln(x)改写成的形式,希望每加一个节点时，只附加一项上去即可。????一、差商的定义及性质1阶差商2阶差商上一页下一页

返回

§3Newton插值多项式第67页，课件共77页，创作于2023年2月n阶差商：Warning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi

的顺序无关！称之为差商的对称性.上一页下一页

返回

第68页，课件共77页，创作于2023年2月其中差商的性质第69页，课件共77页，创作于2023年2月节点xk函数值f(xk)一阶差商二阶差商三阶差商…x0f(x0

)x1f(x1

)f[x0

,

x1

]x2f(x2

)f[x1

,

x2

]f[x0,

x1

,

x2

]x3f(x3

)f[x2,

x3

]f[x1,

x2