计算方法重修

1、2022-6-22科学计算的魅力科学计算的魅力 南京航空航天大学数学系南京航空航天大学数学系 2022-6-22内容提要1. 1. 科学计算的地位与应用科学计算的地位与应用 2. 2. 科学计算的基本内容科学计算的基本内容理论理论研究研究科学科学实验实验科学研究科学研究/工程技术工程技术 科学计算的地位科学计算的地位科学科学计算计算应用应用问题问题数学数学模型模型计算计算方法方法建模建模计算计算算法算法软件软件 科学工程计算科学工程计算 计算方法的意义计算方法的意义: （3）基于离散数据建立数学模型时）基于离散数据建立数学模型时 无法采用传统数学方法获得所需解的三种有代表性无法采用传统数学方法

2、获得所需解的三种有代表性的情形的情形 :（1）所涉及的数学模型无系统的求解析解的方法）所涉及的数学模型无系统的求解析解的方法 （2）所涉及数学模型的解法计算量大，只适用）所涉及数学模型的解法计算量大，只适用 于规模较小的情形于规模较小的情形 什么是计算方法（数值分析）？什么是计算方法（数值分析）？研究怎样通过计算机所能执行的基本运算，求得研究怎样通过计算机所能执行的基本运算，求得各类问题数值解或近似解的学问。各类问题数值解或近似解的学问。加、减、乘、加、减、乘、除、逻辑运算除、逻辑运算 计算方法计算方法（又称为（又称为数值分析数值分析）的任务）的任务:研究如何对给定的问题构建只须进行有限步四则

3、研究如何对给定的问题构建只须进行有限步四则运算的计算模型，以便有效地借助于计算机迅速运算的计算模型，以便有效地借助于计算机迅速求出所需要的数值解。这种计算模型通常又称为求出所需要的数值解。这种计算模型通常又称为计算格式计算格式。计算方法不同于纯粹数学学科的一些新特点计算方法不同于纯粹数学学科的一些新特点: : 面向计算机：将要求解的数学问题简化成一系列的面向计算机：将要求解的数学问题简化成一系列的 算术运算和逻辑运算算术运算和逻辑运算，以便在计算机，以便在计算机 上求出问题的上求出问题的数值解数值解。遵循的遵循的相容性原则相容性原则，满足控制误差积累的，满足控制误差积累的数值稳定性数值稳定性要

4、求要求，以及评价计算格式优劣的，以及评价计算格式优劣的计算复杂性计算复杂性，为适应，为适应大型计算机的计算，现今又提出了大型计算机的计算，现今又提出了并行性并行性要求。要求。三.科学计算的基本内容线性方程组求解线性方程组求解非线性方程求根非线性方程求根插值与拟合插值与拟合数值微分与积分数值微分与积分常微分方程数值解常微分方程数值解计算格式的相容性与稳定性计算格式的相容性与稳定性定义定义1.11.1 如果一个计算格式在取某种极限后可还原成如果一个计算格式在取某种极限后可还原成某数学模型，则称该计算格式与此数学模型相容。某数学模型，则称该计算格式与此数学模型相容。 定义定义1.21.2 如果在用某

