数值分析第二章-插值总结课件

第二章插值方法/*Interpolation*/Interpolation_introduction§1

问题提出—函数逼近

/*problemformulation-----functionapproximation*/用第二章插值方法/*Interpolation*/InInterpolation_introduction函数逼近的方法有很多，例如Taylor级数，Fourier级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。本书讨论连续函数的逼近，主要介绍插值法(chapter2)和最佳一直逼近、最小平方逼近离散数据拟合(chapter3)Interpolation_introduction函数逼近Interpolation_introduction插值节点插值条件---插值问题多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章数值积分和数值微分），解微分方程（第五章）、积分方程插值Interpolation_introduction插值节点多项式插值----polynomialinterpolationProblemI.

给定y=f(x)的函数表,xi[a,b]niyxPiin,...,0,)(==求次数不超过n

的多项式使得条件：无重合节点，即InterpolationintervalInterpolationconditionInterpolationpolynomialInterpolationpointsInterpolationpolynomial

(2.1)(2.2)多项式插值----polynomialinterpolatx0x1x2x3x4xPn(x)

f(x)多项式插值的几何意义Interpolationpolynomial

求x0x1x2x3x4xPn(x)f(x)多项式插值的几插值多项式的唯一性

提问：ProblemI中的Pn(x)是否存在？若存在，是否唯一？如何求？Interpolationpolynomial

插值多项式的唯一性提问：ProblemI中的PInterpolationpolynomial

如何求？解线性方程组（2.3）----待定系数法Interpolationpolynomial如何求？解Interpolationpolynomial

Interpolationpolynomial§2拉格朗日多项式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

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

y0,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0,y0)和

(x1,y1)

两点的直线。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij

/*KroneckerDelta*/§2LagrangePolynomial§2拉格朗日多项式/*LagrangePolynn

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

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

。li(x)每个li有n

个根x0…

xi…xn==jiC0=-njijxx)(---inxxixxxxC0))...()...((ixl)(-=jijxixiC)(1=iixl1)(LagrangePolynomial与节点有关，而与f无关==niinxlxP0)()(yi基函数法（n=1情形的推广）§2LagrangePolynomialn1希望找到li(x)，i=0,…,n使得定理(唯一性)满足的n

阶插值多项式是唯一存在的。证明：(前面已利用Vandermonde

行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n

阶多项式Pn(x)满足Pn(xi)=yi

。考察则Qn

的阶数n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n

，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。§2LagrangePolynomial定理(唯一性)满足

插值余项

/*Remainder*/设节点在[a,b]内存在,考察截断误差，且f

满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。推广：若使得使得存在使得Rn(x)至少有个根n+1=-=niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2

个不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意这里是对t求导=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§2LagrangePolynomial插值余项/*Remainder*/设节点在[a,§1LagrangePolynomial注：

通常不能确定x

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

将作为误差估计上限。当

f(x)为任一个次数n

的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。Quiz:

给定xi=i+1,i=0,1,2,3,4,5.

下面哪个是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

ABC§1LagrangePolynomial注：通常不§1LagrangePolynomial例：已知分别利用sinx的1次、2次Lagrange插值计算sin50

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

以及x1,x2

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

/*extrapolation*/

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

/*interpolation*/

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

所在的区间的端点，插值效果较好。§1LagrangePolynomial例：已知分别利§1LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……§1LagrangePolynomialn=2)1Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemnexttime.Whenyoustart§3逐次线性插值

/*LagrangePolynomial*/§3逐次线性插值/*LagrangePolyno数值分析第二章-插值总结课件实际上，是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为逐次线性插值。

Aitken法(按下表计算)线性插值基函数实际上，是对两个低次插值的线性插值，这种通过低次插值再作线性增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。k1k0k2k3k4增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边

Neville法(按下表计算)增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。k1k0k1k1k1HW:用类似于前面的方法构造Neville计算公式Neville法(按下表计算)增加如果精度不构，增加节点注：Atkin方法和Neville方法与Lagrange公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适当变化。误差估计：由插值多项式的存在唯一性知，仍有但这里可采用一种更简便的方法。当f(n+1)(x)在插值区间变化不大时，设f(n+1)(x)L，则有注：Atkin方法和Neville方法与Lagrange公式可认为满足精度要求。根据前面的计算结果估计当前的误差：事后误差估计（实用），前面给出的误差估计（事先误差估计）不实用HW:p.58-59#1-8可认为§4牛顿插值/*Newton’sInterpolation*/Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。公式不具有继承性，不利于编程。将Ln(x)改写成的形式，希望每加一个节点时，只附加一项上去即可。????

