计算思维与计算方法优秀课件.ppt

《计算思维与计算方法优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算思维与计算方法优秀课件.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页，本讲稿共99页&参考书目参考书目计算方法计算方法刘师少刘师少编著编著（科学出版社，（科学出版社，2011年修订版年修订版）数值计算数值计算张军等编著张军等编著（清华大学出版社（清华大学出版社,2008年）年）&参考资料参考资料11周以真周以真.计算思维计算思维.中国计算机学会通讯中国计算机学会通讯,2007,3(11),2007,3(11)22王飞跃王飞跃.从计算思维到计算文化从计算思维到计算文化J.J.中国计算机学会通中国计算机学会通 讯，讯，20072007，3(11).3(11).33何钦铭等何钦铭等.计算机基础教学的核心任务是计算思维能力计算机基础教学的核心任务是计算思维能力

2、的培养的培养九校联盟（九校联盟（C9C9）计算机基础教学发展战略）计算机基础教学发展战略 联联 合声明合声明解读解读J.J.中国大学教学，中国大学教学，2010(9).2010(9).4 4 郑毓信郑毓信,肖柏荣肖柏荣,熊萍熊萍.数学思维与数学方法论数学思维与数学方法论 M.四川教育出版社四川教育出版社，20012001第2页，本讲稿共99页 了解计算思维的基本内容，了解人与了解计算思维的基本内容，了解人与 计算机器能力计算机器能力 的局限性，了解计算思维解决问题的一般步骤的局限性，了解计算思维解决问题的一般步骤.1、基本要求1 理解计算思维在问题解决过程中所发挥的作用理解计算思维在问题解决过

3、程中所发挥的作用23 掌握掌握计算机解决实际问题的一般步骤以及常用计算机解决实际问题的一般步骤以及常用 的医学信息处理（计算）算法（计算方法）。的医学信息处理（计算）算法（计算方法）。第3页，本讲稿共99页计算思维的概念计算思维的概念2、教学内容1 计算方法概念及其计算方法概念及其研究对象与特点研究对象与特点23 插值法语曲线拟合的最小二乘法插值法语曲线拟合的最小二乘法第4页，本讲稿共99页 考核方式考核方式考核方式考核方式n选择下列主题之一选择下列主题之一,完成综述：完成综述：1.1.医学院校学生应具有的医学院校学生应具有的 计算思维能力计算思维能力2.2.最小二乘法在医学信息处最小二乘法在

4、医学信息处 理中的应用理中的应用3.3.插值法在医学信息处理中插值法在医学信息处理中 的应用的应用 要求要求35003500字以上字以上表格下载：表格下载：ftp:/192.168.21.1ftp:/192.168.21.1第5页，本讲稿共99页0文献综述以学号文献综述以学号+姓名作为文件名上传至姓名作为文件名上传至ftp:/192.168.99.6个人账号下个人账号下&要求：要求：截止日期截止日期2011.12.31第6页，本讲稿共99页3、计算思维的概念、计算思维的概念 国际上广泛认同的计算思维定义来自周以真国际上广泛认同的计算思维定义来自周以真（Jeannette WingJeannet

5、te Wing）教授。周教授认为，计算思维是）教授。周教授认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计，运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解的涵盖计算机科学之广度的一系列以及人类行为理解的涵盖计算机科学之广度的一系列思维活动。思维活动。是抽象和自动化是抽象和自动化 如同所有人都具备如同所有人都具备“读、写、算读、写、算”能力一样，能力一样，计算思维是必须具备的思维能力。计算思维是必须具备的思维能力。计算思维的本质计算思维的本质第7页，本讲稿共99页 计算思维是通过约简、嵌入、转化和仿真等方法，把计算思维是通过约简、嵌入、转化和仿真等方法，把一个困难

6、的问题阐释为如何求解它的思维方法。一个困难的问题阐释为如何求解它的思维方法。计算思维是一种递归思维，是一种并行处理，是一计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法维分析推广的类型检查方法3.1 计算思维更细致的阐述 12计算思维是一种采用抽象和分解的方法来控制计算思维是一种采用抽象和分解的方法来控制庞庞杂的任务或进行巨型复杂系统的设计，是基于关杂的任务或进行巨型复杂系统的设计，是基于关注点分离的方法（注点分离的方法（SoC方法）。方法）。34计算思维是一种选择合适的方式去陈述一个问

