计算方法第一章优秀PPT.ppt

计算方法第一章现在学习的是第1页，共70页v1 1 函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算,而又需要而又需要计算许多点处的函数值计算许多点处的函数值v2 2 仅有几个采样点处的函数值仅有几个采样点处的函数值,而又需要知道而又需要知道非采样点处的函数值非采样点处的函数值 vv上述问题的一种上述问题的一种解决思路解决思路：建立复杂函数或者：建立复杂函数或者未知函数的一个便于计算的近似表达式未知函数的一个便于计算的近似表达式.v解决方法解决方法插值法插值法 1.0 1.0 插值问题插值问题一、问题提出一、问题提出现在学习的是第2页，共70页二、插值问题定义二、插值问题定义求插值函数求插值函数(x x)的问题称为的问题称为插值问题插值问题。现在学习的是第3页，共70页三、几何意义、内插法、外插法三、几何意义、内插法、外插法内插外插现在学习的是第4页，共70页四、多项式插值问题四、多项式插值问题F对于不同的函数族对于不同的函数族的选择，得到不同的插值问题的选择，得到不同的插值问题当当为一些三角函数的多项式集合时为一些三角函数的多项式集合时:三角插值三角插值;当当为一些有理分式集合时：有理插值；为一些有理分式集合时：有理插值；当当为一些多项式集合时：多项式插值（代数插为一些多项式集合时：多项式插值（代数插值）值）现在学习的是第5页，共70页五、插值多项式的存在唯一性五、插值多项式的存在唯一性F分析分析 对于多项式插值问题，插值条件（对于多项式插值问题，插值条件（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 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页六、插值余项六、插值余项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页七、插值方法七、插值方法 由于插值多项式的存在唯一性，无论是用何种方法由于插值多项式的存在唯一性，无论是用何种方法构造出的插值多项式，它们均恒等，进而截断误差也都构造出的插值多项式，它们均恒等，进而截断误差也都相同。相同。本章我们要讨论的插值方法有本章我们要讨论的插值方法有：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上满足插值条件：上满足插值条件：则称这则称这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 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：基函数组所含的基函数个数与插值节点个数相基函数组所含的基函数个数与插值节点个数相同。同。现在学习的是第15页，共70页二、二、LagrangeLagrange型插值公式型插值公式 上式是不超过上式是不超过n n次的多项式，且满足所有的插值条件，次的多项式，且满足所有的插值条件，因而就是我们所需构造的插值多项式，称之为因而就是我们所需构造的插值多项式，称之为LagrangeLagrange插插值多项式。值多项式。当当n n1 1时，有时，有当当n n2 2时，有时，有现在学习的是第16页，共70页 L L1 1(x x)和和L L2 2(x x)分别称为线性插值多项式和二次插分别称为线性插值多项式和二次插值多项式，其几何意义分别表示通过点值多项式，其几何意义分别表示通过点(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 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),),其插值余项为：其插值余项为：其中其中 (a a,b b)且依赖于且依赖于x x。上式给出的余项通常称为。上式给出的余项通常称为LagrangeLagrange型余项。型余项。现在学习的是第18页，共70页定理证明定理证明证毕证毕现在学习的是第19页，共70页RemarkRemark 一般情况下，余项表达式中的一般情况下，余项表达式中的 (a a,b b)的具体数值无的具体数值无法知道。但是，如果能够求出法知道。但是，如果能够求出，则可以得出插值多项式的截断误差限为：，则可以得出插值多项式的截断误差限为：由此可以看出，误差大小除了与由此可以看出，误差大小除了与Mn+1有关外，还有关外，还与插值节点有密切关系。当给定与插值节点有密切关系。当给定m个点处的函数个点处的函数值，但仅选用其中值，但仅选用其中n1（n1m）个作为插值）个作为插值条件而求某个点条件而求某个点 处函数值时，处函数值时，n1个节点的个节点的选取应尽可能接近选取应尽可能接近 ，以使使得所计算的函数，以使使得所计算的函数值的误差限尽可能小。值的误差限尽可能小。现在学习的是第20页，共70页例题例题#现在学习的是第21页，共70页四、反插值法四、反插值法分析分析现在学习的是第22页，共70页问题求解问题求解#现在学习的是第23页，共70页FLagrangeLagrange 插值公式的特点：插值公式的特点：形式对称形式对称通常用于理论分析通常用于理论分析当增加插值节点时，在计算实践中不方便当增加插值节点时，在计算实践中不方便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 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 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.差商的计算差商的计算现在学习的是第30页，共70页 根据插值多项式的存在唯一性知，如果根据插值多项式的存在唯一性知，如果f f(x x)充分光滑，充分光滑，则有估计则有估计不足：不足：对函数的光滑性要求高；对函数的光滑性要求高；需估计导函数的最值；需估计导函数的最值；偏保守。偏保守。导数型误差导数型误差估计估计三、三、NewtonNewton插值余项插值余项现在学习的是第31页，共70页 差商型误差估计差商型误差估计导数和差商的关系导数和差商的关系差商型误差估计特点差商型误差估计特点：对被插值函数光滑性要求不高；：对被插值函数光滑性要求不高；但不适用于实际计算。但不适用于实际计算。现在学习的是第32页，共70页四、例题四、例题解解 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,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 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：各阶差分可用函数值线性表示，其计算公式各阶差分可用函数值线性表示，其计算公式为：为：其中性质性质2 2：差分与差商满足下述关系：差分与差商满足下述关系：证明：证明：利用数学归纳法利用数学归纳法当k1时，有即结论成立。即结论成立。现在学习的是第36页，共70页设设k km-1m-1时结论成立，即时结论成立，即则当则当k km m时，有时，有由数学归纳法知，结论成立。由数学归纳法知，结论成立。证毕现在学习的是第37页，共70页Remark：类似地可以定义类似地可以定义向后差分向后差分与与中心差分中心差分：性质性质3 3：差分与导数满足关系：差分与导数满足关系：证明：证明：利用差商与导数、差分的关系，有：利用差商与导数、差分的关系，有：证毕现在学习的是第38页，共70页二、二、NewtonNewton向前向前插值公式插值公式 令令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向前插值公式向前插值公式，又称表初公式，它利用差分表的最，又称表初公式，它利用差分表的最上面一个斜行的数值进行计算。上面一个斜行的数值进行计算。现在学习的是第41页，共70页四、例题四、例题解解现在学习的是第42页，共70页#现在学习的是第43页，共70页五、五、NewtonNewton向后插值公式向后插值公式 类似于向前差分，也可以得到差商与向后差分的关系：类似于向前差分，也可以得到差商与向后差分的关系：将插值节点从大到小排列，即将插值节点从大到小排列，即 类似于向前插值公式，可得到类似于向前插值公式，可得到NewtonNewton向后插值公式向后插值公式，又称又称表末公式表末公式，它利用差分表的最下面一个斜行的数值进，它利用差分表的最下面一个斜行的数值进行计算。行计算。同样，还可以利用中心差分，构造插值公式，称为同样，还可以利用中心差分，构造插值公式，称为贝贝塞尔（塞尔（BesselBessel）插值公式）插值公式。现在学习的是第44页，共70页 这一类插值问题为这一类插值问题为埃尔米特埃尔米特(Hermite)(Hermite)插值问题插值问题。其。其几何意义是在插值点上插值曲线与被插值曲线有公共切线。几何意义是在插值点上插值曲线与被插值曲线有公共切线。由这由这2 2n n+2+2个条件可以唯一确定一个个条件可以唯一确定一个2 2n n+1+1次的插值多项式。次的插值多项式。具体我们采用基函数的方法来确定。具体我们采用基函数的方法来确定。1.4 1.4 埃尔米特插值埃尔米特插值一、问题一、问题现在学习的是第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页三、特殊情形带不完全导数的插值问题举例三、特殊情形带不完全导数的插值问题举例分析分析（方法（方法1 1）：）：误差：误差：#现在学习的是第52页，共70页1.1.高次插值的评述高次插值的评述 在实际应用中在实际应用中,很少采用高次插值。很少采用高次插值。.在两相邻插值节点间在两相邻插值节点间,插值函数未必能够很好地近似被插值函数未必能够很好地近似被插值函数。插值函数。一、分段插值法一、分段插值法.对于等距节点的牛顿插值公式对于等距节点的牛顿插值公式,函数值的微小扰动函数值的微小扰动可能引起高阶差分有很大的变化可能引起高阶差分有很大的变化.1.5 1.5 三次样条插值三次样条插值现在学习的是第53页，共70页 函数函数 在区间在区间-5,5-5,5上用等距上用等距节点的插值问题是上世纪初节点的插值问题是上世纪初RungeRunge研究过的一个研究过的一个有名实例有名实例.在区间上分别采用在区间上分别采用1010次、次、1515次、次、2020次的等距节点插值多项式。随着插值次数的提次的等距节点插值多项式。随着插值次数的提高高,在在 范围内的近似程度并没有变好范围内的近似程度并没有变好,反而变坏反而变坏.高次插值并不一定带来更好的近似高次插值并不一定带来更好的近似效果。效果。现在学习的是第54页，共70页(a)现在学习的是第55页，共70页(b)(c)函数函数 的等距节点插值公式的等距节点插值公式 在区间在区间0,5上的近似程度示意图上的近似程度示意图 现在学习的是第56页，共70页2.2.分段插值分段插值 设设 已知节点已知节点 上的函数值上的函数值 若若 满足满足 则称则称 为分段插值函数。为分段插值函数。是整体插值区间上的连续函数是整体插值区间上的连续函数,随着子区间随着子区间长度长度 变小变小,不提高子区间上的插值幂次便可以不提高子区间上的插值幂次便可以满足给定的任意精度要求满足给定的任意精度要求.但一般说来但一般说来,在子区间在子区间的端点处导数是不存在的的端点处导数是不存在的.为了避免高次插值的缺点，常采用分段插值，即将为了避免高次插值的缺点，常采用分段插值，即将插值区间分成若干小区间，在每个小区间上利用前面介插值区间分成若干小区间，在每个小区间上利用前面介绍的插值方法构建低次插值多项式。绍的插值方法构建低次插值多项式。现在学习的是第57页，共70页二、二、三次样条三次样条插值插值 分段插值法具有一致的收敛性分段插值法具有一致的收敛性,但它只保证插值函数但它只保证插值函数整体的连续性整体的连续性,但在连接处不一定光滑，不能够满足精密但在连接处不一定光滑，不能够满足精密机械设计（如船体、飞机、汽车等的外形曲线设计）对函机械设计（如船体、飞机、汽车等的外形曲线设计）对函数光滑性的要求。数光滑性的要求。早期的工程技术人员在绘制给定点的曲线时，使用一早期的工程技术人员在绘制给定点的曲线时，使用一种具有弹性的细长木条（或金属条），称之为种具有弹性的细长木条（或金属条），称之为样条样条（SplineSpline），强迫它弯曲通过已知点。弹性力学理论指出样），强迫它弯曲通过已知点。弹性力学理论指出样条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之间为三次多项式，即为数学上的间为三次多项式，即为数学上的三次样条插值曲线三次样条插值曲线。现在学习的是第58页，共70页1.1.三次样条插值函数的定义三次样条插值函数的定义 定义定义 给定区间给定区间 的一个分划的一个分划 .在小区间在小区间 上是上是3 3次多项式次多项式.在节点在节点 处具有处具有2阶连续的导数阶连续的导数;则称则称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个个约约束束条条件件.常常用用的的约束条件有以下三类：约束条件有以下三类：此时一般有此时一般有 成立成立.周期性边界条件周期性边界条件 ,.弯矩边界条件 特别的称 为自然边界条件.转角边界条件转角边界条件 现在学习的是第61页，共70页2.2.三弯矩构造法三弯矩构造法记 ,基本步骤如下：.取 为待定参数，并用S(x)的插值条件写出 的表达式。.代入S(x)的表达式，得各个区间上的表达式。.用 在内节点 的连续条件及边界条件导出关于 的方程组。.求解后得到 。现在学习的是第62页，共70页式中 。对 积分两次,并利用插值条件 ,确定两个积分常数,得到 现在学习的是第63页，共70页计算 类似可以得到类似可以得到 现在学习的是第64页，共70页 两边同乘以两边同乘以 ,得得 令令 ,有有式中 ,.现在学习的是第65页，共70页若附加弯矩约束条件若附加弯矩约束条件,得得 系数矩阵严格对角占优系数矩阵严格对角占优,故系数矩阵非奇异故系数矩阵非奇异,上述上述线性方程组有唯一解，可用追赶法求解。将解带回到子线性方程组有唯一解，可用追赶法求解。将解带回到子区间上的表达式中（用二阶导表示），即有区间上的表达式中（用二阶导表示），即有s s(x x)在每个在每个区间上的表达式。区间上的表达式。现在学习的是第66页，共70页若附加转角边界条件若附加转角边界条件,得得线性方程组线性方程组为为 现在学习的是第67页，共70页对于周期性边界条件对于周期性边界条件,得：得：即即式中 ,.现在学习的是第68页，共70页线性方程组为线性方程组为:将将 当作已知参数当作已知参数,从后从后 个方程中求解出用个方程中求解出用 表表示的后示的后 个参数个参数,然后将它们代入第一个方程解然后将它们代入第一个方程解得得 ,最终得到其它参数最终得到其它参数.现在学习的是第69页，共70页Remark：1.类似地，可以使用节点处的一阶导数来表类似地，可以使用节点处的一阶导数来表示三次样条插值函数。示三次样条插值函数。2.2.对三次样条插值函数来说，当插值节点逐渐对三次样条插值函数来说，当插值节点逐渐加密时，可以证明，不但样条插值函数收敛于加密时，可以证明，不但样条插值函数收敛于函数本身，而且其导数也收敛于函数的导数。函数本身，而且其导数也收敛于函数的导数。现在学习的是第70页，共70页