差商(亦称均差)

/*divideddifference*/1阶差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2阶差商f(x0)1阶差商的几何意义：弦截线的斜率§4Newton’sInterpolation§4牛顿插值/*Newton’sInterpol§4Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商：事实上其中Warning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi

的顺序无关！§4Newton’sInterpolation11101.线性：2.差商可以表示为函数值的线性组合：3.

对称性：由2知，差商的值与节点的顺序无关！4.

差商的另一种定义：由2，3及均差定义可得§4Newton’sInterpolation1.线性：2.差商可以表示为函数值的线性组合：3.对称性：6.5.

差商与导数的关系：f(x)Ck[a,b],则[a,b],s.t.HW:证明差商的性质2，4§4Newton’sInterpolation6.5.差商与导数的关系：f(x)Ck[a,b],则§4Newton’sInterpolation牛顿插值

/*Newton’sInterpolation*/…………Nn(x)—n次多项式，满足：Nn(xi)=f(xi)Rn(x)—插值余项，满足Rn(xi)=0，i=0,…,n

ai=

f[x0,…,xi](1)(2)(n)(n)(n-1)…(2)(1)§4Newton’sInterpolation牛顿§4Newton’sInterpolation注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，表达形式不同，故其余项也相同，即

实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]增加如果精度不构，增加节点xn+1,同时表中增加一行，三角形斜边上即为所要求的各次项系数。§4Newton’sInterpolation注：数值分析第二章-插值总结课件§4Newton’sInterpolation

等距节点公式

/*FormulaewithEqualSpacing*/向前差分

/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分

/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分

/*centereddifference*/其中当节点等距分布时:fi=f(xi)§4Newton’sInterpolation等距

差分计算可通过构造差分表得到增加差分计算可通过构造差分表得到增加数值分析第二章-插值总结课件

差分的重要性质：

线性：例如

各阶差分可用函数值表示：其中/*binomialcoefficients*/§4Newton’sInterpolation

函数值可用各阶差分表示：差分的重要性质：线性：例如各阶差分可用函数值表

差商与差分的关系：

若f(x)是n

次多项式，则是次多项式，而差商与差分的关系：若f(x)是n次多项式，则

