数值分析-第章-插值法与最小二乘拟合法(与“插值”相关共85张)

第5章插值法与最小二乘拟合法4.1代数插值法及其唯一性4.2Lagrange插值法4.3Newton插值法4.5Hermite插值法4.7三次样条插值法4.8最小二乘拟合法InterpolationandLinearLeastSquareMethod2022/11/281

更一般地，给定一个函数表:要求出任意点上的函数值。

在工程技术中，经常会遇到只给定一个函数表，要求根据该函数表求出某些点上函数值的问题。求高度时的大气压为多少?

x

x0

x1

…

xn

y=f(x)

y0

y1

…

yn方法一：插值法,插值曲线经过给定的插值点高度

0

1.5

2.5

3

4.8大气压

1

0.9

0.85

0.7

0.67方法二：拟合法,高度与大气压的探测数据2022/11/282插值法

/*Interpolation*/当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn

处测得函数值y0

=f(x0),…yn

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

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

称为f(x)的插值函数。最常用的插值函数是…?多项式x0x1x2x3x4xP(x)f(x)2022/11/283插值法是数值分析中的一个古老的分支；等距节点内插法—隋朝数学家刘焯zhou(公元544-610年)首先提出的；不等距节点内插法—唐朝数学家张遂(公元683-727年)首先提出的；插值法在数值积分、数值微分、微分方程数值解、曲线曲面拟合、函数值近似计算中有着广泛的应用。插值法的历史背景常用插值函数的类型代数插值：多项式插值有理插值：有理分式函数三角插值：三角函数2022/11/2844.1代数插值法及其唯一性4.1.1插值多项式及其唯一性定义4-1

已知函数f(x)在互不相同的点x0<

x1<

…<

xn

处的函数值y0

=f(x0),y1

=f(x1),…yn

=f(xn)，若存在多项式P(x),使得

P(xi)

=

f(xi)(i=0,1,…n)，则称P

(x)

称为f(x)的插值多项式，点x0,

x1,…,

xn

称为插值节点。插值条件

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

x)

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

x)

存在，如何构造P(x)？（3）如何估计用P(

x)近似替代f

(

x)产生的误差？（4）P(

x)是否收敛于

f

(

x)？2022/11/285由插值条件得关于系数的元线性方程组系数矩阵为称为范德蒙德（Vandermonde）矩阵,由互异，故因此线性方程组的解存在且唯一.2022/11/286定理4-1

对给定n+1个互不相同的点x0

,

x1,…,xn及其对应的函数值y0,

y1,

…,yn,

存在唯一的次数≤

n的多项式P(x)满足

P(xk)=yk,

k=0,1,…,n。P(x)?2022/11/287方程组(*)是病态方程组,阶数n越高,病态越严重。为此我们从另一途径寻求获得P(x)的方法----Lagrange插值和Newton插值。（这两种方法称为基函数法）(*)2022/11/2884.1.2插值余项/*Remainder*/

定义4-2

若Pn(x)

是被插函数f(x)的插值多项式，则称Rn(x)=f(x)-Pn(x)(i=0,1,…n)，为插值多项式的插值余项。定理4-2

设f(x)在区间[a,b]连续，在(a,b)内有直到n+1阶的导数，x0,x1,…,xn是区间[a,b]上的n+1个互不相同的点，Pn(x)

是满足插值条件P(xi)

=

f(xi)(i=0,1,…n)的插值多项式，则插值余项其中ξ∈(a,b)，且与x有关。2022/11/289注：

通常不能确定

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

将作为误差估计上限。当

f(x)为任一个次数n

的多项式时，,可知即插值多项式对于次数n的多项式是精确的。推论当f(x)是次数不超过n的多项式时，其n次插值多项式就是f(x)本身。2022/11/2810

例已知函数在点的函数值，求其三次插值多项式。

解对于次数不大于n的多项式，其n次插值多项式就是其本身。所以其三次插值多项式2022/11/28114.1.3代数插值的几何意义代数插值就是与被插值函数在插值节点处都相交的多项式曲线x0x1x2x3x4xP(x)

f(x)2022/11/2812=

y0+y14.2Lagrange（拉格朗日）插值法

niPi(xi)=yi

,,...,0=求n

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

,

x1

;

y0

,

y1，求P1(x)=a0+a1x，使得

P1(x0)=y0

,P1(x1)=y1

