数值分析1PPT课件

1、教材教材 应用数值分析应用数值分析 郑咸义等郑咸义等 编著编著 （华南理工大学出（华南理工大学出版社）版社）参考书目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（机械工业出版社) Numerical Analysis (Seventh Edition) Richard L. Burden & J. Douglas Faires （高等教育出版社）第1页/共554页 数值分析的研究对象数值分析的研究对象n 数值分析属于计算数学的

2、范畴，是数学的一个分支，也称为数值计算方法、计算方法、数值方法等。n 其研究对象是求解各种数学问题的数值方法的设计、分析及其有关的数学理论和具体实现的一门学科。n 它是科学与工程计算（科学计算）的基础。第2页/共554页 许多科学与工程实际问题（如：核武器的研制、导弹的发射、气象预报等）的解决都离不开科学计算。 目前，理论、试验、计算已成为人类进行科学活动的三大方法。 数值分析的研究对象数值分析的研究对象第3页/共554页 科学计算的过程，是从数学模型的提出到上机计算得出结果的完整过程。（下图表明了其中的图表明了其中的主要步骤主要步骤和和相互关系相互关系 ）数学化离散化程序化数学模型数值算法编

3、制程序上机运行输出结果实际问题 数值分析研究的对象数值分析研究的对象第4页/共554页 数值分析研究的对象数值分析研究的对象 n 数值分析是数学、计算机科学与其他学科数值分析是数学、计算机科学与其他学科交叉交叉的产物的产物。n 本门课程将着重介绍进行本门课程将着重介绍进行科学计算科学计算所所必须掌握的一些最基本、最常用的必须掌握的一些最基本、最常用的数值方数值方法法（数值算法），并作相关分析（数值算法），并作相关分析。第5页/共554页数值分析的任务数值分析的任务 对典型的数学问题给出数值求解方法对典型的数学问题给出数值求解方法( (近似方法近似方法) )，并对算法进行理论分析，使，并对算法进

4、行理论分析，使得其能够在计算机有效地得以实现。得其能够在计算机有效地得以实现。 数值算法的数值算法的构造构造 算法的理论算法的理论分析分析第6页/共554页数值分析的任务数值分析的任务 针对数值问题研究可在计算机上执行且行之有效行之有效 的计算公式（数值算法）。 例：解线性方程组，已有Cramer法则，但不可行。 数值算法的分析，主要包括误差分析误差分析（数值问题的性态，数值方法的截断误差、舍入误差和稳定性、收敛性等）和复杂性分析复杂性分析（计算量、存储量）。 第7页/共554页课程课程目的目的 学习一些常用的数值方法，掌握 数值方法的基本理论，为进一步 研究和使用更复杂的数值算法奠定 基础。

5、 初步掌握一种科学计算软件包 （如Matlab）的使用方法。 第8页/共554页课程主要内容课程主要内容u 插值方法；u 曲线拟合与函数逼近； 数值逼近u 数值积分与数值微分；u 线性代数方程组数值求解的直接法；u 线性代数方程组数值求解的迭代法； 数值代数u 非线性方程与方程组数值求解；u 常微分方程数值求解。 Matlab 简介第9页/共554页第一章第一章 绪绪 论论主要内容：u 一些常用概念；u 数值算法的复杂度与稳定性。u 数值计算中的误差；u 数值算法设计的若干原则；第10页/共554页 1. 1.数值分析中常用的一些概念数值分析中常用的一些概念 F 数值问题F 数值解F 算法F

6、计算量F 病态问题F 算法数值稳定性第11页/共554页 数值问题、数值解数值问题、数值解 、算法、算法 由一组已知数据（输入数据），求出一组结果数据（输出数据），使得这两组数据之间满足预先制定的某种关系的问题，称为数值问题。 由数值计算公式算出的数值形式的解(通常由计算机计算得到)称为数值解。一般数值解是近似解。由给定的已知量，经过有限次的四则运算及规定的运算顺序，求出所关心的未知量的数值解，这样所构成的整个计算步骤，称为数值算法（简称算法）。 第12页/共554页 计算量计算量一个算法所需要的乘法和除法总次数称为计算量。计算量的单位为flop，表示完成一次浮点数乘或除法所需要的时间。算法的

7、计算量可以衡量算法的优劣，因为它体现着算法的计算效率，通常算法的计算量越小，则算法的计算效率越高，因而该算法也越好。由于计算机做加减法要比乘除法快得多，故算法的计算量可以不考虑加减法的时间。例: 设A，分别为1020，2050，5010的矩阵，计算 D=ABC 就有如下不同的算法和计算量 算法1：D=(AB)C 计算量 N1=15000 flop; 算法2：D=A(BC) 计算量 N2=12000 flop.第13页/共554页 病态问题病态问题因初始数据的微小变化，导致解产生剧烈变化问题称为病态问题。病态问题也称为坏问题，这类问题通常是问题本身固有的。 求解病态问题应该特别注意，因为实际问题

