数值分析 第一章 插值方法

教学要求：掌握插值概念、插值方法；掌握差商和导数的关系;初步掌握插值算法的程序设计；最小二乘解的概念与求法。教学重点、难点：插值方法、最小二乘解的概念与求法。教学内容：插值问题的提法、拉格朗日插值公式、插值余项、牛顿插值公式、分段插值法、曲线拟合的最小二乘法。第一章插值方法2023/1/3111.1问题的提出

1.2拉格朗日插值公式1.3插值余项1.4*

埃特金插值方法1.5牛顿插值公式1.6埃尔米特插值1.7分段插值法1.8*

样条函数1.9曲线拟合的最小二乘法2023/1/312实际问题中遇到的函数,其表达式可能很复杂，有些甚至都给不出解析表达形式，仅仅提供一些离散数据,譬如某些点的函数值和导数值,(xi,yi

,y’i

,i=0,1,2,…),直接研究该函数非常困难.因此,一个很自然的想法就是：能否构造某个简单的函数作为原函数的近似——插值问题.插值：在一定条件下，在某一范围内，用一简单函数p(x)近似代替另一个较为复杂或无法用解析式表达的函数f(x)，以便于计算和研究其性质.2023/1/3132023/1/314插值条件：

；插值函数：p(x)称为

f

(x)的插值函数；插值节点：

,

；插值区间：[a,

b]；插值法：

按插值条件

①,求函数

f

(x)的插值函数

p(x)

的方法称为插值法。----①2023/1/315因代数多项式结构简单，数值计算和理论分析方便，故常用代数多项式作为插值函数。例如：插值多项式：设f是区间[a,b]上的一个实函数，且有n+1个相异点x0,x1,…,xn∈[a,b],f在xi处的值yi

=f(xi)(i=0,1,2,..,n),若存在一个简单函数p(x)，使得

p(xi)=yi

(i=0,1,2,..,n)

①则称p(x)为函数f(x)的插值函数；f(x)称为被插值函数;若p∈Hn,即p(x)=a0+a1x+…+anxn,ai

(i=0,1,2,..,n)为实数，称p(x)为插值多项式.2023/1/3161.1问题的提出1.泰勒插值（f(x)在x

0的U(x

0,δ)内有n+1阶导数）泰勒多项式：②显然，……2023/1/317结论：pn(x)与f(x)在x0点具有相同的k阶导数值：因此，

pn(x)在x0的邻近能很好地逼近f(x)。定理1

假设f(x)在含有点x0的区间[a,b]内有直到n+1阶导数，则对于pn(x)

