计算方法第一章精选PPT.ppt

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

1、计算方法第一章第1页，此课件共70页哦v1 1 函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算,而又需而又需要计算许多点处的函数值要计算许多点处的函数值v2 2 仅有几个采样点处的函数值仅有几个采样点处的函数值,而又需要知道而又需要知道非采样点处的函数值非采样点处的函数值 vv上述问题的一种上述问题的一种解决思路解决思路：建立复杂函数或者：建立复杂函数或者未知函数的一个便于计算的近似表达式未知函数的一个便于计算的近似表达式.v解决方法解决方法插值法插值法 1.0 1.0 插值问题插值问题一、问题提出一、问题提出第2页，此课件共70页哦二、插值问题定义二、插值问题定义求插值函数求插值函

2、数(x x)的问题称为的问题称为插值问题插值问题。第3页，此课件共70页哦三、几何意义、内插法、外插法三、几何意义、内插法、外插法内插外插第4页，此课件共70页哦四、多项式插值问题四、多项式插值问题F对于不同的函数族对于不同的函数族的选择，得到不同的插值问题的选择，得到不同的插值问题当当为一些三角函数的多项式集合时为一些三角函数的多项式集合时:三角插值三角插值;当当为一些有理分式集合时：有理插值；为一些有理分式集合时：有理插值；当当为一些多项式集合时：多项式插值（代数插为一些多项式集合时：多项式插值（代数插值）值）第5页，此课件共70页哦五、插值多项式的存在唯一性五、插值多项式的存在唯一性F分

3、析分析 对于多项式插值问题，插值条件（对于多项式插值问题，插值条件（1 1）等价于）等价于确定多项式的系数，使得满足如下的线性方程组确定多项式的系数，使得满足如下的线性方程组 定理定理1(存在唯一性存在唯一性)满足插值条件满足插值条件(1)(1)的不超过的不超过n n次的插值多项式是存在唯一的。次的插值多项式是存在唯一的。第6页，此课件共70页哦定理证明：定理证明：多项式插值问题满足的线性方程组是关于多项式的系数多项式插值问题满足的线性方程组是关于多项式的系数a a0 0，a a1 1，a a2 2，a an n的的n n1 1阶线性方程组，其系数矩阵的行阶线性方程组，其系数矩阵的行列式列式V

4、 Vn n(x x0 0,x x1 1,x xn n)称为范德蒙称为范德蒙(Vandermonde)(Vandermonde)行列式。行列式。利用行列式的性质可以求得利用行列式的性质可以求得 由于假设由于假设i i j j时，时，x xi i x xj j，故所有因子，故所有因子x xi i-x xj j 0 0，于是，于是V Vn n(x x0 0,x x1 1,x xn n)0 0。由克莱姆。由克莱姆(Grammer)(Grammer)法则，方程组的法则，方程组的解存在且唯一，从而插值多项式是存在唯一的。解存在且唯一，从而插值多项式是存在唯一的。证毕证毕第7页，此课件共70页哦六、插值余项

5、六、插值余项F引理引理 已知函数已知函数f(x)f(x)在在 a,ba,b 上具有上具有m m-1-1阶连续导函数，阶连续导函数，且在（且在（a,ba,b）上存在）上存在m m阶导数。阶导数。若它在该区间上有若它在该区间上有m m+1+1个个零点，则它的零点，则它的m m阶导函数在阶导函数在(a,ba,b)内至少存在一个零点。内至少存在一个零点。第8页，此课件共70页哦F分析：分析：第9页，此课件共70页哦第10页，此课件共70页哦第11页，此课件共70页哦七、插值方法七、插值方法 由于插值多项式的存在唯一性，无论是用何种方法构造由于插值多项式的存在唯一性，无论是用何种方法构造出的插值多项式，

6、它们均恒等，进而截断误差也都相同。出的插值多项式，它们均恒等，进而截断误差也都相同。本章我们要讨论的插值方法有本章我们要讨论的插值方法有：LagrangeLagrange插值法插值法NewtonNewton插值法插值法等距节点等距节点插值公式插值公式带导数的带导数的插值问题插值问题第12页，此课件共70页哦1.1 1.1 拉格朗日插值拉格朗日插值一、插值基函数一、插值基函数1.1.定义定义：若若n n次多项式次多项式l lk k(x x)()(k k=0,1,=0,1,n),n)在在n n+1+1个插值个插值节点节点x x0 0 x x1 1 x xn n上满足插值条件：上满足插值条件：则称这

