数值分析第1,2章

1、1数数 值值 分分 析析Numerical Analysis主讲主讲 张学莹张学莹2&教材教材 (Text Book) 李庆扬、王能超、易大义，数值分析（李庆扬、王能超、易大义，数值分析（5 5 版）版）, ,北京：清华大学出版社北京：清华大学出版社, ,2008& 参考书目参考书目 (Reference) 易大义，陈道琦，数值分析引论易大义，陈道琦，数值分析引论, ,浙江大学出版社浙江大学出版社, ,2000 蔡大用，白峰彬，高等数值分析，清华大学大学出版社，蔡大用，白峰彬，高等数值分析，清华大学大学出版社，1997 J.Stoer & R. Bulirsch，Int

2、roduction to Numerical Analysis (Second Edition)，New York: Springer, 1993 其他（略）其他（略）3课程简介课程简介 数值计算方法是计算数学的一个分支数值计算方法是计算数学的一个分支, 又称数值又称数值分析或计算方法分析或计算方法, 它是研究用计算机求解各种数学它是研究用计算机求解各种数学问题的数值方法及其理论的一门学科问题的数值方法及其理论的一门学科, 是程序设计是程序设计和对数值结果进行分析的依据和基础。和对数值结果进行分析的依据和基础。应用计算机解决科学技术和工程问题的步骤：应用计算机解决科学技术和工程问题的步骤： (

3、1) 提出实际问题提出实际问题 (2) 建立数学模型建立数学模型 (3) 选用数值计算方法选用数值计算方法 (4) 编程上机计算得出数据结果。编程上机计算得出数据结果。4 提问：数值分析是做什么用的？提问：数值分析是做什么用的？5 由于计算机和科学计算的发展，求解各种数学由于计算机和科学计算的发展，求解各种数学问题的数值方法也愈来愈应用于科学计算的各个领问题的数值方法也愈来愈应用于科学计算的各个领域，新的交叉学科不断涌现，如计算力学、计算物域，新的交叉学科不断涌现，如计算力学、计算物理、计算生物学、计算经济学等，统称为科学计算。理、计算生物学、计算经济学等，统称为科学计算。 科学计算、理论研究