7、题计算思维是一种选择合适的方式去陈述一个问题,或对一个问题的相关方面建模使其易于处理的思维或对一个问题的相关方面建模使其易于处理的思维方法方法.第8页，本讲稿共99页5计算思维是按照预防、保护及通过冗余、容错、纠计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维错的方式，并从最坏情况进行系统恢复的一种思维方法。方法。6计算思维是利用启发式推理寻求解答，即在不确定计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法。情况下的规划、学习和调度的思维方法。7计算思维是利用海量数据来加快计算，在时间和空间计算思维是利用海量数据来加快计算，

8、在时间和空间之间、在处理能力和存储容量之间进行折中的思维方之间、在处理能力和存储容量之间进行折中的思维方法法第9页，本讲稿共99页计算思维是一种根本技能，是每一个人为了在现代计算思维是一种根本技能，是每一个人为了在现代社会中发挥职能所必须掌握的。社会中发挥职能所必须掌握的。计算思维是人类求解问题的一条途径计算思维是人类求解问题的一条途径 特别注意123计算思维是思想，不是人造品。重要的是计算的计算思维是思想，不是人造品。重要的是计算的概念，它被人们用来求解问题、管理日常生活以概念，它被人们用来求解问题、管理日常生活以及与他人进行交流和互动。及与他人进行交流和互动。计算思维是数学与工程思维的互补

9、与融合，它作为计算思维是数学与工程思维的互补与融合，它作为一个问题解决的有效工具，人人都应掌握，处处都一个问题解决的有效工具，人人都应掌握，处处都会被使用。会被使用。4第10页，本讲稿共99页3.2计算思维与计算思维与计算方法联系与区别计算方法联系与区别 计算思维是一种选择合适的方式陈述一个问题计算思维是一种选择合适的方式陈述一个问题或对一个问题的相关方面建模使其易于处理的或对一个问题的相关方面建模使其易于处理的思维方法。思维方法。区别计算方法又称计算方法又称“数值分析数值分析”。是求解各类数学问题。是求解各类数学问题的数值解的方法，是研究分析用计算机求解数学计的数值解的方法，是研究分析用计算

10、机求解数学计算问题的数值计算方法及其理论的学科，是基于计算问题的数值计算方法及其理论的学科，是基于计算机考虑问题求解算机考虑问题求解第11页，本讲稿共99页3.2计算思维与计算思维与计算方法联系与区别计算方法联系与区别计算思维与计算方法互补性很强计算思维与计算方法互补性很强,可以相互促进。可以相互促进。联系 计算方法可以对计算思维研究方面取得的成果计算方法可以对计算思维研究方面取得的成果 进行再研究和吸收进行再研究和吸收,最终丰富计算方法的内容。最终丰富计算方法的内容。计算思维的重要作用也可以通过计算方法得计算思维的重要作用也可以通过计算方法得 到更好的提高。到更好的提高。第12页，本讲稿共9

11、9页设计算法3.3用计算机解决实际问题的一般步骤是：用计算机解决实际问题的一般步骤是：建立数学模型分析实际问题编写程序代码上机计算 前三步为建模，前三步为建模，集中于问题及其解法集中于问题及其解法或算法，与任何特定的计算机或计算机语或算法，与任何特定的计算机或计算机语言无关。言无关。后两步为模型求解，后两步为模型求解，集中于选择某一集中于选择某一种程序设计语言，把算法表达给特定的计种程序设计语言，把算法表达给特定的计算机。算机。广义地说，为解决一个问题而采广义地说，为解决一个问题而采取的方法和步骤，就称为取的方法和步骤，就称为“算法算法”。第13页，本讲稿共99页1.1.对于要解决的问题建立数

12、学模型对于要解决的问题建立数学模型2.2.研究用于求解该数学问题近似解的算法和过程研究用于求解该数学问题近似解的算法和过程3.3.按照按照2 2进行计算，得到计算结果进行计算，得到计算结果建立数学模型转化为数值公式进行计算换句话说第14页，本讲稿共99页由此可见。由数学模型找到求解方法的过程，是计由此可见。由数学模型找到求解方法的过程，是计算方法要研究的核心问题。也是计算思维涵盖的内容。算方法要研究的核心问题。也是计算思维涵盖的内容。计算方法所面对的正是计算方法所面对的正是“模型求解模型求解”，或者说求模，或者说求模型的数值解。因此我们不能把型的数值解。因此我们不能把“计算方法计算方法”理解为

