计算方法第三章插值法.ppt

《计算方法第三章插值法.ppt》由会员分享，可在线阅读，更多相关《计算方法第三章插值法.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算方法第三章插值法现在学习的是第1页，共55页假设已经获得假设已经获得n+1点上的函数值点上的函数值即提供了一张数据表即提供了一张数据表 如何利用这张表求如何利用这张表求 f(x)在在其他给定点上的合其他给定点上的合理的近似值呢理的近似值呢?现在学习的是第2页，共55页在实验数据的处理、难以计算的函数的逼近、在实验数据的处理、难以计算的函数的逼近、数值微积分等方面需要解决这样的问题，这是数值微积分等方面需要解决这样的问题，这是数值逼近中的一个基本问题。一个自然的想法数值逼近中的一个基本问题。一个自然的想法是找一个简单易计算的函数是找一个简单易计算的函数(x)，使得，使得将将(x)作为作为f(

2、x)在一定范围内的近似函数，对于在一定范围内的近似函数，对于这个范围内的某个给定点这个范围内的某个给定点a，取，取 f(a)(a)。这种近。这种近似方法称为似方法称为插值法插值法。(x)称为称为f(x)的以的以xi(i=0,1,n)为插值节点的为插值节点的插值函数插值函数。插值节点上所给。插值节点上所给的函数值称为的函数值称为样本值样本值。现在学习的是第3页，共55页(xi)=yi 称为称为插值条件插值条件。函数值待求的点称为函数值待求的点称为插值点插值点。插值节点所界定的范围称为插值节点所界定的范围称为插值区间插值区间。如。如果所给插值点位于插值区间之内，这种插值过程称果所给插值点位于插值区

3、间之内，这种插值过程称为为内插内插，否则称为，否则称为外插外插。若用多项式来作为插值函数，则称其为若用多项式来作为插值函数，则称其为插值插值多项式。多项式。通常用通常用n 次多项式作为次多项式作为n+1个插值条件个插值条件的插值多项式。如果插值条件只是给出节点的函的插值多项式。如果插值条件只是给出节点的函数值，称为数值，称为拉格朗日插值拉格朗日插值，如果既有函数值也有，如果既有函数值也有节点处函数的导数值，称为节点处函数的导数值，称为埃尔米特插值埃尔米特插值。现在学习的是第4页，共55页因式定理：多项式因式定理：多项式P(x)具有具有r 次因式次因式(x-a)r 的充的充要条件是要条件是最一般

4、的插值条件：最一般的插值条件：是是重插值节点，重插值节点，定理：给定上述定理：给定上述n+1个插值条件，则个插值条件，则n次插值次插值多项式是多项式是存在唯一存在唯一的。的。现在学习的是第5页，共55页设函数设函数y=f(x)在闭区间在闭区间a,b 上有上有n+1阶导数，阶导数，满足前面的一般插值条件，且插值节点各不相同，满足前面的一般插值条件，且插值节点各不相同，则插值截断误差为则插值截断误差为现在学习的是第6页，共55页证明思路：构造辅助函数，用罗尔定理。证明思路：构造辅助函数，用罗尔定理。现在学习的是第7页，共55页值得注意的是在较大区间上进行插值时，误差可能会值得注意的是在较大区间上进

5、行插值时，误差可能会很大！另外，一般情况下，外推不如内插好！很大！另外，一般情况下，外推不如内插好！现在学习的是第8页，共55页第二节第二节Lagrange插值公式插值公式插值条件是插值条件是Lagrange插值实质上是求通过上面插值实质上是求通过上面n+1个点的个点的n次多项式。次多项式。现在学习的是第9页，共55页一次插值：一次插值：问题为求一次多项式，即一次函数，过以下问题为求一次多项式，即一次函数，过以下两点：两点：容易求出，该函数为：容易求出，该函数为：现在学习的是第10页，共55页一般插值问题：求过一般插值问题：求过n+1n+1个点个点的不超过的不超过n n次多项式次多项式 。称为

6、称为LagrangeLagrange插值基函数，满足：插值基函数，满足：现在学习的是第11页，共55页求过求过n+1n+1个点的不超过个点的不超过n n次多项式的插值多项次多项式的插值多项式是唯一的。式是唯一的。插值公式的误差为：插值公式的误差为：现在学习的是第12页，共55页计算程序计算程序框图框图现在学习的是第13页，共55页第三节第三节 逐次线性插值逐次线性插值函数函数 y=f(x)在节点在节点上的插值多项上的插值多项式记为式记为，则有，则有现在学习的是第14页，共55页Aitken（埃特肯）算法埃特肯）算法Neville（列维尔）算法列维尔）算法现在学习的是第15页，共55页Aitke

7、n（埃特肯）算法埃特肯）算法现在学习的是第16页，共55页Neville（列维尔）算法列维尔）算法现在学习的是第17页，共55页例子：求方程例子：求方程x3-2x-5=0在在(2,3)内的根内的根思路思路:设设y=f(x)=x3-2x-5，其反函数为，其反函数为x=f-1(y)，则，则根为根为x*=f-1(0)。先用。先用3=f-1(16)，2=f-1(-1)插值，得插值，得N0,1(y)f-1(y),计算计算N0,1(0)=2.058823,f(2.058823)=-0.39，以，以-0.39为新的节点，继续为新的节点，继续yixiNi,i+1(0)Ni,i+1,i+2(0)Ni,i+1,i