8、的数据都是近似的或经计算机计算要对输入数据做舍入处理，这都引起原始数据的扰动，若所求解的正好是个病态问题，则采用通常算法计算就会出现很隐蔽的错误，导致不良的后果。病态问题在函数计算、方程求根及方程组求解中都是存在的，它的计算或求解应用专门的方法或将其转化为非病态问题来求解。第14页/共554页 例例：病态的方程组病态的方程组考察方程组和 上述方程组尽管只是右端项有微小扰动，但解大不相同： 一个是 ，一个是 。 这类方程组称为病态的。 121221.00012.0001xxxx121221.00012xxxx121xx122,0 xx第15页/共554页算法的数值稳定性算法的数值稳定性 在计算过

9、程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为数值稳定算法。不是数值稳定的算法称为数值不稳定算法。 数值不稳定算法会导致计算结果失真，对数值不稳定的算法常采用转化成相应的数值稳定的算法来处理 。第16页/共554页 2. 2.对算法所要考虑的问题对算法所要考虑的问题2 20 09 9. .7 7 1 10 01. 计算速度。计算速度。 例如，求解一个20阶线性代数方程组，若用克莱姆法则要进行约 次乘法运算，如用每秒1亿次乘法运算的计算机要30万年。而用Gauss消去法只需约3000次乘法运算，用普通微机1秒之内便可算出结果。20209.7109.71021102.

10、存储量。 大型问题有必要考虑。 3. 收敛性。 不收敛的算法无使用价值。 4. 数值稳定性。 在大量计算中，舍入误差的积累能否控制住，这与算法有关。第17页/共554页3. 3. 数值计算中的误差数值计算中的误差来源及种类 - 模型误差、参数误差、 截断误差、舍入误差。1. 模型误差（也称描述误差）模型误差（也称描述误差） 模型误差是在建立数学模型时，由于忽略了一些次要因素而产生的误差，它是数学建模阶段要考虑的误差，不是计算方法可以解决的。2. 参数误差（也称观测误差）参数误差（也称观测误差） 测量已知参数时，数据带来的误差 ，它也不是计算方法能解决的问题。第18页/共554页 数值计算中的误

11、差数值计算中的误差3. 截断误差（也称方法误差）截断误差（也称方法误差） 截断误差是对参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），即数学模型的数值解与精确解之间数值解与精确解之间的误差的误差，是计算方法关注的内容。（举例：P6 sinx = ）4. 舍入误差（也称计算误差）舍入误差（也称计算误差） 舍入误差是由于计算机只能表示有限位数字，因而只能取取有限位数进行计算所得的误差有限位数进行计算所得的误差，它也是计算方法关注的内容。 （举例： ）3.141592653第19页/共554页 数值计算中的误差数值计算中的误差误差的基本

12、概念 绝对误差 - 近似数 x * 关于准确数 x 的绝对误差： E(x) = x x *（或E(x *) = x x * ） - 近似数 x * 关于准确数 x 的绝对误差限：E(x)= x x * - 工程上表示准确数 x 的范围： x * x x * + 或 x = x * - 函数值的绝对误差：Ef (x) f (x) E(x) （利用微分中值公式导出） 举例：f (x) = x3第20页/共554页数值计算中的误差数值计算中的误差相对误差 - 近似数 x * 关于准确数 x 的相对误差：( )( )( )( )或rr xE xE xE xE xxxxxxxx( )rE xxxx( )

13、( )( )( )( )( )rE f xE xEfffxxf xx- 函数值的相对误差限： - 近似数 x * 关于准确数 x 的相对误差限：第21页/共554页 数值计算中的误差数值计算中的误差有效数字 - 用 x * 表示 x 时准确到小数点后第 k 位：1102kxx11211221 20.1010 (101010 ),01102mnnnnmnmxx xxxxxx x xxx nm xx 即 其中 = 0 9，且 （最左一位非零字）； 是正整数，是整数。- 近似数 x * 具有 n 位有效数字：举例1113.1415926530.314592653103.14160.31416 103

14、.140.314 10第22页/共554页 数值计算中的误差数值计算中的误差有效数字与相对误差的关系 - n 位有效数字的近似数 x * 其相对误差：11(1)11002( )nrxxEx（最左一位），且 (1)11( )11002(1)nrExxx（最左一位），且 - 相对误差为 的近似数 x * 至少具有 n 位有效数字。注：在未标明近似数的绝对误差时默认该近似数准确到末位数字， 从其最左边的非零数字起直到最右边的一位数字止均为有效数字。第23页/共554页 4. 4. 数值计算中应注意的几个问数值计算中应注意的几个问题题若干原则 - 注意简化计算步骤，减少运算次数； （例：秦九韶算法)避