，有10)1()()!1()()()(++-+=-nnnxxnfxpxfx——泰勒余项定理2023/1/318泰勒插值已知一组数据，求n次多项式pn(x),使得pn(x)满足(*)对某一函数f(x)，已知一组数据

求pn(x),使得pn(x)满足由上面知，f(x)的泰勒多项式满足(*)式条件，所以f(x)的泰勒插值多项式就是pn(x)。2023/1/319例1求在x0=100的一次、二次泰勒多项式，利用他们计算的近似值，并估计误差解：已知x0=100,所以有3位有效数字。如果不知道如何估计误差？2023/1/3110误差同理有4位有效数字。2023/1/3111结论：利用f(x)的泰勒多项式研究f(x)，需知f(x)在某点x0的各阶导数，这不易做到。2.拉格朗日插值拉格朗日插值：求n次多项式pn(x),满足条件其中，xi为插值节点，

几何语言描述：通过曲线y=f(x)上给定的n+1个点(xi,yi

)

(i=0,1,…,n),求作一条n次代数曲线y=pn(x)作为y=f(x)的近似。2023/1/31120xyPn(x)f(x)注:

n次插值多项式pn(x)，精确讲应该是次数≤n的插值多项式，如下图2023/1/3113插值多项式的存在性、唯一性[利用待定系数法求解并证明]已知[证pn(x)存在并唯一]证：[证ai存在并唯一]分别将代入上式得：求关于未知量a0,a1,……,an

的n+1阶线性方程组，如何判断此方程有解？2023/1/3114判断方程组的系数行列式≠0？上式是范德蒙行列式，由已知xi≠xj

,若i≠j,所以，根据线性代数知识，该行列式≠0，从而证明方程组解存在并唯一。

注：上述显然是求解pn(x)的一种方法，但此方法工作量大，不便应用。2023/1/31151.2拉格朗日插值公式1.线性插值求通过两点(x0,y0)、(x1,y1)函数的插值多项式.因n=1,插值多项式的次数≤1（一条直线）.yx0p1(x)f(x)x0x1过两点(x0,y0)、(x1,y1)的线性方程：2023/1/3116即称为线性插值多项式.当y1=y0时，p1(x)=y0——0次多项式.例2(P16)已知解(点斜式)2023/1/3117将(1)变形:【便于研究多节点的pn(x)】称为拉格朗日插值基函数.

——显然是一次的(对称式)2023/1/31182.抛物插值线性插值仅仅利用两个节点的信息，精度低，为了提高精度，下面考察三个插值节点的情形.已知(x0,y0)、

(x1,y1)和(x2,y2),n=2.所求插值多项式次数≤2.

由线性插值知：启示：？能否求得且满足关键是能否构造出2023/1/3119逆推：假设l0(x0)=1,l0(x1)=0,l0(x2)=0，可得x1,x

2

是l0(x)的两个零点，即l0(x)含有x-x1与x-x2两个因式,则l0(x)=c(x-x1)(x-x2)，c未知，下面求c。由l0(x0)=1,得同理以l0(x)

,l1(x),l2(x)作为基函数的二次插值多项式是：(4)——抛物插值公式2023/1/3120例3(P18).利用100,121,144的开方值求解

利用抛物插值：有4位有效数字。2023/1/31213.一般情形求过n+1个互异点的插值多项式。从插值基函数入手，是n次多项式，且满足条件（*）式表明：有个零点，由lk(xk)=1,代入(5)式，得：∏j=0j≠kn1∏j=0j≠kn代入(5)式，∏j=0j≠kn∏j=0j≠kn从而得∏j=0j≠kn2023/1/3122∏j=0j≠knpn(x)是次数≤n的多项式，且附：已知(xi,yi),i=0,1,…,n及x，编程求y.main(){int

j,k,n;floatx,y=0,t,ax[15],ay[15];

printf(“n,x=”);

scanf(“%d%f”,&n,&x);——拉格朗日插值公式2023/1/3123

for(k=0;k<n;k++){printf(“ax[%d]ay[%d]:”,k,k);

scanf(“%f%f”,&ax[k],&ay[k]);}

for(k=0;k<=n;k++){t=1;

for(j=0;j<=n;j++){if(k==j)continue;t=t*(x-ax[j])/(ax[k]-ax[j]);}y=y+t*ay[k];}

printf(“y=%f\n”,y);}2023/1/31241.3

插值余项1.

拉格朗日余项定理插值：就是依据f(x)所给出函数表“插出”所需函数值.插值函数pn(x)只是近似地刻画了原函数f(x)，而∀x≠xi

,pn(xi

)与f(xi

)是有一定误差的。称为插值函数的截断误差或插值余项。插值函数pn(x)是否有效地近似于f(x)，看R

(x)是否满足所需要的精度。2023/1/3125定理3

设区间[a,b]含有节点x0,x1,…xn,f(x)在[a,b]内有连续的直到n+1阶导数，且f(xi)=yi

(i=0,1,2,…,n),则当x∈[a,b]时，对于pn(x),有∏j=0j≠kn

(11)成立，其中与x有关，且∈[a,b]。转回2023/1/3126补充：拉格朗日中值定理xy0abf(x)若函数f(x)①在[a,b]上连续②在(a,b)内可导则至少∃∈(a,b)，使得罗尔定理xy0abf(x)①、②同上③f(a)=f(b)则至少∃∈(a,b)，使得换句话:f(a)=f(b),则f

(x)在(a,b)上至少存在一个零点.进一步:f(a)=f(b)=0,则f

(x)在(a,b)上至少存在一个零点.2023/1/3127证明：当x等于某个xi(i=0,1,…,n)时，显然(11)式两端都等于0，转(11)定理成立。假设x≠xi(i=0,1,…,n)，构造辅助函数——关于t的函数其中显然:∵f(t)、pn(t)、ω(t)都是(a,b)上n+1阶可导函数,∴g(t)在(a,b)上具有n+1阶导数。证明：2023/1/3128显然g(t)在(a,b)上有n+2个互异的零点：x,x0,x1,…,xn由罗尔定理：g’(t)在(a,b)上至少有n+1个零点；同理g”(t)在(a,b)上至少有n个零点；g(n+1)(t)在(a,b)上至少有1个零点，反复用罗尔定理，记为ξ∈(a,b),有g(n+1)(ξ)=0，显然ξ与x有关。（*）将ξ代入(*)式，得其中继续2023/1/3129f(x)有2个零点xk和xk+1，f’(x)至少有

个零点1ξ.f(x)有3个零点xk,xk+1和xk+2，f’(x)至少有

个零点:2ξ1和ξ2.ξxkxk+1f(x)返回ξ1ξ2f(x)xkxk+1xk+22023/1/3130注意：如果插值点x偏离插值节点xi较远，插值效果可能不理想。一般当f(x)是次数不高于n的多项式时，无论互异点xi(i=0,1,…,n)如何选取，f(x)的插值多项式pn(x)就是f(x)本身。特别：f(x)≡1的pn(x)对于任意互异的xi

(i=0,1,…,n)的插值基函数，有——插值区间2023/1/31312.误差的事后估计利用(11)式，在f(x)未知的情况下，去估计误差是困难的。下面介绍另外一种误差分析方法。三个插值节点x0,x1,x2:根据余项定理：1)利用x0,x1进行线性插值,求出f(x)的一个近似，记为y1;~2)利用x0,x2进行线性插值,求出f(x)的另一个近似,记为y2.~y=f(x),f(x)≈p01(x)=y1,f(x)≈p02(x)=y2,~~~~