5、一计算格式进行数值计算的如果在用某一计算格式进行数值计算的过程中，误差不会严重积累，从而保证解满足所要过程中，误差不会严重积累，从而保证解满足所要求的精确度求的精确度( (简称精度），则称该计算格式简称精度），则称该计算格式数值稳数值稳定定（简称为（简称为稳定稳定），反之则为），反之则为不稳定不稳定。 稳定性分析通常基于对初始误差的传播状况的讨论。 补充内容：补充内容：一般来说，若一个计算格式满足如下误差关系式一般来说，若一个计算格式满足如下误差关系式 )(|为常数为常数初初后后CeCe 则认为该计算格式数值稳定。则认为该计算格式数值稳定。 所以，人们通常以相容性和稳定性作所以，人们通常以相容

6、性和稳定性作为对一个计算格式可行性的基本要求。为对一个计算格式可行性的基本要求。 稳定性分析稳定性分析 第二章第二章 线性方程组的数值解法线性方程组的数值解法 2.1 消去法消去法2.2 矩阵分解法矩阵分解法2.3 向量与矩阵范数向量与矩阵范数3.4 经典迭代法经典迭代法给定一个线性方程组给定一个线性方程组Ax=b1112111212222212(),nnijn nnnnnnnaaaxbaaaxbAaxbaaaxb 其其中中A A为系数矩阵为系数矩阵,b,b为右端向量，为右端向量，x x为需为需求解的未知向量。求解的未知向量。 直接法直接法：按求精确解的方法运算求解，：按求精确解的方法运算求解

7、， 有有GaussGauss消去法及修正（矩阵分解法）等。消去法及修正（矩阵分解法）等。迭代法迭代法：给一个初始近似解：给一个初始近似解, ,按一定法则按一定法则逐步求更精确的近似解的过程逐步求更精确的近似解的过程; ; 有经典与有经典与现代迭代法现代迭代法. . 解线性方程组数值解法有两类：解线性方程组数值解法有两类：2.3 2.3 向量范数与矩阵范数向量范数与矩阵范数定义定义2.12.1 从向量到实数的实值函数满足下列从向量到实数的实值函数满足下列3 3个条件称为个条件称为向量范数向量范数：(1)0;00 xxx ；(3),xyxy 三三角角不不等等式式： (2),ncR xRcxc x

8、任任意意有有；111niixx ( (1 1) )- - 范范数数：1/222122niixx （） 范范数数： 13maxii nxx （ ） - - 范范数数： 三个常用向量范数：三个常用向量范数：定义定义2.22.2 设设|是是Rn上向量范数，上向量范数， A为为Rnn中的矩阵，中的矩阵，称称 矩阵范数矩阵范数。1maxxAAx 12112211max,max,xxAAxAAx1maxxAAx 三个常用矩阵范数为三个常用矩阵范数为1211max|,(),(2.3.2 )nTijj niAaAA Aa 11max|(2.3.2 )niji njAab 三个常用矩阵范数的计算公式为三个常用矩

9、阵范数的计算公式为例例2.6 2.6 设设 23(1,2, 3) ,11TxA 求常用的向量与矩阵范数。求常用的向量与矩阵范数。解：解：126,14,3;xxx 12152214,5.2AAA 2.4 2.4 经典迭代法经典迭代法( (Classic Iterative Methods) ) 迭代法思想：迭代法思想： (1)AxbxMxf (1)( )(2)kkxMxf 迭迭代代格格式式：0(3),x（）取取初初始始用用迭迭代代格格式式求求解解。 2.4.1 2.4.1 JacobiJacobi迭代法迭代法 ( (以对角元为分母以对角元为分母) )12310213210115 ,012510i

10、ixxax 例例2. 7：2. 7：1122331021310211551210 xxxxxx 解解：11223300.20.10.30.200.11.50.20.402xxxxxx (1)( )( )123(1)( )( )213(1)( )( )3120.20.10.30.20.11.50.20.42kkkkkkkkkxxxxxxxxx (11)1(11)2(11)31.0002.0003.000 xxx 将上述过程一般将上述过程一般化化建立迭代格式建立迭代格式(0)(0)(0)1230 xxx将初值将初值 代入后迭代得代入后迭代得以分量表示方程组得以分量表示方程组得 1(1,2,)nij

11、jija xbin 对角元对应的量对角元对应的量移到左边，其它移到左边，其它量在右边量在右边便得便得 ：11()(1,2,)niiijjj iiijxba xina Jacobi迭代迭代 (1)( )11()(1,2,;0,1,2)(2.4.2)nkkiiijjj iiijxba xin ka 从而可建立迭代格式从而可建立迭代格式1212121110000,000nnnnnn naaaaLUaaa 1122,nnaaADLUDa可可逆逆雅可比迭代格式（雅可比迭代格式（2.4.22.4.2）可用矩阵表示为）可用矩阵表示为 (1)1( )1()kkxDLU xD b MJf J迭代法的矩阵表示迭代

12、法的矩阵表示 2.4.2、Guass-SeidaliGuass-Seidali迭代法迭代法( (及时更新计算值及时更新计算值) )将例将例2.7中对中对Jacobi迭代格式修改得迭代格式修改得(1)( )( )123(1)(1)( )213(1)(1)(1)3130.20.10.30.20.11.50.20.42kkkkkkkkkxxxxxxxxx 将上述过程一般化将上述过程一般化用矩阵表示为用矩阵表示为 1(1)(1)( )111()1,2,(2.4.5)inkkkiiijjijjjj iiixba xa xina Gauss-Seidel迭代迭代 (1)1( )1()()(2.4.7)kk

13、xDLU xDLbf GMG例例 2.8 用用JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法求解迭代法求解线性方程组线性方程组 1231021321011512510 xxx解解Gauss-Seidel迭代迭代(1)( )( )123(1)(1)( )213(1)(1)(1)3120.30.20.11.50.20.120.20.4kkkkkkkkkxxxxxxxxx (1)( )( )123(1)( )( )213(1)( )( )3120.30.20.11.50.20.120.20.4kkkkkkkkkxxxxxxxxx Jacobi迭代迭代令

14、令 取四位小数迭代计算取四位小数迭代计算 (0)(0)(0)1230,xxx由由Jacobi迭代得迭代得 (11)(11)(11)1231.000,2.000,3.000 xxx由由Gauss-SeidelGauss-Seidel迭代得迭代得 (6)(6)(6)1231.000,2.000,3.000 xxx相应的迭代公式相应的迭代公式为为 2.4.3 一般一般 迭代法的收敛性迭代法的收敛性 定义定义3.2 3.2 设设 , , 其精确解为其精确解为 x*, AxbxMxf 等等价价于于相应的迭代格式为相应的迭代格式为 (1)( )(2.4.9)kkxMxf 如果存在某个向量范数使得如果存在某

15、个向量范数使得( )*lim0,kxxx 则称由（则称由（2.4.92.4.9）确立的迭代法收敛）确立的迭代法收敛, , 否则称发散否则称发散. .定理定理 2.12.1 设方程组设方程组Ax=b的精确解为的精确解为x*。如果存在一。如果存在一个矩阵范数使得（个矩阵范数使得（2.4.92.4.9）中的迭代矩阵满足条件）中的迭代矩阵满足条件 1M 则由则由(2.4.9)(2.4.9)确立的迭代任何初始向量均收敛确立的迭代任何初始向量均收敛。且。且 证证 1,M 而而( )*lim0,kkxx因因此此定理得证。定理得证。 (1)*( )*( )*()()kkkxxM xxMxx 迭代式相减取范数得

16、迭代式相减取范数得 (1)*( )*kkxxMxx 进一步递推得进一步递推得1(1)*( )*()kkkxxMxx 则由则由(2.4.9)(2.4.9)确立的迭代法收敛确立的迭代法收敛。 121,1,1MMM 或或或或推论推论 2.12.1 若若(2.4.9)(2.4.9)迭代矩阵迭代矩阵 满足条件满足条件推论推论 2.2 2.2 若若JacobiJacobi（Gauss-SeidelGauss-Seidel）迭代法的迭代矩阵）迭代法的迭代矩阵 满足条件满足条件利用定理利用定理2.1很容易判别迭代法的收敛性。以常用很容易判别迭代法的收敛性。以常用矩阵范数为例，有下列结论。矩阵范数为例，有下列结

17、论。则则JacobiJacobi（Gauss-SeidelGauss-Seidel）迭代法对任何初始向量均收敛。）迭代法对任何初始向量均收敛。 11221(1),1(1),1(1)JGJGJGMMMMMM或或或或第三章第三章 非线性方程非线性方程(组组)的数值解法的数值解法 3.1 二分法二分法 3.2 不动点迭代法不动点迭代法 3.3 Newton法法 3.4 割线法割线法 3.5非线性方程组的非线性方程组的Newton法法（1 1）确定初始含根区间）确定初始含根区间 数值计算方法主要分为两大类。数值计算方法主要分为两大类。第一类是第一类是区间收缩法区间收缩法。 0)(: xf求求解解问问题

18、题（2 2）收缩含根区间）收缩含根区间第二类是第二类是迭代法迭代法。 （1 1）选定根的初始近似值）选定根的初始近似值（2 2）按某种原则生成收敛于根的近似点列）按某种原则生成收敛于根的近似点列 二分法评述二分法评述优点优点：简单可靠，易于编程实现，它对函数要：简单可靠，易于编程实现，它对函数要 求低，适用于的奇数重根情形。求低，适用于的奇数重根情形。缺点缺点：不能直接用于求偶重根，不能用于求复：不能直接用于求偶重根，不能用于求复 根，也难以向方程组推广使用，收敛速度根，也难以向方程组推广使用，收敛速度 慢。慢。3.2 不动点迭代法不动点迭代法0( )f x 迭代法的算法思想为：迭代法的算法思

19、想为： 1) 把（把（1 1）等价变换为如下形式）等价变换为如下形式 ( )(3.2.1)xx 2) 建立迭代格式建立迭代格式13()( .2.2)kkxx 3) 适当选取初始值适当选取初始值x 0 ，递推计算出所需的解。递推计算出所需的解。 3.2.13.2.1不动点与不动点迭代法不动点与不动点迭代法 1: ( )()kkxxg x 其其中中迭迭代代函函 迭迭代代格格式式数-称为不动点迭代法称为不动点迭代法或更一般地建立迭代格式或更一般地建立迭代格式 111(,)()kkkk mxxxxm 称为称为多步迭代法，多步迭代法，而迭代格式而迭代格式(3.2.2)(3.2.2)称为称为单步迭代法单步

