计算方法第五章1插值法

第五章

插

值

法计算方法§5.0

引言§5.1

拉格朗日（Lagrange）插值§5.2

牛顿（Newton）插值§5.3

分段线性插值§5.4

埃尔米特（Hermite）插值§5.5

样条插值§5.0

引言(问题的提出)工程中，给出一些离散点，如何求出一条通过（或接近）这些点的光滑曲线表达式？有函数表达式，但函数式不易直接用计算机计算，如何构造一个简单函数来近似它？x0x1x2x3x4xφ(x)1、插值法精确函数y

=f

(x)插值函数φ(x)

f

(x)f(x)解决办法有两种：插值示意图插值和拟合示意图(x2,

y2)(x3,

y3)(x0,

y0)(xn,

yn)插值拟合(x1,

y1)2、曲线拟合（函数逼近）§5.0

引言插值问题：求一条曲线严格通过数据点曲线拟合问题：求一条曲线在一定意义下靠近数据点注：曲线拟合问题称函数逼近问题§5.1拉格朗日插值5.1.1多项式插值5.1.2拉格朗日插值多项式5.1.3插值多项式的误差估计1)插值问题的有关概念已知条件设给出关于函数y=f

(x)的一组函数值，xx0x1x2…xnyy0y1y2…yn其中x0

,x1,x2,…,xn是区间[a,b]上的互异点(因为函数是这样的映射：一个x唯一的对应一个y)，5.1.1多项式插值求

一个简单函数φ(x)作为f(x)的近似表达式，以满足(

xi

)

yi

,

i

0,1,,

n称这样的问题为插值问题，解决插值问题的方法称为插值法。称φ(x)为f(x)的插值函数，f(x)为被插值函数，x0

,x1,x2,…,xn是插值节(基)点(

xi

)

yi

,

i

0,1,,

n称为插值条件.条件思考题

当数据点(xi,yi)给定后，满足插值条件的插值函数φ(x)有多少种类型？答有许多种。例如给出平面上两个点，则过这两个点的曲线有无穷多种，可以是代数多项式、三角多项式、有理函数等等。插值函数P(x)的选择不同，就产生不同类型的插值：若P(x)为有理函数,就称为有理函数插值；若P(x)为三角多项式,就称为三角多项式插值；若P(x)为代数多项式,就称为代数多项式插值,简称插值多项式。选用的插值函数不同，近似的效率也不同。但最简单而最常用的是代数多项式，它有许多良好的性质，故本章仅考虑代数多项式插值问题，即代数插值xx0x1x2…xnyy0y1y2…yn其中x0

,

x1,

x2,

…,

xn是区间[a,

b]上的互异点(一共n+1个节点),2）代数多项式插值问题已知条件设给出关于函数y=f

(x)的一组函数值，求

一个次数不超过n的多项式Pn

(

x)

a0

a1

x

a2

x2

an

xn使满足插值原则(条件)Pn

(

xi

)

yi

,

i

0,1,,

n称Pn(x)为f

(x)的n次插值多项式一、插值问题解的存在唯一性？二、插值多项式的常用构造方法？三、插值函数的误差如何估计？代数插值定理在n+1个互异节点处满足插值条件且次数不超过n的多项式Pn(x)存在并且唯一。证明

设Pn(x)为所求多项式，则naa

a1

xn

a

x

a

x

y2

n2

n

n

n01

a

a

x

a

x2

a

xn

y1

1

2

1

n

100

a

x

a

x2

a

xn

y1

0

2

0

n

00这是未知量a0,a1,…,an的线性方程组，其系数行列式是范德蒙行列式n

n

nx

nx

nx

n

x

21x

2110x

2001

x1

x1

xV

(

x0

,x1

,,

xn

)

因为x0,x1,…,xn互不相同，故系数行列式不等于0，因此方程组有唯一解，即

Pn(x)存在并唯一。0