13、理解为“计计算算”的的“方法方法”，而应理解为利用计算工具求解复杂数，而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。学问题的方法论和基本方法。第15页，本讲稿共99页我们我们所讲述的算法只限于计算机算法，即计算机能所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。算机能否执行。计算机算法可分为两大类别：数值运算和非数值计算机算法可分为两大类别：数值运算和非数值运算。运算。数值运算的目的是求数值解，例如函数插值、曲线数值运算的目的是求数值解，例如函数插值、曲线拟合的最小二乘法等，都属于

14、数值运算范围。拟合的最小二乘法等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如教务管理、学籍管理等。目于事务管理领域，例如教务管理、学籍管理等。目前，计算机在非数值运算方面的应用远远超过了在前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用数值运算方面的应用注意：注意：不论是哪类方式，对它们的基本要求都是能提供不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义的描述，以便使我们能够将这种描述对算法的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。很容易转换成计算机高级语言（程

15、序）。第16页，本讲稿共99页4.1 4.1 问题的提出问题的提出 在生产实际中，连续函数往往只能由若干个离散点上在生产实际中，连续函数往往只能由若干个离散点上的值来表示，而难以得到具体的解析式的值来表示，而难以得到具体的解析式4 4 4 4 插值插值 25.6 27.2 36.9 34.4 26.8 24.3 4 8 12 16 20 24温度（）时间（时）Co第17页，本讲稿共99页 每隔每隔4 4小时记录一次小时记录一次温度，以反映某地一温度，以反映某地一天的气温变化状况天的气温变化状况那么如何利用离散点值那么如何利用离散点值来推测其余点上的函数来推测其余点上的函数值值,(如如1111、

16、1515、1919点温点温度度),从而反映被测函数从而反映被测函数的整体状况呢？的整体状况呢？构造这个函数过构造这个函数过程就称为插值程就称为插值方法方法:构造一个通过所构造一个通过所有离散测试点的函数，有离散测试点的函数，用这个函数来逼近被用这个函数来逼近被测函数。测函数。第18页，本讲稿共99页 还有许多这样的实例还有许多这样的实例函数解析式未知函数解析式未知,通过实验观测得到的一组数据通过实验观测得到的一组数据,即即在某个区间在某个区间 a,ba,b上给出一系列点的函数值上给出一系列点的函数值 yi=f(xi)或者给出函数表，希望构出能近似代替原来的函数或者给出函数表，希望构出能近似代替

17、原来的函数y=f(x)y=p(x)xx0 x1x2xnyy0y1y2yn第19页，本讲稿共99页 动物实验中心为白鼠服用了某种新产品药物后，在对动物实验中心为白鼠服用了某种新产品药物后，在对1 1对白鼠在周内的食物消费量（克对白鼠在周内的食物消费量（克,x)及及6 6周间增加的体周间增加的体（克（克,y)y)测量数据如下测量数据如下:i123456 xi568608 636 636660 684 yi106126 134 134128 158 试确定白鼠体重试确定白鼠体重 y y 与白鼠之食物与白鼠之食物消费量消费量x x 的函数的函数关系关系 y=f(x)y=f(x)那么，左边图那么，左边图

18、形的形的y=f(x)y=f(x)解解析函数如何求析函数如何求呢？呢？第20页，本讲稿共99页血药浓度问题血药浓度问题,为试验某种新药的疗效为试验某种新药的疗效,研究人员对志愿研究人员对志愿者用快速静脉注射方式一次注入该药者用快速静脉注射方式一次注入该药30mg30mg（毫克）后（毫克）后,在在一定的时刻一定的时刻t(h)t(h)采取血样采取血样,测得血药浓度测得血药浓度C(g/ml)C(g/ml)（微（微克毫升）数据如下克毫升）数据如下:试确定血药浓度试确定血药浓度C C与时间与时间 t t 的函数关系的函数关系 C=f(t)i123456789t(h)0.250.511.523468C(g/

19、ml)19.21 18.15 15.36 14.1 12.9 9.32 7.45 5.24 3.01第21页，本讲稿共99页4.2 插值法的基本原理函数函数y y=f f(x x)给出一组函数值给出一组函数值 x:x0 x1 x2 xny:y0 y1 y2 yn其中其中x x0 0,x,x1 1,x,x2 2,x,xn n是区间是区间 a a,b b 上的互异点，要构造上的互异点，要构造一个简单的函数一个简单的函数(x)(x)作为作为f f(x x)的近似表达式，使满足的近似表达式，使满足(插值原则、插值条件插值原则、插值条件)这类问题称为这类问题称为插值问题。插值问题。-f f(x x)的的

