计算思维与计算方法精选文档.ppt

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

1、本讲稿第一页，共九十九页&参考书目参考书目计算方法计算方法刘师少刘师少编著编著（科学出版社，（科学出版社，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本讲稿第二页，共九十九页 了解计算思维的基本内容，了解人与了解计算思维的基本内容，了解人与 计算机器能力计算机器能力 的局限性，了解计算思维解决问题的一般步骤的局限性，了解计算思维解决问题的一般步骤.1、基本要求、基本要求1 理解计算思维在问题解决过程中所发挥的作用理解计算思

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

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

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

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

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

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

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

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

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

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

13、法所面对的正是“模型求解模型求解”，或者说求模，或者说求模型的数值解。因此我们不能把型的数值解。因此我们不能把“计算方法计算方法”理解为理解为“计计算算”的的“方法方法”，而应理解为利用计算工具求解复杂数，而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。学问题的方法论和基本方法。本讲稿第十五页，共九十九页我们我们所讲述的算法只限于计算机算法，即计算机能执行的所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。算法。在设计一个计算机算法时，应当考虑到计算机能否执行。计算机算法可分为两大类别：数值运算和非数值运计算机算法可分为两大类别：数

14、值运算和非数值运算。算。数值运算的目的是求数值解，例如函数插值、曲线拟合数值运算的目的是求数值解，例如函数插值、曲线拟合的最小二乘法等，都属于数值运算范围。的最小二乘法等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用于事非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如教务管理、学籍管理等。目前，计算务管理领域，例如教务管理、学籍管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面机在非数值运算方面的应用远远超过了在数值运算方面的应用的应用注意：注意：不论是哪类方式，对它们的基本要求都是能提供对算法不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义

15、的描述，以便使我们能够将这种描述很容易转换的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。成计算机高级语言（程序）。本讲稿第十六页，共九十九页4.1 4.1 问题的提出问题的提出 在生产实际中，连续函数往往只能由若干个离散点上的在生产实际中，连续函数往往只能由若干个离散点上的值来表示，而难以得到具体的解析式值来表示，而难以得到具体的解析式4 4 插值插值 25.6 25.6 27.2 27.2 36.9 36.9 34.4 34.4 26.8 26.8 24.3 24.3 4 4 8 8 12 12 16 16 20 20 24 24温度（温度（）时间（时）时间（时

16、）Co本讲稿第十七页，共九十九页 每隔每隔4 4小时记录一次温小时记录一次温度，以反映某地一天的度，以反映某地一天的气温变化状况气温变化状况那么如何利用离散点值那么如何利用离散点值来推测其余点上的函数来推测其余点上的函数值值,(如如1111、1515、1919点温度点温度),从而反映被测函数的从而反映被测函数的整体状况呢？整体状况呢？构造这个函数过构造这个函数过程就称为插值程就称为插值方法方法:构造一个通过所有构造一个通过所有离散测试点的函数，用离散测试点的函数，用这个函数来逼近被测函这个函数来逼近被测函数。数。本讲稿第十八页，共九十九页 还有许多这样的实例还有许多这样的实例函数解析式未知函数

17、解析式未知,通过实验观测得到的一组数据通过实验观测得到的一组数据,即在某个区即在某个区间间 a,ba,b上给出一系列点的函数值上给出一系列点的函数值 yi=f(xi)或者给出函数表，希望构出能近似代替原来的函数或者给出函数表，希望构出能近似代替原来的函数y=f(x)y=p(x)xx0 x1x2xnyy0y1y2yn本讲稿第十九页，共九十九页 动物实验中心为白鼠服用了某种新产品药物后，在对动物实验中心为白鼠服用了某种新产品药物后，在对1 1对对白鼠在周内的食物消费量（克白鼠在周内的食物消费量（克,x)及及6 6周间增加的体（克周间增加的体（克,y)y)测测量数据如下量数据如下:i123456 x

18、i568608 636 636660 684 yi106126 134 134128 158 试确定白鼠体重试确定白鼠体重 y y 与白鼠之食物消费与白鼠之食物消费量量x x 的函数关系的函数关系 y=f(x)y=f(x)那么，左边图那么，左边图形的形的y=f(x)y=f(x)解析解析函数如何求呢？函数如何求呢？本讲稿第二十页，共九十九页血药浓度问题血药浓度问题,为试验某种新药的疗效为试验某种新药的疗效,研究人员对志愿者研究人员对志愿者用快速静脉注射方式一次注入该药用快速静脉注射方式一次注入该药30mg30mg（毫克）后（毫克）后,在一定在一定的时刻的时刻t(h)t(h)采取血样采取血样,测得