假设f”(x)在[a,b]内变化不大，将两式相除:2023/1/3132~~~~~~可见：利用(x1,y1)、(x2,y2)作线性插值,得(15)~~~~y1的误差可通过y2-y1来估计——事后估计.~~所以：2023/1/3133xy0x0x1x2p01(x)p02(x)x~y1~y22023/1/3134例4(P21例4).

已知x0=100,x1=121,x2=144,x=115

y0=10,y1=11,y2=12,y=?根据(15)式:~~~~解：由例2，用x0,x1作线性插值，求得y1=10.71428用x0,x2作线性插值，求得y2=10.68182~~2023/1/3135变题：上述原函数改为，结果又如何？例题讲解——Lagrange

插值例1

设,试用Lagrange插值公式给出以-1，0，1，2为节点的三次插值多项式.你从中感悟到什么结论？若f(x)本身就是k次多项式函数，并且对它进行n次插值的Lagrange插值函数Pn(x)，则有当n>=k时,Pn(x)

≡f(x);否则,

Pn(x)

≠f(x).2023/1/3136例题讲解——Lagrange

插值例2

证明：由下列插值条件所确定的Lagrange插值多项式是一个2次多项式.Pn(x)

=x^2-1对f(x)进行n次插值的Lagrange插值函数Pn(x)，则有Pn(x)并非一定是n次多项式，而是次数≤n.x00.511.522.5f(x)-10.7501.2525.25你从中感悟到什么结论？2023/1/3137例题讲解——Lagrange插值例3

设是以为节点的Lagrange插值基函数，证明：（1）（2）（3）（4）2023/1/3138例题讲解——Lagrange插值余项例4

设充分光滑，，证明：2023/1/3139§1.5牛顿插值

（Newton’sInterpolation）Lagrange插值虽然易算，但若要增加一个节点时，全部基函数

li

(x)都需要重新计算.能否重新在Pn中寻找新的基函数？希望每加一个节点时，只附加一项上去即可。------不具“承袭性”2023/1/31401.利用承袭性构造插值公式线性插值：记：则：启发：过三点的插值多项式p2(x)是否可以由p1(x)得到?即p1(x)可以由p0(x)得到.【看作是零次插值多项式】2023/1/3141∵是函数f(x)节点，所以有整理后：令(0)关键是能否求出c2？只能利用显然，这两式与求c2无关，所以,求

c2。由(0)式2023/1/31422.差商及其性质1)关于x0，x1的一阶差商定义：(23)2023/1/31432)关于x0，x1

，

x2的二阶差商定义：3)关于x0,x1，……,xn的n阶差商定义：差商可用离散的节点的函数值表示:对①变形：----具有“承袭性”2023/1/3144对②变形：对③变形：∏j=0j≠kn结论：差商与节点的排列顺序无关——差商的对称性即2023/1/31453.差商形式的插值公式根据差商定义：同理可推出：……………………2023/1/3146除第一式外，反复将后一式代入前一式得：令2023/1/3147下面说明pn(x)是f(x)的n次插值多项式:∵∀xi

(i=0,1,…,n),有R

(xi)=0又∵f(x)=pn(x)

+R(x)

∴f(xi)=pn(xi

)

(i=0,1,…,n)——插值条件∴pn(x)是f(x)的n次插值多项式，R(x)为插值余项.⑤式称为牛顿插值公式.由插值问题的唯一性知：牛顿插值公式是拉格朗日公式的一种变形.2023/1/3148定理4

在节点x0,x1,…,xn