15、免两个相近的数相减，减少有效 数字的损失；（例）使用数值稳定的算法;（例:习题1.16）小心处理病态的数学问题；第24页/共554页复习题习题 1.1(3)(4)、1.2、1.3、1.4、 1.6、1.9 (1) 、1.15、1.16第25页/共554页2.1 插值问题的提出第二章 函数近似计算的插值法第26页/共554页( )iiyf xxf1. 在工程实际问题中,某些变量之间的函数关系是存在的, 但通常不能用式子表示,只能由实验或观测得到 在一系列离散点上的函数值. 2( )f x. 有的函数虽然有表达式,但比较复杂, 计算函数很 不经济且不利于在计算机上进行计算.( ,)( ).iixf

16、yf x希望通过这些数据计算函数在其他指定点处的近似值或获取其他信息,( )( ).P xf x这两种情况下 都希望用简单的函数来逼近原函数插值问题的提出第27页/共554页插值：已知a, b上的函数y= f (x)在n+1个互异点处的函数值:fnf2f1f0f(x)xnx2x1x0 x求简单函数 P (x)，使得( )0,1,( ),*iiP xfin计算 f (x)可通过计算 P (x)来近似代替。如下图所示。yxx0 x1f0f1x2f2xifixi+1fi+1xn-1fn-1xnfnP (x)f(x)一、插值问题的数学提法第28页/共554页这就是插值问题, (*)式为插值条件,( )

17、( )P xf x称函数为函数的 插值函数则称之为插值多项式为多项式函数如果,)(xP称为插值节点点, 2 , 1 , 0,nixi称为插值区间区间,ba个等分点上若给定如函数5,0,sinxy 其插值函数的图象如图第29页/共554页00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533

18、.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy( )( )f xP x对于被插函数和插值函数ix在节点处的函数值必然相等( )( )P xf x但在节点外的值可能就会偏离( )( )P xf x因此近似代替必然存在着误差（截断误差）第30页/共554页整体误差的大小反映了插值函数的好坏.为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式或有理函数.本章讨论的就是(代数)多项式插值.第31页/共554页1. 满足插值条件的多项式 P(x)是否存在且唯一？2. 若满足插值条件的P(x)存在,又如何构造出P(x);即插值多项式的常用构造方法有哪些？

19、3. 用P(x)代替f(x)的误差估计，即截断误差的估计；对于多项式插值，我们主要讨论以下几个问题：4. 当插值节点无限加密时，插值函数是否收敛于 f(x)。第32页/共554页二、插值多项式的存在唯一性( ) , yf xa b设函数在区间上的代数插值多项式为nnnxaxaxaaxP2210)(且满足()0,1,2, ,niiP xfin.ia其中是n+1个待定的系数第33页/共554页012( ),nnP xa a aa即多项式的系数满足线性方程组20102000nnaa xa xa xf201 12111nnaa xa xa xf2012nnnnnnaa xa xa xf-(1)上述方程

20、组的系数行列式为n+1阶Vandermond行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx 0第34页/共554页定理1. 由Cramer法则,线性方程组(1)有唯一解nnnxaxaxaaxP2210)()0,1,2,niiP xfin-(3)-(2),(jixxji若插值节点则满足插值条件的次数 n 的插值多项式存在且唯一.虽然线性方程组(1)推出的插值多项式存在且唯一,但通过解线性方程组(1)求插值多项式却不是好方法.第35页/共554页 2.2 Lagrange插值多项式第二章 函数近似计算的插值法第36页/共554页若通过求解线性方程

21、组(1)来求解插值多项式 系数 , 不但计算工作量较大, 且难于得到ia( )nP x的简单表达式.一、 代数多项式的构造:( )nP x可通过找插值基函数的方法,得到插值多项式!十八世纪法国数学家Lagrange对以往的插值算法进行研究与整理，提出了易于掌握和计算的统一公式，称为Lagrange插值公式。 它的特例是线性插值公式和抛物线插值公式。Lagrange插值多项式第37页/共554页1. 线性插值 已知两个插值点及其函数值：xx0 x1f(x)f0f1插值节点对应的函数值求一次多项式1( ),P xabx使得 11110001)()(fbxaxPfbxaxP 由于方程组的系数行列式0

22、110110 xxxx第38页/共554页所以，按Gramer法则，有唯一解01100110110011xxfxfxxxxfxfa 010110101111xxffxxffb 于是,)(01010110011xxxffxxfxfxxP 101001011)(fxxxxfxxxxxP 或(B-1）第39页/共554页 容易验证，过点（x0，f0）与（x1，f1）直线方程就是式（B-1），如图2-3所示。yxx0 x1P1(x)f(x)P1(x)f(x)误差图2-3第40页/共554页2. 抛物线插值 已知三个插值节点及其函数值：f2f1f0f(x)x2x1x0 x求一个二次多项式22( )P x

23、abxcx使得 222222121112020002)()()(fcxbxaxPfcxbxaxPfcxbxaxP由于该方程组的系数行列式 。行列式行列式阶阶eVandermondxxxxxx30111222211200 第41页/共554页所以，有唯一解。即满足这样条件的二次多项式是唯一确定的。满足上述条件，所以它就是所求的二次多项式。 容易看出2120210121012002010212)()()()()()()(fxxxxxxxxfxxxxxxxxfxxxxxxxxxP（B-2）容易验证，P2(x)是过点(x0, f0)、(x1, f1)与(x2, f2)三点的抛物线，如图2-4所示。yx

24、x1x0 x2P2(x)f(x)图2-4f0f1f2第42页/共554页3. n 次Lagrange插值已知 n+1 个插值节点及其函数值：fnf2f1f0f(x)xnx2x1x0 x插值节点相应的函数值求次数不超过 n 的多项式Pn(x) 。2012( )nnnP xaa xa xa x使得 nnnnnnnnnnnnnnnnnfxaxaxaaxPfxaxaxaaxPfxaxaxaaxPfxaxaxaaxP2210222222102112121101002020100)()()()(第43页/共554页维的间是的多项式构成的线性空所有次数不超过n1n根据线性空间的理论,11nn这个维线性空间的

25、基也由个多项式组成并且形式不是唯一的n而任意一个 次多项式可由基线性表示且在不同的基下有不同的形式01( ),( ),( )1nxxxn设为上述维线性空间的一个基第44页/共554页线性表示可由次多项式且任意)(,),(),()(10 xxxxPnnn线性无关显然)(,),(),(10 xxxn)()()()(1100 xaxaxaxPnnn的插值函数为某个函数如果)()(xfxPn为插值基函数则称)(,),(),(10 xxxnnifxPiin, 2 , 1 , 0)(且满足插值条件:为插值节点其中nixi,2 , 1 , 0,()0,1,2,iif xfin第45页/共554页上的一组节点

26、为区间如果,210babxxxxannjxlnj,2 , 1 ,0),(次多项式我们作一组)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjiiijixxxx0)()(nj,2 , 1 ,0010()()()()nniixxxxxxxx1( )nx令)(1jnx则)()()(1110njjjjjjjxxxxxxxxxxn+1次多项式第46页/共554页)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,2 , 1 ,0且()jilx10ijijnji,2 , 1

