计算思维与计算方法PPT课件

参考书目计算方法刘师少编著（科学出版社，2011年修订版）数值计算张军等编著（清华大学出版社,2008年）,参考资料1周以真.计算思维.中国计算机学会通讯,2007,3(11)2王飞跃.从计算思维到计算文化J.中国计算机学会通讯，2007，3(11).3何钦铭等.计算机基础教学的核心任务是计算思维能力的培养九校联盟（C9）计算机基础教学发展战略联合声明解读J.中国大学教学，2010(9).4郑毓信,肖柏荣,熊萍.数学思维与数学方法论M.四川教育出版社，2001,了解计算思维的基本内容，了解人与计算机器能力的局限性，了解计算思维解决问题的一般步骤.,1、基本要求,理解计算思维在问题解决过程中所发挥的作用,掌握计算机解决实际问题的一般步骤以及常用的医学信息处理（计算）算法（计算方法）。,计算思维的概念,2、教学内容,计算方法概念及其研究对象与特点,插值法语曲线拟合的最小二乘法,考核方式,选择下列主题之一,完成综述：1.医学院校学生应具有的计算思维能力2.最小二乘法在医学信息处理中的应用3.插值法在医学信息处理中的应用要求3500字以上,表格下载：,文献综述以学号+姓名作为文件名上传至个人账号下,要求：,截止日期2011.12.31,3、计算思维的概念,国际上广泛认同的计算思维定义来自周以真（JeannetteWing）教授。周教授认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解的涵盖计算机科学之广度的一系列思维活动。,是抽象和自动化如同所有人都具备“读、写、算”能力一样，计算思维是必须具备的思维能力。,计算思维的本质,计算思维是通过约简、嵌入、转化和仿真等方法，把一个困难的问题阐释为如何求解它的思维方法。,计算思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法,3.1计算思维更细致的阐述,计算思维是一种采用抽象和分解的方法来控制庞杂的任务或进行巨型复杂系统的设计，是基于关注点分离的方法（SoC方法）。,计算思维是一种选择合适的方式去陈述一个问题,或对一个问题的相关方面建模使其易于处理的思维方法.,计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法。,计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法。,计算思维是利用海量数据来加快计算，在时间和空间之间、在处理能力和存储容量之间进行折中的思维方法,计算思维是一种根本技能，是每一个人为了在现代社会中发挥职能所必须掌握的。,计算思维是人类求解问题的一条途径,特别注意,计算思维是思想，不是人造品。重要的是计算的概念，它被人们用来求解问题、管理日常生活以及与他人进行交流和互动。,计算思维是数学与工程思维的互补与融合，它作为一个问题解决的有效工具，人人都应掌握，处处都会被使用。,3.2计算思维与计算方法联系与区别,计算思维是一种选择合适的方式陈述一个问题或对一个问题的相关方面建模使其易于处理的思维方法。,计算方法又称“数值分析”。是求解各类数学问题的数值解的方法，是研究分析用计算机求解数学计算问题的数值计算方法及其理论的学科，是基于计算机考虑问题求解,3.2计算思维与计算方法联系与区别,计算思维与计算方法互补性很强,可以相互促进。,计算方法可以对计算思维研究方面取得的成果进行再研究和吸收,最终丰富计算方法的内容。,计算思维的重要作用也可以通过计算方法得到更好的提高。,3.3用计算机解决实际问题的一般步骤是：,前三步为建模，集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。后两步为模型求解，集中于选择某一种程序设计语言，把算法表达给特定的计算机。,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,1.对于要解决的问题建立数学模型2.研究用于求解该数学问题近似解的算法和过程3.按照2进行计算，得到计算结果,换句话说,由此可见。由数学模型找到求解方法的过程，是计算方法要研究的核心问题。也是计算思维涵盖的内容。,计算方法所面对的正是“模型求解”，或者说求模型的数值解。因此我们不能把“计算方法”理解为“计算”的“方法”，而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。,我们所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。,计算机算法可分为两大类别：数值运算和非数值运算。数值运算的目的是求数值解，例如函数插值、曲线拟合的最小二乘法等，都属于数值运算范围。,非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如教务管理、学籍管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用,注意：不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。,4.1问题的提出在生产实际中，连续函数往往只能由若干个离散点上的值来表示，而难以得到具体的解析式,4插值,o,每隔4小时记录一次温度，以反映某地一天的气温变化状况,那么如何利用离散点值来推测其余点上的函数值,(如11、15、19点温度),从而反映被测函数的整体状况呢？,构造这个函数过程就称为插值,方法:构造一个通过所有离散测试点的函数，用这个函数来逼近被测函数。,还有许多这样的实例函数解析式未知,通过实验观测得到的一组数据,即在某个区间a,b上给出一系列点的函数值yi=f(xi)或者给出函数表，希望构出能近似代替原来的函数,y=f(x),y=p(x),动物实验中心为白鼠服用了某种新产品药物后，在对1对白鼠在周内的食物消费量（克,x)及6周间增加的体（克,y)测量数据如下:,试确定白鼠体重y与白鼠之食物消费量x的函数关系y=f(x),那么，左边图形的y=f(x)解析函数如何求呢？,血药浓度问题,为试验某种新药的疗效,研究人员对志愿者用快速静脉注射方式一次注入该药30mg（毫克）后,在一定的时刻t(h)采取血样,测得血药浓度C(g/ml)（微克毫升）数据如下:,试确定血药浓度C与时间t的函数关系C=f(t),4.2插值法的基本原理,函数y=f(x)给出一组函数值,x:x0 x1x2xny:y0y1y2yn,其中x0,x1,x2,xn是区间a,b上的互异点，要构造一个简单的函数(x)作为f(x)的近似表达式，使满足,(插值原则、插值条件),这类问题称为插值问题。,-f(x)的插值函数,f(x)-被插值函数,x0,x1,x2,xn-插值节点,求插值函数的方法称为插值法。,若xa,b,需要计算f(x)的近似值(x),则称x为插值点,用插值法求函数的近似表达式时，首先要选定函数的形式。可供选择的函数很多，常用的是多项式函数，因为多项式函数计算简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积分仍为多项式。用多项式作为研究插值的工具，称为代数插值。,即求一个次数不超过n次的多项式,满足,满足,则称P(x)为f(x)的n次插值多项式。其几何意义如下图所示,定理4.1n次代数插值问题的解是存在且惟一的,证明:设n次多项式,是函数在区间a,b上的n+1个互异的节点(i=0,1,2,n)上的插值多项式,则求插值多项式P(x)的问题就归结为求它的系数(i=0,1,2,n)。,由插值条件:(i=0,1,2,n),可得,这是一个关于待定参数的n+1阶线性方程组,其系数矩阵行列式为,称为Vandermonde（范德蒙）行列式，因xixj（当ij），故V0。根据解线性方程组的克莱姆（Gramer）法则，方程组的解存在惟一，从而P(x)被惟一确定。,惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式,只要满足插值条件(4.1)其结果都是相互恒等的。,4.3拉格朗日多项式(Lagrange),求n次多项式使得,条件：无重合节点，即,n=1,要构造线性函数P1(x)=a0+a1x,使满足插值条件P1(x0)=y0,P1(x1)=y1.,（线性插值多项式）,（拉格朗日线性插值多项式）,公式的结构：它是两个一次函数的线性组合,（线性插值基函数）,可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。,称为拉氏基函数满足条件li(xj)=ij,基函数的性质,例4.1已知,求,解:这里x0=100,y0=10,x1=121,y1=11,利用线性插值公式,这就是二次插值问题。其几何意义是用经过3个点的抛物线近似代替曲线,如下图所示。因此也称之为抛物插值。,抛物插值抛物插值又称二次插值，它也是常用的代数插值之一。设已知f(x)在三个互异点的函数值，要构造次数不超过二次的多项式,使满足二次插值条件：,n=2,P(x)的参数直接由插值条件决定，即满足下面的代数方程组：,的行列式是范德蒙行列式，当时，方程组的解唯一。,求二次式,使其满足条件：,仿线性插值,用基函数的方法求解方程组。先考察一个特殊的二次插值问题：,这个问题容易求解。由上式的后两个条件知:是的两个零点。于是,再由另一条件确定系数,从而导出,类似地可以构造出满足条件：的插值多项式,及满足条件：的插值多项式,这样构造出来的称为抛物插值的基函数,取已知数据作为线性组合系数,将基函数线性组合可得,容易看出,P(x)满足条件,所以二次插值称之为抛物插值。当三点(x0,y0),(x1,y1),(x2,y2)位于一条直线上时，显然插值函数的图形是直线。,例4.2已知函数y=f(x)的观测数据如表所示，试求其拉格朗日插值多项式，并计算f(1.5)的近似值。,解,4.3.2拉格朗日插值多项式,换句话说,每个li(x)有n个根x0xi-1、xi+1xn,Lagrange,所以次数不超过n次的代数插值多项式。,称为n次拉格朗日插值多项式。记为,插值基函数,基函数具有性质:,解:由线性插值多项式公式得,例4.4已知x=1,4,9的平方根值,用抛物插值公式,求,=2.7,=2.64575,解：,例4.5已知函数y=f(x)在节点上满足求二次多项式p(x)=a0+a1x+a2x2使之满足p(xi)=yii=0,1,2,解上述方程,将求出的a0,a1,a2代入p(x)=a0+a1x+a2x2即得所求二次多项式,0,0,1,1,2,2,解:用待定系数法,将各节点值依次代入所求多项式,得,例4.6求过点(0,1)、(1,2)、(2,3)的三点插值多项式,解:由Lagrange插值公式,（给定的三个点在一条直线上）,例4.7已知f(x)的观测数据,解四个点可构造三次Lagrange插值多项式:基函数为,构造Lagrange插值多项式,Lagrange插值多项式为,为便于上机计算,常将拉格朗日插值多项式(5.8)改写成,例4.8已知f(x)的观测数据,解:四个点可以构造三次插值多项式,将数据代入插值公式，有,这个例子说明p(x)的项数不超过n+1项,但可以有缺项,构造插值多项式,4.3.3拉格朗日插值算法实现,a,在插值区间a,b上用插值多项式p(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。,若记R(x)=f(x)-p(x)则R(x)就是用p(x)近似代替f(x)时的截断误差,或称插值余项我们可根据后面的定理来估计它的大小。,4.3.4插值多项式的误差,定理4.2设f(x)在a,b有n+1阶导数，x0,x1,xn为a,b上n+1个互异的节点,p(x)为满足p(xi)=f(xi)(i=1,2,n)的n次插值多项式，那么对于任何xa,b有,ab且依赖于x,插值余项,对于线性插值，其误差为,对于抛物插值（二次插值），其误差为,例4.9已知=100,=121,用线性插值估计在x=115时的截断误差,解:由插值余项公式知,例4.10已知x0=100,x1=121,x2=144,当用抛物插值求在x=115时的近似值，估计其的截断误差,例4.11设f(x)=x4,用余项定理写出节点-1,0,1,2的三次插值多项式,解:根据余项定理,所谓”曲线拟合”,是指根据给定的数据表,寻找一个简单的表达式来”拟合”该组数据,此处的”拟合”的含义为:不要求该表达式对应的近似曲线完全通过所有的数据点,只要求该近似曲线能够反映数据的基本变化趋势.,6曲线拟合的最小二乘法,如果要求所得的近似函数曲线精确无误地通过所有的点(xi,yi),就会使曲线保留着一切测试误差。当个别数据的误差较大时,插值效果显然是不理想的。此外,由实验或观测提供的数据个数往往很多,如果用插值法,势必得到次数较高的插值多项式，这样计算起来很烦琐。,6曲线拟合的最小二乘法,6曲线拟合的最小二乘法,曲线拟合的问题：,设函数y=f(x)在n个互异点的观测数据为,求一个简单的近似函数(x)，使之“最好”地逼近f(x)，而不必满足插值原则。称函数y=(x)为拟合曲线或经验公式,换句话说:求一条曲线,使数据点均在离此曲线的上方或下方不远处,它既能反映数据的总体分布,又不至于出现局部较大的波动,更能反映被逼近函数的特性,使求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小,这就是最小二乘法。,两种逼近概念:插值:在节点处函数值相同.拟合:在数据点处误差平方和最小,与函数插值问题不同,曲线拟合不要求曲线通过所有已知点,而是要求得到的近似函数能反映数据的基本关系。在某种意义上,曲线拟合更有实用价值。,在对给出的实验(或观测)数据,作曲线拟合时,怎样才算拟合得最好呢？一般希望各实验(或观测)数据与拟合曲线的偏差的平方和最小,这就是最小二乘原理。,（注意它与插值法的不同）,函数插值是插值函数P(x)与被插函数f(x)在节点处函数值相同,即,而曲线拟合函数不要求严格地通过所有数据点,也就是说拟合函数在xi处的偏差(亦称残差）,不都严格地等于零。,为了使近似曲线能尽量反映所给数据点的变化趋势,要求按某种度量标准最小。,若记向量,即要求向量的某种范数最小,如的1-范数或-范数即,为了便于计算、分析与应用，通常要求的2-范数,即,为最小。这种要求误差（偏差）平方和最小的拟合称为曲线拟合的最小二乘法。,例6.1某种纤维的强度与其拉伸倍数的关系.下表是实际测定的24个纤维样品的强度与相应的拉伸倍数的数据记录:,可以看出,纤维强度随拉伸倍数增加而增加,并且24个点大致分布在一条直线附近,该直线(拟合)称为这一问题的数学模型,因此可认为强度与拉伸倍数之间的主要关系是线性关系,怎样确定a,b,使得直线能较好地反映所给数据的基本“变化趋势”?,一般情况,各点误差,总误差,令,问题转化为求参数使达到最小值。,这种求线性函数y=a+bx的过程称为直线拟合。,代入,得,正规方程组,解:把表中所给数据画在坐标纸上将会看到数据点的分布可以用一条直线来近似地描述,设所求的拟合直线为,例6.2设有某实验数据如下：,用最小二乘法求以上数据的拟合函数,记x1=1.36,x2=1.37,x3=1.95x4=2.28,y1=14.094,y2=16.844,y3=18.475,y4=20.963,其中,将以上数据代入上式正规方程组,得,解得,即得拟合直线,例6.3已知实验数据表,用最小二乘法拟合这组数据。,解:作图看出接近一条直线,设公式为,正规方程组为,解得,得经验公式为,y=-12.5+6.55x,n=4,多项式拟合有时所给数据点的分布并不一定近似地呈一条直线,这时仍用直线拟合显然是不合适的,可用多项式拟合。对于给定的一组数据寻求次数不超过m(mN)的多项式，,来拟合所给定的数据，与线性拟合类似，使偏差的平方和,为最小,由于Q可以看作是关于(j=0,1,2,m)的多元函数,故上述拟合多项式的构造问题可归结为多元函数的极值问题。令,得,即有,这是关于系数的线性方程组，通常称为正规方程组。可以证明，正规方程组有惟一解。,（6.1）,用最小二乘法求一个多项式拟合这组数据,例6.4设某实验数据如下：,解：将已给数据点描在坐标系中，可以看出这些点接近一条抛物线，因此设所求的多项式为,由正规方程组（6.1）,经计算得,N=6,其法方程组为,解之得,所求的多项式为,所求的多项式为,（3）可化为线性拟合的非线性拟合有些非线性拟合曲线可以通过适当的变量替换转化为线性曲线，从而用线性拟合进行处理，对于一个实际的曲线拟合问题，一般先按观测值在直角坐标平面上描出散点图，看一看散点的分布同哪类曲线图形接近，然后选用相接近的曲线拟合方程。再通过适当的变量替换转化为线性拟合问题，按线性拟合解出后再还原为原变量所表示的曲线拟合方程。表6-1列举了几类经适当变换后化为线性拟合求解的曲线拟合方程及变换关系,表6-1,曲线拟合方程变换关系变换后线性拟合方程,几种常见的数据拟合情况。图(a)表示数据接近于直线，故宜采用线性函数拟合；图(b)数据分布接近于抛物线。可采拟合；二次多项式,拟合；,(a),(b),图(c)的数据分布特点是开始曲线上升较快随后逐渐变慢,宜采用双曲线型函数或指数型函数图(d)的数据分布特点是开始曲线下降快,随后逐渐变慢,宜采用或或等数据拟合。,(c),(d),用最小二乘法求拟合曲线,解:将已给数据点描在坐标系中下图所示,可以看出这些点接近指数曲线,因而可取指数函数作为拟合函数.,例6.5设某实验数据如下:,对函数两边取对数得.令,则就得到线性模型,则正规方程组为,其中,将以上数据代入上式正规方程组，得,由得,代入,于是得到拟合指数函数为,解得,的图形如下所示,例6.6求一个经验函数,使它与观测数据拟合,解对公式两边取对数得,正规方程组为,则得到线性模型,（4）超定方程组的最小二乘解设线性方程组Ax=b中，,b是m维已知向量，x是n维解向量，当mn，即方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说，超定方程组无解（此时为矛盾方程组),这时需要寻求方程组的一个“最近似”的解.记,称使,即最小的解为方程组Ax=b的最小二乘解。,定理6.1是Ax=b的最小二乘解的充分必要条件为是的解.（证明见教材）,例6.7求超定方程组,的最小二乘解,并求误差平方和。,解:方程组写成矩阵形式为,正规方程组为,即,解得,此时,误差平方和为,我们已经讨论了最小二乘意义下的曲线拟合问题,由于方程比较简单,实际中应用广泛,特别是因为任何连续函数至少在一个较小的邻域内可以用多项式任意逼近,因此用多项式作数据拟合,有它的特殊重要性。从而在许多实际问题中,不论具体函数关系如何,都可用多项式作近似拟合,但用多项式拟合时,当n较大时(n7),其法方程的系数矩阵的条件数一般较大,所