19、血药浓度测得血药浓度C(g/ml)C(g/ml)（微克毫升）（微克毫升）数据如下数据如下:试确定血药浓度试确定血药浓度C C与时间与时间 t t 的函数关系的函数关系 C=f(t)i123456789t(h)0.250.511.523468C(g/ml)19.21 18.15 15.36 14.1 12.9 9.32 7.45 5.24 3.01本讲稿第二十一页，共九十九页4.2 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

20、是区间是区间 a a,b b 上的互异点，要构造一个简上的互异点，要构造一个简单的函数单的函数(x)(x)作为作为f f(x x)的近似表达式，使满足的近似表达式，使满足(插值原则、插值条件插值原则、插值条件)这类问题称为这类问题称为插值问题。插值问题。-f f(x x)的的插值函数插值函数,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为为插值点插值点 本讲稿第二十二页

21、，共九十九页 用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。用插值法求函数的近似表达式时，首先要选定函数的形式。可供选择的函数很多，常用的是多项式函数，因为多项式函数可供选择的函数很多，常用的是多项式函数，因为多项式函数可供选择的函数很多，常用的是多项式函数，因为多项式函数可供选择的函数很多，常用的是多项式函数，因为多项式函数计算简便，只需用加、减、乘等运算，便于上机计算，而且其计算简便，只需用加、减、乘等运算，便于上机计算，而且其计算简便，只需用加、减、乘等运算，便于上机计算，而且其

22、计算简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积分仍为多项式。用多项式作为研究插值的工具，称为导数与积分仍为多项式。用多项式作为研究插值的工具，称为导数与积分仍为多项式。用多项式作为研究插值的工具，称为导数与积分仍为多项式。用多项式作为研究插值的工具，称为代数插值。代数插值。代数插值。代数插值。即求一个次数不超过即求一个次数不超过即求一个次数不超过即求一个次数不超过n n n n次的多项式次的多项式满足满足 本讲稿第二十三页，共九十九页满足满足则称则称P(x)P(x)为为f(x)f(x)的的n n次插值多项式。其几何意义如下图所示次插值多项式。其几何意义如下图所示 本讲稿第二十四

23、页，共九十九页定理定理4.1 n4.1 n次代数插值问题的解是存在且惟一的次代数插值问题的解是存在且惟一的 证明证明:设设n n次多项式次多项式 是函数是函数 在区间在区间 a,ba,b上的上的n+1n+1个互异的节点个互异的节点 (i=0,1,2,i=0,1,2,n),n)上的插值多项式上的插值多项式,则求插值多项式则求插值多项式P(x)P(x)的问题就归结为求它的系数的问题就归结为求它的系数 (i=0,1,2,i=0,1,2,n),n)。由插值条件由插值条件:(:(i=0,1,2,i=0,1,2,n),n),可得可得 这是一个关于待定参数这是一个关于待定参数 的的n+1n+1阶线性方阶线性

24、方程组程组,其系数矩阵行列式为其系数矩阵行列式为 本讲稿第二十五页，共九十九页 称为称为VandermondeVandermonde（范德蒙）行列式，因范德蒙）行列式，因x xi ixxj j（当当ijij），），故故V0V0。根据解线性方程组的克莱姆根据解线性方程组的克莱姆（GramerGramer）法则，方程组的解法则，方程组的解 存在惟一，从而存在惟一，从而P(x)P(x)被惟一确定。被惟一确定。惟一性说明，不论用何种方法来构造，也不论用何种形惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式式来表示插值多项式,只要满足插值条件只要满足插值条件(4.1)4.1)其结果都其

25、结果都是相互恒等的。是相互恒等的。本讲稿第二十六页，共九十九页4.3 4.3 拉格朗日多项式拉格朗日多项式 (Lagrange)Lagrange)求求n次多项式次多项式 使得使得条件：条件：无重合节点，即无重合节点，即n=1xx0 x1yy0 y1已知已知x0,x1;y0,y1，求，求使得使得要构造线性函数要构造线性函数 P1(x)=a0+a1 x ,使满足插值条件使满足插值条件 P1(x0)=y0,P1(x1)=y1.本讲稿第二十七页，共九十九页 （线性插值多项式）（线性插值多项式）（拉格朗日线性插值多项式）（拉格朗日线性插值多项式）公式的结构：它是两个一次函数的线性组合公式的结构：它是两个