27、,0,-(4)线性无关显然)(,),(),(),(210 xlxlxlxln)()(11jjnnxxxx从而第47页/共554页的插值基函数作如果用)()(,),(),(),(210 xfyxlxlxlxln则的插值多项式为而,)()(xfxPn)()()()(1100 xlaxlaxlaxPnnn为待定参数、其中naaa10)(inxPnifxfii, 2 , 1 , 0)(令即njijjxla0)(nifi, 2 , 1 , 0由(4)式,可得nifaii, 2 , 1 , 0第48页/共554页为记为项式为插值基函数的插值多以上在节点于是)(), 1 , 0()(,), 1 , 0()(

28、,xLnixlnixxfynji0011( )( )( )( )nnnL xlx fl x flx f)(xljnjiiijixxxx0)()(其中-(6)-(5)(5)( )( )nL xyf xLagrange称式为的插值多项式( ) (0,1, )jlxinnLagrange称(6)式为 次插值基函数第49页/共554页0( )( )( )nnnkkkP xL xlxf其中11( )( )()()nknkkxlxxxx 这个改写了的Lagrange插值公式，在许多理论分析中是比较有用的。Lagrange插值公式的标准型公式:第50页/共554页例1:15)225(,13)169(,12)

29、144()(fffxf满足已知.)175(,)(的近似值并求插值多项式的二次作fLagrangexf解:225,169,144210 xxx设)(0 xl插值基函数为的二次则Lagrangexf)()()(201021xxxxxxxx2025)225)(169(xx)(1xl)()(210120 xxxxxxxx1400)225)(144(xx)(2xl)()(120210 xxxxxxxx4536)169)(144(xx01212,13,15fff第51页/共554页插值多项式为的二次因此Lagrangexf)(20 01 12 2( )( )( )( )L xf lxf l xf lx且)

30、175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例1中,如果只给出两个节点169和225,也可以作插值多项式,即1次Lagrange插值多项式,有两个插值基函数,也就是Lagrange线性插值.第52页/共554页Lagrange线性插值基函数(一次插值)为Lagrange线性插值多项式为0101,x xff节点函数值101xxxx0( )lx1( )l x010 xxxx10011( )( )( )L xlx fl x f1001xxfxx0110 xxfxx第53页/共554页例2.).175(1fLagrange中的线性插值多项式求例

31、用之间与在由于插值点22516917521xxx解:为插值节点与因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函数为Lagrange线性插值多项式为11 12 2( )( )( )L xf l xf lx5622513x5616915x第54页/共554页)175(f5622517513561691751571285214.13所以第55页/共554页二、插值余项插值的从上节可知Lagrangexfy)(,0( )( )nnjjjL xlx f满足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不会完

32、全成立因此, 插值多项式存在着截断误差, 那么我们怎样估计这个截断误差呢？1( )( )( ),( )( )( )( )( )nninnnRxf xL xxRxf xL xK xx设则 为其零点，可设第56页/共554页1( )( )( )( )nnf xL xK xx01( )( )( )( )( )nntf tL tK xt若引入辅助函数)(x则有0的区分与注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2,)(,nbatxxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)(1( )( ),( ),( )nnL xxf xt由于和为多项

33、式 因此若可微 则也可微1( )( )( )( )nnf xL xK xx1()()( )()ininif xL xK xx则成立第57页/共554页根据Rolle定理,个零点上有至少在区间1),()(nbat再由Rolle定理,个零点上有至少在区间nbat),()( 依此类推阶导数为零的使得内至少有一个点在区间1)(,),(ntba0)()1(n)()1(tn1()()()( )()nntf tL tK xt(1)(1)(1)1( )( )( )( )nnnnnftLtK xt由于第58页/共554页)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfn

34、n所以)()()(截断误差的余项为插值多项式称xPxRnn(1)(1)(1)(1)1( )( )( )( )( )nnnnnnfLK x因此)!1()()()1(nxKfn0即第59页/共554页定理1.0( ) , 1,( )( ) , , , , , ,nniif xa bnLxf xa bnxa bxa b 设在区间上阶可微为在上的 次插值多项式 插值节点为则有( )nRx(1)1( )( )(1)!nnfxn,)()(01niinxxx其中.,),(xba且依赖于Lagrange型余项n=1:n=2:第60页/共554页|)(|max)1(1xfMnbxan|)(|)(|011niin

35、nxxxN设|)(|xRn则)()!1()(1)1(xnfnn11)!1(1nnNMn第61页/共554页插值基函数的性质(1)10(1)00:( )( )( )1( )( )( )(1)!( )1,1(1,2, )( )0,( )1( )1nnnniininiiinniif xLxRxl x ffxnf xfinl xfl x 插值基函数的一个重要性质:证明取则及故第62页/共554页Lagrange插值算法特点&局限性 优点：公式简洁, 理论分析方便 直观； 对称；容易编程上机等。 缺点：基函数计算复杂，计算量大 每增加一个节点，插值多项式的所有 系数都得重算；计算量为 。 222

36、nn下一节提出的Newton插值法就克服了上述缺点。第63页/共554页罗尔(Rolle)定理补充资料补充资料-01 如果函数 f(x) 在闭区间 a, b 上连续，在开区间(a, b)内具有导数，且在区间端点的函数值相等，即 f(a) = f(b) ，那么在(a, b) 内至少有一点 （a b），使得函数f(x)在该点的导数等于零：( )0 f。Rolle定理的几何意义是：如果连续曲线 y = f(x)的弧 上除端点外处处具有不垂直于 x 轴的切线且两端点的纵坐标相等（ f(a) = f(b) ） ，那么这弧 上至少有一点C处的切线平行于 x 轴（见图-A）。BA BA 图-AABCabyx

37、 （1）第64页/共554页Lagrange中值定理 如果函数 f(x) 在封闭区间 a,b 上连续，在开区间(a,b)内具有导数，那么在(a,b) 内至少有一点 （a 7时,舍入误差亦会增大.可知, Runge现象是由f(x)的高阶导数无界所致.)()!()()()()()(xwnfxLxfxRnnnn1 考考虑虑第103页/共554页01i1 (x) a,b , (1) ( ) , ;() (2) (x) , 0,1) ( ) ( ) niffffxxC a bx xinf xkxf x定义:设是定义在区间 上的函数，在结点上的函数值为若函数 （ ）满足连续在子区间（上是的 次插值多项式。