7、则称这n n1 1个个n n次多项式次多项式l l0 0(x x),),l l1 1(x x),),l ln n(x x)为插值为插值节点节点x x0 0,x x1 1,x xn n上的上的n n次次插值基函数插值基函数。RemarkRemark：容易验证，：容易验证，n n次插值基函数的线性组合在插值节点次插值基函数的线性组合在插值节点x x0 0,x x1 1,x xn n上满足插值条件，从而可以利用插值基函数上满足插值条件，从而可以利用插值基函数来构造插值多项式。来构造插值多项式。第13页，此课件共70页哦2.2.插值基函数的构造插值基函数的构造 由于由于i i k k时，时，l lk

8、k(x xi i)=0=0，故，故x x0 0,x x1 1,x xk k-1-1,x xk k+1+1,x xn n为为l lk k(x x)的零点，从而可以设的零点，从而可以设由由l lk k(x xk k)1 1可得可得故故若记若记 ，则有，则有 ，从，从而而第14页，此课件共70页哦3.3.插值基函数的性质插值基函数的性质性质性质1 1：性质性质2 2：插值基函数插值基函数l lk k(x x)()(k k=0,1,=0,1,n),n)为由插值节点为由插值节点x x0 0,x x1 1,x xn n唯一确定的唯一确定的n n次函数。次函数。性质性质3 3：基函数组所含的基函数个数与插值

9、节点个数相同。基函数组所含的基函数个数与插值节点个数相同。第15页，此课件共70页哦二、二、LagrangeLagrange型插值公式型插值公式 上式是不超过上式是不超过n n次的多项式，且满足所有的插值条次的多项式，且满足所有的插值条件，因而就是我们所需构造的插值多项式，称之为件，因而就是我们所需构造的插值多项式，称之为LagrangeLagrange插值多项式。插值多项式。当当n n1 1时，有时，有当当n n2 2时，有时，有第16页，此课件共70页哦 L L1 1(x x)和和L L2 2(x x)分别称为线性插值多项式和二次分别称为线性插值多项式和二次插值多项式，其几何意义分别表示通

10、过点插值多项式，其几何意义分别表示通过点(x x0 0,y y0 0),(),(x x1 1,y y1 1)的一条直线和通过点的一条直线和通过点(x x0 0,y y0 0),(),(x x1 1,y y1 1)，(x x2 2,y y2 2)的一条抛物线。的一条抛物线。类似地可以写出当类似地可以写出当n n为其它值时地插值多项式，为其它值时地插值多项式，如如n n3 3时，有时，有第17页，此课件共70页哦三、三、LagrangeLagrange插值多项式的余项插值多项式的余项 设设f f(x x)为定义在为定义在 a a,b b 上的被插值函数，上的被插值函数，L Ln n(x x)为为f

11、 f(x x)的的n n次次LagrangeLagrange插值多项式，其插值余项为：插值多项式，其插值余项为：R Rn n(x x)=)=f f(x x)-L-Ln n(x x)定理：定理：如果如果f f(n n)(x x)在区间在区间 a a,b b 上连续，上连续，f f(n n1)1)(x x)在在(a a,b b)内存在，内存在，L Ln n(x x)为在节点为在节点a a x x0 0 x x1 1 x xn n b b上满足插值上满足插值条件的条件的n n次次LagrangeLagrange插值多项式，则对任一插值多项式，则对任一x x(a a,b b),),其插值其插值余项为：

12、余项为：其中其中 (a a,b b)且依赖于且依赖于x x。上式给出的余项通常称为。上式给出的余项通常称为LagrangeLagrange型余项。型余项。第18页，此课件共70页哦定理证明定理证明证毕证毕第19页，此课件共70页哦RemarkRemark 一般情况下，余项表达式中的一般情况下，余项表达式中的 (a a,b b)的具体数值无的具体数值无法知道。但是，如果能够求出法知道。但是，如果能够求出，则可以得出插值多项式的截断误差限为：，则可以得出插值多项式的截断误差限为：由此可以看出，误差大小除了与由此可以看出，误差大小除了与Mn+1有关外，还有关外，还与插值节点有密切关系。当给定与插值节