jin(

xi

x

j

)注意 从定理的证明可以看出，只要通过求解一个线性方程组得出a0,

a1,…,an的值，便可以确定Pn(x)了。然而这样构造多项式不但计算量大，而且难以得到Pn(x)的简单公式，因此本章下面几节将介绍几种直接构造Pn(x)的方法。注：若不将多项式次数限制为n，则插值多项式不唯一。ni0P(x)

Pn

(x)

p(x)(x

xi

)也是一个插值多项式，其中p(x)可以是任意多项式。例如例n元实向量集合Rn＝{α，β，，…}，由线性代数知，向量有加法运算与数乘向量运算。向量的加法运算具有四条性质：加法交换律

α+β＝β+α

(α，β∈Rn)加法结合律

(α+β)+＝α+(β+)

(α，β，∈Rn)存在零向量“0”，满足α+0＝0+α对于Rn中任何—个实向量α＝(a1，a2，…，an)都有对应的负向量-α＝(-a1，-a2，…，-an)，满足

α+(-α)＝0。数乘向量运算也具有四条性质：(5)

1·α＝α(7)

(k+l)α＝kα+lα(6)

k(lα)＝(kl)

α(8)

k(α+β)＝kα+kβ例设R[x]n＝{次数小于n的变量x的实系数多项式f(x)＝a0+a1x+a2x2+…+an-1xn-1集合}R[x]n中的两个多项式f(x)与g(x)的加法按通常多项式加法运算一样，数乘多项式f(x)按通常数乘多项式运算一样,则多项式的加法运算具有四条性质：加法交换律加法结合律f(x)+g(x)＝g(x)+f(x)[f(x)+g(x)]+h(x)＝f(x)

+[

g(x)+

h(x)](3)

存在零多项式0，满足

f(x)

+0＝0

+

f(x)＝f(x)对于R[x]n中任何一个多项式f(x)＝a0+a1x+a2x2+…+a

n-1xn-1都有对应的负多项式-

f(x)＝-a0-a1x-a2x2-…-a

n-1xn-1满足f

(x)+(-f(x))＝01·f(x)＝f(x)k(l

f(x))＝(kl)

f(x)(k+l)

f(x)＝k

f(x)+l

f(x)k(f(x)

+

g(x))＝k

f(x)

+

kg(x)定义

设V是一个非空集合，F是一个数域，在集合V的元素之间定义了加法运算。即对于V中任意两个元素α与β，在V中有唯一的元素与它们相对应，称之为α与β的和，记为＝α+β。并且加法运算满足下面四条法则：交换律α

+β＝β

+α结合律(α

+β)+＝α

+(β+)零元素在V中有一元素0（称作零元素），对于V中任一元素α都有

α+0＝α负元素对于V中每一个元素α，都有V的元素β，使得α+β＝0在集合V的元素与数域F中的数之间还定义了一种运算．叫做数乘。即对于V中任一元素α与F中任一数k，在V中有唯一的一个元素与它们对应，称为k与α的数乘积，记为＝kα，并且数乘运算满足下面四条法则：1·α＝αk(lα)＝(kl)

α(k+l)

α＝kα+lαk(α+β)＝kα+kβ其中k，l表示数域F中的任意数，α，β表示V中任意元素，称这样的V为数域F上的线性空间Lagrange插值Newton插值基本思想:在n

次多项式空间Pn中找一组合适的基函数0(x),1(x),…,

n(x

),使Pn(

x

)=a0

0(x)

+a1

1(x)

+…+an

n(x)不同的基函数的选取导致不同的插值方法5.1.2

拉格朗日插值多项式一、线性插值二、二次插值三、n次插值一、线性插值1.

线性插值的定义当n=1时的n次代数多项式插值称为线性插值，即：已知在互异点x0,x1处的函数值f(x0)=y0,f(x1)=y1，要构造线性函数L1(x)=a0+a1x，满足L1(xi)=yi，i

=0,12.