差分与导数的关系(由差分与差商、差商与导数的关系得）：差分与导数的关系(由差分与差商、差商与导数的关系得）：§4Newton’sInterpolation等距节点牛顿公式

牛顿前差公式/*Newton’sforward-differenceformula*/§4Newton’sInterpolation等距节点注：一般当x

靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。

牛顿后差公式/*Newton’sforward-differenceformula*/HW:p.59#9-16注：一般当x靠近x0时用前插，靠近xn时用后插，§5厄米插值/*HermiteInterpolation*/§5厄米插值/*HermiteInterpola不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数

(x)

满足

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

(mi)(xi).注：

N

个条件可以确定

阶多项式。N

1要求在1个节点x0处直到m0

阶导数都重合的插值多项式即为Taylor多项式其余项为一般只考虑f

与f'的值。厄米插值不仅要求函数值重合，而且要求若干阶导数也重合。注：N个§3HermiteInterpolation例：设x0

x1x2,已知f(x0)、f(x1)、f(x2)

和f’(x1),求多项式P(x)

满足P(xi)=f(xi)，i=0,1,2，且P’(x1)=f’(x1),并估计误差。模仿Lagrange多项式的思想，设解：首先，P

的阶数=3+=213)()()()()(=0iiixhx1f’xhxfxPh0(x)有根x1,x2，且h0’(x1)=0x1是重根。)()()(22100xxxxCxh--=又:h0(x0)=1C0h2(x)h1(x)有根x0,x2

))()(()(201xxxxBAxxh--+=由余下条件h1(x1)=1和

h1’(x1)=0可解。与h0(x)完全类似。

(x)h1有根x0,x1,x2

h1))()(()(2101xxxxxxCx---=h1又:’(x1)=1C1

可解。其中hi(xj)=ij,hi’(x1)=0,

(xi)=0,

’(x1)=1h1h1与Lagrange分析完全类似§3HermiteInterpolation例：设x§3HermiteInterpolation一般地，已知x0

,…,xn

处有y0

,…,

yn

和y0’

,…,yn’

，求H2n+1(x)

满足H2n+1(xi)=yi，H’2n+1(xi)=yi’。§3HermiteInterpolation一般地，已数值分析第二章-插值总结课件解：设+=ni)()()(=0iixxyixH2n+1n=0iyi’其中

i(xj)=ij,i’(xj)=0,

(xj)=0,

’(xj)=ij

ii(x)有根x0

,…,xi,…,xn且都是2重根由余下条件i

(xi)=1和

i’(xi)=0可解Ai

和Bi

(x)i有根x0

,…,xn,除了xi

外都是2重根i)()(iili2(x)xxCx-=又i(xi)=1Ci

=1i)(x)(ili2(x)xx-=设则这样的Hermite插值唯一i)()()(2xlBxAxiii+=i解：设+=ni)()()(=0iixxyixH2n+1数值分析第二章-插值总结课件数值分析第二章-插值总结课件数值分析第二章-插值总结课件类似的，类似的，Th.设f(x)C2n+2[a,b],则[a,b],s.t.满足下面插值条件Th.设f(x)C2n+2[a,b],则[a数值分析第二章-插值总结课件数值分析第二章-插值总结课件数值分析第二章-插值总结课件数值分析第二章-插值总结课件数值分析第二章-插值总结课件§3HermiteInterpolationQuiz:

给定xi=i+1,i=0,1,2,3,4,5.

下面哪个是i(x)的图像？x0--10.5123456yxy0---10.5123456斜率=1

求Hermite多项式的基本步骤：写出相应于条件的i(x)、i(x)的组合形式；对每一个i(x)、i(x)找出尽可能多的条件给出的根；根据多项式的总阶数和根的个数写出表达式；根据尚未利用的条件解出表达式中的待定系数；最后完整写出H2n+1(x)。HW:p.59#17-19注：待定系数法仍适用，但插值节点多时比较麻烦。§3HermiteInterpolationQuiz:§4分段低次插值/*piecewisepolynomialapproximation*/RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端点附近抖动越大，称为Runge现象Ln(x)f(x)分段低次插值§4分段低次插值/*piecewisepolyn§4PiecewisePolynomialApproximation

分段线性插值

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

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

分段Hermite插值

/*Hermitepiecewisepolynomials*/给定在上利用两点的y及y’构造3次Hermite函数导数一般不易得到。Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache…§4PiecewisePolynomialAppro§5三次样条

/*CubicSpline*/定义设。三次样条函数

,

且在每个上为三次多项式

/*cubicpolynomial*/。若它同时还满足，则称为f的三次样条插值函数

/*cubicsplineinterpolant*/.注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。f(x)H(x)S(x)§5三次样条/*CubicSpline*/定§5CubicSpline

构造三次样条插值函数的三弯矩法

/*methodofbendingmoment*/在上，记],[for)()(1][jjjxxxxSxS-=对每个j,此为3次多项式则S[j]”(x)为次多项式，需个点的值确定之。12设S[j]”(xj1)=Mj1，S[j]”(xj)=Mj

对应力学中的梁弯矩，故名对于x

[xj1,

xj

]可得到S[j]”(x)=jjjjjjhxxMhxxM11---+-积分2次，可得S[j]’(x)和S[j](x)：jjjjjjjAhxxMhxxM+-+-----2)(2)(21121S[j]’(x)=jjjjjjjjBxAhxxMhxxM++-+---6)(6)(3131S[j](x)=利用已知S[j](xj1)=yj1

S[j](xj)=yj

可解§5CubicSpline构造三次样条插值函数的§5CubicSplinejjjjjjjhMMhyyA611-----=jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6(-----+--=+下面解决Mj

：利用S’

在xj的连续性[xj1,

xj

]:

S[j]’(x)=jjjjjjjjjjjhMMxxfhxxMhxxM6],[2)(2)(112121------+-+--1111211216],[2)(2)(+++++++--+-+--jjjjjjjjjjjhMMxxfhxxMhxxM[xj,

xj+1]:

S[j+1]’(x)=利用S[j]’(xj)=S[j+1]’(xj)，合并关于Mj1、

Mj、Mj+1的同类项，并记,,,整理后得到：11jjjjhhh+++=l1jj-=lm]),[],[(6111jjjjjjjxxfxxfhhg-++-+=211gMMMjjjjjj=+++-lm

j

1n1即：有个未知数，

个方程。n1n+1还需2个边界条件

/*boundaryconditions*/§5CubicSplinejjjjjjjhMMhyy§5CubicSpline

第1类边条件

/*clampedboundary*/：S’(a)=y0’，S’(b)=yn’[a

,

x1

]:

S[1]’(x)=1011012112106],[2)(2)(hMMxxfhaxMhxxM--+-+--010110)],[(62gy0’xxfhMM=-=+nnnnnngxxfyn’hMM=-=+--]),[(6211类似地利用[xn1,

b

]上的

S[n]’(x)

第2类边条件：S”(a)=y0”

=

M0，S”(b)=yn”

=

Mn这时：特别地，M0=

Mn=0

称为自由边界

/*freeboundary*/，对应的样条函数称为自然样条

/*NaturalSpline*/。

第3类边条件/*periodicboundary*/

：当f

为周期函数时，

yn

=y0

，

S’(a+)=S’(b)

M0=

Mn§5CubicSpline第1类边条件/*c§5CubicSpline注：另有三转角法(p.49-53)得到样条函数，即设S[j]’(xj)=mj，则易知[xj1,

xj

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

f(x)即:提高精度只须增加节点,而无须提高样条阶数。稳定性：只要边条件保证|0|,|0|,|n|,|n|<2，则方程组系数阵为SDD阵，保证数值稳定。HW:p.59-60,#19-25§5CubicSpline注：另有三转角法(p.4§5CubicSpline

SketchoftheAlgorithm:CubicSpline①

计算j,j,gj;

②

计算Mj(追赶法等);③

找到x

所在区间(即找到相应的j);④

由该区间上的S[j](x)算出f(x)的近似值。插值法小结Lagrange:给出y0…

yn，选基函数li(x)，其次数为

节点数–1。

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

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

i(x)

。Spline：分段低次,自身光滑,f的导数只在边界给出。§5CubicSplineSke§6快速傅立叶变换

/*FastFourierTransform*/问题的背景/*background*/傅立叶变换

——函数展开为三角级数设f(x)周期为2，在[0,2]上展开为三角级数，其中Cj

为复系数，，则实际计算时要取级数的前N项，并要求在区间的N

个等分点上与f(x)重合。即：给定[0,2]上N个等分点上的函数值，令满足插值条件。N个未知数N个方程DiscreteFourierTransformInverseofDFT总之要进行形如的计算，其中已知，§6快速傅立叶变换/*FastFourierT§6FastFourierTransform

FastFourierTransform快速计算(j=0,1,…,N1)，其中直接计算需复数乘法次N2

降到N·logN由于W的周期性WqN+s=Ws,Wkj实际上只有这

个不同的值。若N

为偶数，则Wkj只有个不同值。10...-NWWN

N/2先合并同类项，再做乘法。I’mgonnaneedsomemagichere…§6FastFourierTransformFa§6FastFourierTransform例：N=23=8,计算，j=0,1,2,3,4,5,6,7技巧：将k,j

先记为二进制数

/*binarynumbers*/=++==++=)(222)(222012001122012001122jjjjjjjkkkkkkkkjW)222()222(001122001122++++=kkkjjjW)()222()222(012010213212031422kkkjkkkjkkkjW++++++=)()0()00(012001102kkkjkkjkjW++=23次乘法全部计算需要238次乘法一般地：取N=2p

，每个Cj

用2p

次乘法，共用2Nlog2N

次乘法。利用，还可以进一步化简到N(p1)/2

次乘法。HW:p.138#1§6FastFourierTransform例：N第二章插值方法/*Interpolation*/Interpolation_introduction§1

问题提出—函数逼近

/*problemformulation-----functionapproximation*/用第二章插值方法/*Interpolation*/InInterpolation_introduction函数逼近的方法有很多，例如Taylor级数，Fourier级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。本书讨论连续函数的逼近，主要介绍插值法(chapter2)和最佳一直逼近、最小平方逼近离散数据拟合(chapter3)Interpolation_introduction函数逼近Interpolation_introduction插值节点插值条件---插值问题多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章数值积分和数值微分），解微分方程（第五章）、积分方程插值Interpolation_introduction插值节点多项式插值----polynomialinterpolationProblemI.

给定y=f(x)的函数表,xi[a,b]niyxPiin,...,0,)(==求次数不超过n

的多项式使得条件：无重合节点，即InterpolationintervalInterpolationconditionInterpolationpolynomialInterpolationpointsInterpolationpolynomial

(2.1)(2.2)多项式插值----polynomialinterpolatx0x1x2x3x4xPn(x)

f(x)多项式插值的几何意义Interpolationpolynomial

求x0x1x2x3x4xPn(x)f(x)多项式插值的几插值多项式的唯一性

提问：ProblemI中的Pn(x)是否存在？若存在，是否唯一？如何求？Interpolationpolynomial

插值多项式的唯一性提问：ProblemI中的PInterpolationpolynomial

如何求？解线性方程组（2.3）----待定系数法Interpolationpolynomial如何求？解Interpolationpolynomial

Interpolationpolynomial§2拉格朗日多项式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

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

y0,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0,y0)和

(x1,y1)

两点的直线。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij

/*KroneckerDelta*/§2LagrangePolynomial§2拉格朗日多项式/*LagrangePolynn

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

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

。li(x)每个li有n

个根x0…

xi…xn==jiC0=-njijxx)(---inxxixxxxC0))...()...((ixl)(-=jijxixiC)(1=iixl1)(LagrangePolynomial与节点有关，而与f无关==niinxlxP0)()(yi基函数法（n=1情形的推广）§2LagrangePolynomialn1希望找到li(x)，i=0,…,n使得定理(唯一性)满足的n

阶插值多项式是唯一存在的。证明：(前面已利用Vandermonde

行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n

阶多项式Pn(x)满足Pn(xi)=yi

。考察则Qn

的阶数n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n

，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。§2LagrangePolynomial定理(唯一性)满足

插值余项

/*Remainder*/设节点在[a,b]内存在,考察截断误差，且f

满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。推广：若使得使得存在使得Rn(x)至少有个根n+1=-=niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2

个不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意这里是对t求导=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§2LagrangePolynomial插值余项/*Remainder*/设节点在[a,§1LagrangePolynomial注：

通常不能确定x

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

将作为误差估计上限。当

f(x)为任一个次数n

的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。Quiz:

给定xi=i+1,i=0,1,2,3,4,5.

下面哪个是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

ABC§1LagrangePolynomial注：通常不§1LagrangePolynomial例：已知分别利用sinx的1次、2次Lagrange插值计算sin50

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

以及x1,x2

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

/*extrapolation*/

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

/*interpolation*/

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

所在的区间的端点，插值效果较好。§1LagrangePolynomial例：已知分别利§1LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……§1LagrangePolynomialn=2)1Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemnexttime.Whenyoustart§3逐次线性插值

/*LagrangePolynomial*/§3逐次线性插值/*LagrangePolyno数值分析第二章-插值总结课件实际上，是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为逐次线性插值。

Aitken法(按下表计算)线性插值基函数实际上，是对两个低次插值的线性插值，这种通过低次插值再作线性增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。k1k0k2k3k4增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边

Neville法(按下表计算)增加如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。k1k0k1k1k1HW:用类似于前面的方法构造Neville计算公式Neville法(按下表计算)增加如果精度不构，增加节点注：Atkin方法和Neville方法与Lagrange公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适当变化。误差估计：由插值多项式的存在唯一性知，仍有但这里可采用一种更简便的方法。当f(n+1)(x)在插值区间变化不大时，设f(n+1)(x)L，则有注：Atkin方法和Neville方法与Lagrange公式可认为满足精度要求。根据前面的计算结果估计当前的误差：事后误差估计（实用），前面给出的误差估计（事先误差估计）不实用HW:p.58-59#1-8可认为§4牛顿插值/*Newton’sInterpolation*/Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。公式不具有继承性，不利于编程。将Ln(x)改写成的形式，希望每加一个节点时，只附加一项上去即可。????

差商(亦称均差)

/*divideddifference*/1阶差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2阶差商f(x0)1阶差商的几何意义：弦截线的斜率§4Newton’sInterpolation§4牛顿插值/*Newton’sInterpol§4Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商：事实上其中Warning:myheadisexploding…Whatisthepointofthisformula?差商的值与xi

的顺序无关！§4Newton’sInterpolation11101.线性：2.差商可以表示为函数值的线性组合：3.

对称性：由2知，差商的值与节点的顺序无关！4.

差商的另一种定义：由2，3及均差定义可得§4Newton’sInterpolation1.线性：2.差商可以表示为函数值的线性组合：3.对称性：6.5.

差商与导数的关系：f(x)Ck[a,b],则[a,b],s.t.HW:证明差商的性质2，4§4Newton’sInterpolation6.5.差商与导数的关系：f(x)Ck[a,b],则§4Newton’sInterpolation牛顿插值

/*Newton’sInterpolation*/…………Nn(x)—n次多项式，满足：Nn(xi)=f(xi)Rn(x)—插值余项，满足Rn(xi)=0，i=0,…,n

ai=

f[x0,…,xi](1)(2)(n)(n)(n-1)…(2)(1)§4Newton’sInterpolation牛顿§4Newton’sInterpolation注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，表达形式不同，故其余项也相同，即

实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]增加如果精度不构，增加节点xn+1,同时表中增加一行，三角形斜边上即为所要求的各次项系数。§4Newton’sInterpolation注：数值分析第二章-插值总结课件§4Newton’sInterpolation

等距节点公式

/*FormulaewithEqualSpacing*/向前差分

/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分

/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分

/*centereddifference*/其中当节点等距分布时:fi=f(xi)§4Newton’sInterpolation等距

差分计算可通过构造差分表得到增加差分计算可通过构造差分表得到增加数值分析第二章-插值总结课件

差分的重要性质：

线性：例如

各阶差分可用函数值表示：其中/*binomialcoefficients*/§4Newton’sInterpolation

函数值可用各阶差分表示：差分的重要性质：线性：例如各阶差分可用函数值表

差商与差分的关系：

若f(x)是n

次多项式，则是次多项式，而差商与差分的关系：若f(x)是n次多项式，则

差分与导数的关系(由差分与差商、差商与导数的关系得）：差分与导数的关系(由差分与差商、差商与导数的关系得）：§4Newton’sInterpolation等距节点牛顿公式

牛顿前差公式/*Newton’sforward-differenceformula*/§4Newton’sInterpolation等距节点注：一般当x

靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。

牛顿后差公式/*Newton’sforward-differenceformula*/HW:p.59#9-16注：一般当x靠近x0时用前插，靠近xn时用后插，§5厄米插值/*HermiteInterpolation*/§5厄米插值/*HermiteInterpola不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数

(x)

满足

(xi)=f