38、则称 （ ）是在 , a bk上的分段次插值多项式。分段低次插值第104页/共554页二、分段线性Lagrange插值,ix设插值节点为,0,1,ifin函数值为,11kkkkxxxx形成一个插值区间任取两个相邻的节点构造Lagrange线性插值1,2 , 1 ,0,1nixxhiiiiihhmax1. 分段线性插值的构造第105页/共554页11kkkkxxfxx11kkkkxxfxx1, 1 , 0nk-(1)-(2)( )kx显然,当 时1,kkkxxx 或者通过分段插值基函数 的线性组合来表示 :0 ( )niil x( )x( )x0( )( ) ,niiixl x f , xa b

39、第106页/共554页其中0( )lx 101,xxxx01,xx x01,xx x( )il x 11,iiixxxx1,iixxx1 ,iixx x( )nlx 11,nnnxxxx1,nnxxx1,nnxxx0,11,iiixxxx0,11,iixxx0,且0( )1niil x第107页/共554页-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-1012

40、34-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81( )yx分段线性插值的图象( ,) ,0,1,iix yin实际上是连接点的一条折线也称折线插值,如右图曲线的光滑性较差在节点处有尖点 但如果增加节点的数量减小步长,会改善插值效果0lim ( )hx)(xf上连续在若,)(baxf因此则第108页/共554页)()!1()(1)1(xnfnn由第二节定理1可知,n次Lagrange插值多项式的余项为)()()(xPxfxRnn( )x那么分段线性插值的余项为1( )( )( )R xf

41、 xx)(2)(1 kkxxxxf有关与且xxxxkk,1|)(|1xR| )( |max| )(|max2111 kkxxxbxaxxxxxfkk224121hM 2281hM2. 分段线性插值的误差估计第109页/共554页2121 f(x)C , ,(),(0,1, ), ( ) (ab), , h |f(x)- (x)|max |( ) | (6.5.1)8 iini iii na bf xyinxy l xxxa bfx 定理 设且（ ）则对任意有其中11 hmax()iii nxx 第110页/共554页三、分段三次Hermite插值( ) , ,0,1,iif xa bxf in

42、设函数在上的节点 上的函数值为,0,1,iixf in 在节点 上的导数值为1, 1 ,0,1nkxxkk对任意两个相邻的节点可构造两点三次Hermite插值多项式( )( )( )( )( )3011011( )( )( )( )( )kkkkkkkkkHxfxfxfxfx,1kkxxx1, 1 ,0nk插值基函数为Hermitexxxxkkkk)(),(),(),()(1)(0)(1)(0第111页/共554页)()(0 xk)()(1xk)()(0 xk)()(1xk1121kkkxxxx21kkkxxxxkxx 211kkkxxxx21kkkxxxx1kxxkkkxxxx121211k

43、kkxxxx其中我们称( )331( )( ) ,0,1,1kkkHxHxxxxkn 为分段三次Hermite插值多项式，其余项为)()(! 4)(max)(max)(212)4(10)(3103kknkknkxxxxfxRxR212104)()(max! 41kknkxxxxxxxMkk第112页/共554页例2.21( )1f xx设函数在节点处的函数值及导数值,比较几种插值.我们分别用分段二次、三次Lagrange插值和分段两点三次Hermite插值作比较解:44221104384)4)(max! 4hMxxMkknk)(3xR即第113页/共554页 f(x)0.80000 0.307

44、690.137930.075470.04160 H3(x) 0.81250 0.30750 0.13750 0.07537 0.04159 x0.51.52.53.54.8 R3(x)=f(x)-H3(x)-0.01250000000000 0.00019230769231 0.00043103448276 0.00009972579487 0.00001047427455 L2(x)0.875000.32500 0.12500 0.072060.04087 L3(x)0.800000.325000.133820.074430.04269第114页/共554页分段低次插值的特点:计算较容易可以

45、解决Runge现象,可保证收敛性但插值多项式分段插值曲线在节点处会出现尖点,不可导第115页/共554页 习题 2.12.4、2.62.11、 2.13 、2.15、 2.20(1) 复习题第116页/共554页第二章第二章 函数近似计算的插值法函数近似计算的插值法 2.6 样条函数及三次样条插值第117页/共554页 2.6 三次样条插值样条:是 指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具.样条本质上是一段一段的三次多项式拼合而成的曲线在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的1946年,Schoenberg将样条引入数学,即所谓的样条函数一、三次样条插值

46、函数定义1. 的一个分割为区间,10babxxxan:,)(上满足条件在区间如果函数baxS第118页/共554页,)(,)(),(),()1(2baCxSbaxSxSxS 即上连续都在区间上都是三次多项式在每个小区间,)()2(1kkxxxS上的三次样条函数为区间则称,)(baxS处的函数值为在节点如果函数nxxxxf,)()3(10njyxfjj, 1 , 0,)(满足而三次样条函数)(xSnjyxSjj, 1 , 0,)(上的三次样条插值函数在为则称,)()(baxfxS-(1)第119页/共554页二、三次样条插值构造法 三转角方法处的函数值为在节点如果函数nxxxxf,)(10njy

47、xfjj, 1 , 0,)(的一个分割为区间,10babxxxan则其必满足的三次样条插值函数是如果,)()(xfxSnjyxSjj, 1 , 0,)(1, 1,)()(limnjmxSxSjjxxj1, 1),()(lim njxSxSjxxj1, 1,)()(limnjyxSxSjjxxj-(2)第120页/共554页条件个共要满足上述四组)24()(nxS即然是分段函数上必在,)(baxS,)(,)(,)(11211100nnnxxxxSxxxxSxxxxS)(xS满足三次样条插值多项式两点上的是,)(,)(1kkkxxxSjjkyxS)()(lim)(lim1xSxSkxxkxxkk)