26、一次函数的线性组合 （线性插值基函数）（线性插值基函数）可见可见P1(x)是过是过(x0,y0)和和(x1,y1)两点的两点的直线。直线。=y0+y1本讲稿第二十八页，共九十九页l0(x)l1(x)称为拉氏基函数 满足条件 li(xj)=ij本讲稿第二十九页，共九十九页基函数的性质基函数的性质 本讲稿第三十页，共九十九页例例4.1 4.1 已知已知 ,求求 解解:这里这里x x0 0=100,=100,y y0 0=10,=10,x x1 1=121,=121,y y1 1=11,=11,利用线性插值公式利用线性插值公式 x100 121y10 11本讲稿第三十一页，共九十九页这就是二次插值问

27、题。其几何意义是用经过这就是二次插值问题。其几何意义是用经过3 3个点个点 的抛物线的抛物线 近似代替曲线近似代替曲线 ,如下图所示。因此也称之为抛物插值。如下图所示。因此也称之为抛物插值。xx0 x1 x2yy0 y1 y2抛物插值抛物插值 抛物插值又称二次插值，它也是常用的代数插值之抛物插值又称二次插值，它也是常用的代数插值之 一。设一。设已知已知f(x)f(x)在三个互异点在三个互异点 的函数值的函数值 ，要构造次数不超过二次的多项式要构造次数不超过二次的多项式使满足二次插值条件：使满足二次插值条件：n=2本讲稿第三十二页，共九十九页P(x)P(x)的参数的参数直接由插值条件决定，直接由

28、插值条件决定，即即 满足下面满足下面的代数方程组：的代数方程组：该三元一该三元一次方程组次方程组的系数矩阵的系数矩阵的行列式是范德蒙行列式，当的行列式是范德蒙行列式，当 时，时，方程组的解唯一。方程组的解唯一。本讲稿第三十三页，共九十九页求二次式求二次式 ,使其满足条件：使其满足条件：仿线性插值仿线性插值,用基函数的方法求解方程组。先考察一个特殊的用基函数的方法求解方程组。先考察一个特殊的二次插值问题：二次插值问题：这个问题容易求解。由上式的后两个条件知这个问题容易求解。由上式的后两个条件知:是是 的两个零点。于是的两个零点。于是 再由另一条件再由另一条件 确定系数确定系数 从而导出从而导出