,P1(x)是过(

x0

,

y0)和(x1,y1

)两点的直线。)(1xP101xxxx--010xxxx--两点式)()(0010101xxxxyyyxP---+=点斜式

线性插值l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij2022/11/2813==10)(iiiyxjl对称式称l0(x)和l1(x)为以x0,x1为节点的基本插值多项式，也称为线性插值的插值基函数。基函数的线性组合满足li(xj)=ij

l0(x)+l1(x)≡1.其中l0(x)和l1(x)满足：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,

P1(xj)实质上l0(x)和l1(x)满足函数表=

y0+y1)(1xP101xxxx--010xxxx--l0(x)l1(x)==10)(iiiyxl

j=y2022/11/2814线性插值的几何意义用直线近似代替被插值函数。以直代曲线性插值的截断误差：2022/11/2815例

造数学用表——平方根表

给定函数在100、121两点的平方根如下表，试用线性插值求115的平方根。解

x0=100,x1=121,x=115x100121y10112022/11/2816抛物线（二次）插值:(三点二次插值）1.定义已知f(x)在三个互异点x0

,x1

,x2的函数值y0

,y1,y2

xx0x1x2yy0y1y2构造一个次数不超过二次的多项式

使满足插值条件

2.公式的构造：拉格朗日二次插值多项式满足插值条件n=2xx0x1x2L0(x)100

L1(x)010

L2(x)001

插值基函数满足：2022/11/2817例4-1

已知x=1,4,9的平方根值,用抛物插值公式,求

，并估计误差.(x0–x1)(x0–x2)(x–x1)(x–x2)y0+(x1–x0)(x1–x2)(x–x0)(x–x2)y1+(x2–x0)(x2–x1)(x–x0)(x–x1)y2p2(5)=x0=1,x1=4,x2=9,y0=1,y1=2,y2=3,(1–4)(1–9)(5–4)(5–9)*1+(4–1)(4–9)(5–1)(5–9)*2+(9–1)(9–4)(5–1)(5–4)*3=136/60≈

p2(x)=解实际误差：抛物插值的截断误差：2022/11/2818希望找到li(x)，i=0,…,n

使得

li(xj)=ij

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

yi

。n

2li(x)每个li有n

个根x0…xi-1,

xi+1…xn=j0-==nji

jiiixxC(x-x0)...(x-xi-1

)

(x-xi+1

)

...

(x-xn

)

Cxl)()(-==ji

jiiiixxCxl)(11)(LagrangePolynomial与有关，而与无关节点f展开2022/11/2819基函数的特点1.基函数的个数等于节点数。2.n+1个节点的基函数是n次代数多项式。3.基函数和每一个节点都有关。节点确定，基函数就唯一的确定。4.基函数和被插值函数无关。5.基函数之和为1。例

给定xi=i+1,i=0,1,2,3,4,4.下面哪个是l2(x)的图像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC2022/11/2820例4-1

求过点(2,0)，(4,3)，(6,5)，(8,4)，(10,1)的拉格朗日型插值多项式。x0=2,x1=4,x2=6,x3=8,x4=10,y0=0,y1=3,y2=5,y3=4,y4=1,解用4次插值多项式对5个点插值2022/11/2821例已知分别利用sinx的1次、2次Lagrange插值计算sin50

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

以及x1,x2

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

/*extrapolation*/

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

/*interpolation*/

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

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

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

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

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

为克服上述两个缺点,

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

下面我们将看到，这是可能的。我们可以有具有“承袭性”的所谓牛顿公式。2022/11/28264.3Newton插值法

/*Newton’sInterpolation*/

Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。将Pn(x)改写成的形式，希望每加一个节点时只附加一项上去即可。????2022/11/28274.3.1差商及其性质定义4-3

称为函数f(x)关于点x0,xk的一阶差商.称为f(x)的二阶差商.一般地,称

为f(x)的k阶差商(均差).

f[x0,xk]=f(xk)-f(x0)xk-x0

f[x0,x1,xk]=f[x0,xk]-f[x0,x1]xk-x1

f[x0,x1,…,xk]=f[x0,…,xk-2,xk]-f[x0,x1,…,xk-1]xk-xk-1

/*divideddifference*/1阶差商2阶差商差商的值与xi

的顺序无关！2022/11/2828均差的基本性质

1ºn阶均差可表示为函数值f(x0),f(x1),…,f(xn)的线性组合,即

f[x0,x1,…,xn]=f(xj)(xj-xj+1)…(xj-xn)…(xj-xj-1)(xj-x0)∑

nj=02º均差与节点的排列次序无关——均差的对称性

f[x0,x1,…,xn]=f[x1,x0,x2,…,xn]=…=f[x1,…,xn,x0]

f[x0,x1,…,xk]=f[x1,…,xk-1,xk]-f[x0,x1,…,xk-1]xk-x03º由性质1º可得:2022/11/28294.3.2Newton插值多项式

12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)牛顿插值多项式Rn(x)3/*Newton’sInterpolation*/ai

=

f[x0,…,xi]2022/11/2830n=1n=22022/11/2831注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即2022/11/2832Nn(x)均差实际计算过程为2022/11/2833例4-2

已知函数f(x)的数据如下表:286-2f(xk)-1201xk

求其Newton插值多项式。解:

利用牛顿插值公式N3(x)xkf(xk)一阶均差二阶均差三阶均差1-20628-12建立如下差商表:N3(x)2022/11/2834例

依据如下函数值表建立不超过3次的拉格朗日插值多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性.解:(1)拉格朗日插值多项式Pn(x).插值基函数xk0124f(xk)19233拉格朗日插值多项式为:2022/11/2835xkf(xk)一阶均差二阶均差三阶均差0119822314343-10-8(2)牛顿插值多项式Nn(x).建立如下差商表牛顿插值多项式为:(3)唯一性验证.通过比较牛顿插值多项式和拉格朗日插值多项式,知:Nn(x)=Ln(x)这一事实与插值多项式的唯一性一致.注：

当题目中没有指明用哪一种方法建立插值多项式时，原则上拉格朗日插值方法和牛顿插值方法都可行，做题目时选较为方便的一种方法。近似计算时，由于牛顿插值多项式的非整理形式可以直接写成秦九韶算法的形式，计算量小，且当节点增加时只需增加一项，前面的工作依然有效，因而通常情况下牛顿插值比较方便，拉格朗日插值则没有该优点，但在理论证明上因其基函数的特点广泛应用。2022/11/28361.Lagrange插值思想:

根据线性（一次）插值多项式L1(x)的形式推广到一般形式的n次插值多项式Ln小结称为拉氏基函数，满足条件li(xj)=ij插值余项2022/11/28372.Newton插值Nn(x)Rn(x)ai

=

f[x0,…,xi]2022/11/28382022/11/28394.4Hermite插值法

/*HermiteInterpolation*/4.4.1Hermite插值多项式

不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数

(x)

满足

(xi)=f(xi),’(xi)=f’(xi),…,(mi)(xi)=f

(mi)(xi).定义4-4

已知函数y=f(x)在k+1个互异节点xi(i=0,1,...,k)处的函数值f(xi)和直到mi阶导数值f（j）(xi)(j=1,...,mi)。若存在次数不超过n的多项式pn(x)，满足pn（j）(xi)=f（j）(xi),j=0,1,...,mi,i=0,1,...,k

则称pn(x)为f(x)的Hermite插值多项式。Hermite插值也叫带指定微商值的插值，它要构造一个插值函数既满足插值节点xi的函数值条件，又满足微商条件的插值函数，使插值函数和被插函数的密和程度更好。2022/11/2840,k)处的函数值f(xi)和直到mi阶导数值f（j）(xi)(j=1,.更一般地，给定一个函数表:(2)Si=yi(i=1,2,…,n)；插值法在数值积分、数值微分、微分方程数值解、曲线曲面拟合、函数值近似计算中有着广泛的应用。不等距节点内插法—唐朝数学家张遂(公元683-727年)首先提出的；Hermite插值也叫带指定微商值的插值，它要构造一个插值函数既满足插值节点xi的函数值条件，又满足微商条件的插值函数，使插值函数和被插函数的密和程度更好。其中是待定的3次多项式，由插值条件，满足1Hermite插值多项式的形式，希望每加一个节点时f[x0,x1,…,xk]=m=1时，称为直线拟合;m=2时，称为二次拟合或抛物线拟合。常见的边界条件有以下3种：InterpolationandLinearLeastSquareMethod仍然是已知x1…xn;y1…yn,求一个简单易算的近似函数P(x)f(x)。选择要计算的x所在的区间的端点，插值效果较好。由于计算均方误差的最小值的原则容易实现而被广泛采用。LagrangePolynomial注

N

个条件可以确定阶多项式。N

1要求在1个节点x0处直到m0阶导数都重合的插值多项式即为Taylor多项式其余项为一般只考虑f

与f′的值。2022/11/2841例4-3已知f(1)=3，f´(1)=5，f〞(1)=-2，f(2)=4，求3次Hermite插值多项式。

解由插值条件P3(1)=3，P3´(1)=5，P3〞(1)=-2，则再由P3(2)=4得故2022/11/28424.4.2三次Hermite插值(两点、完全导数)

给定f(x)在两个互异节点x0

,x1处的函数值f(x0),f(x1)和f´(x0

),f´(x1),求3次Hermite插值多项式P3(x),使其满足插值条件：

P3(x0)=f(x0),P3(x1)=f(x1),

P3´

(x0)=f´(x0),P3´

(x1)=f´(x1)。基函数法其中是待定的3次多项式，由插值条件，满足设所求插值多项式为四个插值条件2022/11/2843根据给定条件可令显然再利用及解得于是求得同理可得2022/11/2844为求，由给定条件可令直接由，得到同理最后代入，得2022/11/2845若存在常数M>0,使得对一切x∈(a,b)都有│f(4)(x)│≤M,则有定理4-3

若(x)在[a,b]上有直到3阶的连续导数,且在(a,b)内存在4阶导数，则对任意一点x[a,b]时,都存在ξ∈(a,b)，使得余项2022/11/2846例4-4

以4和9为插值节点，利用3次Hermite插值多项式求在x=5处的近似值，并估计插值引起的误差。解：由

f(4)=2,f(9)=3，且故实际误差2022/11/28474.5三次样条插值法我们已经知道插值有多种方法：Lagrange插值、Newton插值、Hermite插值等多种方式。插值的目的就是数值逼近的一种手段，而数值逼近是为得到一个数学问题的精确解或足够精确的解。那么，是否插值多项式的次数越高，越能够达到这个目的呢？现在我们来讨论一下这个问题。

f(x)在n+1个节点xi(i=0，1，2，…，n)上的n次插值多项式Pn

(x)的余项设想当节点数增多时会出现什么情况。由插值余项可知，当f(x)充分光滑时，若余项随n增大而趋于0时，这说明可用增加节点的方法达到这个目的，那么实际是这样吗？4.4.1背景2022/11/2848构造拉格朗日插值多项式为函数在上的各阶导数均存在.在[5,5]上考察的Ln(x)。取令2022/11/2849

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

实践上作插值时一般只用一次、二次最多用三次插值多项式。那么如何提高插值精度呢？分段低次插值n=2n=4n=10n=8n

越大，端点附近抖动越大，称为Runge（龙格）现象2022/11/2850(1)分段线性插值(2)分段二次插值(3)分段Hermite插值(4)分段三次样条插值2022/11/2851分段线性插值

/*piecewiselinearinterpolation*/在每个区间上，用1次多项式

(直线)逼近f(x):记，易证：当时，一致失去了原函数的光滑性。分段Hermite插值

/*Hermitepiecewisepolynomials*/给定在上利用两点的y及y’构造3次Hermite函数导数一般不易得到。2022/11/2852上面介绍的分段低次插值，虽然具有计算简便，收敛性有保证，数值稳定性又好且易在计算机上实现等优点，但它却不能保证整条曲线的光滑性，从而不能满足某些工程技术上的要求，从六十年代开始，首先由于航空、造船等工程设计的需要而发展起来的样条插值（spline)方法，既保留了分段低次插值的各种优点，又提高了插值函数的光滑性，在许多领域有越来越广泛的应用。

