典型数值分析模型精.ppt
( 4.5 )《典型数值分析模型精.ppt》由会员分享，可在线阅读，更多相关《典型数值分析模型精.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、典型数值分析模型典型数值分析模型第1页，本讲稿共94页第一节插值法在生产和科学研究中,经常出现这样的问题:由实验或测量得到的某一函数在一系列点处的值,需要构造一个简单函数作为函数的近似表达式:,使得这类问题称为插值问题.称为被插值函数,称为插值函数称为插值节点;式(6-1)称为插值条件.常用的插值函数是多项式与样条函数.第2页，本讲稿共94页拉格朗日(lagrange)插值取n次多项式pn(x)作为插值函数pn(x)=a0+a1x+a2x2+anxn 利用插值条件有：其系数行列式为n+1阶范德蒙行列式，因插值节点互不相同，所以方程组的解存在且唯一。第3页，本讲稿共94页其系数行列式为范德蒙(V
2、andermonde)行列式:由于插值节点互不相同,所以上述行列式不等于0,故由克莱姆(Cramer)法则知,方程组(6-3)的解存在而且是唯一的.实际上比较简单的方法不是解方程组(6-3),而是构造一组插值基函数.为此,首先求满足条件第4页，本讲稿共94页的n次多项式因为式（6-4）表明，除点以外，其他所有的节点都是n次多项式的零点，故设其中A为待定常数。由可得所以第5页，本讲稿共94页称之为拉格朗日插值基函数。利用插值基函数（6-5），可以构造多项式就是满足插值条件的拉格郎日插值问题的解，称式（6-6）为拉格朗日插值多项式。特别地，当n=1时称为线性插值，其插值多项式为：满足从几何上看,为
3、过两点的直线。第6页，本讲稿共94页当n=2时，称为抛物线插值，其插值多项式为：满足从几何上看为过点和的一条抛物线。第7页，本讲稿共94页埃尔米特插值许多插值问题不但要求在节点上函数值相等，而且还要求对应的导数值也相等，甚至要求高阶导数也相等，满足这种要求的插值多项式被称为埃尔米特（Hermite）插值多项式设在节点上，要求插值多项式，满足条件由于（6-7）式给出了2n+2个条件，因此可以唯一确定一个次数不超过2n+1的多项式，其形式为根据（6-7）式来确定显然非常复杂。第8页，本讲稿共94页仿照拉格朗日插值多项式的基函数方法，可先求插值基函数，及共用2n+2个，每一个基函数都是2n-1次多项
4、式，且满足条件于是满足条件（6-7）的插值多项式可写成由条件（6-8）式显然有第9页，本讲稿共94页利用拉格朗日插值基函数令其中为（6-5）式所表示的基函数。由条件（6-8）式可得整理得:解出对两边取对数求导可得于是第10页，本讲稿共94页同理仿照拉格朗日插值余项的证明方法，若在内的2n+2阶导数存在，则其插值余项为其中第11页，本讲稿共94页三次样条插值分段线性插值，具有良好的稳定性和收敛性，但光滑性较差。在数学上若函数（曲线）的k阶导数存在且连续，则称该曲线具有k阶光滑性。易见，分段线性插值不光滑，这影响了它在某些工程技术实际问题中的应用。例如：在船体、飞机等外形曲线的设计中，不仅要求曲线
5、连续而且还要求曲线的曲率连续，这就要求插值函数具有连续的二阶导数。为解决这一类问题，就产生了三次样条插值。所谓样条（Spline），本来是指一种绘图工具，它是一种富有弹性的细长木条，在飞机或轮船制造过程中，被用于描绘光滑的外形曲线。使用时，用压铁将其固定在一些给定的节点上，在其他地方任其自然弯曲，然后依样画下的光滑曲线，就称为样条曲线。它实际上是由分段三次曲线拼接而成，在连续点即节点上，不仅函数自身是连续的，而且它的一阶和二阶导数也是连续的。从数学上加以概括，可得到样条函数的定义如下：第12页，本讲稿共94页三次样条函数记作S（x），axb，满足：在每个小区间xi，xi+1（i=0,1,n-1
6、）是三次多项式在每个内节点xi（i=1,2,n-1）上具有二次连续导数S（xi）=yi，i=0,1,2,n由三次样条函数中的条件知，S（x）有4n个待定系数。由条件知，S（x）在n-1个内节点上具有二阶连续导数，即满足条件：第13页，本讲稿共94页共有3（n-1）个条件。由条件，知S（xi）=yi（i=0,1,2,n），共有n+1个条件。因此，要确定一个三次样条，还需要外加4n-3（n-1）-（n+1）=2个条件，最常用的三次样条函数S（x）的边界条件有两类：第一类边界条件：第二类边界条件：特别地，,称为自然边界条件第三类边界条件：称为周期边界条件。三次样条插值不仅光滑性好，而且稳定性和收敛性
7、都有保证，具有良好的逼近性质。样条插值函数的建立第14页，本讲稿共94页构造满足条件的三次样条插值函数的表达式可以有多种方法。下面我们利用的二阶导数值表达，由于在区间上是三次多项式，故在上是线性函数，可表示为其中对积分两次并利用及，可定出积分常数，于是得三次样条表达式第15页，本讲稿共94页上式中是未知的，为确定对求导得由此可得类似地可求出在区间上的表达式，从而得利用可得第16页，本讲稿共94页其中对第一类边界条件，可导出两个方程第17页，本讲稿共94页如果令则式（6-14）及其（6-16）可写出矩阵通过求解上述三对角矩阵可求得对于第二类边界条件，直接得端点方程第18页，本讲稿共94页如果令，
8、则式（6-14）及式（6-18）也可以写成矩阵（6-17）的形式对于第三类边界条件，可得其中则式（6-14）及式（6-19）可以写成矩阵形式求解上述矩阵可得第19页，本讲稿共94页曲线拟合通过实验等方法观测到反映某个函数y=f(x)的数据(xi，yi)（i=1,2,n），要求利用这些数据构造出y=f（x）的近似表达式y=P（x），上面介绍的插值法就是寻求近似函数的方法之一。但由于实验观测数据不可避免地带有误差，甚至是较大的误差，所以使用插值法是不合适的，它会保留数据的误差。因此，不必要求近似函数y=P（x）满足 P（xi）=yi（i=1,n），而只要求偏差按某种标准最小，以反映所给数据的总体趋
9、势，消除局部波动的影响，这就是曲线拟合问题。这样的函数P（x）称为拟合函数。拟合的准则：衡量一个函数P（x）同所给数据（xi，yi）（i=1,n）的偏差的大小，常用的准则有如下三种：第20页，本讲稿共94页(1)最小二乘准则：使偏差的平方和最小，即(2)最小一乘准则：使偏差的绝对值之和为最小，即(3)极小极大准则：使偏差的最大绝对值最小，即第21页，本讲稿共94页计算的方法(1)最小二乘准则下的计算方法设为m个线性无关的函数，对给定的数据（xi，yi）（i=1,2,n），求使最小。利用极值的必要条件得到关于的线性方程组第22页，本讲稿共94页则方程组可表示为，其中由于线性无关，所以G是列满秩，
10、GTG是可逆矩阵，方程组的解存在且唯一，并且常用的拟合曲线:第23页，本讲稿共94页(a)取，得直线拟合(b)取，得多项式拟合(c)取，得多元线性拟合(d)取，则得曲线拟合第24页，本讲稿共94页还有许多非线性拟合，例如，S曲线可通过变量代换，令，化为对 a1，a2的线性函数。一般地，已知一组数据，先画出数据的散点图，在直观判断的基础上，选几种曲线分别作拟合，选择偏差平方和Q最小的曲线。第25页，本讲稿共94页(2)最小一乘准则下的计算方法设为m个线性无关的函数，对给定的数据（xi，yi）（i=1,2,n），求使达到最小。易见式中目标函数含有绝对值，为了去掉上式中的绝对值，令第26页，本讲稿共
11、94页则Ui0，Vi0，且此时（6-20）式可改写为相应地（6-21）式可改写为综合以上几个式子，求得的问题可归结为如下线性规划问题：为任意常数第27页，本讲稿共94页(3)极小极大准则下的计算方法设为m个线性无关的函数，对给定的数据（xi，yi）（i=1,2,n），求使达到最小。上式可改写为第28页，本讲稿共94页记，则求解的问题可归结为如下线性规划问题：为任意常数第29页，本讲稿共94页第二节非线性方程求根本节主要讨论单变量非线性方程的求根问题，这里。在科学与工程计算中有大量方程求根问题，其中一类特殊的问题是多项式方程其中系数为实数。方程的根，又称为函数的零点，它使，若可分解为其中为正整数
12、，且。当时，则称单根，若称为重根，或为的重零点。若是的重零点，且充分光滑，则第30页，本讲稿共94页当为代数多项式（6-25）时，根据代数基本定理可知，n次方程在复数域中有且只有n个根（含复根，m重根为m个根），n=1，2时方程的根是大家熟悉的，n=3，4时虽有求根公式但比较复杂，可在数学手册中查到，但已不适合于数值计算，而时就不能用公式表示方程的根。因此，通常对的多项式方程求根与一般连续函数方程（6-20）一样都可采用迭代法求根。迭代发要求先给出根的一个近似，若且，根据连续函数性质可知在内至少有一个实根，这时称为方程（6-20）的有根区间。通常可通过逐次搜索法求得方程的有根区间。第31页，本
13、讲稿共94页例1.求方程的有根区间。解：f(0)0,f(1)0,f(3)0,f(4)0,f(5)0;由此可知，方程的有根区间为1,2,3,4,5,6;练习:求方程的有根区间。第32页，本讲稿共94页1不动点迭代法将方程（6-24）改写成等价的形式若要求满足，则；反之亦然，称为函数的一个不动点。求的零点就等价于求的不动点，选择一个初始近似值，将它代入（6-26）右端，即可求得可以如此反复迭代计算称为迭代函数。如果对任何，由（6-27）得到的序列有极限则称迭代方程（6-27）收敛，且为的不动点，故称（6-27）为不动点迭代法。第33页，本讲稿共94页上述迭代是一种逐次逼近法，其基本思想是将隐式方程
14、（6-26）归结为一组显式的计算公式（6-27），就是说，迭代过程实质上是一个逐步显式化的过程。方程的求根问题在xy平面上就是在确定曲线与直线y=x交点，对于的某个近似值，在曲线上可确定一点,它以为横坐标，而纵坐标则等于。过引平行x轴的直线，设此直线交直线y=x于点，然后过再作平行于y轴的直线，它与曲线的交点记作，则点的横坐标为，纵坐标则等于，在曲线上得到点列，其横坐标分别为依公式求得的迭代值。如果点列趋向于点，则相应的迭代值收敛到所求的根。第34页，本讲稿共94页2不动点的存在性与迭代法的收敛性首先考察在上不动点的存在唯一性。定理1设满足以下两个条件：（1）对任意的有。（2）存在正常，使对任
15、意都有则在上存在唯一的不动点。在的不动点存在唯一的情况下，可得到迭代法（6-27）收敛的一个充分条件。定理2设满足定理1中的两个条件，则对任意，由（6-27）得到的迭代序列收敛到的不动点，并有误差估计第35页，本讲稿共94页迭代过程是个极限过程。在用迭代法进行实际计算时，必须按精度要求控制迭代次数。误差估计式（6-29）原则上可用于确定迭代次数，但它由于含有信息L而不便于实际应用。根据式(6-30)，对任意的正整数p有在上式中令知由此可见，只要相邻两次计算结果的偏差足够小即可保证近似值具有足够的精度。第36页，本讲稿共94页对定理1和定理2中的条件（2），在使用时如果且对任意有则由中值定理可知
16、对有它表明定理中的条件（2）可用（6-30）代替。3局部收敛性与收敛阶上面给出了迭代序列在区间上的收敛性，通常称为全局收敛性。有时不易检验定理的条件，实际应用时通常只在不动点的邻近考察其收敛性，即局部收敛性。第37页，本讲稿共94页定义1设有不动点，如果存在的某个邻域，对任意，迭代（6-26）产生的序列。且收敛到，则称迭代法（6-26）局部收敛。定理3设为的不动点，在的某个邻域连续，且，则迭代法（6-26）局部收敛。为衡量迭代法收敛速度的快慢，我们给出下列定义。定义2设迭代过程收敛于方程的根，如果迭代误差当时成立下列渐进关系式第38页，本讲稿共94页则称该迭代过程是P阶收敛的，特别地，P=1时
17、称线性收敛，P1时称超线性收敛，P=2时称平方收敛。定理4对于迭代过程，如果在所求根的邻近连续，并且则该迭代过程在点邻近是p阶收敛的。上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数的选取，如果当时，则该迭代过程只可能是线性收敛。第39页，本讲稿共94页第三节牛顿法及其收敛性1.牛顿法对于方程如果是线性函数，则它的求根是容易的，牛顿法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。设已知方程有近似根（假定），将函数在点展开，有于是方程可近似地表示为第40页，本讲稿共94页这是个线性方程，记其根为，则的计算公式为这就是牛顿（Newton）法。牛顿法有明显的几何解释
18、，方程的根可解释为曲线与x轴的交点的横坐标，设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与x轴的交点的横坐标作为的新的近似值。注意到切线方程为这样求得的值必满足（6-32）从而就是牛顿公式（6-33）的计算结果。由于这种几何背景，牛顿法亦称切线法。第41页，本讲稿共94页关于牛顿法（6-33）的收敛性，可直接由定理4得到，对（6-33）其迭代函数为由于假定是的一个单根，即，则由上式知，于是依据定理4可以断定，牛顿法在根的邻近是平方收敛的。又因，可得第42页，本讲稿共94页2.简化牛顿法与牛顿下山法牛顿法的优点是收敛快，缺点是每步迭代要计算及，计算量较大且有时计算较困难，二是初始近
19、似只在根附近才能保证收敛，如给的不合适可能不收敛。为克服这两个缺点，通常可用下述方法。(1)简化牛顿法，也称平行弦法，其迭代公式为迭代函数若，即取。在根附近成立，则迭代法（6-35）局部收敛。第43页，本讲稿共94页在（6-35）中取，则称为简化牛顿法，这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与x轴交点作为的近似。（2）牛顿下山法。牛顿法收敛性依赖初值的选取。如果偏离所求根较远，则牛顿法可能发散。例如，用牛顿法求解方程此方程在附近的一个根。设取迭代初值，用牛顿法公式第44页，本讲稿共94页计算得迭代三次得到的结果有六位有效数字。但是，如果改用作为迭代初值，则依牛顿法公式（6-37
20、）迭代一次得这个结果反而比更偏离了所求的根为了防止迭代发散，我们对迭代过程再附加一项要求，即具有单调性：满足这项要求的算法称为下山法。第45页，本讲稿共94页我们将牛顿法和下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。为此，我们将牛顿法的计算结果与前一步的近似值适当加权平均作为新的改进值其中称为下山因子，（6-39）即为第46页，本讲稿共94页称为牛顿下山法。选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件（6-38）成立为止。若用此法解方程（6-36），当时由（6-37）求得，它不满足条件（6-38），通过逐次取半进行试算，当时可求得。此时有而，显
21、然。由计算时，均能使条件（6-33）成立。计算结果如下：第47页，本讲稿共94页即为的近似。一般情况只要能使条件（6-38）成立，则可得到，从而使收敛。第48页，本讲稿共94页第四节弦截法与抛物线法用牛顿法求方程（6-24）的根，每步除计算外还要算，当函数比较复杂时，计算往往较困难，为此可以利用已求函数值来回避导数值的计算的计算，这类方法是建立插值原理基础上的，下面介绍两种常用方法。1弦截法设是的近似根，我们利用构造一次插值多项式，并用的根作为的新的近似根。由于第49页，本讲稿共94页因此有这样导出的迭代公式（6-42）双点弦截法可以看作牛顿公式中的导数用差商取代的结果。现在解释这种迭代过程的
22、几何意义。如图6-4，曲线上横坐标为的点分别记为，则弦线的斜率等于差商值第50页，本讲稿共94页其方程是因此，按（6-42）式求得的实际上是弦线与x轴交点的横坐标。这种算法因此而称为弦截法。弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别。切线法在计算时只用到前一步的值，而弦截法（6-42），在求时要用到前面两步的结果，因此使用这种方法必须先给出两个初始值。第51页，本讲稿共94页2抛物线法设已知方程的三个近似根，我们以这三点为节点构造二次插值多项式。并适当选取的一个零点作为新的近似根，这样确定的迭代过程称抛物线法。亦称密勒（Mller）法。在几何图形上，这种方法的基本思想是用抛物线
23、与x轴交点作为所求根的近似位置（图6-5）。现在推导抛物线法的计算公式。插值多项式第52页，本讲稿共94页有两个零点式中为了从（6-43）中定出一个值，我们需要讨论根式前正负号的取舍问题。在三个近似根中，自然假定更接近所求的根，这时，为了保证精度，我们选式（6-43）中较接近的值作为新的近似根。为此，只要取根式前的符号与的符号相同。第53页，本讲稿共94页第五节第五节孩子成长和学生考试成绩问题ti（从（从11岁起年龄）岁起年龄）0 0.8 1.4 2.0 2.4 3.2 4.0 增长高度增长高度hi（cm）0 0.74 2.25 5.25 8.25 15.00 21.38 ti（从（从11岁起
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 典型 数值 分析 模型
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内