29、本讲稿第三十四页，共九十九页类似地可以构造出满足条件：类似地可以构造出满足条件：的插值多项式的插值多项式及满足条件：及满足条件：的插值多项式的插值多项式这样构造出来的这样构造出来的 称为抛物插值的基函数称为抛物插值的基函数 取已知数据取已知数据 作为线性组合系数作为线性组合系数,将基函数将基函数 线性组合可得线性组合可得 容易看出容易看出,P(x)P(x)满足条件满足条件 本讲稿第三十五页，共九十九页 所以二次插值称之为所以二次插值称之为抛物插值抛物插值 。当三点当三点(x(x0 0,y,y0 0),(x),(x1 1,y,y1 1),(x),(x2 2,y,y2 2)位于一条直线位于一条直线

30、上时，显然插值函数的图形是直线。上时，显然插值函数的图形是直线。本讲稿第三十六页，共九十九页例例4.2 4.2 已知函数已知函数y y=f f(x x)的观测数据如表所示，试求其拉的观测数据如表所示，试求其拉格朗日插值多项式，并计算格朗日插值多项式，并计算f f(1.5)(1.5)的近似值。的近似值。x0 1 2y2 -1 4解解 本讲稿第三十七页，共九十九页4.3.2 4.3.2 拉格朗日插值多项式拉格朗日插值多项式 换句话说换句话说 我们看到我们看到,两个插值点可求出一次插值多项式两个插值点可求出一次插值多项式,而而三个插值点可求出二次插值多项式。插值点增加到三个插值点可求出二次插值多项式

31、。插值点增加到n+1n+1个时个时,也就是通过也就是通过n+1n+1个不同的已知点个不同的已知点,来构造一个次数为来构造一个次数为n n的代数多项式的代数多项式P(x)P(x)。与推导抛物插与推导抛物插值的基函数类似值的基函数类似,先构造一个特殊先构造一个特殊n n次多项式次多项式 的的插值问题插值问题,使其在各节点使其在各节点 上满足上满足 本讲稿第三十八页，共九十九页希望找到希望找到li(x)，i=0,n使得使得 li(xj)=ij；然后令；然后令=niiinyixlxP0)()(，则显然有，则显然有Pn(xi)=yi。li(x)每个每个li(x)有有n个根个根x0 xi-1、xi+1xn

32、-=j i jiiiixxCxl)(11)(Lagrange 与 有关，而与 无关节点节点f本讲稿第三十九页，共九十九页所以次数不超过所以次数不超过n n次的代数插值多项式。次的代数插值多项式。称为称为n n次拉格朗日插值多项式。记为次拉格朗日插值多项式。记为 ,插值基函数插值基函数基函数具有性质基函数具有性质:本讲稿第四十页，共九十九页例例4.3 4.3 已知已知y=f(x)y=f(x)的函数表的函数表 求线性插值多项式求线性插值多项式,并计算并计算x=1.5 x=1.5 的值的值X 1 3 y 1 2解解:由线性插值多项式公式得由线性插值多项式公式得本讲稿第四十一页，共九十九页例例4.4

33、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 本讲稿第四十二页，共九十九页例例4.5 4.5 已知函数已知函数y=f(x)y=f(x)在节点上满足在节点上满足求二次多项式求二次多项式 p p(x)=a(x)=a0 0+a+a1 1x+ax+a2 2x x2 2 使之满足使之满足 p p(x(xi i)=y)=yi i i=0,1,2i=0,1,2解上述方程解上述方程,将求出的将求出的a a0 0,a,a1 1,a,a2 2 代入代入p(x)=a

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

35、据 解解 四个点可构造三次四个点可构造三次LagrangeLagrange插值多项式插值多项式:基函数为基函数为 x0124 f(x)19233构造构造LagrangeLagrange插值多项式插值多项式本讲稿第四十五页，共九十九页LagrangeLagrange插值多项式为插值多项式为 为便于上机计算为便于上机计算,常将拉格朗日插值多项式常将拉格朗日插值多项式(5.8)(5.8)改写成改写成本讲稿第四十六页，共九十九页例例4.8 4.8 已知已知f(x)f(x)的观测数据的观测数据解解:四个点可以构造三次插值多项式四个点可以构造三次插值多项式,将数据将数据 代入插值公式，有代入插值公式，有这

36、个例子说明这个例子说明p(x)p(x)的项数不超过的项数不超过n+1n+1项项,但可以有缺项但可以有缺项 x1234 f(x)0-5-63构造插值多项式构造插值多项式本讲稿第四十七页，共九十九页本讲稿第四十八页，共九十九页4 4.3 3.3 3 拉拉格格朗朗日日插插值值算算法法实实现现 本讲稿第四十九页，共九十九页ax0 x1xixi+1xn-1xny=f(x)y=p(x)b在插值区间在插值区间 a,ba,b 上用上用插值多项式插值多项式p(x)p(x)近似代替近似代替f(x),f(x),除了除了在插值节点在插值节点x xi i上没有误差外，在其它点上一般是存在误差的。上没有误差外，在其它点上

37、一般是存在误差的。若记若记 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 4.3.4 插值多项式的误差插值多项式的误差本讲稿第五十页，共九十九页定理定理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

38、i)()(i i=1,2,=1,2,n n)的的n n 次插值多项式，那么对于任何次插值多项式，那么对于任何x x a,b 有有 a a b b 且依赖于且依赖于x x其中其中证明证明 (略略)插值余项插值余项本讲稿第五十一页，共九十九页对于线性插值，其误差为对于线性插值，其误差为对于抛物插值（二次插值），其误差为对于抛物插值（二次插值），其误差为本讲稿第五十二页，共九十九页例例4.9 4.9 已知已知 =100,=121,=100,=121,用线性插值估计用线性插值估计 在在x=115x=115时的截断误差时的截断误差解解:由插值余项公式知由插值余项公式知 本讲稿第五十三页，共九十九页例例4