样条是绘图员用于描绘光滑曲线的一种机械器件,它是一些易弯曲材料制成的窄条或棒条.在绘制需要通过某点的光滑曲线时,对它在这些点的位置上“压铁”,它就被强制通过或接近图表上确定的描绘点.“样条函数”这个术语意在点出这种函数的图象与机械样条画出的曲线很象.2022/11/28534.4.2三次样条插值的概念/*cubicsplineinterpolant*/.

定义4-5

给定函数f(x)在区间[a,b]上的n+1个点a=x0<x1<…<xn=b处的函数值yi=f(xi)(i=0,1,2,…,n),若函数S(x)满足(1)S(x)在每个小区间[xi

,

xi+1])(i=1,2,…,n)上是一个次数不超过3次的多项式；(2)Si=yi(i=1,2,…,n)；(3)S(x)在区间[a,

b]上具有2阶的连续导数，则称S(x)是f(x)基于节点x0

,x1

,

…,xn

的三次样条插值函数，简称三次样条/*CubicSpline*/.

f(x)H(x)S(x)注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。2022/11/2854如何求的三次样条插值函数:4n个未知数因为在上二阶导数连续，所以在节点处应满足连续性条件满足个插值条件；三次样条插值条件的分析个条件共有个条件，还需要2个才能确定.2022/11/2855边界条件通常可在区间[a,b]端点a=x0,b=xn上各加一个条件（称为边界条件），常见的边界条件有以下3种：1.第I型边界条件：已知两端的一阶导数值，即2.第II型边界条件：已知两端的二阶导数值，即当时，称为自然边界条件