20、迭代法. .例例3.313( )0f xxx 3-1xx由此建立迭代格式由此建立迭代格式 131(),( )-kkxxxx 其其中中：31xx 也可建立迭代格式也可建立迭代格式13(),( )1kkxxxx 其其中中：1021112()(),(),kkkxxxxxxxxx 得得到到列列数1021112()(),(),kkkxxxxxxxxx 得得到到列列数-发散发散-收敛收敛求求01.5x 在在 附近的一个根附近的一个根.3.2.2 迭代法的收敛性迭代法的收敛性 定理定理3.1 (3.1 (不动点存在唯一性定理不动点存在唯一性定理) ) 设设 ,( ) , xC a b 并且满足以下两个条件并

21、且满足以下两个条件: : , ,( )1.xa bxL *, ( ) , .xa bx 那那么么在在上上存存在在唯唯一一不不区间动点(2) (2) 存在常数存在常数 01,L , ,( ) , xa bxa b 若若有有；(1)对对 都收敛于都收敛于 的唯一不动点的唯一不动点 , , 并且并且 定理定理3.2 3.2 （非局部收敛定理）（非局部收敛定理） 在定理在定理3.13.1的条件下的条件下, , 01 , ,()kkxa bxx( )x*x1|(3.2.6)1kkkLxxxxL 103 2 51|( . . )kkLxxxxL 1ln1|ln|ln|101 LxxLK |11kkxxLL

22、（2）事后误差估计事后误差估计 (1) 事前误差估计事前误差估计简单地以简单地以 |1kkxx对给定的精度对给定的精度 可进行可进行 |*xxk代之代之注注: 在区间在区间 内内 , 对任何对任何 ，迭，迭代格式代格式 不收敛。不收敛。 ,ba( )1x 1()kkxx,0bax 定理定理3.3 设设 ， 若若 在在 x* 附近连续且附近连续且 ，则迭代格式，则迭代格式 在在 x* 附近局部收敛。附近局部收敛。 1*|()|x 注注: 由于由于 x* 事先未知，故实际应用时，事先未知，故实际应用时，代之以近似判则代之以近似判则 。 但需注但需注 意意 ，这实际上是假设了，这实际上是假设了x0充