8、+2,i+3(0)163-122.058823-0.392.058232.0965892.0956590.0122.0956592.0945292.0945542.0945531.51E-52.094553现在学习的是第18页，共55页第四节第四节 牛顿插值牛顿插值设插值点为设插值点为插值多项式形如插值多项式形如称为称为Newton形式的插值多项式。形式的插值多项式。现在学习的是第19页，共55页差商概念：差商概念：设函数设函数 f(x)，定义函数在两个不同点的一阶差商为定义函数在两个不同点的一阶差商为三个不同点的二阶差商为：三个不同点的二阶差商为：在点在点处处K+1 阶差商为：阶差商为：现在

9、学习的是第20页，共55页给定给定 n+1个点的函数值个点的函数值则牛顿插值公式为：则牛顿插值公式为：现在学习的是第21页，共55页差商的计算简表：差商的计算简表：现在学习的是第22页，共55页例子：例子：用用0、30、45、60、90五个点作出五个点作出sinx牛顿插值多项式。牛顿插值多项式。做差商表做差商表00300.50.016667450.70710.013807-0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049现在学习的是第23页，共55页现在学习的是第24页，共55页牛顿

10、插值的截断误差：牛顿插值的截断误差：现在学习的是第25页，共55页例子：例子：用用0、90、180、270、360五个点作出五个点作出sinx牛顿插值多项式。牛顿插值多项式。做差商表做差商表009010.011111800-0.01111-1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70现在学习的是第26页，共55页现在学习的是第27页，共55页差商的性质差商的计算公式：差商的计算公式：通过比较插值多项式的Lagrange形式和Newton形式即可得。现在学习的是第28页，共55页差商的对称性：差商的对称性：差商的线性性：差商

11、的线性性：现在学习的是第29页，共55页由于由于n次插值多项式是唯一的，所以牛顿插值公式与次插值多项式是唯一的，所以牛顿插值公式与LagrangeLagrange插值多项式一样，这意味着余项也一样，插值多项式一样，这意味着余项也一样，LagrangeLagrange余项为：余项为：所以牛顿余项也一样，所以牛顿余项也一样，现在学习的是第30页，共55页差商与导数的关系差商与导数的关系重节点差商重节点差商推论：当推论：当n个节点全为同一个点，牛顿插值变成个节点全为同一个点，牛顿插值变成泰勒多项式。泰勒多项式。现在学习的是第31页，共55页差商的导数差商的导数n次多项式的的次多项式的的1阶差商是阶差

12、商是n-1次多项式。次多项式。推论：设推论：设p(x)是是 n次多项式，次多项式，k n时时k阶差商阶差商是是n-k次多项式，次多项式，kn时时k阶差商为零。阶差商为零。现在学习的是第32页，共55页差分差分设函数设函数 ，定义，定义 为该函为该函数在数在 i 点的点的一阶向前差分一阶向前差分，记为，记为类似地，定义类似地，定义二阶向前差分为二阶向前差分为：K 阶差分为阶差分为：此差分称为此差分称为向前差分向前差分。现在学习的是第33页，共55页类似地，类似地，向后差分向后差分定义为：定义为：中心差分中心差分定义为：定义为：现在学习的是第34页，共55页差商与差分的关系：差商与差分的关系：等距

13、节点时等距节点时现在学习的是第35页，共55页第五节第五节 带导数的插值带导数的插值问题的提出：如果在已知节点处不仅知道函数值，问题的提出：如果在已知节点处不仅知道函数值，同时还知道导数同时还知道导数值，这样，插值多项式就要求在值，这样，插值多项式就要求在已知节点处与已知节点处与函数值和导数值都相等函数值和导数值都相等。这就是所。这就是所谓谓埃尔米特（埃尔米特（Hermite）插值）插值。现在学习的是第36页，共55页1、推广牛顿插值法、推广牛顿插值法如果已知如果已知某个点某个点i 的的，则，则插值节点应视为插值节点应视为个相同节点个相同节点，并注意到，并注意到k+1重节点的差商重节点的差商现

14、在学习的是第37页，共55页例子：例子：已知关于函数已知关于函数y=f(x)的函数值、导数值的函数值、导数值xif(xi)f(xi,xi+1)f(xi,xi+1,xi+2)3阶差商阶差商4阶差商阶差商5阶差商阶差商-100-4-40-4040-403-11-222-101-253121现在学习的是第38页，共55页2、构造基函数法构造基函数法已知函数在已知函数在n个不同的节点处的函数值和导数值：个不同的节点处的函数值和导数值：求次数不超过求次数不超过2n-1次的多项式次的多项式设想其具有形式设想其具有形式：要求：要求：现在学习的是第39页，共55页由条件可得：由条件可得：此外，由此外，由 得：