线性插值的几何意义用通过两点(x0,y0)、(x1,y1)的直线

y=L1(x)近似代替曲线y=f(x)，如下图所示。y=L1(x)y=f(x)x1x0y0y1xyo3.

线性插值公式的推导根据直线的点斜式，有1

0010y

y(x

x

)x

xL1

(x)

y0

把上式改写成1

0101

y0

l0

(

x)

y1

l1

(

x)x

x0

yx0

x1

x

xx

x1L

(

x)

y称按如上方法确定的L1(x)为拉格朗日线性插值多项式，其特点为：L1(x)是两个函数l0(x),l1(x)的线性组合，组合系数分别为y0，y1，并且l0(x),l1(x)具有性质：都是一次多项式；线性插值基函数x0x1l0(x)10l1(x)01n=1时的基函数图像00.2

0.4

0.6

0.8100.20.40.60.8100.2

0.4

0.6

0.8100.20.40.60.81l0

(x)l1

(x)二、二次插值1.

二次插值的定义设给出关于函数y=f(x)在三个互异点处的函数值，xx0x1x2yy0y1y2求

一个次数不超过二次的多项式.L2

(

x)

a0满足L2(

xi

)

yi这就是二次插值问题

a1

x

a2

x2(i

0,1,

2)2.

二次插值的几何意义用经过三点(x0,y0),(x1,y1),(x2,y2)的抛物线y=L2(x)近似代替曲线y=f(x)，如下图所示。xoy

y=f(x)y=L2(x)x2x0y0y2y1x13.

二次插值公式的推导仿照线性插值多项式的构造特点，先对每个基点xi构造一个二次函数li(x)(i=0,1,2),使满足li

(

xi

)

1,

li

(

x

j

)

0,i

j,

i,

j

0,1,2先构造l0(x)。l0(x)满足l0

(

x0

)

1,

l0

(

x1

)

0,

l0

(

x2

)

0则l0(x)可设为如下形式l0

(x)

A(x

x1

)(

x

x2

)又因为

l0

(x0

)

1，即l0

(x0

)

A(x0

x1

)(x0

x2

)

1解得1(x0

x1

)(

x0

x2

)A

即0(x0

x1

)(

x0

x2

)(x

x1

)(

x

x2

)l

(x)

同理可得1(x

x0

)(x

x2

)l

(x)

2(

x2

x0

)(

x2

x1

)(x1

x0

)(x1

x2

)(

x

x0

)(

x

x1

)l

(

x)

称这三个函数为二次插值基函数再令L2

(

x)

y0

l0

(

x)

y1

l1

(

x)

y2

l2

(

x)显然它是次数不超过2次的多项式，且满足L2

(

x0

)

y0

l0

(

x0

)

y0L2

(

x1

)

y1

l1

(

x1

)

y1L2

(

x2

)

y2

l2

(

x2

)

y2即为所求的二次插值多项式n=2时的基函数l0

(x)01200.20.40.60.8101200.20.40.60.8101200.20.40.60.81l1

(x)l2

(x)x0x210l1

(x)2l

(x)x1l0

(x)三、n次插值1.

n次插值的定义设给出关于函数y=f(x)在n+1个互异点处的函数值xx0x1x2…xnyy0y1y2…yn求

一个次数不超过n次的多项式Ln(x)插值这n+1个点。n2.

n次插值的一般形式Ln

(x)

y0l0

(x)

ynln

(x)

yili

(x)in(x

)i

0

i

i1i

i1

i

n

(x)n1j

0

xii

n1

ij

i其中l

(x)x

x

j

x

j

(x

x

)

i

0(x

x0

)(x

xi1

)(x

xi1

)(x

xn

)(x

x

)(x

x

)(x

x

)(x

x

)是n次插值基函数3.

n次插值的算法（1）输入x，xi

，yi

，(i=0

，1

，2

，…，n)（2）对i=0

，1

，2