48、(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk个条件共24 n1,; 1, 2 , 1 , 0kkjnk-(3)-(4)第121页/共554页个待定的系数应有式上的三次样条插值多项是4,)(1kkkxxxS个待定的系数必须确定即要确定nxS4)(少两个条件并且我们不能只对插值函数在中间节点的状态进行限制也要对插值多项式在两端点的状态加以要求也就是所谓的边界条件:第一类(一阶)边界条件:00)(fxSnnfxS)(第二类(二阶)边界条件:00)(fxS nnfxS )(第三类(周期)边界条件:()()001()()ppnnSxSx2

49、 , 1 ,0p-(5)-(6)-(7)第122页/共554页加上任何一类边界条件(至少两个)后个好也是个待定的系数的条件正必须确定确定nnxS44)(一般使用第一、二类边界条件,即jjkyxS)()(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk1,; 1, 1 , 0kkjnk1,2 , 1nk1,2 , 1nkkm00)(fxSnnfxS)(-(8)00)(fxS nnfxS )(或常用第二类边界条件.第123页/共554页njmxSjj, 1 ,0,)(设)(,)(1xSxxxf

50、kkk上的三次插值多项式在小区间逐个求插值多项式上的两点三次表示为将HermitexxxSkkk,)(1)(xSk)()()()()()(11)(0)(11)(0)(3xmxmxyxyxHkkkkkkkkk11121kkkkxxxxy21kkkxxxxkkxxm211kkkxxxx21kkkxxxx11kkxxmkkkkxxxxy121211kkkxxxx-(9)第124页/共554页kkkkkkyxxhxxhxS213)()(2)(1231)()(2kkkkkyxxhxxhkkkkmxxhxx212)()(1221)()(kkkkmxxhxx加以整理后可得并整理后得求二阶导数对,)(xSk)