23、分接近充分接近 x* ，若若 x0 离离 x* 较远，迭代格式可能不收敛。较远，迭代格式可能不收敛。 01|()|x *()xx ( )x 1()kkxx 3 , 2052)(3 xxxxf2531 kkxx3152 kkxx例例3.43.4352( ),xx 2322 31( ), , |( )|xxx 由由知知在在内内, ,所以该迭代格式在区所以该迭代格式在区间内间内发散发散，不可取。，不可取。 325( )xx 23321( )3(25)20( )(2)193xxx 又又由由在在区区间间内内单单调调减减得得故由定理故由定理3.2得：任取得：任取 ，该迭代格式该迭代格式收敛收敛。02,3x

24、 易知在易知在 x 0时时 单调增，单调增，故有故有( )x 22 3 3( )( )( )x则称该序列是则称该序列是 p p 阶收敛阶收敛的。的。p p=1=1且且0C1 0C1 时称为时称为线性收敛线性收敛; ;p p=1=1且且C=0 C=0 时称为时称为超线性收敛超线性收敛; ;p p=2 =2 时称为时称为平方收敛平方收敛。 10()kpkeC Ce 定义定义 设解序列设解序列 收敛于收敛于 ，如果迭代误，如果迭代误差差 当当 满足渐近关系式满足渐近关系式 kxkkexx k*x一般迭代法：线性收敛一般迭代法：线性收敛*11*()()( )()( )()1kkkkkkkkkxxexx

25、xxexxxxxxx 3.3 牛顿迭代法牛顿迭代法 3.3.1 3.3.1 牛顿迭代公式的构造牛顿迭代公式的构造 设设 f (x) 在其零点在其零点 附近连续可微，已知附近连续可微，已知 为的第为的第k次近似值，则次近似值，则 *xkx )()()()()()()(12xPxxxfxfxxOxxxfxfxfkkkkkkk 取取 的根作为的根作为 的第的第k+1次近似值次近似值 0)(1xPx1kx1()()()kkkkf xxxfx 解解得得3.3.33.3.3其迭代函数为其迭代函数为 ( )( )()( )f xxxfx 3.3.43.3.4牛顿迭代法牛顿迭代法几何意义几何意义：过点过点 作

26、函数作函数y= f (x)的切线的切线 l： ,()kkP xf x()()()kkkyf xfxxx 以切线以切线 l 与与x 轴的交点轴的交点 作为作为 的新近似值的新近似值 1kx*xxxk+1x*xkly3.3.2 3.3.2 牛顿迭代法的收敛性与收敛速度牛顿迭代法的收敛性与收敛速度 定理定理 3.5 给定给定 f (x)=0，如果在根，如果在根 附近附近 f (x)二阶连二阶连续，且续，且 为为 f (x)=0的单根，则牛顿迭代法在的单根，则牛顿迭代法在 附附近至少是平方收敛的。近至少是平方收敛的。 *x*x*x证证 2( )( )( )( )f x fxxfx 首先证明牛顿迭代法的

27、收敛性：首先证明牛顿迭代法的收敛性： 因此由定理因此由定理3.33.3知，牛顿迭代法局部收敛。知，牛顿迭代法局部收敛。 1()x 即即001*()()()fxxx 对牛顿迭代法对牛顿迭代法而单根保证了而单根保证了其次证明牛顿迭代法的收敛速度：其次证明牛顿迭代法的收敛速度： 之间之间与与介于介于由由kkkkkxxxxfxxxfxfxf 2)(21)()()(0整理得整理得 212)()()(21)()()(21)()(kkkkkkkkxxxffxxxxffxfxfxx 121( )1()2()2()kkkkeffxefxfx 所所以以 可见，当可见，当 时，牛顿迭代法为平方收敛；时，牛顿迭代法为

28、平方收敛；当当 时，牛顿迭代法超平方收敛。时，牛顿迭代法超平方收敛。 0)( xf0)( xf例例 3.5 试用牛顿迭代法求解试用牛顿迭代法求解 在区在区间间 (2,3) 内满足精度要求内满足精度要求 的根。的根。 3( )250f xxx810相应于该方程的牛顿迭代公式为相应于该方程的牛顿迭代公式为 2352231 kkkkkxxxxx取取 x0 = 2 ，计算结果见表，计算结果见表2-4。 解解0 2 1 2.1 0.12 2.094568121 -0.005431879 3 2.094551482 -0.000016639 4 2.094551482 01 kkkxxxk83410 xx

29、牛顿迭代法评述牛顿迭代法评述 优点：优点：收敛速度比较快收敛速度比较快 缺点缺点：(1) (1) 局部收敛局部收敛. （2 2）当）当 为为 重根时，牛重根时，牛顿迭代法仅仅线性收敛。顿迭代法仅仅线性收敛。 ( )0(2)f xm的的*x（3 3）由于涉及）由于涉及 的计算，计算量大的计算，计算量大. . 因此，因此，人们致力于研究牛顿迭代法的修改形式。人们致力于研究牛顿迭代法的修改形式。本章仅对非线性方程介绍一种较为有效的修改本章仅对非线性方程介绍一种较为有效的修改算法算法弦截法。弦截法。 ( )fx 3.4 3.4 割线法割线法( (弦截法弦截法) ) , 1 , 0,)()()()(10

30、111 kxxxxxfxfxfxxkkkkkkk割线法割线法 计算思想是：若已知计算思想是：若已知 x* 的两个近似值的两个近似值 xk 和和 xk-1，则，则以以 f (x) 在在 xk 与与 xk-1 之间的平均变化率之间的平均变化率(差商差商) 近似代替近似代替 ，据此把牛顿迭代法修改为，据此把牛顿迭代法修改为 11)()( kkkkxxxfxf)(kxf 几何意义几何意义是以过是以过 和和 两点两点做曲线做曲线 的弦线的弦线 l ： )(,kkxfxP )(,11 kkxfxQ)(xfy )()()()(11kkkkkkxxxxxfxfxfy 以以 l 与与 x 轴的交点轴的交点 作为

31、的新近似值作为的新近似值1 kxyo xkxy=f(x)PQ1 kx1 kxx 该定理说明割线法是超线性收敛的算法，也是该定理说明割线法是超线性收敛的算法，也是局部收敛的方法，其迭代初始值亦可用二分法提供局部收敛的方法，其迭代初始值亦可用二分法提供。 定理定理 3.63.6 设设 f (x) 在其零点在其零点 x* 的邻域的邻域 内二阶连续，且对内二阶连续，且对 ，则，则对对 ，相应的割线法是，相应的割线法是 阶收敛的。阶收敛的。 |xxx0)(, xfx 10,xx618. 1251 p 定理定理 3.63.6 设设 f (x) 在其零点在其零点 x* 的邻域的邻域 内二阶连续，且对内二阶连

32、续，且对 ，则，则对对 ，相应的割线法是，相应的割线法是 阶收敛的。阶收敛的。 |xxx0)(, xfx 10,xx618. 1251 p 例例 3.73.7 试用割线法求解试用割线法求解 在区间在区间(2,3)内满足精度要求内满足精度要求 的根。的根。 052)(3 xxxf810 相应于该方程的割线法公式为相应于该方程的割线法公式为 )()52()52(521131331 kkkkkkkkkkxxxxxxxxxx解解取取 计算，结果见表计算，结果见表3.5。 3,210 xx4.1 引言引言 4.2 Lagrange插值多项式插值多项式 4.3 Newton插值多项式插值多项式 4.4 分

33、段低次插值分段低次插值则称则称P(x)为为f (x)的的插值函数插值函数。这时，我们称。这时，我们称a,b为为插值插值区间区间， 称称 为为插值节（结）点插值节（结）点，称（，称（4-14-1）为）为插值条件插值条件，f (x)为为被插函数被插函数。求插值函数。求插值函数P(x)的方法称的方法称为为插值法插值法。 4.1 4.1 引言引言 定义定义 4.14.1 设设 y= f(x) 在区间在区间a,b上连续，在上连续，在a,b内内n+1个互不相同的点个互不相同的点 上取上取值值 。如果存在一性态较好的简单函数。如果存在一性态较好的简单函数P(x)，使，使得得 010,()nnxxx axxb

34、01,nyyy()(0,1,)(41)iiP xyin01,nxxx 从几何上看，插值法就是确定一个简单曲线从几何上看，插值法就是确定一个简单曲线为为y=P(x) ，使其通过给定的，使其通过给定的 n+1个点个点 ， 并用它近似已知曲线并用它近似已知曲线 y=f (x).(,),0,1,iixyin 图图2-12-1 特别地，当特别地，当P(x)为次数不超过为次数不超过n次的代数多项式时，次的代数多项式时，相应的插值法称为相应的插值法称为多项式插值多项式插值；当；当P(x)为三角多项式为三角多项式时，相应的插值法称为时，相应的插值法称为三角插值三角插值；当；当P(x)为分段解析为分段解析函数时

35、，相应的插值法称为函数时，相应的插值法称为分段插值分段插值。其中三角插值。其中三角插值主要用于处理周期函数。本章仅介绍最基本的多项式主要用于处理周期函数。本章仅介绍最基本的多项式插值插值。 定理定理 4.14.1 在在 n+1 个互异点个互异点 上满足插上满足插值条件值条件 (4-1) 的次数不超过的次数不超过n次的插值多项式次的插值多项式Pn(x) 存在且存在且惟一惟一。 01,nxxx4.2 Lagrange4.2 Lagrange插值多项式插值多项式 4.2.1 4.2.1 线性插值与二次插值线性插值与二次插值 设给定函数设给定函数 两点两点 ， 经过这两点的经过这两点的多项式插值就是直

36、线多项式插值就是直线( )yf x0011(,),(,)xyxy011010110( )xxxxL xyyxxxx 称给定称给定 为线性插值多项式。称为线性插值多项式。称为关于点为关于点 的线性插值基函数，其在节点处满足的线性插值基函数，其在节点处满足：1( )L x01,xx01010110( ),( )xxxxlxlxxxxx 1,()0,ijijl xij 4.2.1 4.2.1 线性插值与二次插值线性插值与二次插值 假定插值节点为假定插值节点为 ， ， ，要求二次插值多项式，要求二次插值多项式2x1x0 x),(2xL 几何上几何上 是通过三点是通过三点 的抛物线的抛物线. .)(2x

37、L),(),(),(221100yxyxyx).2, 1, 0()(2 jyxLjj 可以用基函数的方法求可以用基函数的方法求 的表达式，的表达式，)(2xL),(0 xl),(1xl)(2xl是二次函数，是二次函数，);2, 1(,0)(, 1)(000 jxlxlj);2,0(,0)(, 1)(111 jxlxlj).1 ,0(,0)(, 1)(222 jxlxlj 4.2.2 4.2.2 拉格朗日插值多项式拉格朗日插值多项式 1(),0,1,(44)0ijijijl xi jnij 0()naxxb解解 的零点为)(,110 xlxxxxiniinjijjixxxl0)()(中含有因式而

38、此因式已为而此因式已为n次多项式，故应有次多项式，故应有为待定系数injijjiiAxxAxl0)()(), 1 , 0()(nixli求的求的n+1个次数个次数 次的插值多项式次的插值多项式满足满足 n01()()niiiijj ijl xAxx 再由 01()inijj ijAxx 得得00 1()( )(, , )()njij iijjxxl xinxx 00045( )( )()nnnjni iiiij iijjxxLxy l xyxx 称为称为n次拉格朗日（次拉格朗日（LagrangeLagrange）插值基函数）插值基函数或称为或称为拉格朗日基本插值多项式拉格朗日基本插值多项式。(

39、 (据之，我们可构造据之，我们可构造多项式多项式 它称为它称为n次拉格朗日插值多项式。次拉格朗日插值多项式。 引进引进 n+1 次与次与n n次多项式函数为次多项式函数为10( )()(4.2.10)nnjjxxx 1( )( )/()inixxxx 0( )( )()niniiiixLxyx n次拉格朗日插值多项式可表示为次拉格朗日插值多项式可表示为误差估计定理误差估计定理 注注 （1 1）余项公式主要用于理论分析。实际使用时，代）余项公式主要用于理论分析。实际使用时，代 之以误差估计式之以误差估计式 11( )( )(1)!nnnMRxxn 4.2.2 4.2.2 插值余项与误差估计插值余

40、项与误差估计 定理定理4.2 设设f(x)的的n+1阶导数阶导数 在在a,b存在，存在，则对任何则对任何 ，插值余项满足，插值余项满足(1)1( )( )( )( )( ), , (1)!nnnnfRxf xLxxxa bn ( )( , ).xa b其其中中(1)( )nfx a,bx （2 2）插值节点的选取应尽量靠近插值点，以使）插值节点的选取应尽量靠近插值点，以使 尽可能小，以减小误差。尽可能小，以减小误差。 )(1xn(1)( )=(),( )0,knf xxknfx 若若那那么么 0( )( )0,nkkniiiRxxx l x 0( ),0,1, .nkkiiix l xxkn

41、0( )1.niil x 特别地，当特别地，当k=1时时例例4.14.1：已知函数：已知函数 x -1 0 1 y 1.25 0.75 1.25 2L ( )x求求3001122( )( )( )( )P xlx ylx ylx y 解解：1200102()()1( )(1)()()2xxxxlxx xxxxx 而而0211012()()( )(1)(1)()()xxxxlxxxxxxx 0122021()()1( )(1)()()2xxxxlxx xxxxx 2001122012( )() ( )() ( )() ( )1.25 ( )0.75 ( )1.25 ( )L xf x lxf x

42、 lxf x lxlxlxlx255(1)0.75(1)(1)(1)883142x xxxx xx 例例 4.2 给定函数表给定函数表试分别用线性插值和抛物插值求试分别用线性插值和抛物插值求ln 1.46的近似值并估计误差。的近似值并估计误差。 x1.21.31.41.51.61.7lnx0.1823220.2623640.3364720.4054650.4700040.530628解解作线性插值作线性插值 得得010110101)(xxxxyxxxxyxL 377868. 05 . 1ln4 . 15 . 14 . 146. 14 . 1ln5 . 14 . 15 . 146. 146. 1

43、ln 414 . 125 . 14 . 121012. 6)5 . 146. 1)(4 . 146. 1(! 251002. 05102. 01)(lnmax RxxMxx误差为误差为378402. 06 . 1ln)5 . 16 . 1)(4 . 16 . 1 ()5 . 146. 1)(4 . 146. 1 (5 . 1ln)6 . 15 . 1)(4 . 15 . 1 ()6 . 146. 1)(4 . 146. 1 (4 . 1ln)6 . 14 . 1)(5 . 14 . 1 ()6 . 146. 1)(5 . 146. 1 (46. 1ln 37843643.046.1ln 精精确

44、确值值为为7289.02 )(lnmax4 .135,14 .13 xxxxM52101 . 4)6 . 146. 1)(5 . 146. 1)(4 . 146. 1(! 37289. 0 R误误差差为为 作抛物插值作抛物插值 6 . 15 . 14 . 1210 xxx取取)()()()()()()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL 4.3 Newton4.3 Newton插值多项式插值多项式问题：利用插值基函数得到的拉格朗日插值多项式有何优问题：利用插值基函数得到的拉格朗日插值多项式有何优缺点？缺点？优点：结构紧凑，便于

45、理论分析，易于编程求解。优点：结构紧凑，便于理论分析，易于编程求解。缺点：当插值节点增减时全部插值基函数均要随之变化，缺点：当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化整个公式也将发生变化. .问题：如何改进？问题：如何改进？4.3 Newton4.3 Newton插值多项式插值多项式 4.3.1 4.3.1 均差的定义和性质均差的定义和性质定义定义：称 为函数 关于点 的一阶均差一阶均差. 100110()(),f xf xf xxxx )(xf01,xx120101220,f xxf xxf xxxxx 称为 关于点 的二阶均差二阶均差.)(xf012,xxx 一般地，

46、称11011010,nnnnnf xxxf xxxf xxxxx 为 的 阶均差阶均差n)(xf（均差也称为差商差商）.4.3 Newton4.3 Newton插值多项式插值多项式 4.3.1 4.3.1 均差的定义和性质均差的定义和性质利用如下均差表来计算均差：利用如下均差表来计算均差：0011012212012332312301234434234123401234()1st2nd3rd4th()(),(),(),(),kkxf xxf xxf xf xxxf xf x xf xx xxf xf xxf x xxf xx xxxf xf xxf xxxf x xxxf xx xxx 表21均

47、差均差均差均差（）（）（）（）解解 根据给定函数表造出均差表根据给定函数表造出均差表 给出给出 的如下函数表，的如下函数表，由此计算由此计算 关于点关于点0,2,4,80,2,4,8的三阶均差的三阶均差 . .( )f x( )f x例例9 9-39-39-3-310108 84 42 20 0kx)(kxf-2.875-2.875-18-18-39-394 40.9843750.9843755 512129 98 8-6.5-6.5-3-32 210100 0三阶均差三阶均差二阶均差二阶均差一阶均差一阶均差kx)(kxf0,2,4,8f均差的性质：均差的性质：时恒为零。次多项式，当时为当阶均

48、差函数次多项式，则其为若）（nkknnkxxxPknxPknn,)(210的任一排列），为排列顺序无关，即有由此知，均差与节点的kiiixxxfxxxfxxxfxxxfkiiikkikjijjiikk10,(,)124()()(,) 1 (1010001010这性质又称为均差关于自变量的对称性均差关于自变量的对称性。 根据均差定义，把根据均差定义，把 看成看成 上一点，上一点，x , a b000 ,( )()(),f x xf xf xxx010001011012212 , ,(), ,(),f xxxxf xxf x xxf x xf x xxxxfxxxxx010101 , ,().nn

49、nnf x xxf xxxf x xxxxx 可得可得4.3 Newton4.3 Newton插值多项式插值多项式 4.3.2 Newton4.3.2 Newton均差插值多项式均差插值多项式只要把后一式代入前一式，就得到只要把后一式代入前一式，就得到 0010( )(),()f xf xf xxxx01201,()()f xx xxxxx( )( ),nnNxRx0010( )(),()nNxf xf xxxx01201,()()f xxxxxxx其中其中 0101,()()nnf xxxxxxx 01 ,( )nnf x xxx 0101,()(),nnf xxxxxxx 4.3.2 Ne

50、wton Newton均差插值多项式均差插值多项式01( )( )( ) ,( ),nnnnRxf xNxf x xxx （*） 是同是同LagrangeLagrange余项定义的余项定义的. )(1xn 显然，由确定的多项式显然，由确定的多项式 满足插值条件满足插值条件，( )nNx且次数不超过且次数不超过n n 的多项式，其所给出形式的系数为的多项式，其所给出形式的系数为00 1,(, , ).kkaf xxkn称称 为为牛顿（牛顿（NewtonNewton）均差插值多项式）均差插值多项式. ( )nNx 系数系数 就是均差表就是均差表4-14-1中主对角线上的各阶均差，中主对角线上的各阶

51、均差，它比拉格朗日插值计算量省，且便于程序设计它比拉格朗日插值计算量省，且便于程序设计.ka 4.3.2 Newton Newton均差插值多项式均差插值多项式例例4.3：已知：已知x0.400.550.650.800.901.05y0.410750.578150.696150.888111.026521.25386。计计算算试试利利用用。计计算算求求)596. 0()()2()596. 0(),()1(25fxNfxN0 0.40 0.410751 0.55 0.57815 1.11602 0.65 0.69615 1.1860 0.28003 0.80 0.88811 1.2757 0.3

52、583 0.1974 0.90 1.02652 1.3848 0.4336 0.214 0.0345 1.05 1.25386 1.5156 0.5260 0.231 0.034 0 k xk yk 一阶一阶 二阶二阶 三阶三阶 四阶四阶 五阶五阶 )80. 0)(65. 0)(55. 0)(40. 0(034. 0)65. 0)(55. 0)(40. 0(197. 0)55. 0)(40. 0(2800. 0)40. 0(1160. 141075. 0)(5 xxxxxxxxxxxN63192.0)596.0()596.0(5 Nf6320. 0)596. 0()55. 0)(40. 0(2

53、800. 0)40. 0(1160. 141075. 0)(22 NxxxxN解解: (1)(2)与与0.596最接近的三个节点最接近的三个节点65. 055. 040. 0210 xxx例例 4.4 给定表格函数给定表格函数 x12345f(x)0.50.1751.31-1.49510.36 （1）试用二次牛顿均差插值法求）试用二次牛顿均差插值法求 f (2.8) 的近似值；的近似值； （2）设）设 f (x)=-1.166 已知，试用（已知，试用（1）中构造的插值多项）中构造的插值多项 式求式求 x 的近似值。的近似值。1728. 0)2 . 1()2 . 0(8 . 09 . 0)48

54、. 2)(38 . 2)(28 . 2(1 , 4 , 3 , 2)8 . 2()8 . 2(3982. 1)38 . 2)(28 . 2(97. 1)28 . 2(135. 1175. 0)8 . 2(22 fNfN解解 (1) 选取节点选取节点x=2,3,4)(,)(,)()(1021001002xxxxxxxfxxxxfxfxN k xkf (xk)一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差020.1751.135-1.97-0.9131.31-2.0805-1.0724-1.495-0.665310.5929. 342647. 1929. 30749.12985.1097. 11

55、66. 1)3(297. 12135. 1175. 0)2(212 xxxxxxxx故故所所求求解解为为，舍舍去去），（超超出出区区间间，解解得得整整理理得得）（）（由由解 由于是由于是3 3次函数次函数, ,所以取靠近所以取靠近0.450.45的的4 4个点产生均差表个点产生均差表. . 例4.5 根据给定数据根据给定数据( (见课本第见课本第6565页的表页的表) )，用，用3 3次牛顿插值次牛顿插值多项式计算多项式计算 f(0.45)(0.45)的近似值的近似值, ,并估计近似误差并估计近似误差. . 4.3.2 Newton4.3.2 Newton均差插值多项式均差插值多项式 一阶一阶

56、 二阶二阶 三阶三阶 0.2 0.587785 0.4 0.951057 1.816360 0.6 0.951057 0.00000 -4.540900 0.8 0.587785 - 1.816360 -4.540900 0.00000()iixf x3(0.4( )0.5( 0.540900)(0.6)(0.000001.8871)785(0.2)6360Nxxxx 于是于是 4(0.45)(0.45)0.985114fN 按牛顿插值公式，将数据代入得按牛顿插值公式，将数据代入得为了估计误差，增加一个靠近为了估计误差，增加一个靠近0.450.45的插值点的插值点0.00.0，在均差，在均差表

57、后加一行（均差与节点排列无关）表后加一行（均差与节点排列无关）. . 一阶一阶 二阶二阶 三阶三阶 四阶四阶 0.2 0.587785 0.4 0.951057 1.816360 0.6 0.951057 0.00000 -4.540900 0.8 0.587785 - 1.816360 -4.540900 0.00000 0.0 0.000000 0.734733 -4.251817 -0.722708 3.613540()iixf x因此，截断误差因此，截断误差 3044(0.45),(0.4596)0.0024.Rf xx 事实上，给定的函数是事实上，给定的函数是 因此可计算实际误差因此

58、可计算实际误差 3sin0.45(0.45)0.002574N 由此可见，误差估计是相当有效的。由此可见，误差估计是相当有效的。sinx 5.1 5.1 数值微分数值微分5.2 5.2 数值积分数值积分0002()( )( )()( )limlim()()limhhhf xhf xf xf xhfxhhf xhf xhh 微积分中，关于导数的定义如下：微积分中，关于导数的定义如下：自然，而又简单的方法就是，自然，而又简单的方法就是，取极限的近似值，即差商取极限的近似值，即差商.5.1 5.1 数值微分数值微分5.1.1 5.1.1 差商型求导公式差商型求导公式000()()()f xhf xf

59、xh 由由Taylor展开展开2000002()()()( ),!hf xhf xhfxfxxh因此，有误差因此，有误差0002()()( )()( )( )!f xhf xhR xfxfO hh 5.1 5.1 数值微分数值微分5.1.1 5.1.1 差商型求导公式差商型求导公式000()()()f xf xhfxh 由由Taylor展开展开2000002()()()( ),!hf xhf xhfxfxxh因此，有误差因此，有误差0002()()( )()( )( )!f xf xhhR xfxfO hh 5.1 5.1 数值微分数值微分5.1.1 5.1.1 差商型求导公式差商型求导公式0

60、002()()()f xhf xhfxh 由由Taylor展开展开23000010102300002020()()()()(),2!3!()()()()(),2!3!hhf xhf xhfxfxfxxhhhf xhf xhfxfxfxhx因此，有误差因此，有误差00022212()()( )()2 ()()( )()126f xhf xhR xfxhhhfffO h5.1 5.1 数值微分数值微分5.1.1 5.1.1 差商型求导公式差商型求导公式由误差表达式，由误差表达式，h h越小，误差越小，但同时舍入误差增大，越小，误差越小，但同时舍入误差增大，所以，有个所以，有个最佳步长最佳步长我们可