，…，n，计算njixi

xx

x

jj0jil

(

x)

（3）计算插值nLn

(

x)

yili

(

x)i0（4）输出Lf(x)，停机。仅限于计算非节点处的插值拉格朗日插值特点：n次插值多项式Ln(x)是n+1个同阶多项式(插值基函数)lj(x)(j=0,1,

…,n)的线性组合；形式对称，有很强的规律性，便于记忆；计算某点的近似值需要计算n+1个多项式在该点的值，然后取线性组合，重复计算多,导致计算量大；插值基函数lj(x)依赖于所有节点，当增加插值节点时，原来已算出的所有lj(x)都需要重新计算，使计算量加大。定义

函数f(x)用n次插值多项式Ln(x)近似代替时，截断误差记为Rn

(

x)

f

(

x)

Ln

(

x)称Rn(x)为n次插值多项式Ln(x)的余项Ln(x)中的n指的是Ln(x)为n次多项式，而Rn(x)中的n指的是它是与Ln(x)相对应的余项，Rn(x)不一定是x的n次多项式。5.1.3插值多项式的误差估计思考1设f(x)=x2，求f(x)的次数不超过1、2、3、…的插值多项式各是什么？在哪些点处会有误差？思考1答案：当f(x)是次数不超过n的多项式时，其≥n次的插值多项式就是f(x)本身。此时误差为0！f(x)的次数超过n时存在误差：只在插值点处没有误差。思考2

设f(x)=sinx，求f(x)的次数不超过1、2、3、…的插值多项式各是什么？在哪些点处会有误差？思考2答案：当f(x)是非多项式时，其任何的插值多项式除插值点外均有误差！sinx的幂展开为无限多次项。当f(x)足够光滑时，有如下估计定理：定理设函数f(x)在包含节点x0,x1,…,xn的区间[a,b]上连续，在(a,b)上具有n+1阶导数，Ln(x)为满足插值条件的n次插值多项式，则对任一点x∈[a,b]，总存在相应的点ξ∈(a,b)，使Rn

(

x)

(n

1)!

n1

(

x)f

(n1)

(

)其中n1

(x)

(x

x0

)(x

x1

)(x

xn

)注意根据此定理可计算插值多项式的余项(误差)。定理中的下标意义不同Ln(x)和ωn+1(x)的下标表示次数，而Rn(x)的下标则不表示次数。复习罗尔定理罗尔定理 如果函数满足：如果在闭区间[a,b]上连续；在开区间（a,b）上可导；在区间端点处函数值相等，即：

f(a)=f(b),那么在(a,b)上至少存在 一点(a<<b),使得：证明

由给定条件知Rn(x)

在插值基点xi

(i=1,2,…,n)上为零，Rn

(x)

f

(x)

Ln

(x)

K

(x)(x

x0

)(x

x1)(x

xn

)

K

(x)n1(x)其中K(x)是与x有关的待定函数。现把x看成[a,b]上一个固定点，作函数

K

(

x)(t

x0

)(t

x1

)(t

xn

)(t

)

f

(t

)

Ln

(t

)则(t)

K

(t)(t

x0

)(t

x1)(t

xn

)

K

(x)(t

x0

)(t

x1)(t

xn

)

0(t)

K

(t)(t

x0

)(t

x1)(t

xn

)

K

(x)(t

x0

)(t

x1)(t

xn

)根据插值条件及余项定义，可知φ(t)在x0,x1,…,xn

及x

处均为0

，故φ(t)在[a,b]上有n+2个零点，根据罗尔定理(t)在φ(t)的两个零点间至少有一个零点，故(t

)在[a,b]内至少有n+1个零点。依次类推，

(n1)(t

)在(a,b)内至少有一个零点，记为ξ，（导数的阶数与零点个数之和是n+2）于是(n

1)!K

(x)

0f

(n1)

(

)(n1)n1(t)

(n

1)!(t)

f

(t)