51、()2(6)(131kkkkkkyyhxxxxS kkkkmhxxx21426121246kkkkmhxxx-(10)-(11)1, 1 ,01nkxxhkkk，令第125页/共554页)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk由条件)(limxSkxxk )(612kkkyyhkkmh412kkmh)(lim1xSkxxk )(6121kkkyyh112kkmhkkmh14由于以上两式相等,得11111)11(21kkkkkkkmhmhhmh)(321121kkkkkkhyyhyy1, 1nk个未知量个方程共个1,1nn第126页/共554页得并加以整理除上式的两边用

52、,111kkhh112kkkkkmmmkg1kkkkhhh11kkkkhhh)(3111kkkkkkkkkhyyhyyg1, 1nk-(12)1, 1nk个未知量个方程共个1,1nn(12)式称为基本方程组其中：第127页/共554页如果问题要求满足第一类(一阶)边界条件:00)(fxSnnfxS)(-(5)00fmnnfm-(5)基本方程组(12)化为n-1阶方程组0112112fgmmkkkkkkgmmm1122, 3 ,2nknnnnnnfgmm111212-(13)即将(13)式化为矩阵形式第128页/共554页222222122433221nnn12321nnmmmmmnnnnfgg

53、ggfg11232011-(14)这是一个三对角方程组如果问题要求满足第二类(二阶自然)边界条件:00)(fxS nnfxS )(时，称为自然边界条件00 nff第129页/共554页由(11)式,可知)()2(6)(013001000yyhxxxxS 020100426mhxxx120100246mhxxx)(60120yyh004mh102mh0f )(6)(1211 nnnnnyyhxS112nnmhnnmh14nf -(15)-(16)整理后得的方程式是关于,)16)(15(110nnmmmm第130页/共554页0000110232fhhyymm nnnnnnnfhhyymm 232

54、11110gng-(17)-(18)与基本方程组(12)联合,并化为矩阵形式,得212222121132211nnnnmmmmm1210nnggggg1210-(19)第131页/共554页(19)式与(14)一样,都是三对角方程组,并且都严格对角占优可以使用追赶法求解,并且解是唯一的对于问题要求满足第三类(周期)边界条件请同学们自己思考现在回到(10)式后解出式或通过nmmm,)19()14(10式代入将)10(,10nmmm)()(,),(),(110 xSxSxSxSn三次样条插值函数从而得到便可得到第132页/共554页思考：5 , 5112xxy函数使用不同的插值方法于定理 . 次样

55、条插值函数，满足任意边界条件的三为节点是以设,), 1 ,0()(,)(2nkxxSbaCxfk,min,max,10101iniiniiiihhhxxh设时则当 ch)()(,)()(xfxfbaxSxS和上一致收敛到在和最后，给出一个有用的结论第133页/共554页则有且若,)(4baCxf)(|)()(|max4)()(kkkbxahoxSxf2 , 1k 复习题 习题 2.26、2.27第134页/共554页第三章第三章 曲线拟合的最小二乘法曲线拟合的最小二乘法 / /函数平方逼近初步函数平方逼近初步第135页/共554页曲线拟合问题: (建立试验数据的模型) 在实际应用中，往往并不需

56、要曲线通过给定的数据点，而只要求用曲线(函数)近似代替给定的列表函数时，其 误差在某种度量意义下最小。函数逼近问题: (连续函数的逼近) 在实际应用中常需为解析式子比较复杂的函数寻找一个简单函数来近似代替它，并要求其误差在某种度量意义下最小。可统称为最佳逼近问题 3.1 拟合与逼近问题第136页/共554页插值法是使用插值多项式来逼近未知或复杂函数的，它要求插值函数与被插函数在插值节点上函数值相同 ，而在其他点上没有要求。在非插值节点上有时函数值会相差很大。若要求在被插函数的定义区间上都有较好的近似，就是最佳逼近问题。必须找到一种度量标准来衡量什么是最佳逼近.第137页/共554页 最佳一致逼

57、近是在函数空间 M中选 P(x) 满足 但由于绝对值函数不宜进行分析运算，常替之以来讨论，于是最佳逼近问题变为最佳平方逼近问题 这即为连续函数的最佳平方逼近.对于离散的问题，最佳平方逼近问题为:就是常说的曲线拟合的最小二乘法. (*)min)()(maxxpxfbxamin)()()(2dxxxpxfbamin)()(20 xpxfiimii第138页/共554页二. 预备知识K,(u,v),:(1) (u, u)0, (u, u)=0u=0;(2) (u, v)=(u, v);(3) ( u, v)= (u, v), K;(4) (u+v, w)=(u, w)+(v, w), wX,(u,

58、v) u v X设X是数域K上的线性空间,若对 u,vX,有 中一个数与之对应 记为其满足且则 称为 与的内积; 而定义了内积的线性空间 称为内积空间.内积:第139页/共554页常采用的内积与范数n12121. Rxyx(,)y(,)iiiTnTnx yx xxy yyni=1向量空间上的内积:( , )=212: x(x,x)niiix由内积定义范数（满足三个条件）范数第140页/共554页2. , :, , ,( , )( ) ( );( , )( ) ( ) ( ),( ).babaC a bf gC a bf gf x g x dxf gx f x g x dxx 连续函数空间 上的

59、内积设 定义内积:及加权内积为权函数1122222:( , )( )( )baff fx fx dx范数第141页/共554页0123.1.1, , ,(Gram)nC a b 定理设由他们的内积构成的矩阵 称矩阵G ),(),(),(01000n),(),(),(11101n),(),(),(10nnnn012G,.n 则 非奇异的充分必要条件是:线性无关第142页/共554页 1.正交函数族与正交多项式 定义1 若f(x),g(x)Ca,b, (x)为a,b上的权函数 且满足: 则称f(x)与g(x)在a,b上带权(x)正交。 正交多项式 第143页/共554页 若函数族 0(x), 1(

60、x), , n(x), 满足关系 则称k(x)是a,b上带权(x)的正交函数族。 例如，三角函数族 1 ,cosx , sinx , cos2x , sin2x , 就是在区间 -, 上的正交函数族。 第144页/共554页 定义2 设 n(x) 是a,b上首项系数 an0 的 n次多项式,(x)为a,b上权函数，如果多项式序列 满足关系式: 则称为多项式序列 为在a,b上带权(x)正交，称n(x)为a,b上带权(x)的n次正交多项式。 第145页/共554页 只要给定区间a,b及权函数(x), 均可由一族线性无关的幂函数 1 , x , , xn , 利用逐个正交化手续(Gram-Schmidt正交化方法)： 构