4、、试验研究科学计算、理论研究、试验研究6计算数学研究适用于计算机编程的算法计算数学研究适用于计算机编程的算法 基础性、应用性、边缘性基础性、应用性、边缘性面向计算机的算法：串行、并行面向计算机的算法：串行、并行好的算法的标准：可靠的理论性、好的算法的标准：可靠的理论性、计算复杂性好（时间复杂性、空间复杂性）计算复杂性好（时间复杂性、空间复杂性） 数值分析的特点：数值分析的特点：面向计算机、有可靠的理论分析、好的计算复杂性、面向计算机、有可靠的理论分析、好的计算复杂性、数值试验数值试验 数学软件数学软件 软件包软件包 LAPACK（EISPACK,LINPACK) 、 IMSL 、NGA(100

5、0多个）、多个）、 MATLAB7一、误差的来源一、误差的来源1. 模型误差模型误差:在建立数学模型过程中在建立数学模型过程中, 不可能将所有因素均考虑不可能将所有因素均考虑, 必必然要进行必要的简化然要进行必要的简化, 这就带来了与实际问题的误差。这就带来了与实际问题的误差。2. 观测误差观测误差: 测量已知参数时测量已知参数时, 数据带来的误差。数据带来的误差。3. 截断误差截断误差: 在设计算法时在设计算法时,近似处理带来的误差。近似处理带来的误差。第二节第二节 数值计算的误差数值计算的误差8函数函数 用泰勒多项式用泰勒多项式)(xf2( )11( )(0)(0)(0)(0)2!nnnP

6、 xffxfxfxn近似代替时，有误差近似代替时，有误差(1)11( )( )( )( )(1)!nnnnRxf xP xfxn 其中其中 在在 与与 之间。这种误差就是截断误差。之间。这种误差就是截断误差。 0 x例如：例如：94. 舍入误差舍入误差: 计算机的字长是有限的计算机的字长是有限的, 每一步运算每一步运算 均需四舍五入均需四舍五入, 由此产出的误差。由此产出的误差。例如：例如：用用3.14159近似代替近似代替 , 产生的误差产生的误差 0000026. 014159. 3 R就是舍入误差。就是舍入误差。10二、误差的基本概念二、误差的基本概念 1. 1. 误差和误差限误差和误差

7、限 设设 是准确值是准确值 x 的一个近似值的一个近似值, ,称称 为近似值为近似值 的的绝对误差绝对误差, , 简称误差简称误差. . 又简记又简记 . . xxxxe )( x)( xe e误差是无法计算的误差是无法计算的 ( (因为准确值因为准确值 x 不知道不知道), ), 但可以但可以估计出它的一个上界。即估计出它的一个上界。即 , ,称称 是近似值是近似值 的的绝对误差限绝对误差限, , 简称误差限简称误差限. .)( xxx )( x x误差是有量纲的，可正可负。误差是有量纲的，可正可负。112. 相对误差和相对误差限相对误差和相对误差限()()re xxxexxx 称称为近似值

8、为近似值 的的相对误差相对误差。简记为。简记为 。 x re实际计算中实际计算中, , 由于准确值由于准确值 x 总是未知的总是未知的, , 且由于且由于()()e xe xxx ()()e xxxxx 2( ()()e xx xe x 2()1()rrexex 12()()re xxxexxx 相对误差是无量纲的相对误差是无量纲的, , 也可正可负也可正可负, , 它的绝对值的上它的绝对值的上界称为该近似值的界称为该近似值的相对误差限相对误差限, , 记作记作)( xr 简记为简记为 r 是是 的平方项级的平方项级, 故当故当 较小时较小时, 常取常取)( xer)( xer13三、有效数字

9、三、有效数字 如果近似值如果近似值x* 的误差限是其某一位的半个单位的误差限是其某一位的半个单位, 该位到该位到x*的第一位非零数字共有的第一位非零数字共有n 位位, 我们称我们称x* 有有n 位位有效数字有效数字。定义：定义：*nx 位位误差限不超过该位的半个单位误差限不超过该位的半个单位自左向右看自左向右看, 第一位非零数字第一位非零数字14*0.0020.005xx 所以所以 x* = 3.14 作为作为的近似值的近似值,有有3位有效数字；位有效数字；而取而取x*=3.1416 时时,*0.0000080.00005xx 所以所以 x* = 3.1416 作为作为 的近似值的近似值,有有

10、5位有效数字。位有效数字。例例 = 3.1415926535, 取取 x* = 3.14 时，时，15120.10mnkxa aaa 下面给出有效数字的另一等价定义下面给出有效数字的另一等价定义 用用 表示表示x 的近似值，并将的近似值，并将 表示成表示成 x x若其误差限若其误差限nmxx 1021,则称则称 具有具有 n 位位有效有效数字数字, , 这里这里 m 是整数是整数, a1, a2 , ak 为为 09 中的一个数字中的一个数字, 且且a1 0. x定义：定义：自左向右看自左向右看, 第一位非零数字第一位非零数字16例例 = 3.1415926535 , 取取 = 3.14时，时

11、， x 21021005.0002.0 xx即即 m- n = - 2, m=1, n = 3, 所以所以 = 3.14 作为作为 近似值近似值时时, , 就有就有3 位有效数字。位有效数字。 x 17四、四、 相对误差限与有效数字的关系相对误差限与有效数字的关系证明证明mnaaax10.021 故故111110)1(|10 mmaxa111021)( nrax 定理定理1 1有有n 位有效数字，位有效数字，。则其相对误差限为则其相对误差限为mnaaax10.021 01 a设近似值设近似值11111021101050 nmnmraa.xxx)(x 18nm 102111111(1)10102

12、(1)mnaa 则它至少有则它至少有n 位有效数字。位有效数字。定理定理2设近似值设近似值mnaaax10.021 的相对误差限的相对误差限,10)1(2111 na不大于不大于故故 至少有至少有n 位有效数字。位有效数字。 x 已知已知证明证明111102(1)na *xr)(*xxxxr19例例解解由于由于,5204 所以所以,41 a由定理由定理1有有,%1 . 0102111 na即即,81104 n得得4 n要使要使 的近似值的相对误差限小于的近似值的相对误差限小于0.1% , 要取几位有效数字。要取几位有效数字。20故只要对故只要对 的近似数取的近似数取4 位有效数字位有效数字,其

13、相对误差其相对误差20472. 420 因此因此,可取可取就可小于就可小于0.1%,20五、数值运算的误差估计五、数值运算的误差估计（一一）、算术运算的误差算术运算的误差所以和或差的所以和或差的误差限误差限是误差限之和。是误差限之和。以上的结论适用于任意多个近似数的和或差。以上的结论适用于任意多个近似数的和或差。同理可得：乘、除运算的误差同理可得：乘、除运算的误差, ,以两数为例写出以两数为例写出112212222|()|(),0()xxxxxxxx *1*2*2*1*2*1xxxxxx1.21它是对数函数的微分。它是对数函数的微分。设设 u = xy , 则则 lnu=lnx+lny , 因

14、而因而dlnu = dlnx + dlny 这就是说这就是说, , 乘积的相对误差乘积的相对误差是各乘数的相对误差之和是各乘数的相对误差之和, ,相对误差限是各乘数的相对误差限之和。相对误差限是各乘数的相对误差限之和。2. 的的相对误差相对误差是是 xd()dlnrxxxexxxx )y()x()u()y(e)x(e)u(errrrrr 22即商的相对误差是被即商的相对误差是被除数与除数的相对误差除数与除数的相对误差之差之差, , 但但相对误差限是各乘数的相对误差限之和相对误差限是各乘数的相对误差限之和. .由此可得由此可得: : 任意多次连乘、连除所得结果的相对误差限等于各乘任意多次连乘、连

15、除所得结果的相对误差限等于各乘数和除数的相对误差限之和。数和除数的相对误差限之和。同样同样, , 若若 u = x/y, 则则 lnu = lnx lny, 因此因此dlnu = dlnx dlny 即即)()()()()()( yxuyexeuerrrrrr 23例例1解解lnlnlnlnlnuxyz 所以所以dlndlndlndlnlnuxyzd 从而得到从而得到dlndlndlnlndlnxxydz u 的相对误差限等于乘数的相对误差限等于乘数x、y和除数和除数z、的相对误差的相对误差限之和限之和。xyuz 设设求求 u 的相对误差限。的相对误差限。因因24（二）（二） 函数运算误差函数

16、运算误差设设 f (x)在在(a,b)内连续可微内连续可微, , x 的近似值为的近似值为 , f (x)的近的近似值为似值为 , 其误差为其误差为 , 误差限为误差限为 ()f x x)( xf)( xfe ()d( )( )d() ()e f xf xfxxfx e x 取绝对值得取绝对值得)()()()()()()( xxfxxfxexfxfe 其中其中 为近似数为近似数 的误差限的误差限。()x x25可得出一元函数运算的误差限和相对误差限分别为：可得出一元函数运算的误差限和相对误差限分别为：)()()()()()()( xxfxfxxfxfxfr )()()(| )(|)( xxfx

17、xfxf 26对多元函数对多元函数),(21nxxxfy 自变量的近似值为自变量的近似值为yxxxn,21 的近似值为的近似值为12(,),nyf xxx 函数值函数值 的运算误差为的运算误差为 y1212121211() (,)(,)(,)(,)()()nnnnnniiiiiie ye f xxxdf xxxf xxxf xxxe xe xxx 27记记则上式简记为则上式简记为,),(21 iinxfxxxxf)()()(11 iniiiniixexfxexfye28相对误差限相对误差限于是误差限于是误差限)()()(11 iniiiniixexfxexfye niiniixfxfy11)(

18、 |)(|)()(11yxxfyxxfyniiniir29 病态问题与条件数病态问题与条件数第三节第三节 误误 差的定性分析与避免误差的危害差的定性分析与避免误差的危害30设计算法时应注意的原则设计算法时应注意的原则一、简化计算步骤一、简化计算步骤, 减少运算次数减少运算次数 计算多项式的值计算多项式的值: 0()nknkkPxa x 每项每项 ak xk 有有k 次乘法运算次乘法运算, 因此计算因此计算 Pn (x) 共需共需 11 22n nn 次乘法和次乘法和n 次加法运算。次加法运算。如将如将 Pn (x) 写成写成: 1210nnnnPxa xaxaxaxa 例例131用递推算法用递

19、推算法: 01, , 1,2, .nkkn kuauuxakn 最终最终 Pn (x)=un 共需共需n 次乘法和次乘法和n 次加法运算。次加法运算。 一般地要注意一般地要注意: 能在循环外计算能在循环外计算, 就不要放在循环就不要放在循环内计算。内计算。 1210nnnnPxa xaxaxaxa 32二、二、 注意避免两个相近数的相减注意避免两个相近数的相减如用四位有效数字计算如用四位有效数字计算: 例例217013 13.04 130.04 结果只有一位有效数字；结果只有一位有效数字；两个相近的数相减两个相近的数相减, 有效数字会大大损失。有效数字会大大损失。170130.0384048

20、如改为：如改为：11170130.0384013.041317013 有四位有效数字有四位有效数字, 新算法避免了两个相近数的相减。新算法避免了两个相近数的相减。33三、防止大数三、防止大数 “吃掉吃掉” 小数小数例例3 解解 用五位十进制计算机进行计算用五位十进制计算机进行计算:0.1被大数被大数“吃掉吃掉”了了,从而从而有有10001524920.152492i 555524920.10.52492 100.000001 100.52492 1010001524920.1i 计算计算 34如改为如改为 0.1 就没有被吃掉。就没有被吃掉。 这也是构造算法时要注意的问题这也是构造算法时要注意

21、的问题, 避免重要的参数避免重要的参数被吃掉。被吃掉。100010.15249210052492i 10001524920.1i 35四、避免除数的绝对值远小于被除数的绝对值四、避免除数的绝对值远小于被除数的绝对值当当| x | y | 时时, 舍入误差会扩大。舍入误差会扩大。2()()()xyyxxyy 因为因为36例例4 7311214100.510151010 xxxx 很小的数作除数有时还会造成计算机的溢出而停机。很小的数作除数有时还会造成计算机的溢出而停机。30.510 的舍入误差均为的舍入误差均为, 而而舍入误差为舍入误差为:,则则710 xy2()()()xyyxxyy yx ,

22、37五、使用数值稳定的算法五、使用数值稳定的算法用分部积分公式得递推用分部积分公式得递推公式公式:例例5110,0,1,2,nxnIx edxn In=1- -nIn-1 在运算过程中在运算过程中,舍入误差能控制在某个范围内的算法舍入误差能控制在某个范围内的算法称为称为数值稳定的算法数值稳定的算法,否则就称为否则就称为不稳定的算法不稳定的算法.用四位有效数字计算用四位有效数字计算:近似值近似值 的递推公式的递推公式: nI,11 nnnII误差误差 的递推公式的递推公式:)( nIe, )()(1 nnIneIe 0110106321. 01IedxeIx38于是于是I7* , I8* 与精确

23、值已经面目全非。与精确值已经面目全非。n精确值精确值 In 近似值近似值In*n精确值精确值 In 近似值近似值In*0 1 2 3 40.632120.367870.264240.207270.170890.6321 0.3678 0.2642 0.2074 0.17045 6 7 8 90.145530.126800.112380.100930.091610.1408 0.1120 0.2180 -0.7280 7.5520算法一算法一 In =1- -nIn-1 ,100*10.6321IeI 代入得下表代入得下表 110,0,1,2,nxnIx edxn 39由于计算由于计算I0有误差

24、有误差 不计中间再产生的舍入误差不计中间再产生的舍入误差 |e(In* )|= n! |e(I0* ) | 到到 I8 时时 |e(I8* )|= 8! = 40320 误差扩大了误差扩大了4万倍万倍, 因而该算法是不稳定的。因而该算法是不稳定的。 40105 . 0)*( Ie e(In* ) = - - n e( In- -1* ) 100*10.6321IeI 分析：分析： In=1- -nIn-1 , 40可以估计出可以估计出 故故 70.04600.1250I80.04090.1111I11011neInn 110,0,1,2,nxnIx edxn 算法二算法二 如果递推式改为如果递

25、推式改为 In-1 =(1- -In )/n 则则 In- -1* =(1- - In* )/n 误差误差 e (In- -1* )= - - e (In* )/n 41若计算若计算 I9 有误差有误差 , 由由e (In- -1* )= - - e (In* )/n ，其传播，其传播 到到 I0所引起的误差仅为所引起的误差仅为 故该算法是稳定的故该算法是稳定的。 119!362880 由由 I9* = 0.1000, In 1* =(1 In* ) /n，列表如下列表如下42 设设 y= f(x) 是区间是区间a , b 上的一个实函数上的一个实函数, , xi ( i=0, 1, . ,n

26、)是是a,b上上n+1个互异实数个互异实数, ,已知已知 y=f(x) 在在 xi 的值的值 yi=f(xi) (i=0,1,.,n), , 求次数不超过求次数不超过n n的多的多项式项式Pn(x)使其满足使其满足Pn(xi)=yi (i=0,1, ., n) (2-1)这就是插值问题这就是插值问题. .第第2 2章章 插值法插值法第一节第一节 引言引言n一、一、 插值问题插值问题43其中其中Pn(x) 称为称为 f(x) 的插值多项式的插值多项式, , f(x) 称为称为被插函被插函数数, , xi(i=0,1, .,n)称为称为插值节点插值节点, , (xi, yi) (i=0,1, ,n

27、) 称为称为插值点插值点, , a,b 称为称为插值区间插值区间, , 式式( (2-1) )称为称为插值插值条件条件。 从从几何意义几何意义来看来看, ,上上述问题就是要求一条多述问题就是要求一条多项式曲线项式曲线 y=Pn(x), , 使使它通过已知的它通过已知的n n+1+1个点个点(xi,yi) (i=0,1, ,n), ,并用并用Pn(x)近似表示近似表示f(x). .44二、插值多项式的存在性和唯一性二、插值多项式的存在性和唯一性定理定理1 1 设节点设节点xi (i=0,1, ,n)互异互异, 则则满足插值条件满足插值条件Pn(xi)=yi 的次数不超过的次数不超过n的多项式存在

28、且唯一的多项式存在且唯一. .证证 设所求的插值多项式为设所求的插值多项式为 Pn(x)=a0+a1x+a2x2+.+anxn (2-2)则由插值条件式则由插值条件式Pn(xi)=yi (i=0,1, ., n) 可得关于系数可得关于系数a0 ,a1 , ,an的线性代数方程组的线性代数方程组45 nnnnnnnnnyxaxaayxaxaayxaxaa101111000010此方程组有此方程组有n n+1+1个方程个方程, , n n+1+1个未知数个未知数, , 其系数行列式其系数行列式是范德蒙行列式，即：是范德蒙行列式，即：（2-3） ijijnnnnnnxxxxxxxxxxx)(1112

29、1211020046 ijijnnnnnnxxxxxxxxxxx)(111212110200由于插值节点由于插值节点 xi 互不相同互不相同, , 所有因子所有因子 xj-xi 0, 所以所以上上述行列式不等于零述行列式不等于零, ,故由克莱姆法则知方程组故由克莱姆法则知方程组 (2-3) 的的解存在唯一解存在唯一. . 即满足条件式即满足条件式 (2-1)的次数不超过的次数不超过n的多的多项式项式(2-2) 存在且唯一。证毕。存在且唯一。证毕。 47第二节第二节 拉格朗日插值拉格朗日插值一、基函数一、基函数 0,()(0,1, )1,ijjil xjnji 故可设故可设)()()()(110

30、niiixxxxxxxxAxl 考虑下面最简单考虑下面最简单 最基本的插值问题。求最基本的插值问题。求n 次多项次多项式式 l i(x) (i=0,1, , n)，使其满足条件，使其满足条件48)()()()(110niiixxxxxxxxAxl 其中其中A A为常数为常数, , 由由li (xi)=1可得可得)()()(1110niiiiiixxxxxxxxA 490110110()()()()( )()()()()()(0,1, )()iiniiiiiiinnjjijj ixxxxxxxxl xxxxxxxxxxxinxx 称之为称之为拉格朗日基函数拉格朗日基函数。50 n=1时的一次基函

31、数为时的一次基函数为: : 01010110( ),( ).xxxxlxlxxxxx 0 x1xy 1 O x)(0 xl0 x1x)(1xl y Ox51021201010210120122021()()()()( ),( ),()()()()()()( ).()()xxxxxxxxlxlxxxxxxxxxxxxxlxxxxx n=2时的二次基函数为时的二次基函数为 : 520110110()()()()( )()()()()()(0,1, )()iiniiiiiiinnjjijj ixxxxxxxxl xxxxxxxxxxxinxx 0( )( )nni iiLxy l x 利用利用拉格朗

32、日基函数式拉格朗日基函数式l i(x), , 构造多项式构造多项式二、拉格朗日插值多项式二、拉格朗日插值多项式设节点设节点xi (i=0,1, ,n)互异互异, 插值条件插值条件Ln(xi)=yi53 特别地特别地, , 当当 n =1时又叫线性插值时又叫线性插值, ,其几何意义为其几何意义为过两点的直线过两点的直线. . 当当n =2时又叫抛物插值时又叫抛物插值, , 其几何意其几何意义为过三点的抛物线义为过三点的抛物线. .可知其满足可知其满足()(0,1, )njjLxyjn ,称为拉格朗日称为拉格朗日)()(xLxPnn 插值多项式插值多项式, , 由插值多项式的唯一性，得由插值多项式

33、的唯一性，得54551)(0 niixl 值得注意的是值得注意的是, , 插值基函数插值基函数l i(x) (i=0,1, ,n)仅由插值仅由插值节点节点xi (i=0,1, ,n)确定确定, ,与被插函数与被插函数 f(x)无关无关. .还应注意还应注意, ,对于插值节点对于插值节点, ,只要求它们互异只要求它们互异, ,与大小次序与大小次序无关。无关。 以以 xi (i=0,1,n)为插值节点为插值节点, , 函数函数 f(x) 1作插值作插值多项式多项式, , 则由插值多项式的唯一性立即得到基函数的则由插值多项式的唯一性立即得到基函数的一个性质一个性质56019141( )(9), (

34、)(4)495945xxlxxlxx 所以所以1137(7)2.65L 01,4,9,yx xx 7 例例1 1 已知已知 用线性插值求用线性插值求 近近 似值。似值。012,3,yy 基函数分别为基函数分别为:解解10 01 111( )( )( )2(9)3(4)55Lxy lxy lxxx 插值多项式为插值多项式为23(9)(4)55xx 1(6)5x 57)4)(3)(1(401)41)(31)(11()4)(3)(1()(0 xxxxxxxl)4)(3)(1(121)41)(31)(11()4)(3)(1()(1 xxxxxxxl)4)(1)(1(81)43)(13)(13()4)(

35、1)(1()(2 xxxxxxxl)3)(1)(1(151)34)(14)(14()3)(1)(1()(3 xxxxxxxl)3, 4(),6, 3(),0 , 1(),2, 1( 例例2 求过点求过点 的三次插值多项式。的三次插值多项式。4, 3, 1, 13210 xxxx解解 以以为节点的基函数为节点的基函数分别为分别为: :58)()()()()(332211003xlyxlyxlyxlyxL )3)(1)(1(1513)4)(1)(1(81)6()4)(3)(1(1210)4)(3)(1(401)2( xxxxxxxxxxxx)3)(1)(1(51)4)(1)(1(43)4)(3)(

36、1(201 xxxxxxxxx3423 xx59三、插值余项三、插值余项 截断误差截断误差Rn(x)=f (x) -Ln(x)也称为插值多项式的余也称为插值多项式的余项。以下为拉格朗日余项定理。项。以下为拉格朗日余项定理。 定理定理1 设设f (x)在区间在区间a ,b上存在上存在n+1 阶导数阶导数, xi a, b (i=0,1, , n) 为为n+1个互异节点个互异节点, 则对任何则对任何x a ,b, , 有有(1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn ( , )a b 且与且与x 有关有关) )()(n0i1inxxx 其中其中60证证 由插值条件

37、和由插值条件和 n+1(x) 的定义的定义, 当当x=xk 时时, 式子显然式子显然成立成立, 且有且有 n+1(xk)=0 ( k=0,1,n ), 这表明这表明x0 , x1, , xn 都是函数都是函数 n+1(x) 的零点的零点, 从而从而1( )( )( )( )( )nntf tL tK xt (1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn 1( )( )( )( )( )nnnRxf xLxK xx 其中其中K(x)是待定函数是待定函数。 对于任意固定的对于任意固定的x a,b, x xk ,构造自变量构造自变量t 的辅助的辅助函数函数611( )

38、( )( )( )( )nntf tL tK xt 由式由式 n+1(xk)=0 和式和式 Ln(xk)=yk( k=0,1,n ), ,以及以及1( )( )( )( )( )nnnRxf xLxK xx 可知：可知：x0 , x1, , xn和和x是是 (t) 在区间在区间a,b上的上的n+2个互个互异零点异零点, 因此根据罗尔因此根据罗尔(Rolle)定理定理, 至少存在一点至少存在一点 = (x) (a,b), ,使使 (1)( )0n (1)( )( )(1)!nfK xn 即即(1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn 所以所以62在估计误差时下

39、列不等式很有用。在估计误差时下列不等式很有用。),(, )()!1()(01baxxxnMxRniinn niinnnxxnfxLxfxR0)1()()!1()()()()( ),(,)(max)!1()(01baxxxnMxRniibxann 或或 xfMnbxan)1(1max 其中其中6315. 1425. 005. 02 xx,1)(xxf ，节节点点4, 5 . 2, 2210 xxx)(xf求求的抛物插值多项式的抛物插值多项式, ,且计算且计算f (3)的近似值并估计误差的近似值并估计误差。例例3 设设25. 0)4(, 4 . 0)5 . 2(, 5 . 0)2(210 fyfy

40、fy解解 )45 . 2)(25 . 2()4)(2(4 . 0)42)(5 . 22()4)(5 . 2(5 . 0)(2 xxxxxL)5 . 24)(24()5 . 2)(2(25. 0 xx插值为多项式插值为多项式64于是于是 325. 0)3(2 xLf因为因为 83)2()(max,64,24 fxfxxfx可得可得03125. 0)43)(5 . 23)(23(8361)3()3()3(22 LfR65例例4 已知已知 用线性插值计算用线性插值计算sin0.33333487. 034. 0sin,314567. 032. 0sin 解解 (1) 用线性插值用线性插值324027.

41、 0)33487. 0314567. 0(2132. 034. 032. 033. 0333487. 034. 032. 034. 033. 0314567. 0)33. 0(33. 0sin1 L66第三节第三节 均差与牛顿插值公式均差与牛顿插值公式一、差商及其基本性质一、差商及其基本性质定义定义1 称称101010)()(,xxxfxfxxf 为为 f (x)在在x0、x1点的一阶差商点的一阶差商.一阶差商的差商一阶差商的差商202110210,xxxxfxxfxxxf 称为函数称为函数f (x)在在x0、x1 、x2 点的二阶差商点的二阶差商.67一般地，一般地，n-1阶差商的差商阶差商

42、的差商nnnnnnxxxxxfxxxfxxxf 01112010, 称为称为f (x)在在x0 , x1 , , xn点的点的 n 阶差商。阶差商。差商的计算步骤与结果可列成差商表，如下差商的计算步骤与结果可列成差商表，如下68xk函数值函数值一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商. x0 x1 x2 x3 .f (x0) f (x1) f (x2) f (x3) . f x0 , x1 f x1 , x2 f x2 , x3 . f x0, x1, x2 f x1, x2, x3 . f x0, x1, x2 , x3 .表表5-169这一性质可以用数学归纳法证明，它表明差商与节这

43、一性质可以用数学归纳法证明，它表明差商与节点的排列次序无关，即点的排列次序无关，即 fx0 , x1 , x2 , ., xn= fx1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 nknkkkkkkknxxxxxxxxxfxxxf011010)()()()(,性质性质1 差商可以表示为函数值的线性组合，即差商可以表示为函数值的线性组合，即称之为差商的对称性称之为差商的对称性。70性质性质2 若若f(x)在在a,b上存在上存在n阶导数阶导数, 且节点且节点x0 , x1 , xn a,b ,则至少存在一点则至少存在一点 a, b 满足下式满足下式!)(

44、,)(10nfxxxfnn 例例1 f(x)=- -6x8+7x5- -10,求求f1,2, ,9及及f1,2, ,10. 解解 f (8)(x)=- -68 !, f 1,2, ,9=-6, f (9)(x)=0, f 1,2, ,10=0.71例例2 已知已知1215207431ix)(ixf计算三阶差商计算三阶差商 . 7 , 4 , 3 , 1 f72解解 做差商表做差商表7三三阶阶差差商商二二阶阶差差商商01425. 1 ix)(ixf所以所以25. 17 , 4 , 3 , 1 f13472151213141473二、牛顿插值多项式二、牛顿插值多项式如此继续下去，可得一系列等式如此

45、继续下去，可得一系列等式设设x是是a，b上一点，由一阶差商定义得上一点，由一阶差商定义得000)()(,xxxfxfxxf 同理，由二阶差商定义同理，由二阶差商定义110010,xxxxfxxfxxxf )(,110100 xxxxxfxxfxxf 得得)(,)()(000 xxxxfxfxf 得得7401010 , ,()nnnnf x xxf xxxf x xxxx )(,)()(000 xxxxfxfxf )(,110100 xxxxxfxxfxxf )(,221021010 xxxxxxfxxxfxxxf 依次把后式代入前式，最后得依次把后式代入前式，最后得00000100101001

46、001201012012( )() ,()(),() ,()()(),(),()() ,()()()f xf xf x xxxf xf xxxxf x xxxxxxf xf xxxxf xxxxxxxf x xxxxxxxxx75)()(,)()()(,)(,)(,)()(,)(,)()(10021021010210010010100100nnnxxxxxxxxxfxNxxxxxxxxxxfxxxxxxxfxxxxfxfxxxxxxxfxxxxfxfxf 001001201001( )(),(),()(),()()nnnN xf xf x xxxf x x xxxxxf xxxxxx 其中其中

47、76可见可见, Nn(x)为次数不超过为次数不超过n 的多项式的多项式,且易知且易知 Nn(x) 满足满足插值条件式插值条件式,故其为插值问题的解故其为插值问题的解,称之为牛顿插值多项称之为牛顿插值多项式。式。由插值多项式的唯一性知，它与拉格朗日插值多项式由插值多项式的唯一性知，它与拉格朗日插值多项式 是等价的是等价的,即即 Ln(x) Nn(x)77且有如下递推形式且有如下递推形式)()(,)()(1001 nnnnxxxxxxfxNxN和余项公式和余项公式)()(,)(010nnnxxxxxxxxfxR )()()!1()(0)1(nnxxxxnf 由此即得性质由此即得性质2 2。且。且k

48、010( ),()()nnnR xf xx xxxxxx78例例3 已知已知求满足以上插值条件得牛顿型插值公式。求满足以上插值条件得牛顿型插值公式。1121520743ix)(ixf79解解 在例在例1中，我们已经计算出中，我们已经计算出;25. 1,3210 xxxxf4, 1, 0)(210100 xxxfxxfxf则牛顿三次插值多项式为则牛顿三次插值多项式为2675.381425. 1)4)(3)(1(25. 1)3)(1(4)1(0)(233 xxxxxxxxxxN80 xk f(xk)一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商0.40 0.55 0.65 0.8

49、0 0.900.4107 0.5781 0.6967 0.8881 1.02651.1160 1.1860 1.2757 1.38410.2800 0.3588 0.43360.1970 0.2137 0.0344例例5 已知已知f(x)=shx的数表的数表,求三次牛顿插值多项式求三次牛顿插值多项式,并由此并由此计算计算f(0.596)的近似值。的近似值。 81)55. 0)(40. 0(2800. 0)40. 0(1160. 141075. 0)(2 xxxxN解解 由上表可得过前三点的二次牛顿插值多项式为由上表可得过前三点的二次牛顿插值多项式为632010. 0)596. 0()596.

50、0(2 Nf故故82又又1970. 0,3210 xxxxf可得过前四点的三次牛顿插值多项式可得过前四点的三次牛顿插值多项式)65. 0)(55. 0)(40. 0(1970. 0)()(23 xxxxNxN6319145. 0)596. 0()596. 0(3 Nf故故)80. 0)(65. 0)(55. 0)(40. 0(0344. 0)(3 xxxxxR可得可得N3(x)的截断误差的截断误差631034. 0)596. 0( R0344. 0,40 xxf83差分与等距节点的牛顿插值多项式差分与等距节点的牛顿插值多项式 设函数设函数y=f(x)在等距节点在等距节点xi=x0+ih (i=

51、0,1, ,n)上的上的函数值为函数值为fi=f(xi)(h为步长为步长)定义定义2 fi=fi+1-fi 和和 fi=fi-fi-1 分别称为函数分别称为函数f(x)在点在点xi处的一阶向前差分和一阶向处的一阶向前差分和一阶向后差分。后差分。 一般地一般地, f(x) 在点在点 xi 处的处的 m 阶向前差分和阶向前差分和 m 阶向阶向后差分分别为后差分分别为 mfi= m-1fi+1- m-1fi 和和 mfi= m-1fi- m-1fi-184函数值函数值一阶差分一阶差分二阶差分二阶差分三阶差分三阶差分四阶差分四阶差分. f (x0) f (x1) f (x2) f (x3) f (x4

52、) . f0 ( f1) f1 ( f2) f2 ( f3) f3 ( f4) . 2f0 ( 2f2) 2f1 ( 2f3) 2f2 ( 2f4) . 3f0 ( 3f3) 3f1 ( 3f4) . 4f0 ( 4f4) .表表5-285性质性质1 1 mfi= mfi+m性质性质2 2 111,!1,!miii mimmi mi miimf x xxfm hf xxxfm h差分有如下基本性质差分有如下基本性质86代入牛顿插值公式代入牛顿插值公式 ,可得可得)1()1(!)1(!2)()(002000 ntttnfttftffthxNxNnnn称为牛顿向前插值公式，其余项为称为牛顿向前插值

53、公式，其余项为),()()!1()()1()()(0)1(10nnnnnxxfhnntttthxRxR 插值节点为插值节点为 xi=x0+ih (i=0,1, ,n), 如果要计算如果要计算 x0附近点附近点 x 处的函数值处的函数值f(x), 可令可令 x=x0+th (0 t 1)87 类似地类似地, 若计算若计算 xn 附近的函数值附近的函数值 f(x), 可令可令 x=xn+th (- 1 t 0) ，可得牛顿向后插值公式，可得牛顿向后插值公式)1()1(!)1(! 2)()(2 ntttnfttftffthxNxNnnnnnnnn),(, )()!1()()1()()(0)1(1nn

54、nnnnxxfhnntttthxRxR 及其余项及其余项88例例6 设设 y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三次插值多项式用三次插值多项式求求f(1.2) 及及f(2.8)的近似值的近似值.解解 相应的函数值及差分表如下相应的函数值及差分表如下: 0.4814 0.74210 1.22356 1.14396 1.88606 3.10962 1.76341 2.90347 4.79343 7.90305 2.71828 4.4816 7.28906 12.1824 20.0855四阶差分四阶差分三阶差分三阶差分二阶差分二阶差分一阶差分一阶差分函数值函数值89函数

55、值函数值一阶差分一阶差分二阶差分二阶差分三阶差分三阶差分四阶差分四阶差分2.71828 4.48169 7.28906 12.1824 20.0855 1.76341 2.90347 4.79343 7.90305 1.14396 1.88606 3.10962 0.74210 1.22356 0.4814 求求f(1.2)用牛顿前插公式用牛顿前插公式, 且由且由 1.2=1+0.5t, 得得t=0.431.14396(1.2)(1.2)2.71828 1.76341 0.40.4 (0.4 1)2!0.742100.4 (0.4 1)(0.4 2)3.33386323!fN 90求求f(2.

56、8)用牛顿后插公式用牛顿后插公式,且由且由 2.8=3+0.5t, 得得 t= -0.43(2.8)(2.8)3.1096220.085547.90305 ( 0.4)( 0.4) ( 0.4 1)2!1.22356( 0.4) ( 0.4 1)( 0.42)15.76808723!fN 91第四节第四节 埃尔米特埃尔米特(Hermite)插值插值n一、一、 埃尔米特插值多项式埃尔米特插值多项式 为了使插值函数能更好的切合原来的函数，许多问为了使插值函数能更好的切合原来的函数，许多问题不但要求节点上的函数值相等，还要求导数值相同题不但要求节点上的函数值相等，还要求导数值相同，甚至高阶导数也相等

57、，这类插值问题称为埃尔米特，甚至高阶导数也相等，这类插值问题称为埃尔米特插值。插值。92xi a, b (i=0,1, , n) 为为n+1个互异节点个互异节点,考虑函数值考虑函数值与导数个数相等的情况。与导数个数相等的情况。 jjxfy jjxfm nj, 0 我们要求插值多项式我们要求插值多项式H(x)满足满足jjjjmxHyxH )(,)(共共2n+2个条件，可确定次数不超过个条件，可确定次数不超过2n+1的多项式。的多项式。93 ), 1 , 0,(, 0nkjxxjkkk 满足上述条件的插值多项式可以写成用插值基函数满足上述条件的插值多项式可以写成用插值基函数表示的形式表示的形式 n

58、jjjjjnxmxyxH012)()()( 94对插值基函数先取对数再求导数得，对插值基函数先取对数再求导数得，959697基函数满足下列插值条件基函数满足下列插值条件)(, )(, )(, )(1010 xxxx 001(0)()0(1)()0(0,1)iiixixi 33()(0,1)()iiiiHxyiHxm H3(x)称为三次埃尔米特插值多项式称为三次埃尔米特插值多项式。98110(0)()1(1)()0(0,1)iiixixi 001(0)()0(1)()0(0,1)iiixixi 110(0)()1(1)()0(0,1)iiixixi 99 条条 件件 函函 数数函数值函数值导数值

59、导数值x0 x1x0 x1 0(x)1000 1(x)0100 0(x)0010 1(x)0001表表2-3即即100210100)()(xxxxxxx ,)(21 )(21010100 xxxxxxxxx 201011)()(xxxxxxx ,)(21)(20101011xxxxxxxxx 2201000022101111( )12 ( )( )( )()( )( )12 ( )( )( )()( )xlx lxxxxlxxlx lxxxxlx 即即)(),(10 xlxl插值点的插值点的Lagrange),(),(1100yxyx为为以以一次基函数一次基函数. 101可得满足条件的三次埃尔

60、米特插值多项式为可得满足条件的三次埃尔米特插值多项式为300110011( )( )( )( )( )Hxyxyxmxmx 20101121010020101011210101003)()()(21)(21)(xxxxxxmxxxxxxmxxxxxxxxyxxxxxxxxyxH 定理定理3 满足条件式满足条件式 的三次埃尔米特插值多项式存在且唯一。的三次埃尔米特插值多项式存在且唯一。33(),()(0,1)iiiiHxy Hxmi 102二、误差估计二、误差估计定理定理4 设设f(x)在包含在包含x0、x1的区间的区间a,b内存在四阶导内存在四阶导数，则当数，则当xa,b时有时有(4)2233011( )( )(