所界定的范围I：内，存在一点，使得证明：由插值余项定理(P19)，即区间[a,b]上有n+1个节点x0,x1,…xn

,f(x)在[a,b]内有连续的n+1阶导数，且f(xi)=yi(i=0,1,2,…,n),则对于插值多项式

pn(x)，有两式比较得：2023/1/3149根据⑦式,牛顿插值多项式：特别：固定x0，当xi→x0(i=1,2,…,n)，可得到泰勒公式.可变形为：2023/1/3150补充：差商表xif(xi)一阶二阶三阶四阶x0f(x0)x1f(x1)f(x0,x1)x2f(x2)f(x1,x2)f(x0,x1,x2)x3f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)f(x0,x1,x2,x3,x4)………………………2023/1/3151………………………四阶三阶二阶一阶1.26520.90.888110.80.696750.650.578150.550.410750.4f(xi)xi例：函数f(x)的数据表xi0.40.550.650.80.9f(xi)0.410750.578150.696750.888111.26521.1161.1861.275731.38410.280.358930.433480.197330.031340.213R(x)=?2023/1/3152若

x=0.62,f(x)=?R(x)=?2023/1/31534、差分形式的插值公式在实际应用Newton插值多项式时，经常遇到插值节点是等距的，即n+1个插值节点：

这里间距

h

为定数，称为步长.于是在差商中，分母部分将变得简单，计算量主要集中在分子（两节点处函数值的差）.定义：设函数f

(x)在等距节点上的值为：则称：为f(x)

在处一阶差分称：为f(x)在处二阶差分2023/1/3154

依据所给数据

可以逐步求出它的各阶差分，而生成如下形式的差分表：称：为f

(x)在处n

阶差分.2023/1/3155例：给定

的函数表如下：00.10.20.30.40.50.610.9950.980070.955340.921060.877580.825342023/1/3156在节点等距的情况下，差商可用差分来表示.有2023/1/3157

这样，对于等距节点的情况，将牛顿插值公式中的差商换成相应的差分。令：则：于是，牛顿插值公式中的一般项则称此公式为函数插值的有限差分公式2023/1/3158例：已知函数y=sinx

的如下函数值表，利用插值法计算Sin(0.42351)的近似值。

x0.40.50.6Sinx0.389420.479430.56464解：因为节点是等距分布的，可以使用牛顿插值公式取建立如下差分表xSin(x)一阶差分二阶差分0.40.389420.50.479430.090010.60.564640.08521-0.004802023/1/3159利用插值公式有：2023/1/31601.6埃尔米特插值前面讨论的插值问题只要求多项式pn

(x)满足

pn(xi)=f(xi),i=0,1,…,n,得到的插值多项式不能全面反映被插函数f(x)的性态.如果插值条件再增加对节点处导数的限制,则构造的多项式一定能更好地逼近函数f(x).1.求p2(x),满足

即p2(x)与f(x)有两个交点(x0,y0),(x1,y1),且在(x0,y0)点两者相切。解一：基于承袭性:---切触插值、Hermite插值2023/1/3161代入（*）式得因为条件无助于求解c，因此要利用。对上式两端关于x求导得2023/1/3162解二：基函数方法首先，假设x0=0,x1=1,

求p2(x).其中是二次基函数.下面求解它们.1是的零点,令解得,同理解得,由2023/1/3163对任意两点x0,x1，记h=x1-x0，显然，所以有因此∆∆(ζ与x0,x1,x有关)插值余项：2023/1/31642.求p3(x)，满足p3(x0)=y0，p’

3(x0)=y’

0，p3(x1)=y1，

p’

3(x1)=y’

1.方法同上求解p3(x)：(ζ与x0,x1,x有关)插值余项：(练习,自证)2023/1/31651.7分段插值法1.高次插值的龙格现象对于插值多项式，其次数随着节点的增加而升高(特殊情况除外)，而高次插值的逼近效果往往并不理想，即：并非次数越高越好。例将区间n等分，有n+1个等分点，以n+1个分点作为插值节点，求pn(x)。当n=5、10时，教材P30给出p5(x),p10(x)的图形。2023/1/31662023/1/3167虽然高次插值函数会在更多的点上与f(x)取值相同，但整体上看，逼近效果不一定理想.上例中n↗,

pn(x）在两端发生激烈的震荡——龙格现象.2.分段插值的概念事实表明：克服龙格现象的有效方法之一是：采用分段低次插值，即在较小的范围内，运用低次插值.对上述函数f(x)在每个子段上用线性插值,就能保证一定要求的逼近效果。2023/1/3168分段插值步骤：1).将区间[a,b]作一分划∆:a=x0<x1<……<xn=b在每个子段[xi,xi+1]上构造插值多项式;2).