Ln

(t)

K

(x)(t

x0

)(t

x1

)(t

xn

)使

(

n1)

(

)

f

(

n1)

(

)

(n

1)!

K

(

x)Rn

(

x)

(n

1)!

n1

(

x)f

(n1)

(

)其中ξ∈(a,b)且依赖于x。将

K(x)

代入余项表达式即可得到结论。Rn

(x)

f

(x)

Ln

(x)

K

(x)(x

x0

)(x

x1)(x

xn

)

K

(x)n1(x)对余项表达式的分析：（1）ωn+1(x)对Rn(x)的影响|

ωn+1(x)

|是|Rn(x)|的一个因子，因而越小越好。对于给定的x，|

ωn+1(x)

|的大小就取决于插值基点的选取。为了使得|

ωn+1(x)

|尽可能小一些，插值基点的选取原则是：使x尽可能位于区间Ix的中部，这里Ix是包含x以及所用基点的最小闭区间。定义：设插值基点x0,x1,…,xn中最小者为a、最大者为b，当插值点x∈(a,b)时我们称为内插，否则称为外插（2）若被插函数f(x)是k次多项式，则当插值多项式次数为n≥k时：

Rn=0,因为：f

(n1)(

)为0.例1

给定数据表xf(x)2

3

4

5

6

710

15

18

22

20

16要用插值方法计算f(4.8)的近似值。问线性插值、二次插值和三次插值应选哪些基点？解

如果用线性插值，就选x2

4,

x3

5为基点。如果用二次插值，就选x2

4,

x3

5,

x4

6(因为：4.8-3>6-4.8)为基点。如果用三次插值，就选x1

3,

x2

4,

x3

5,

x4

6为基点。例2

给定函数y=lnx在两点的值如表x10

11y2.303

2.398试用线性插值求ln10.5的近似值，并估计截断误差。解

记f(x)=lnx，取x0=10，x1=11，x=10.5，有ln

10.5

L1

(10.5)

2.303

10.5

11

2.398

10.5

1010

11

11

10

2.3505f

(

x)

1

/

x2因为

f

(

x)

1/

x,故f

(

x)

1/

102

0.01x

[10,11]插值余项为1

012!R

(x)

1

f

(

)(x

x

)(x

x

)所以2!1

0.00125R

(

x)

0.01

(10.5

11)(10.5

10)例3

设f

(x)

C

2[a,

b],f

(a)

f

(b)

0求证：若18''2maxf

(x).axbaxb(b

a)max

f

(x)

（其中：f

(x)

C

2[a,b],表示f(x)在(a,b)上直到二阶导数连续。）证：以a,b

为节点进行线性插值，得1a

b

b

ap

(x)

x

b

f

(a)

x

a

f

(b)''121f

(

x)

p

(

x)

f

(

)(

x

a)(

x

b)因

f

(a)

f

(b)

0

，故p1

(

x)

0.根据插值余项定理，有2

42

42(b

a)2)

a

xba

xba

xb则：max

f

(x)

1

(b

a)2max

f

(x)则：max

g(x)

g(令g(x)(x

a)(b

x)a

b12f

(x)

f

''

(

)(x

a)(x

b)a

b.故

f

(x)

1

f

(

)

(x

a)(b

x)例4

已知函数y

=

lnx

的函数表如下：x101112y2.30622.39792.4849x

13

14y

2.5649

2.6391分别用拉格朗日线性插值和二次插值求ln11.5的近似值，并估计余项。解

线性插值。取两个基点x0

11,

x1

12插值基函数为0

110

(

x

12)x

xx

xl

(

x)

0101

x

11x

xx

xl

(

x)

故线性拉格朗日插值函数为P1

(x)

2.3979(x

12)2.4849(x

11)将x=11.5代入得ln11.5

P1

(11.5)

2.3979(11.5

12)

2.4849(11.5

11)

2.4414其插值余项为2!1(

x