13、点有密切关系。当给定m个点处的函数个点处的函数值，但仅选用其中值，但仅选用其中n1（n1m）个作为插值）个作为插值条件而求某个点条件而求某个点 处函数值时，处函数值时，n1个节点的个节点的选取应尽可能接近选取应尽可能接近 ，以使使得所计算的函数，以使使得所计算的函数值的误差限尽可能小。值的误差限尽可能小。第20页，此课件共70页哦例题例题#第21页，此课件共70页哦四、反插值法四、反插值法分析分析第22页，此课件共70页哦问题求解问题求解#第23页，此课件共70页哦FLagrangeLagrange 插值公式的特点：插值公式的特点：形式对称形式对称通常用于理论分析通常用于理论分析当增加插值节点

14、时，在计算实践中不方便当增加插值节点时，在计算实践中不方便1.2 1.2 牛顿插值牛顿插值问题问题：想要构造一个更加方便灵活的插值格式，当增加：想要构造一个更加方便灵活的插值格式，当增加插值节点时，只需在原有格式的基础上再增加一些即可。插值节点时，只需在原有格式的基础上再增加一些即可。解决方法解决方法：NewtonNewton插值插值第24页，此课件共70页哦一、差商的定义及性质一、差商的定义及性质一般地，一般地，K K阶差商阶差商为：为：定义定义：给定函数：给定函数f f(x x)在互异节点在互异节点x x0 0 x x1 1 x xn n处的函数处的函数值值f f(x x0 0),),f

15、f(x x1 1),),f f(x xn n)，称，称为函数为函数f f(x x)在节点在节点x xi i，x xj j处的处的一阶差商一阶差商。称为函数为函数f f(x x)在节点在节点x xi i，x xj j，x xk k处的处的二阶差商二阶差商。即即f f(x x)的的k k-1-1阶差商的差商称为阶差商的差商称为k k阶差商（均差）。阶差商（均差）。第25页，此课件共70页哦差商的性质差商的性质由于由于性质1：故差商是微商的离散形式。故差商是微商的离散形式。性质性质2 2：k k阶差商阶差商f f x x0 0,x x1 1,x xk k 可以表示为函数值可以表示为函数值f f(x

16、x0 0),),f f(x x1 1),),f f(x xk k)的线性组合，即的线性组合，即k=1,2,n性质性质3 3：差商与插值节点的排列次序无关。差商与插值节点的排列次序无关。第26页，此课件共70页哦1.Lagrange1.Lagrange插值多项式间的关系插值多项式间的关系二、二、NewtonNewton插值多项式插值多项式注：注：A A是是L Lk k(x x)的首项系数。的首项系数。第27页，此课件共70页哦2.Newton2.Newton型插值公式型插值公式第28页，此课件共70页哦k=1,2,nRemark:Remark:递推关系递推关系第29页，此课件共70页哦3.3.差

17、商的计算差商的计算第30页，此课件共70页哦 根据插值多项式的存在唯一性知，如果根据插值多项式的存在唯一性知，如果f f(x x)充分光充分光滑，则有估计滑，则有估计不足：不足：对函数的光滑性要求高；对函数的光滑性要求高；需估计导函数的最值；需估计导函数的最值；偏保守。偏保守。导数型误差导数型误差估计估计三、三、NewtonNewton插值余项插值余项第31页，此课件共70页哦 差商型误差估计差商型误差估计导数和差商的关系导数和差商的关系差商型误差估计特点差商型误差估计特点：对被插值函数光滑性要求不高；：对被插值函数光滑性要求不高；但不适用于实际计算。但不适用于实际计算。第32页，此课件共70