3.第III型边界条件：S(x)是以xn-x0为周期的周期函数，即此时S(x0)=S(xn),S(x)称为周期样条函数。2022/11/2856设S(x)的二阶导数值S"(xj)=Mj

(j=0,1,…,n)，求S(x).由于S(x)在区间[xj,xj+1]上是三次多项式，故S″(x)在[xj,

xj+1]上是线性函数，且对S"(x)积分两次并利用S(xj)=yj及S(xj+1)=yj+1，得三次样条表达式三次样条函数的表达式未知数n+1个2022/11/2857对求导得求得类似地可求出在区间上的表达式，从而得利用可得构造三弯矩方程组2022/11/2858第一种边界条件其中令未知数n+1个方程n-1个矩阵形式严格对角占优阵，有唯一解,三弯矩方程2022/11/2859第二种边界条件令,矩阵形式第三种边界条件其中严格对角占优阵，有唯一解,2022/11/2860矩阵形式2022/11/2861注：另有三转角法得到样条函数，即设S[j]’(xj)=mj，则易知[xj1,

xj

]上的S[j](x)就是Hermite函数。再利用S”的连续性，可导出关于mj的方程组，加上边界条件即可解。CubicSpline由boundaryconditions唯一确定。收敛性：若，且，则一致S(x)