39、.10 4.10 已知已知x x0 0=100,x=100,x1 1=121,x=121,x2 2=144,=144,当用抛物插值求当用抛物插值求 在在x=115x=115时的近似值，估计其的截断误差时的近似值，估计其的截断误差解解=本讲稿第五十四页，共九十九页例例4.11 4.11 设设f f(x x)=x)=x4 4,用余项定理写出节点用余项定理写出节点 -1,0,1,2 -1,0,1,2的三次插值多项式的三次插值多项式解解:根据余项定理根据余项定理本讲稿第五十五页，共九十九页所谓所谓”曲线拟合曲线拟合”,是指根据给定的数据表是指根据给定的数据表,寻找一个寻找一个简单的表达式来简单的表达式

40、来”拟合拟合”该组数据该组数据,此处的此处的”拟合拟合”的含义的含义为为:不要求该表达式对应的近似曲线完全通过所有的数不要求该表达式对应的近似曲线完全通过所有的数据点据点,只要求该近似曲线能够反映数据的基本变化趋势只要求该近似曲线能够反映数据的基本变化趋势.6 6 曲线拟合的最小二乘法曲线拟合的最小二乘法本讲稿第五十六页，共九十九页 如如果果要要求求所所得得的的近近似似函函数数曲曲线线精精确确无无误误地地通通过过所所有有的的点点(x xi i,y,yi i),),就就会会使使曲曲线线保保留留着着一一切切测测试试误误差差。当当个个别别数数据据的的误误差差较较大大时时,插插值值效效果果显显然然是是

41、不不理理想想的的。此此外外,由由实实验验或或观观测测提提供供的的数数据据个个数数往往往往很很多多,如如果果用用插插值值法法,势势必必得得到到次次数数较较高高的的插插值值多多项项式式，这这样样计计算起来很烦琐。算起来很烦琐。6 6 曲线拟合的最小二乘法曲线拟合的最小二乘法本讲稿第五十七页，共九十九页6 6 曲线拟合的最小二乘法曲线拟合的最小二乘法曲线拟合的问题：曲线拟合的问题：设函数设函数y=f(x)y=f(x)在在n n个互异点的观测数据为个互异点的观测数据为求一个简单的近似函数求一个简单的近似函数(x)(x)，使之，使之 “最好最好”地逼近地逼近f(x)f(x)，而不必满足插值原则。称函数，

42、而不必满足插值原则。称函数y=(x)y=(x)为拟合曲线或经验公式为拟合曲线或经验公式xi x1 x2 .xnyi y1 y2 .yn本讲稿第五十八页，共九十九页换句话说换句话说:求一条曲线求一条曲线,使数据点均在离此曲线的上方或下方不使数据点均在离此曲线的上方或下方不远处远处,它既能反映数据的总体分布它既能反映数据的总体分布,又不至于出现局部较大的波又不至于出现局部较大的波动动,更能反映被逼近函数的特性更能反映被逼近函数的特性,使求得的逼近函数与已知函数使求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小从总体上来说其偏差按某种方法度量达到最小,这就是最小二乘这就是最小二乘法。

43、法。两种逼近概念两种逼近概念:插值插值:在节点处函数在节点处函数 值相同值相同.拟合拟合:在数据点处误在数据点处误 差平方和最小差平方和最小本讲稿第五十九页，共九十九页 与与函函数数插插值值问问题题不不同同,曲曲线线拟拟合合不不要要求求曲曲线线通通过过所所有有已已知知点点,而而是是要要求求得得到到的的近近似似函函数数能能反反映映数数据据的的基基本本关关系系。在在某某种种意意义上义上,曲线拟合更有实用价值。曲线拟合更有实用价值。在对给出的实验在对给出的实验(或观测或观测)数据数据 作曲线拟合时作曲线拟合时,怎样才算拟合得最好呢？一般希怎样才算拟合得最好呢？一般希望各实验望各实验(或观测或观测)数