18、页哦四、例题四、例题解解 1 1）建立差商表）建立差商表1.01.52.00.84150.99750.9093 0.312-0.1764-0.48842 2）插值）插值第33页，此课件共70页哦 Newton Newton插值多项式适用于节点任意分布的插值多项式适用于节点任意分布的情形。但当节点等距分布时，可以简化情形。但当节点等距分布时，可以简化NewtonNewton插值公式。插值公式。1.3 1.3 等距节点插值等距节点插值 设设a a=x x0 0 x x1 1 x xn n=b=b，y yi i=f=f(x xi i)为等距节点为等距节点x xi i=x=x0 0+h h(i i=0

19、,1,=0,1,n n)上的函数值，其中上的函数值，其中h h=(=(b b-a a)/)/n n称为称为步长步长。在此基础上我们先定义差分，用差分表示在此基础上我们先定义差分，用差分表示NewtonNewton插值多项式，从而得到等距节点的插值插值多项式，从而得到等距节点的插值公式。公式。第34页，此课件共70页哦一、差分的定义与性质一、差分的定义与性质定义：称称 y yi i=y yi i+1+1-y yi i(i i=0,1,=0,1,n n-1)-1)为为f f(x x)在在x xi i处以处以h h为步长的一阶向前差分。为步长的一阶向前差分。2 2y yi i y yi i1 1-y

20、 yi i=y yi i+2+2-2-2y yi i+1+1+y yi i (i i=0,1,=0,1,n n-2)-2)称称为为f f(x x)在在x xi i处以处以h h为步长的二阶向前差分。为步长的二阶向前差分。一般地，一般地，m my yi i m m-1-1y yi i1 1-m m-1-1y yi i (i i=0,1,=0,1,n n-m m)称称为为f f(x x)在在x xi i处以处以h h为步长的为步长的m m阶向前差分。阶向前差分。第35页，此课件共70页哦差分的性质差分的性质性质性质1 1：各阶差分可用函数值线性表示，其计算公式各阶差分可用函数值线性表示，其计算公式

21、为：为：其中性质性质2 2：差分与差商满足下述关系：差分与差商满足下述关系：证明：证明：利用数学归纳法利用数学归纳法当k1时，有即结论成立。即结论成立。第36页，此课件共70页哦设设k km-1m-1时结论成立，即时结论成立，即则当则当k km m时，有时，有由数学归纳法知，结论成立。由数学归纳法知，结论成立。证毕第37页，此课件共70页哦Remark：类似地可以定义类似地可以定义向后差分向后差分与与中心差分中心差分：性质性质3 3：差分与导数满足关系：差分与导数满足关系：证明：证明：利用差商与导数、差分的关系，有：利用差商与导数、差分的关系，有：证毕第38页，此课件共70页哦二、二、Newt