将每个子段上插值多项式拼接在一起，作为整个区间[a,b]上的插值函数——分段插值多项式.如果函数sk(x)在分划∆的每个子段[xi,xi+1]上都是k次式(不超过k),则称sk

(x)为具有分划∆的分段k次式.点xi(i=0,1,…,n)称作sk(x)的节点.3.分段线性插值假设已知一组数据点(xi,yi),i=0,1,…,n.连接相邻两点得一折线，那么该折线函数就是线性插值函数.2023/1/3169xy0下面求分段线性插值函数s1(x).s1(x)满足s1(xi)=yi

,i=0,1,…,n.考察区间[xi,xi+1]：插值函数s1(x)应满足s1(xi)=yi

,s1(xi+1)=yi+1，令hi=xi+1-xi,则有2023/1/3170

f(x)在[xi,xi+1]上有误差估计式：如何证明上式？定理4

设f(x)∈C

2[a,b]，且f(xi)=yi

,i=0,1,…,n,s1(x)是f(x)的分段线性插值函数，则当x∈[a,b]时，有|f(x)-s1(x)|≤|f”(x)|,h=

hi,因而s1(x)在[a,b]上一致收敛到f(x).h28maxa≤x≤bmaxi2023/1/31714.分段三次插值分段线性插值的算法简单，计算量小，但精度不高，插值曲线也不光滑分段,即在x1,x2,…,xn-1处一阶导数不连续.而分段三次埃尔米特插值具有较好的逼近效果.分段三次埃尔米特插值：具有分划∆的分段三次式s3(x),满足

s3(xi)=yi

,s’3(xi)=y’i

,i=0,1,…,n.在子段[xi,xi+1]上:s3(xi)=yi

,s’3(xi)=y’i

,s3(xi+1)=yi+1,s’3(xi+1)=y’i+1.根据上节知识，2023/1/3172定理5

设f(x)∈C4[a,b]，且f(xi)=yi,f’(xi)=y’i

,

i=0,1,…,n,s3(x)是f(x)的分段埃尔米特插值式,则当x∈[a,b]时，有|f(x)-s3(x)|≤|f(4)(x)|,h=hi。h4384maxa≤x≤bmaxi2023/1/3173总结：f(x)连续⇒分段线性插值函数是一致收敛的.分段插值算法简单.只要节点间距充分小,分段插值法就能得到要求的精度，而不会出现龙格现象.分段插值函数具有局部性质.如果修改某个数据，插值曲线仅在某个局部范围内受到影响.分段三次插值式s3(x)只有在被插函数的所有节点处的函数值和导数值都已知的情况下才能使用;且s3(x)在内节点处的二阶导数一般不连续，因而它的光滑性不高.2023/1/31741.9曲线拟合的最小二乘法从一组观测数据(xi,yi

)，i=1,2,…,n来预测函数y=f(x)的表达式,从几何角度来说,就是由给定的一组数据点(xi,yi

)来描绘出曲线y=f(x)的近似图像。插值方法是一种数值方法，用它来处理这类问题时:1)插值曲线要求严格通过给定的每个数据点;2)如果数据点的数据本身有误差,个别情况下误差很大,这样插值的效果并不理想。曲线拟合方法：从大量看似杂乱无章的数据中找出规律,设法构造一条曲线,能反映出所有数据点总趋势。2023/1/31751.直线拟合假设所给数据点(xi,yi)，i=1,2,…,N

的分布大致成一直线，所求的拟合直线y=a+bx

尽可能地从数据点附近通过，即记^是拟合直线上关于xi点值yi

的近似值。记ei=yi

-yi

——残差。^关于残差大小的衡量有三种准则：（1）使残差的最大绝对值为最小：i（2）使残差的绝对值之和为最小：i2023/1/3176（3）使残差的平方和为最小：由于(1),(2)含有绝对值运算，不便于实际运用，用(3)来选取拟合曲线的方法称为曲线拟合的最小二乘法。直线拟合：对于给定的数据(xi,yi),i=1,2,…,N,求作一次式y=a+bx,使得总残差关于未知量a,b的二元函数二元函数求极值问题最小2023/1/3177补充：f(x,y)在(x0,y0)某领域内具有一阶、二阶连续

偏导数，且fx(x0,y0)=0,fy(x0,y0)=0(极值条件),若-[fxy(x0,y0)]2+fxx(x0,y0)·fyy(x0,y0)>0fxx(x0,