20、插值函数插值函数,f f(x x)-)-被插值函数被插值函数x x0 0,x,x1 1,x,x2 2,x,xn n-插值节点插值节点 求插值函数的方法称为求插值函数的方法称为插值法。插值法。若若xx a,ba,b,需要计算需要计算f(x)f(x)的近似值的近似值(x)(x),则称则称x x为为插值点插值点 第22页，本讲稿共99页 用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。可供选择的函数很多，常用的是多项式函数，因为多项式函数计算

21、可供选择的函数很多，常用的是多项式函数，因为多项式函数计算可供选择的函数很多，常用的是多项式函数，因为多项式函数计算可供选择的函数很多，常用的是多项式函数，因为多项式函数计算简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积分仍为多项式。用多项式作为研究插值的工具，称为代数插值。分仍为多项式。用多项式作为研究插值的工具，称为代数插值。分仍为多项式。用多项式作为研究插值的工具，称为代数插值。分仍为多项式。用多项式作为

22、研究插值的工具，称为代数插值。即求一个次数不超过即求一个次数不超过即求一个次数不超过即求一个次数不超过n n n n次的多项式次的多项式次的多项式次的多项式满足 第23页，本讲稿共99页满足 则称则称P(x)P(x)为为f(x)f(x)的的n n次插值多项式。其几何意义如下图所次插值多项式。其几何意义如下图所示示 第24页，本讲稿共99页定理4.1 n次代数插值问题的解是存在且惟一的 证明:设n次多项式 是函数是函数 在区间在区间 a,ba,b上的上的n+1n+1个互异的节点个互异的节点 (i=0,1,2,i=0,1,2,n),n)上的插值多项式上的插值多项式,则求插值多项式则求插值多项式P(

23、x)P(x)的问题就归结为求它的系数的问题就归结为求它的系数 (i=0,1,2,i=0,1,2,n),n)。由插值条件由插值条件:(:(i=0,1,2,i=0,1,2,n),n),可得可得 这是一个关于待定参数 的n+1阶线性方程组,其系数矩阵行列式为 第25页，本讲稿共99页 称为称为VandermondeVandermonde（范德蒙）行列式，因范德蒙）行列式，因x xi ixxj j（当当ijij），），故故V0V0。根据解线性方程组的克莱姆根据解线性方程组的克莱姆（GramerGramer）法则，方程组的解法则，方程组的解 存在惟一，从而存在惟一，从而P(x)P(x)被惟一确定。被惟一

24、确定。惟一性说明，不论用何种方法来构造，也不论用何种惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式形式来表示插值多项式,只要满足插值条件只要满足插值条件(4.1)4.1)其结其结果都是相互恒等的。果都是相互恒等的。第26页，本讲稿共99页4.3 拉格朗日多项式 (Lagrange)求n次多项式 使得条件：无重合节点，即n=1xx0 x1yy0 y1已知 x0,x1;y0,y1，求使得要构造线性函数要构造线性函数 P1(x)=a0+a1 x ,使满足插值条件使满足插值条件 P1(x0)=y0,P1(x1)=y1.第27页，本讲稿共99页 （线性插值多项式）（线性插值多项式）（

25、拉格朗日线性插值多项式）（拉格朗日线性插值多项式）公式的结构：它是两个一次函数的线性组合公式的结构：它是两个一次函数的线性组合 （线性插值基函数）（线性插值基函数）可见可见P1(x)是过是过(x0,y0)和和(x1,y1)两点的两点的直线。直线。=y0+y1第28页，本讲稿共99页l0(x)l1(x)称为拉氏基函数 满足条件 li(xj)=ij第29页，本讲稿共99页基函数的性质 第30页，本讲稿共99页例4.1 已知 ,求 解解:这里这里x x0 0=100,=100,y y0 0=10,=10,x x1 1=121,=121,y y1 1=11,=11,利用线性插值公式利用线性插值公式 x

26、100 121y10 11第31页，本讲稿共99页这就是二次插值问题。其几何意义是用经过3个点 的抛物线 近似代替曲线 ,如下图所示。因此也称之为抛物插值。xx0 x1 x2yy0 y1 y2抛物插值抛物插值 抛物插值又称二次插值，它也是常用的代数插值之抛物插值又称二次插值，它也是常用的代数插值之 一。设已知一。设已知f(x)f(x)在三个互异点在三个互异点 的函数值的函数值 ，要构造次数不超过二次的多项式要构造次数不超过二次的多项式使满足二次插值条件：n=2第32页，本讲稿共99页P(x)的参数直接由插值条件决定，即 满足下面的代数方程组：该三元一次方程组的系数矩阵 的行列式是范德蒙行列式，