22、onNewton向前向前插值公式插值公式 令令x x=x x0 0+thth，由，由x xi i=x=x0 0+ih(i=0,1,+ih(i=0,1,n),n)得：得：x x-x xi i=(=(t-it-i)h h，则有，则有:将差商与差分的关系式将差商与差分的关系式带入带入NewtonNewton插值多项式，得插值多项式，得:第39页，此课件共70页哦从而可得从而可得NewtonNewton向前插值多项式及其余项为：向前插值多项式及其余项为：第40页，此课件共70页哦三、差分表三、差分表NewtonNewton向前插值公式向前插值公式，又称表初公式，它利用差分表的，又称表初公式，它利用差分

23、表的最上面一个斜行的数值进行计算。最上面一个斜行的数值进行计算。第41页，此课件共70页哦四、例题四、例题解解第42页，此课件共70页哦#第43页，此课件共70页哦五、五、NewtonNewton向后插值公式向后插值公式 类似于向前差分，也可以得到差商与向后差分的类似于向前差分，也可以得到差商与向后差分的关系：关系：将插值节点从大到小排列，即将插值节点从大到小排列，即 类似于向前插值公式，可得到类似于向前插值公式，可得到NewtonNewton向后插值公向后插值公式式，又称，又称表末公式表末公式，它利用差分表的最下面一个斜行的，它利用差分表的最下面一个斜行的数值进行计算。数值进行计算。同样，还

24、可以利用中心差分，构造插值公式，称为同样，还可以利用中心差分，构造插值公式，称为贝塞尔（贝塞尔（BesselBessel）插值公式）插值公式。第44页，此课件共70页哦 这一类插值问题为这一类插值问题为埃尔米特埃尔米特(Hermite)(Hermite)插值问题插值问题。其。其几何意义是在插值点上插值曲线与被插值曲线有公共几何意义是在插值点上插值曲线与被插值曲线有公共切线。由这切线。由这2 2n n+2+2个条件可以唯一确定一个个条件可以唯一确定一个2 2n n+1+1次的插值次的插值多项式。具体我们采用基函数的方法来确定。多项式。具体我们采用基函数的方法来确定。1.4 1.4 埃尔米特插值埃

25、尔米特插值一、问题一、问题第45页，此课件共70页哦1.1.辅助问题及辅助问题及HermitHermit插值插值二、一般情形二、一般情形第46页，此课件共70页哦2.2.辅助问题的求解辅助问题的求解第47页，此课件共70页哦第48页，此课件共70页哦3.Hermite3.Hermite插值问题解的存在唯一性插值问题解的存在唯一性 存在性：存在性：唯一性：唯一性：0第49页，此课件共70页哦4.4.插值余项插值余项分析：第50页，此课件共70页哦定理证明定理证明函数零点（从小到大）至少至少2n+12n+1个零点个零点至少1个零点证毕第51页，此课件共70页哦三、特殊情形带不完全导数的插值问题举例

26、三、特殊情形带不完全导数的插值问题举例分析分析（方法（方法1 1）：）：误差：误差：#第52页，此课件共70页哦1.1.高次插值的评述高次插值的评述 在实际应用中在实际应用中,很少采用高次插值。很少采用高次插值。.在两相邻插值节点间在两相邻插值节点间,插值函数未必能够很好地近似被插值函数未必能够很好地近似被插值函数。插值函数。一、分段插值法一、分段插值法.对于等距节点的牛顿插值公式对于等距节点的牛顿插值公式,函数值的微小扰动可能函数值的微小扰动可能引起高阶差分有很大的变化引起高阶差分有很大的变化.1.5 1.5 三次样条插值三次样条插值第53页，此课件共70页哦 函数函数 在区间在区间-5,5

27、-5,5上用等上用等距节点的插值问题是上世纪初距节点的插值问题是上世纪初RungeRunge研究过的研究过的一个有名实例一个有名实例.在区间上分别采用在区间上分别采用1010次、次、1515次、次、2020次的等距节点插值多项式。随着插值次数的次的等距节点插值多项式。随着插值次数的提高提高,在在 范围内的近似程度并没有变范围内的近似程度并没有变好好,反而变坏反而变坏.高次插值并不一定带来更好的高次插值并不一定带来更好的近似效果。近似效果。第54页，此课件共70页哦(a)第55页，此课件共70页哦(b)(c)函数函数 的等距节点插值公式的等距节点插值公式 在区间在区间0,5上的近似程度示意图上的

28、近似程度示意图 第56页，此课件共70页哦2.2.分段插值分段插值 设设 已知节点已知节点 上的函数值上的函数值 若若 满足满足 则称则称 为分段插值函数。为分段插值函数。是整体插值区间上的连续函数是整体插值区间上的连续函数,随着子区间随着子区间长度长度 变小变小,不提高子区间上的插值幂次便可以不提高子区间上的插值幂次便可以满足给定的任意精度要求满足给定的任意精度要求.但一般说来但一般说来,在子区间在子区间的端点处导数是不存在的的端点处导数是不存在的.为了避免高次插值的缺点，常采用分段插值，为了避免高次插值的缺点，常采用分段插值，即将插值区间分成若干小区间，在每个小区间上利即将插值区间分成若干

29、小区间，在每个小区间上利用前面介绍的插值方法构建低次插值多项式。用前面介绍的插值方法构建低次插值多项式。第57页，此课件共70页哦二、二、三次样条三次样条插值插值 分段插值法具有一致的收敛性分段插值法具有一致的收敛性,但它只保证插值但它只保证插值函数整体的连续性函数整体的连续性,但在连接处不一定光滑，不能够但在连接处不一定光滑，不能够满足精密机械设计（如船体、飞机、汽车等的外形曲满足精密机械设计（如船体、飞机、汽车等的外形曲线设计）对函数光滑性的要求。线设计）对函数光滑性的要求。早期的工程技术人员在绘制给定点的曲线时，使用一早期的工程技术人员在绘制给定点的曲线时，使用一种具有弹性的细长木条（或

30、金属条），称之为种具有弹性的细长木条（或金属条），称之为样条样条（SplineSpline），强迫它弯曲通过已知点。弹性力学理论指出样），强迫它弯曲通过已知点。弹性力学理论指出样条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之间为三次多项式，即为数学上的间为三次多项式，即为数学上的三次样条插值曲线三次样条插值曲线。第58页，此课件共70页哦1.1.三次样条插值函数的定义三次样条插值函数的定义 定义定义 给定区间给定区间 的一个分划的一个分划 .在小区间在小区间 上是上是3 3次多项式次多项式.在节点在节点 处具有处具有2阶连续的导数阶连续

31、的导数;则称则称S(x)是关于分划是关于分划 的的3次次样条函数样条函数.若实值函数若实值函数S(x)满足满足若还满足若还满足.,则则称称S(x)是是f(x)关于分划关于分划 的的3次次样条插值函数样条插值函数。第59页，此课件共70页哦三次样条插值函数三次样条插值函数 在每一个小区间上是在每一个小区间上是3次次的多项式的多项式,在整个插值区间上有在整个插值区间上有4n个系数个系数.且且有有4 4n-2-2个约束个约束:内节点内节点 边界节点边界节点第60页，此课件共70页哦 要要确确定定4 4n n个个系系数数，还还需需附附加加2 2个个约约束束条条件件.常常用用的的约约束条件有以下三类：束

32、条件有以下三类：此时一般有此时一般有 成立成立.周期性边界条件周期性边界条件 ,.弯矩边界条件 特别的称 为自然边界条件.转角边界条件转角边界条件 第61页，此课件共70页哦2.2.三弯矩构造法三弯矩构造法记 ,基本步骤如下：.取 为待定参数，并用S(x)的插值条件写出 的表达式。.代入S(x)的表达式，得各个区间上的表达式。.用 在内节点 的连续条件及边界条件导出关于 的方程组。.求解后得到 。第62页，此课件共70页哦式中 。对 积分两次,并利用插值条件 ,确定两个积分常数,得到 第63页，此课件共70页哦计算 类似可以得到类似可以得到 第64页，此课件共70页哦 两边同乘以两边同乘以 ,

33、得得 令令 ,有有式中 ,.第65页，此课件共70页哦若附加弯矩约束条件若附加弯矩约束条件,得得 系数矩阵严格对角占优系数矩阵严格对角占优,故系数矩阵非奇异故系数矩阵非奇异,上述线上述线性方程组有唯一解，可用追赶法求解。将解带回到子区间性方程组有唯一解，可用追赶法求解。将解带回到子区间上的表达式中（用二阶导表示），即有上的表达式中（用二阶导表示），即有s s(x x)在每个区间上在每个区间上的表达式。的表达式。第66页，此课件共70页哦若附加转角边界条件若附加转角边界条件,得得线性方程组线性方程组为为 第67页，此课件共70页哦对于周期性边界条件对于周期性边界条件,得：得：即即式中 ,.第68

34、页，此课件共70页哦线性方程组为线性方程组为:将将 当作已知参数当作已知参数,从后从后 个方程中求解出用个方程中求解出用 表表示的后示的后 个参数个参数,然后将它们代入第一个方程解然后将它们代入第一个方程解得得 ,最终得到其它参数最终得到其它参数.第69页，此课件共70页哦Remark：1.类似地，可以使用节点处的一阶导数来表示三类似地，可以使用节点处的一阶导数来表示三次样条插值函数。次样条插值函数。2.2.对三次样条插值函数来说，当插值节点逐对三次样条插值函数来说，当插值节点逐渐加密时，可以证明，不但样条插值函数收渐加密时，可以证明，不但样条插值函数收敛于函数本身，而且其导数也收敛于函数的敛于函数本身，而且其导数也收敛于函数的导数。导数。第70页，此课件共70页哦