15、得：现在学习的是第40页，共55页同理：同理：由由 ，可得：，可得：最后，得到埃尔米特插值公式：最后，得到埃尔米特插值公式：现在学习的是第41页，共55页特别，当特别，当 n=2 时，三阶埃尔米特多项式为：时，三阶埃尔米特多项式为：现在学习的是第42页，共55页埃尔米特插值公式唯一。埃尔米特插值公式唯一。误差估计：设被插值函数在插值区间上误差估计：设被插值函数在插值区间上2n次连续可次连续可导，则在导，则在n个节点上的个节点上的2n-1次插值多项式的余项为：次插值多项式的余项为：特别，对于特别，对于2个节点个节点3次插值，余项为：次插值，余项为：现在学习的是第43页，共55页例子：例子：现在学

16、习的是第44页，共55页现在学习的是第45页，共55页如用距离较小的两个点插值，效果会好得多如用距离较小的两个点插值，效果会好得多现在学习的是第46页，共55页现在学习的是第47页，共55页第六节第六节 样条函数样条函数由于被插值函数高阶导数未知，因此，如果高由于被插值函数高阶导数未知，因此，如果高阶导数随阶数增长出现无限增长，则由误差公阶导数随阶数增长出现无限增长，则由误差公式可知，高阶插值公式就不一定无限接近被插式可知，高阶插值公式就不一定无限接近被插值函数。这称为值函数。这称为龙格（龙格（Runge)现象现象。所以，在进行多项式插值时，不宜进行高次多所以，在进行多项式插值时，不宜进行高次

17、多项式插值。项式插值。一个解决的途径是一个解决的途径是分段低次插值分段低次插值。现在学习的是第48页，共55页样条函数：给定区间一个样条函数：给定区间一个划分划分如函数如函数 S(x)满足下面条件：满足下面条件：（1）在每个小区间）在每个小区间上为上为m次多项式；次多项式；（2）S(x)直至直至m1阶导数在整个区间上连续。阶导数在整个区间上连续。则称则称S(x)是关于该划分的是关于该划分的m次次样条函数样条函数，划分点，划分点称为节点，称为节点，m3时，就是最常用的时，就是最常用的3次样条函数。次样条函数。现在学习的是第49页，共55页样条函数插值：样条函数插值：对给定的插值条件，寻找合适的样

18、条对给定的插值条件，寻找合适的样条函数作为插值函数，使其满足插值条件。函数作为插值函数，使其满足插值条件。3次样条插值三弯矩方法的基本思想：次样条插值三弯矩方法的基本思想：将样条函数在每一个子区间端点的二阶导数值当作参将样条函数在每一个子区间端点的二阶导数值当作参数，则用这两个二阶导数值可以将样条函数表示出来，数，则用这两个二阶导数值可以将样条函数表示出来，再利用衔接条件，即每一段样条函数在相邻两个子区间再利用衔接条件，即每一段样条函数在相邻两个子区间端点处的二阶导数相等，建立求解二阶导数的方程组。端点处的二阶导数相等，建立求解二阶导数的方程组。现在学习的是第50页，共55页设设S(x)在每个

19、小区间在每个小区间端点的二阶导端点的二阶导数为：数为：则：则：记记，将上式积分两次，并利用端点函数值已将上式积分两次，并利用端点函数值已知，有：知，有：现在学习的是第51页，共55页我们注意到，在相邻的两个子区间我们注意到，在相邻的两个子区间 和和 的共同端点处，样条函数一阶导数相等，的共同端点处，样条函数一阶导数相等，经过化简，最后得到：经过化简，最后得到：现在学习的是第52页，共55页注意到上面的方程组总共只有注意到上面的方程组总共只有 N1个方程，而未知数却共有个方程，而未知数却共有 N+1个，因此，要求解方程，还需要补充两个条件（即两个个，因此，要求解方程，还需要补充两个条件（即两个方

20、程），通常有以下几种方案之一方程），通常有以下几种方案之一:1、给出端点一阶导数值、给出端点一阶导数值 ，这相当于增加两个方程；，这相当于增加两个方程；2、给定端点二阶导数值，得方程：、给定端点二阶导数值，得方程：特别，令二阶导数在端点为零，得特别，令二阶导数在端点为零，得现在学习的是第53页，共55页3、样条件函数在第一个和最后一个区间上为二次多项式，样条件函数在第一个和最后一个区间上为二次多项式，即样条函数在第一和最后一个区间上的二阶导数为常即样条函数在第一和最后一个区间上的二阶导数为常数，得两个方程：数，得两个方程：总之，以上三种补充条件下，可将方程组统一写为：总之，以上三种补充条件下，可将方程组统一写为：现在学习的是第54页，共55页4、周期性条件（这只有在给的初值满足、周期性条件（这只有在给的初值满足 时才能用），时才能用），此时，由周期性，此时，由周期性，就得到两个方程；，就得到两个方程；第一个方程为第一个方程为 ，第二个方程为，第二个方程为 最后一个方程为：最后一个方程为：最后，方程组为：最后，方程组为：现在学习的是第55页，共55页