f(x)即:提高精度只须增加节点,而无须提高样条阶数。稳定性：只要边条件保证|0|,|0|,|n|,|n|<2，则方程组系数阵为SDD阵，保证数值稳定。2022/11/2862试求三次样条函数，使它满足边界条件设为定义在上的函数，在节点上的值如下：例11解由此得矩阵形式的方程组（）为由（）及（）（6.13）2022/11/2863求解得代入（）得（曲线见图2-6）2022/11/2864图2-62022/11/2865给定函数节点用三次样条插值求取直接上机计算可求出在表2-6所列各点的值.例82022/11/28662022/11/2867下图是用Matlab完成的样条插值（附程序）：2022/11/2868附：样条插值程序n=11;m=61;x=-5:10/(m-1):5;y=1./(1+x.^2);z=0*x;x0=-5:10/(n-1):5;y0=1./(1+x0.^2);y1=interp1(x0,y0,x,’spline’);plot(x,z,’r’,x,y,’k:’,x,y1,’r’)gtext(‘Spline’),gtext(‘y=1/(1+x^2)’)title(‘Spline’)注：interp1(x0,y0,x,’spline’)为Matlab中现成的样条插值程序.2022/11/2869也可以将三种插值结果画在一起：2022/11/2870插值法小结Lagrange:给出y0…

yn，选基函数li(x)，其次数为节点数–1。

NewtonLn(x)，只是形式不同；节点等距或渐增节点时方便处理。

Hermite：给出yi及yi’，选i(x)及

i(x)

。Spline：分段低次,自身光滑,f的导数只在边界给出。2022/11/28714.6最小二乘拟合法仍然是已知x1…xn

;y1…yn,求一个简单易算的近似函数P(x)

f(x)。但是①

n

很大；②

yi本身是测量值，不准确，即yi

f(xi)这时没必要取P(xi)=yi

,而要使P(xi)

yi总体上尽可能小。4.6.1基本概念观测得的一组样本点(xi,yi)，欲寻求一个简单函数y=(x)，使其在样本点处的残差：δi=(xi)-yi,i=0,1,…,n,“整体”尽量小。这样确定的函数y=(x)称为这组样本点的拟合函数，这种构造近似函数的方法称为曲线拟合.2022/11/2872拟合的标准一般有以下几种:

（1）用各点误差绝对值的和表示，即（2）用各点误差按绝对值的最大值表示，即

（3）用各点误差的平方和表示式中S称为均方误差。由于计算均方误差的最小值的原则容易实现而被广泛采用。按均方误差达到极小构造拟合