27、当 时，方程组的解唯一。第33页，本讲稿共99页求二次式 ,使其满足条件：仿线性插值,用基函数的方法求解方程组。先考察一个特殊的二次插值问题：这个问题容易求解。由上式的后两个条件知:是 的两个零点。于是 再由另一条件 确定系数 从而导出 第34页，本讲稿共99页类似地可以构造出满足条件：的插值多项式 及满足条件：的插值多项式 这样构造出来的 称为抛物插值的基函数 取已知数据 作为线性组合系数,将基函数 线性组合可得 容易看出,P(x)满足条件 第35页，本讲稿共99页 所以二次插值称之为所以二次插值称之为抛物插值抛物插值 。当三点当三点(x(x0 0,y,y0 0),(x),(x1 1,y,y

28、1 1),(x),(x2 2,y,y2 2)位于一条位于一条直线上时，显然插值函数的图形是直线。直线上时，显然插值函数的图形是直线。第36页，本讲稿共99页 例4.2 已知函数y=f(x)的观测数据如表所示，试求其拉格朗日插值多项式，并计算f(1.5)的近似值。x0 1 2y2 -1 4解解 第37页，本讲稿共99页4.3.2 拉格朗日插值多项式 换句话说换句话说 我们看到,两个插值点可求出一次插值多项式,而三个插值点可求出二次插值多项式。插值点增加到n+1个时,也就是通过n+1个不同的已知点,来构造一个次数为n的代数多项式P(x)。与推导抛物插值的基函数类似,先构造一个特殊n次多项式 的插值

29、问题,使其在各节点 上满足 第38页，本讲稿共99页希望找到希望找到li(x)，i=0,n使得使得 li(xj)=ij；然后令；然后令=niiinyixlxP0)()(，则显然有Pn(xi)=yi。li(x)每个每个li(x)有有n个根个根x0 xi-1、xi+1xn-=j i jiiiixxCxl)(11)(Lagrange 与 有关，而与 无关节点f第39页，本讲稿共99页所以次数不超过所以次数不超过n n次的代数插值多项式。次的代数插值多项式。称为n次拉格朗日插值多项式。记为 ,插值基函数基函数具有性质基函数具有性质:第40页，本讲稿共99页例4.3 已知y=f(x)的函数表 求线性插值

30、多项式,并计算x=1.5 的值X 1 3 y 1 2解解:由线性插值多项式公式得由线性插值多项式公式得第41页，本讲稿共99页例例4.4 4.4 已知已知x=1,4,9 x=1,4,9 的平方根值的平方根值,用抛物插值用抛物插值 公式公式,求求 =2.7=2.64575解：x0=1,x1=4,x2=9y0=1,y1=2,y2=3 第42页，本讲稿共99页例4.5 已知函数y=f(x)在节点上满足求二次多项式 p(x)=a0+a1x+a2x2 使之满足 p(xi)=yi i=0,1,2解上述方程解上述方程,将求出的将求出的a a0 0,a,a1 1,a,a2 2 代入代入p(x)=ap(x)=a

31、0 0+a+a1 1x+ax+a2 2x x2 2 即得所求二次多项式即得所求二次多项式001122xx0 x1x2yy0y1y2解解:用待定系数法用待定系数法,将各节点值依次代入所求多项式将各节点值依次代入所求多项式,得得第43页，本讲稿共99页例4.6 求过点(0,1)、(1,2)、(2,3)的三点插值多项式解解:由由Lagrange Lagrange 插值公式插值公式（给定的三个点在一条直线上）（给定的三个点在一条直线上）第44页，本讲稿共99页例4.7 已知f(x)的观测数据 解解 四个点可构造三次四个点可构造三次LagrangeLagrange插值多项式插值多项式:基函数为基函数为

32、x0124 f(x)19233构造Lagrange插值多项式第45页，本讲稿共99页LagrangeLagrange插值多项式为插值多项式为 为便于上机计算为便于上机计算,常将拉格朗日插值多项式常将拉格朗日插值多项式(5.8)(5.8)改写成改写成第46页，本讲稿共99页 例4.8 已知f(x)的观测数据解解:四个点可以构造三次插值多项式四个点可以构造三次插值多项式,将数据将数据 代入插值公式，有代入插值公式，有这个例子说明这个例子说明p(x)p(x)的项数不超过的项数不超过n+1n+1项项,但可以有缺项但可以有缺项 x1234 f(x)0-5-63构造插值多项式第47页，本讲稿共99页第48

33、页，本讲稿共99页4 4.3 3.3 3 拉拉格格朗朗日日插插值值算算法法实实现现 第49页，本讲稿共99页ax0 x1 xixi+1 xn-1 xny=f(x)y=p(x)b在插值区间a,b上用插值多项式p(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。若记若记 R(x)=f(x)-p(x)R(x)=f(x)-p(x)则则R(x)R(x)就是用就是用p(x)p(x)近似代替近似代替f(x)f(x)时的截断误差时的截断误差,或称插值或称插值余项我们可根据后面的定理来估计它的大小。余项我们可根据后面的定理来估计它的大小。4.3.4 插值多项式的误差 第50页，

34、本讲稿共99页定理定理4.2 4.2 设设f(x)在在 a,b a,b 有有n+1+1阶导数，阶导数，x x0 0,x x1 1,x xn n 为为 a,b 上上n+1个互异的节点个互异的节点,p(x)为满足为满足 p(xi i)=)=f(xi i)()(i i=1,2,=1,2,n n)的的n n 次插值多项式，那么对于任何次插值多项式，那么对于任何x x a,b 有有 a a b b 且依赖于且依赖于x x其中证明 (略)插值余项第51页，本讲稿共99页对于线性插值，其误差为对于线性插值，其误差为对于抛物插值（二次插值），其误差为对于抛物插值（二次插值），其误差为第52页，本讲稿共99页例

35、4.9 已知 =100,=121,用线性插值估计 在x=115时的截断误差解解:由插值余项公式知由插值余项公式知 第53页，本讲稿共99页例4.10 已知x0=100,x1=121,x2=144,当用抛物插值求 在x=115时的近似值，估计其的截断误差 解=第54页，本讲稿共99页例4.11 设f(x)=x4,用余项定理写出节点 -1,0,1,2的三次插值多项式 解解:根据余项定理根据余项定理第55页，本讲稿共99页所谓所谓”曲线拟合曲线拟合”,是指根据给定的数据表是指根据给定的数据表,寻找一个寻找一个简单的表达式来简单的表达式来”拟合拟合”该组数据该组数据,此处的此处的”拟合拟合”的含义的含

36、义为为:不要求该表达式对应的近似曲线完全通过所有的数不要求该表达式对应的近似曲线完全通过所有的数据点据点,只要求该近似曲线能够反映数据的基本变化趋势只要求该近似曲线能够反映数据的基本变化趋势.6 曲线拟合的最小二乘法第56页，本讲稿共99页 如果要求所得的近似函数曲线精确无误地通过所有的点(xi,yi),就会使曲线保留着一切测试误差。当个别数据的误差较大时,插值效果显然是不理想的。此外,由实验或观测提供的数据个数往往很多,如果用插值法,势必得到次数较高的插值多项式，这样计算起来很烦琐。6 曲线拟合的最小二乘法第57页，本讲稿共99页6 曲线拟合的最小二乘法曲线拟合的问题：设函数设函数y=f(x

37、)y=f(x)在在n n个互异点的观测数据为个互异点的观测数据为求一个简单的近似函数求一个简单的近似函数(x)(x)，使之，使之 “最最好好”地逼近地逼近f(x)f(x)，而不必满足插值原则。称函，而不必满足插值原则。称函数数y=(x)y=(x)为拟合曲线或经验公式为拟合曲线或经验公式xi x1 x2 .xnyi y1 y2 .yn第58页，本讲稿共99页换句话说换句话说:求一条曲线求一条曲线,使数据点均在离此曲线的上方使数据点均在离此曲线的上方或下方不远处或下方不远处,它既能反映数据的总体分布它既能反映数据的总体分布,又不至于又不至于出现局部较大的波动出现局部较大的波动,更能反映被逼近函数的

38、特性更能反映被逼近函数的特性,使使求得的逼近函数与已知函数从总体上来说其偏差按某求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小种方法度量达到最小,这就是最小二乘法。这就是最小二乘法。两种逼近概念两种逼近概念:插值插值:在节点处函数在节点处函数 值相同值相同.拟合拟合:在数据点处误在数据点处误 差平方和最小差平方和最小第59页，本讲稿共99页 与函数插值问题不同,曲线拟合不要求曲线通过所有已知点,而是要求得到的近似函数能反映数据的基本关系。在某种意义上,曲线拟合更有实用价值。在对给出的实验在对给出的实验(或观测或观测)数据数据 作曲线拟合时作曲线拟合时,怎样才算拟合得最好呢？一

39、般怎样才算拟合得最好呢？一般希望各实验希望各实验(或观测或观测)数据与拟合曲线的偏差的平方数据与拟合曲线的偏差的平方和最小和最小,这就是最小二乘原理。这就是最小二乘原理。第60页，本讲稿共99页（注意它与插值法的不同）（注意它与插值法的不同）第61页，本讲稿共99页 函数插值是插值函数P(x)与被插函数f(x)在节点处函数值相同,即 而曲线拟合函数 不要求严格地通过所有数据点 ,也就是说拟合函数 在xi处的偏差(亦称残差）不都严格地等于零。不都严格地等于零。第62页，本讲稿共99页 为了使近似曲线能尽量反映所给数据点的变化趋势,要求 按某种度量标准最小。若记向量若记向量 ,即要求向量即要求向量

40、 的的某种范数某种范数 最小最小,如如 的的1-1-范数范数 或或-范数范数 即即 或 最小第63页，本讲稿共99页为了便于计算、分析与应用，通常要求的2-范数 即 为最小。为最小。这种要求误差（偏差）平方和最小的拟合这种要求误差（偏差）平方和最小的拟合称为曲线拟合的最小二乘法。称为曲线拟合的最小二乘法。第64页，本讲稿共99页例例6.1 6.1 某种纤维的强度与其拉伸倍数的关系某种纤维的强度与其拉伸倍数的关系.下表是实际下表是实际测定的测定的2424个纤维样品的强度与相应的拉伸倍数的数据记录个纤维样品的强度与相应的拉伸倍数的数据记录:编号拉伸倍数 强度编号拉伸倍数强度1 1.91.41355

41、.5221.3145.2532.11.81565.542.52.5166.36.452.72.8176.5662.72.5187.15.373.531986.583.52.72087944218.98.51043.52298114.54.2239.58.1124.63.524108.1第65页，本讲稿共99页可以看出可以看出,纤维强度随纤维强度随拉伸倍数增加而增加拉伸倍数增加而增加并且并且2424个点大致分个点大致分布在一条直线附近布在一条直线附近该直线该直线(拟合拟合)称为这一问题的数学模型称为这一问题的数学模型因此可认为强度与因此可认为强度与拉伸倍数之间的主拉伸倍数之间的主要关系是线性关系

42、要关系是线性关系第66页，本讲稿共99页怎样确定怎样确定a,b,a,b,使得直线能较好地反映所给数据的基使得直线能较好地反映所给数据的基本本“变化趋势变化趋势”?一般情况各点误差总误差令问题转化为求参数 使 达到最小值。第67页，本讲稿共99页代入将第68页，本讲稿共99页编号拉伸倍数 强度编号拉伸倍数强度1 1.91.41355.5221.3145.2532.11.81565.542.52.5166.36.452.72.8176.5662.72.5187.15.373.531986.583.52.72087944218.98.51043.52298114.54.2239.58.1124.63

43、.524108.1第69页，本讲稿共99页这种求线性函数这种求线性函数y=a+bxy=a+bx的过程称为直线拟合的过程称为直线拟合。代入得得正规方程组第70页，本讲稿共99页 解:把表中所给数据画在坐标纸上 将会看到数据点的分布可以用 一条直线来近似地描述,设所 求的拟合直线为 例6.2 设有某实验数据如下：i1234xi1.361.371.952.28yi14.09416.84418.47520.963用最小二乘法求以上数据的拟合函数第71页，本讲稿共99页记x1=1.36,x2=1.37,x3=1.95x4=2.28,y1=14.094,y2=16.844,y3=18.475,y4=20.

44、963其中 将以上数据代入上式正规方程组将以上数据代入上式正规方程组,得得第72页，本讲稿共99页解得解得即得拟合直线即得拟合直线 第73页，本讲稿共99页 例6.3 已知实验数据表,用最小二乘法拟合这组数据。解解:作图看出接近一条直线作图看出接近一条直线,设公式为设公式为 x 2 4 6 8y 2 11 28 40正规方程组为正规方程组为 解得解得 得经验公式为得经验公式为 y=-12.5+6.55xy=-12.5+6.55xn=4,第74页，本讲稿共99页 多项式拟合 有时所给数据点的分布并不一定近似地呈一条直线,这时仍用直线拟合显然是不合适的,可用多项式拟合。对于给定的一组数据寻求次数不

45、超过m(mN)的多项式，来拟合所给定的数据，与线性拟合类似，使偏差的来拟合所给定的数据，与线性拟合类似，使偏差的平方和平方和为最小为最小第75页，本讲稿共99页 由由于于Q Q可可以以看看作作是是关关于于 (j=0,1,2,j=0,1,2,m)m)的的多多元元函函数数,故故上上述述拟拟合合多多项项式式的的构构造造问问题题可可归归结结为为多多元元函函数的极值问题。令数的极值问题。令得 即有即有 第76页，本讲稿共99页这是关于系数 的线性方程组，通常称为正规方程组。可以证明，正规方程组有惟一解。（6.1）第77页，本讲稿共99页用最小二乘法求一个多项式拟合这组数据 i123456xi012345

46、yi521123例6.4 设某实验数据如下：解：将已给数据点描在坐标解：将已给数据点描在坐标系中，可以看出这些点接系中，可以看出这些点接近一条抛物线，因此设所近一条抛物线，因此设所求的多项式为求的多项式为第78页，本讲稿共99页由正规方程组（6.1）,经计算得 N=6其法方程组为 解之得 所求的多项式为所求的多项式为第79页，本讲稿共99页所求的多项式为所求的多项式为第80页，本讲稿共99页（3）可化为线性拟合的非线性拟合 有些非线性拟合曲线可以通过适当的变量替换转化为线性曲线，从而用线性拟合进行处理，对于一个实际的曲线拟合问题，一般先按观测值在直角坐标平面上描出散点图，看一看散点的分布同哪类

47、曲线图形接近，然后选用相接近的曲线拟合方程。再通过适当的变量替换转化为线性拟合问题，按线性拟合解出后再还原为原变量所表示的曲线拟合方程。表6-1列举了几类经适当变换后化为线性拟合求解的曲线拟合方程及变换关系 第81页，本讲稿共99页表6-1 曲线拟合方程 变换关系 变换后线性拟合方程第82页，本讲稿共99页几种常见的数据拟合情况。图(a)表示数据接近于直线，故宜采用线性函数 拟合；图(b)数据分布接近于抛物线。可采拟合；二次多项式 拟合；(a)(b)第83页，本讲稿共99页图(c)的数据分布特点是开始曲线上升较快随后逐渐变慢,宜采用双曲线型函数 或指数型函数 图(d)的数据分布特点是开始曲线下

48、降快,随后逐渐变慢,宜采用 或 或 等数据拟合。(c)(d)第84页，本讲稿共99页用最小二乘法求拟合曲线 解:将已给数据点描在坐标系中下图所示,可以看出这些点接近指数曲线,因而可取指数函数作为拟合函数.例6.5 设某实验数据如下:i123456xi00.511.522.5yi210.90.60.40.3第85页，本讲稿共99页对函数 两边取对数得.令 则就得到线性模型 则正规方程组为则正规方程组为其中 第86页，本讲稿共99页将以上数据代入上式正规方程组，得由 得代入代入于是得到拟合指数函数为于是得到拟合指数函数为 解得 第87页，本讲稿共99页的图形如下所示的图形如下所示第88页，本讲稿共

49、99页例6.6 求一个经验函数 使它与观测数据拟合 x12345678y14.320.527.436.649.164.687.8117.6解解 对公式两边取对数得对公式两边取对数得 正规方程组为正规方程组为 则得到线性模型则得到线性模型第89页，本讲稿共99页第90页，本讲稿共99页 （4 4）超定方程组的最小二乘解）超定方程组的最小二乘解设线性方程组设线性方程组Ax=bAx=b中，中，,b b是是m m维已知向量，维已知向量，x x是是n n维解向量，当维解向量，当m mn n，即方程组中方程的个数多于未知即方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说，量的个数时，

50、称此方程组为超定方程组。一般来说，超定方程组无解（此时为矛盾方程组超定方程组无解（此时为矛盾方程组),),这时需要寻求这时需要寻求方程组的一个方程组的一个“最近似最近似”的解的解.记记 ,称使称使 ,即即 最小的解最小的解 为方程组为方程组Ax=bAx=b的最小二乘解。的最小二乘解。第91页，本讲稿共99页定理6.1 是Ax=b的最小二乘解的充分必要条件为 是 的解.（证明见教材）第92页，本讲稿共99页例6.7 求超定方程组 的最小二乘解,并求误差平方和。解解:方程组写成矩阵形式为方程组写成矩阵形式为正规方程组为正规方程组为第93页，本讲稿共99页即 解得 此时 误差平方和为误差平方和为 第