插值法第一次PPT课件

1、条件条件 已知已知233sin,214sin,216sin 计算计算 sin 50 的近似值的近似值 并估计误差。并估计误差。 需求需求问题实例更一般情况更一般情况问题问题：需要计算函数的近似关系表达式、在未知点的函数值：需要计算函数的近似关系表达式、在未知点的函数值条件：条件： 一组有函数关系的自变量和因变量的测量数据一组有函数关系的自变量和因变量的测量数据),(iiyx第1页/共44页本节课主要内容 插值问题的描述 Lagrange插值多项式的存在唯一性，构造形式，基函数性质 误差分析 应用第2页/共44页 描述事物之间的数量关系：函数。 有两种情况： 一是表格表格形式一组离散的数据离散的

2、数据来表示函数关系；另一种是函数虽然有明显的有明显的表达式表达式，但很复杂，但很复杂，不便于研究和使用。 从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式近似表达式来代替，从而使问题得到简化。一般地，构造某种简单函数代替原来函数。插值法就是一种基本方法0 引言引言(1)(2)(2) 在在 x 为特殊值为特殊值时时, 是好计算的是好计算的, 则则 (2)可转化为可转化为(1)第3页/共44页当精确函数当精确函数 y = f(x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0

3、), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 g(x) f(x)，满足条件，满足条件g(xi) = f(xi) (i = 0, n)。这里的。这里的 g(x) 称为称为f(x) 的的插值函数插值函数。x0 x1x2x3x4xg(x) f(x)第4页/共44页), 1 , 0()(niyxPii（1.1） 设函数 在区间 上有定义，且已知在点 上的值 ，若存在一简单函数 ，使)(xfy ,babxxxan10nyyy,10)(xP成立，就称 为 的插值函数插值函数，点 称为插插值节点值节点，包含节点的区间 称为插值区间插值区间，求插值函数 的方法称为

4、插值法插值法.)(xP)(xfnxxx,10,ba)(xP 插值问题的提出插值问题的提出第5页/共44页nnxaxaaxP10)(（1.2） 若 是次数不超过 的代数多项式，)(xPn其中 为实数，就称 为插值多项式插值多项式，相应的插值法称为多项式插值多项式插值.ia)(xP本章只讨论多项式插值与分段插值. 若 为分段的多项式，就称为分段插值分段插值.)(xP 若 为三角多项式 ，就称为三角插值三角插值.)(xP即插值函数：Lagrange, Newton, Hermite, Spline第6页/共44页由此可以得到关于系数 的 元线性方程组上的函数值 ,求次数不超过 的多项式 ，使 多项式

5、插值多项式插值 ), 1 , 0()(niyxPii（1.3） 设在区间 上给定 个点), 1 , 0)(nixfyii,babxxxan10naaa,101n1nn)(xP第7页/共44页,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa（1.4）此方程组的系数矩阵为,1111100nnnnnxxxxxxA称为范德蒙德（VandermondeVandermonde）矩阵,由于 互异，故), 1 ,0(nixi（1.5）第8页/共44页因此线性方程组（1.4）的解 存在且唯一.naaa,10 定理1 1 满足条件（1.3）的插值多项式 是存在唯一的.(证明)(xP

6、. 0)(det1,njiojijixxA第9页/共44页1 拉格朗日多项式拉格朗日多项式 niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(1xP101xxxx 010 xxxx = y0 + y11.1 线性插值线性插值两点式两点式)()(0010

7、101xxxxyyyxP 点斜式点斜式)(001010 xxxxxxy ()ff（解的存在唯一性）第10页/共44页1.2 二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP 使得使得002,)(yxP112)(yxP 222)(yxP , 为求为求P2(x),将三点代入其表达式将三点代入其表达式,即可得到三个方程式即可得到三个方程式,从而联立方程组解出系数从而联立方程组解出系数a0, a1, a2即可即可:2020100 xaxaay 2121101xaxaay 2222102xaxaay 方程组的方程组的解是否存在解

8、是否存在? 若存在解若存在解,是否是否唯一唯一?!当当 x0 , x1 , x2互异时互异时,方程组的解存在且唯一方程组的解存在且唯一.注：注：显然有显然有, 求求n 次插值时次插值时, 由由n +1个点可有个点可有n +1个方程个方程, 联立方程组即可求出插值多项式的联立方程组即可求出插值多项式的n +1个系数个系数. 然而然而,方程组的求解也并不是一件容易的事方程组的求解也并不是一件容易的事。待定系数法待定系数法第11页/共44页 对于线性插值的对于线性插值的两种形式两种形式解解进行适当的分析进行适当的分析, , 从中寻求规律而得到启发从中寻求规律而得到启发, ,就有了所谓的就有了所谓的拉

9、格朗日拉格朗日插值法插值法( (公式公式) )和和牛顿插值牛顿插值( (公式公式). ). 我们先来看看如何得到二次二次拉格朗日插值公式拉格朗日插值公式（和和牛顿插值公式牛顿插值公式（为讨论方便，留待后述为讨论方便，留待后述）. .第12页/共44页 首先, 线性插值的两点式可看作是两个特殊的一次式可看作是两个特殊的一次式的一种线性组合的一种线性组合.101xxxx 010 xxxx )(1xP= y0 + y1 10)(iiiyxl两点式两点式l0(x)l1(x)实质上实质上0l（x）和）和1l（x）即是满足函数表）即是满足函数表 的一次插值多项式的一次插值多项式 ,称称l0(x)和和l1(

10、x)为以为以x0,x1为节点的基本插为节点的基本插值多项式，也称为值多项式，也称为线性插值的线性插值的插值基函数插值基函数 。 于是，线性插值即是用于是，线性插值即是用基函数的线性组合基函数的线性组合来构造的来构造的. 基函数法基函数法称为称为拉氏基函数拉氏基函数 ，满足，满足 li(xj)= ij 显然有显然有l0(x)+ l0(x)1.这里，这里， l0(x)和和l1(x)具有如下性质：具有如下性质：l0(x0)=1, l0(x1)=0, l1(x0)=0, l1(x1)=1, 第13页/共44页 由此启发，我们希望二次插值也能由一些二次插值基由此启发，我们希望二次插值也能由一些二次插值基

11、函数来线性组合函数来线性组合:这时，这时，l0(x), l1(x), l2(x)都是二次多项式，且应满足都是二次多项式，且应满足满足满足(2.1)式的式的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）第14页/共44页同理可得同理可得 l1(x) 1(x x0)(x x2), l2(x) 2(x x0)(x x1),1(x1x0)(x1x2)12(x2x0)(x2x1)1此即此即二次二次拉格朗日插值公式拉格朗日插值公式, 其中其中, l0(x), l1(x), l2(x)是满足是满足(2.1)的特殊的特殊(基本基本)二次插值多项式二次插值多项式;称为

12、称为二次插值基函数二次插值基函数.P2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1) 先考虑先考虑 l0(x)。因。因 l0(x)是以是以 x1, x2 为零点的二次多项式为零点的二次多项式,所以它可写成所以它可写成 l0(x) 0(x x1)(x x2), 其中其中 0 是待定系是待定系数。数。 又因为又因为 l0( x0)=1，所以，所以 0(x0 x1)(x0 x2)1，则可有，则可有0(x

13、0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), 第15页/共44页n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 niiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()( 拉格朗日拉格朗日 多项式多项式与与 有关，而与有关，而与 无关无关节点节点

14、f1.3 n 次插值次插值第16页/共44页定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。项式是唯一存在的。niyxPii,., 0,)( 证明：证明： ( 存在性存在性可利用可利用Vandermonde 行列式行列式论证论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶数的阶数, )()()(xLxPxQnnn n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：注：若不将多项式次数限制为若不将多项式次数限制为 n

15、，则插值多项式，则插值多项式不唯一不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其中 可以是任意多项式。可以是任意多项式。 niinxxxpxLxP0)()()()()(xp niiinyxlxL0)()(第17页/共44页设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210

16、xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(nxKRxnn 注意这里是对注意这里是对 t 求导求导 !)1)()()()1()1(nxKLfxnnxn !)1()()()1( nfxKxn

17、 niixnnxxnfxR0)1()(! ) 1()()( 1.4 插值余项插值余项 (Remainder) 第18页/共44页注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRn.)(应应用用的的高高阶阶导导数数存存在在时时才才能能余余项项表表达达式式只只有有在在

18、xf,)()( )(61)(2,)( )(21)()(21)(1202102101021xxxxxxxxfxRnxxxxxxfxfxRn ，时，抛物插值的余项为时，抛物插值的余项为当当，时，线性插值余项为时，线性插值余项为当当第19页/共44页例例1 求经过求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式三个插值点的插值多项式.解：解：三个插值节点及对应的函数值为三个插值节点及对应的函数值为.322110221100 yxyxyx，；，；，13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1()()()()()()()(21202101

19、21012002010212 xxxxxxxyxxxxxxxxyxxxxxxxxyxxxxxxxxxL由抛物插值公式得由抛物插值公式得n+1个节点的Lagrange插值多项式不超过n次第20页/共44页例例2：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,

20、sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 (extrapolation ) 的实际误差的实际误差 0.010100.010103,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 (interpolation ) 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区

21、间的端点，插值效果较好。端点，插值效果较好。第21页/共44页n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿第22页/共44页 例例3 考虑下述的插值法问题：求二次多项式考虑下述

22、的插值法问题：求二次多项式P(x)，满足，满足P(x0) = y0, 其中其中 是已给的数据并给出使这一问题的解存在且唯一的条件是已给的数据并给出使这一问题的解存在且唯一的条件.，2211)()(yxPyxP21020yyyxx、，解解：设：设 则则 由已知条件有由已知条件有，cbxaxxP2)(.2)(baxxP11222200202ybaxycbxaxycbxax0012111222020 xxxxx0)()(22220201xxxxx)0(220201xxxxx即即 所以所以故原问题的唯一可解性就归结为上述方程组的唯一可解性而后故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一

23、可解的充要条件为者唯一可解的充要条件为这就是这就是P（x）存在且唯一的条件。）存在且唯一的条件。第23页/共44页HW: p.481,2,4,5(1).)10(.出有牛顿插值公式出有牛顿插值公式形式，从而导形式，从而导项式变形为便于计算的项式变形为便于计算的这一缺点，可把插值多这一缺点，可把插值多为了克服为了克服的的实际计算中是很不方便实际计算中是很不方便式也要发生变化，这在式也要发生变化，这在均要随之变化，整个公均要随之变化，整个公，时，全部插值基函数时，全部插值基函数但是，当插值节点增加但是，当插值节点增加中非常方便中非常方便结构紧凑，在理论分析结构紧凑，在理论分析式，公式式，公式得到拉格

24、朗日插值多项得到拉格朗日插值多项利用插值基函数很容易利用插值基函数很容易nklk 1.5 拉格朗日插值公式的优缺点拉格朗日插值公式的优缺点第24页/共44页。阶导数连续的函数空间上二表示在区间记号其中试证：设例ba,ba,C. )(max)(81)()()()()(max,3.22222xfMMabaxabafbfafxfbaCfbxabxa )()()()()(max)()()()()()(,(),(,(:1axabafbfafxfaxabafbfafxLbfbafabxa于是的线性插值为：通过两点证明第25页/共44页2221)(81)(max2)(2)(max)()(maxMabbxax

25、MbxaxfxLxfbxabxabxa 第26页/共44页课堂练习证明证明njkjkjjxxlxnjx0)(), 1 , 0(:为互异节点，则有设基函数性质505)0(Lagrange5)()5 , 4 , 3 , 2 , 1 , 0(. 1iiiiilxxlix插值基函数，则次为对应的为互异节点，设？50345)() 12(iiiiixlxxx？第27页/共44页本节主要内容Newton插值等距差分公式第28页/共44页 Lagrange插值插值公式公式(利用利用插值基函数插值基函数很容易得到很容易得到): 含义直观含义直观,结构紧凑结构紧凑,在理论分析中非常方便在理论分析中非常方便; 计算

26、机上计算机上实现实现也很也很容易容易. 也有一些也有一些缺点缺点： 一是一是计算量大计算量大，这是显然的；另外，还有一个更严重的，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，缺点，当插值节点增加时，全部插值基函数全部插值基函数均要随之均要随之变化变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要还要增加一项增加一项计算。计算。 为克服上述两个缺点为克服上述两个缺点, 努力：把插值多项式变形为努力：把插值多项式变形为便于计算便于计算的形式。的形式。 希望：希望：计算改变的过程中计算改变的过程中,尽可能能利用已有的计算结

27、果尽可能能利用已有的计算结果. 下面我们将看到下面我们将看到,这是可能的。我们可以有具有这是可能的。我们可以有具有“承袭性承袭性”的所谓牛顿公式。的所谓牛顿公式。第29页/共44页)()(0010101xxxxyyyxP )(001010 xxxxxxy ()fffx0,x1 二次牛顿插值多项式二次牛顿插值多项式 我们再看线性插值线性插值的点斜式点斜式: )(00 xxy fx0,x1常数常数(差商差商) 由此启发，我们希望二次插值也能类似地有有规律的由此启发，我们希望二次插值也能类似地有有规律的组合表达式组合表达式:P2(x)= 0 + 1(x- -x0) + 2(x- -x0)(x- -x

28、1)利用利用P2(x0)=y0有有: 0 = y0 ,利用利用P2(x1)=y1有有: 1 = 0101xxxx ()ff= fx0,x1 ,利用利用P2(x2)=y2有有: 2 = fx0,x1 (x2- -x0)(x2- -x1) (x2- -x0)(x2- -x1)0 xx2 ()ff (x2- -x0)-fx0,x2fx0,x1 x2 - - x1 =-= fx0,x1,x2 ;P2(x)=f(x0) + (x- -x0) + (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x2 x=x0时0第30页/共44页注注: 1. 事实上事实上,从上述可看出二次牛顿

29、插值公式是用从上述可看出二次牛顿插值公式是用待待定系数法定系数法求得的求得的; 2. 它也可看作是三个特殊函数的一种线性组合它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0) + (x- -x0) + (x- -x0)(x- -x1) fx0,x1 fx0,x1,x2 fx0,x1 , fx0,x1,x2 f(x0), 1 , (x- -x0) , (x- -x0)(x- -x1)即函数 的线性组合,组合系数为 本质上还是本质上还是基函数法基函数法.第31页/共44页 更一般地，更一般地，n+1个节点的插值多项式，我们希望由上个节点的插值多项式，我们希望由上述类似的一组特殊函数：述

30、类似的一组特殊函数：来线性组合为：来线性组合为： 1 , (x- -x0) , (x- -x0)(x- -x1)，(x- -x0)(x- -x1)(x- -xn).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN那么其组合系数是什么样的呢？怎么求呢？那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法我们同样可用待定系数法. 容易发现容易发现,计算计算a0, a1, a2 , an 是很有规律的是很有规律的.第32页/共44页 定义定义2 称称 为函数为函数f(x)关于点关于点x0,xk的的一阶均差一阶均差.称称 为为f(x) 的的二阶均差二阶均差.一般地一般地

31、, 称称 为为 f(x) 的的k 阶均差阶均差(差商差商). fx0,xk =f(xk)- -f(x0)xk- -x0 fx0,x1,xk=fx0,xk- - fx0,x1xk- -x1 fx0,x1,xk=fx0, xk-2,xk- - fx0,x1, ,xk-1xk- -xk-1均差有如下的基本性质均差有如下的基本性质: 1 k 阶均差可表示为函数值阶均差可表示为函数值f(x0), f(x1), f(xk)的线性组合的线性组合,即即 fx0,x1,xk=f(xj)(xj- -xj+1)(xj- -xk)(xj- -xj+1)(xj- -x0) kj=0这个性质可用归纳法证明这个性质可用归纳

32、法证明. 这个性质也表明均差与节点的排列这个性质也表明均差与节点的排列次序无关次序无关,称为均差的对称性称为均差的对称性,即即 fx0,x1,xk= fx1,x0,x2,xk= = fx1, , xk ,x0第33页/共44页 fx0,x1,xk=fx1, xk-1,xk- - fx0,x1, ,xk-1xk- -x02 由性质由性质1可得可得:f(n)()n!,ba 3 若若f(x)在在a,b上存在上存在n阶导数阶导数, 且节点且节点x0,x1,xn a,b,则则n阶均差与导数关系如下阶均差与导数关系如下: ,011kkxxxxf,10nxxxf（证明推后到余项分析）第34页/共44页,)(

33、)()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 二、牛顿插值公式二、牛顿插值公式第35页/共44页)().(,.,100nnnxx

34、xxxxxxxf Rn(x).)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn(x)n+1(x)10(0nkxxfakk， 多项式多项式Nn(x)显然满足插值条件显然满足插值条件,即即Nn(xj)=f(xj),(j=1, n),且次数不超过且次数不超过n,由唯一性定理它就是前述的由唯一性定理它就是前述的Ln(x),其系数为其系数为 Nn(x)称为牛顿均差插值多项式称为牛顿均差插值多项式,它比拉格朗日插值多项式它比拉格朗日插值多项式计算量省计算量省,且便于程序设计且便于程序设计.第36页/共44页注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其只是算法不同，故其余项也相同，即余项也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn ),(,!)(,.,maxmin)(0 xxkfxxfkk 实际计算过程为实