44、据与拟合曲线的偏差的平方和最数据与拟合曲线的偏差的平方和最小小,这就是最小二乘原理。这就是最小二乘原理。本讲稿第六十页，共九十九页（注意它与插值法的不同）（注意它与插值法的不同）本讲稿第六十一页，共九十九页 函数插值是插值函数函数插值是插值函数P(x)P(x)与被插函数与被插函数f(x)f(x)在节点在节点处函数值相同处函数值相同,即即 而曲线拟合函数而曲线拟合函数 不要求严格地通过所有数据不要求严格地通过所有数据点点 ,也就是说拟合函数也就是说拟合函数 在在x xi i处的偏差处的偏差(亦亦称残差）称残差）不都严格地等于零。不都严格地等于零。本讲稿第六十二页，共九十九页 为为了了使使近近似似

45、曲曲线线能能尽尽量量反反映映所所给给数数据据点点的的变变化化趋趋势势,要求要求 按某种度量标准最小。按某种度量标准最小。若记向量若记向量 ,即要求向量即要求向量 的的某种范数某种范数 最小最小,如如 的的1-1-范数范数 或或-范数范数 即即 或或 最小最小本讲稿第六十三页，共九十九页为了便于计算、分析与应用，通常要求为了便于计算、分析与应用，通常要求的的2-2-范数范数 即即 为最小。为最小。这种要求误差（偏差）平方和最小的拟合这种要求误差（偏差）平方和最小的拟合称为曲线拟合的最小二乘法。称为曲线拟合的最小二乘法。本讲稿第六十四页，共九十九页例例6.1 6.1 某种纤维的强度与其拉伸倍数的关

46、系某种纤维的强度与其拉伸倍数的关系.下表是实际测定的下表是实际测定的2424个纤维样品的强度与相应的拉伸倍数的数据记录个纤维样品的强度与相应的拉伸倍数的数据记录:编号拉伸倍数 强度编号拉伸倍数强度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.524108.1本讲稿第六十五页，共九十九页可以看出可以看出,纤维强度随纤维强度随拉伸倍数增加而增加拉伸倍数增

47、加而增加并且并且2424个点大致分个点大致分布在一条直线附近布在一条直线附近该直线该直线(拟合拟合)称为这一问题的数学模型称为这一问题的数学模型因此可认为强度与因此可认为强度与拉伸倍数之间的主拉伸倍数之间的主要关系是线性关系要关系是线性关系本讲稿第六十六页，共九十九页怎样确定怎样确定a,b,a,b,使得直线能较好地反映所给数据的基使得直线能较好地反映所给数据的基本本“变化趋势变化趋势”?一般情况一般情况各点误差各点误差总误差总误差令令问题转化为求参数问题转化为求参数 使使 达到最小值。达到最小值。本讲稿第六十七页，共九十九页代入代入将将本讲稿第六十八页，共九十九页编号拉伸倍数 强度编号拉伸倍数

48、强度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.524108.1本讲稿第六十九页，共九十九页这种求线性函数这种求线性函数y=a+bxy=a+bx的过程称为直线拟合的过程称为直线拟合。代入代入得得正规方程组本讲稿第七十页，共九十九页 解解:把表中所给数据画在坐标纸上把表中所给数据画在坐标纸上 将会看到数据点的分布可以用将会看到数据点的分布可以用 一条

49、直线来近似地描述一条直线来近似地描述,设所设所 求的拟合直线为求的拟合直线为 例例6.2 6.2 设有某实验数据如下：设有某实验数据如下：i1234xi1.361.371.952.28yi14.09416.84418.47520.963用最小二乘法求以上数据的拟合函数用最小二乘法求以上数据的拟合函数本讲稿第七十一页，共九十九页记记x x1 1=1.36,=1.36,x x2 2=1.37,=1.37,x x3 3=1.95=1.95x x4 4=2.28,y=2.28,y1 1=14.094,y=14.094,y2 2=16.844,y=16.844,y3 3=18.475,y=18.475,

50、y4 4=20.963=20.963其中其中 将以上数据代入上式正规方程组将以上数据代入上式正规方程组,得得本讲稿第七十二页，共九十九页解得解得即得拟合直线即得拟合直线 本讲稿第七十三页，共九十九页例例6.3 6.3 已知实验数据表已知实验数据表,用最小二乘法拟合这组数据。用最小二乘法拟合这组数据。解解:作图看出接近一条直线作图看出接近一条直线,设公式为设公式为 x 2 4 6 8y 2 11 28 40正规方程组为正规方程组为 解得解得 得经验公式为得经验公式为 y=-12.5+6.55xy=-12.5+6.55xn=4,本讲稿第七十四页，共九十九页 多项式拟合多项式拟合 有时所给数据点的分