计算思维与计算方法

第一页，共九十九页，2022年，8月28日

参考书目

计算方法刘师少编著（科学出版社，2011年修订版）数值计算张军等编著（清华大学出版社,2008年）参考资料[1]周以真.计算思维.中国计算机学会通讯,2007,3(11)[2]王飞跃.从计算思维到计算文化[J].中国计算机学会通讯，2007，3(11).[3]何钦铭等.计算机基础教学的核心任务是计算思维能力的培养—《九校联盟（C9）计算机基础教学发展战略联合声明》解读[J].中国大学教学，2010(9).[4]郑毓信,肖柏荣,熊萍.数学思维与数学方法论[M].四川教育出版社，2001第二页，共九十九页，2022年，8月28日

了解计算思维的基本内容，了解人与计算机器能力的局限性，了解计算思维解决问题的一般步骤.1、基本要求1理解计算思维在问题解决过程中所发挥的作用23掌握计算机解决实际问题的一般步骤以及常用的医学信息处理（计算）算法（计算方法）。第三页，共九十九页，2022年，8月28日计算思维的概念2、教学内容1计算方法概念及其研究对象与特点23插值法语曲线拟合的最小二乘法第四页，共九十九页，2022年，8月28日考核方式选择下列主题之一,完成综述：1.医学院校学生应具有的计算思维能力2.最小二乘法在医学信息处理中的应用3.插值法在医学信息处理中的应用要求3500字以上表格下载：第五页，共九十九页，2022年，8月28日文献综述以学号+姓名作为文件名上传至

个人账号下要求：

截止日期第六页，共九十九页，2022年，8月28日3、计算思维的概念

国际上广泛认同的计算思维定义来自周以真（JeannetteWing）教授。周教授认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解的涵盖计算机科学之广度的一系列思维活动。是抽象和自动化如同所有人都具备“读、写、算”能力一样，计算思维是必须具备的思维能力。计算思维的本质第七页，共九十九页，2022年，8月28日

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

计算思维是一种选择合适的方式去陈述一个问题,或对一个问题的相关方面建模使其易于处理的思维方法.第八页，共九十九页，2022年，8月28日5计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法。6计算思维是利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法。7计算思维是利用海量数据来加快计算，在时间和空间之间、在处理能力和存储容量之间进行折中的思维方法第九页，共九十九页，2022年，8月28日计算思维是一种根本技能，是每一个人为了在现代社会中发挥职能所必须掌握的。计算思维是人类求解问题的一条途径

特别注意123计算思维是思想，不是人造品。重要的是计算的概念，它被人们用来求解问题、管理日常生活以及与他人进行交流和互动。计算思维是数学与工程思维的互补与融合，它作为一个问题解决的有效工具，人人都应掌握，处处都会被使用。4第十页，共九十九页，2022年，8月28日

3.2计算思维与计算方法联系与区别

计算思维是一种选择合适的方式陈述一个问题或对一个问题的相关方面建模使其易于处理的思维方法。

区别

计算方法又称“数值分析”。是求解各类数学问题的数值解的方法，是研究分析用计算机求解数学计算问题的数值计算方法及其理论的学科，是基于计算机考虑问题求解第十一页，共九十九页，2022年，8月28日

3.2计算思维与计算方法联系与区别计算思维与计算方法互补性很强,可以相互促进。

联系计算方法可以对计算思维研究方面取得的成果进行再研究和吸收,最终丰富计算方法的内容。计算思维的重要作用也可以通过计算方法得到更好的提高。第十二页，共九十九页，2022年，8月28日设计算法3.3用计算机解决实际问题的一般步骤是：建立数学模型分析实际问题编写程序代码上机计算前三步为建模，集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。后两步为模型求解，集中于选择某一种程序设计语言，把算法表达给特定的计算机。广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。第十三页，共九十九页，2022年，8月28日1.

对于要解决的问题建立数学模型2.研究用于求解该数学问题近似解的算法和过程3.按照2进行计算，得到计算结果建立数学模型转化为数值公式进行计算换句话说第十四页，共九十九页，2022年，8月28日

由此可见。由数学模型找到求解方法的过程，是计算方法要研究的核心问题。也是计算思维涵盖的内容。计算方法所面对的正是“模型求解”，或者说求模型的数值解。因此我们不能把“计算方法”理解为“计算”的“方法”，而应理解为利用计算工具求解复杂数学问题的方法论和基本方法。第十五页，共九十九页，2022年，8月28日

我们所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。计算机算法可分为两大类别：数值运算和非数值运算。数值运算的目的是求数值解，例如函数插值、曲线拟合的最小二乘法等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如教务管理、学籍管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用注意：不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。第十六页，共九十九页，2022年，8月28日4.1问题的提出在生产实际中，连续函数往往只能由若干个离散点上的值来表示，而难以得到具体的解析式4插值25.627.236.934.426.824.34812162024温度（）时间（时）Co第十七页，共九十九页，2022年，8月28日每隔4小时记录一次温度，以反映某地一天的气温变化状况那么如何利用离散点值来推测其余点上的函数值,(如11、15、19点温度),从而反映被测函数的整体状况呢？

构造这个函数过程就称为插值

方法:构造一个通过所有离散测试点的函数，用这个函数来逼近被测函数。第十八页，共九十九页，2022年，8月28日

还有许多这样的实例函数解析式未知,通过实验观测得到的一组数据,即在某个区间[a,b]上给出一系列点的函数值yi=f(xi)或者给出函数表，希望构出能近似代替原来的函数y=f(x)y=p(x)xx0x1x2……xnyy0y1y2……yn第十九页，共九十九页，2022年，8月28日—

动物实验中心为白鼠服用了某种新产品药物后，在对1对白鼠在６周内的食物消费量（克,x)及6周间增加的体（克,y)测量数据如下:

i123456

xi568608636636660684

yi106126134134128158试确定白鼠体重y与白鼠之食物消费量x的函数关系y=f(x)那么，左边图形的y=f(x)解析函数如何求呢？第二十页，共九十九页，2022年，8月28日—血药浓度问题,为试验某种新药的疗效,研究人员对志愿者用快速静脉注射方式一次注入该药30mg（毫克）后,在一定的时刻t(h)采取血样,测得血药浓度C(μg/ml)（微克／毫升）数据如下:试确定血药浓度C与时间t的函数关系C=f(t)i123456789t(h)0.250.511.523468C(μg/ml)19.2118.1515.3614.112.99.327.455.243.01第二十一页，共九十九页，2022年，8月28日4.2插值法的基本原理函数y=f(x)给出一组函数值

x:x0x1x2……xny:y0y1y2……yn其中x0,x1,x2,…,xn是区间[a,b]上的互异点，要构造一个简单的函数φ(x)

作为f(x)的近似表达式，使满足(插值原则、插值条件)

这类问题称为插值问题。

-----f(x)的插值函数,

f(x)-----被插值函数x0,x1,x2,…,xn-----插值节点

求插值函数的方法称为插值法。

若x∈[a,b],需要计算f(x)的近似值φ(x),则称x为插值点

第二十二页，共九十九页，2022年，8月28日

用插值法求函数的近似表达式时，首先要选定函数的形式。可供选择的函数很多，常用的是多项式函数，因为多项式函数计算简便，只需用加、减、乘等运算，便于上机计算，而且其导数与积分仍为多项式。用多项式作为研究插值的工具，称为代数插值。

即求一个次数不超过n次的多项式满足第二十三页，共九十九页，2022年，8月28日满足

则称P(x)为f(x)的n次插值多项式。其几何意义如下图所示第二十四页，共九十九页，2022年，8月28日定理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阶线性方程组,其系数矩阵行列式为

第二十五页，共九十九页，2022年，8月28日

称为Vandermonde（范德蒙）行列式，因xi≠xj（当i≠j），故V≠0。根据解线性方程组的克莱姆（Gramer）法则，方程组的解存在惟一，从而P(x)被惟一确定。

惟一性说明，不论用何种方法来构造，也不论用何种形式来表示插值多项式,只要满足插值条件(4.1)其结果都是相互恒等的。

第二十六页，共九十九页，2022年，8月28日4.3拉格朗日多项式(Lagrange)求n次多项式使得条件：无重合节点，即n=1xx0x1yy0y1已知x0,x1;

y0,

y1，求使得要构造线性函数P1(x)=a0+a1x,使满足插值条件P1(x0)=y0,P1(x1)=y1.第二十七页，共九十九页，2022年，8月28日

（线性插值多项式）

（拉格朗日线性插值多项式）

公式的结构：它是两个一次函数的线性组合

（线性插值基函数）

可见P1(x)是过(x0

,y0)和(x1,y1

)两点的直线。=y0

+y1第二十八页，共九十九页，2022年，8月28日l0(x)l1(x)称为拉氏基函数

满足条件li(xj)=ij第二十九页，共九十九页，2022年，8月28日基函数的性质

第三十页，共九十九页，2022年，8月28日例4.1已知,,求解:这里x0=100,y0=10,x1=121,y1=11,利用线性插值公式

x100121y1011第三十一页，共九十九页，2022年，8月28日这就是二次插值问题。其几何意义是用经过3个点的抛物线近似代替曲线,如下图所示。因此也称之为抛物插值。xx0x1x2yy0y1y2

抛物插值抛物插值又称二次插值，它也是常用的代数插值之一。设已知f(x)在三个互异点的函数值，要构造次数不超过二次的多项式使满足二次插值条件：n=2第三十二页，共九十九页，2022年，8月28日P(x)的参数直接由插值条件决定，即满足下面的代数方程组：该三元一次方程组的系数矩阵

的行列式是范德蒙行列式，当时，方程组的解唯一。

第三十三页，共九十九页，2022年，8月28日求二次式,使其满足条件：仿线性插值,用基函数的方法求解方程组。先考察一个特殊的二次插值问题：这个问题容易求解。由上式的后两个条件知:是的两个零点。于是再由另一条件确定系数

从而导出

第三十四页，共九十九页，2022年，8月28日类似地可以构造出满足条件：的插值多项式

及满足条件：的插值多项式

这样构造出来的称为抛物插值的基函数

取已知数据作为线性组合系数,将基函数线性组合可得容易看出,P(x)满足条件

第三十五页，共九十九页，2022年，8月28日

所以二次插值称之为抛物插值。当三点(x0,y0),(x1,y1),(x2,y2)位于一条直线上时，显然插值函数的图形是直线。第三十六页，共九十九页，2022年，8月28日

例4.2已知函数y=f(x)的观测数据如表所示，试求其拉格朗日插值多项式，并计算f(1.5)的近似值。x012y2-14解

第三十七页，共九十九页，2022年，8月28日4.3.2拉格朗日插值多项式

换句话说我们看到,两个插值点可求出一次插值多项式,而三个插值点可求出二次插值多项式。插值点增加到n+1个时,也就是通过n+1个不同的已知点,来构造一个次数为n的代数多项式P(x)。与推导抛物插值的基函数类似,先构造一个特殊n次多项式的插值问题,使其在各节点上满足

第三十八页，共九十九页，2022年，8月28日希望找到li(x)，i=0,…,n

使得

li(xj)=ij；然后令==niiinyixlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li(x)

有n

个根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(Lagrange与有关，而与

无关节点f第三十九页，共九十九页，2022年，8月28日所以次数不超过n次的代数插值多项式。称为n次拉格朗日插值多项式。记为

,插值基函数基函数具有性质:第四十页，共九十九页，2022年，8月28日例4.3已知y=f(x)的函数表

求线性插值多项式,

并计算x=1.5的值X13y12解:由线性插值多项式公式得第四十一页，共九十九页，2022年，8月28日例4.4已知x=1,4,9的平方根值,用抛物插值公式,求

=2.7=2.64575解：x0=1,x1=4,x2=9y0=1,y1=2,y2=3第四十二页，共九十九页，2022年，8月28日例4.5已知函数y=f(x)在节点上满足求二次多项式p(x)=a0+a1x+a2x2

使之满足p(xi)=yi

i=0,1,2解上述方程,将求出的a0,a1,a2

代入p(x)=a0+a1x+a2x2

即得所求二次多项式

001122xx0x1x2yy0y1y2解:用待定系数法,将各节点值依次代入所求多项式,得第四十三页，共九十九页，2022年，8月28日例4.6求过点(0,1)、(1,2)、(2,3)的三点插值多项式解:由Lagrange插值公式（给定的三个点在一条直线上）第四十四页，共九十九页，2022年，8月28日例4.7已知f(x)的观测数据解四个点可构造三次Lagrange插值多项式:基函数为x0124f(x)19233构造Lagrange插值多项式第四十五页，共九十九页，2022年，8月28日Lagrange插值多项式为为便于上机计算,常将拉格朗日插值多项式(5.8)改写成

第四十六页，共九十九页，2022年，8月28日

例4.8已知f(x)的观测数据

解:四个点可以构造三次插值多项式,将数据代入插值公式，有

这个例子说明p(x)的项数不超过n+1项,但可以有缺项x1234f(x)0-5-63构造插值多项式第四十七页，共九十九页，2022年，8月28日第四十八页，共九十九页，2022年，8月28日4.3.3拉格朗日插值算法实现

第四十九页，共九十九页，2022年，8月28日ax0x1xixi+1xn-1xny=f(x)y=p(x)b在插值区间a,b上用插值多项式p(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。若记R(x)=f(x)-p(x)

则R(x)就是用p(x)近似代替f(x)时的截断误差,或称插值余项我们可根据后面的定理来估计它的大小。4.3.4插值多项式的误差

第五十页，共九十九页，2022年，8月28日定理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有a<<b

且依赖于x其中证明(略)

插值余项第五十一页，共九十九页，2022年，8月28日对于线性插值，其误差为对于抛物插值（二次插值），其误差为第五十二页，共九十九页，2022年，8月28日例4.9已知=100,=121,用线性插值估计在x=115时的截断误差解:由插值余项公式知第五十三页，共九十九页，2022年，8月28日例4.10已知x0=100,x1=121,x2=144,当用抛物插值求在x=115时的近似值，估计其的截断误差

解=第五十四页，共九十九页，2022年，8月28日例4.11设f(x)=x4,用余项定理写出节点-1,0,1,2的三次插值多项式

解:根据余项定理第五十五页，共九十九页，2022年，8月28日

所谓”曲线拟合”,是指根据给定的数据表,寻找一个简单的表达式来”拟合”该组数据,此处的”拟合”的含义为:不要求该表达式对应的近似曲线完全通过所有的数据点,只要求该近似曲线能够反映数据的基本变化趋势.6曲线拟合的最小二乘法第五十六页，共九十九页，2022年，8月28日

如果要求所得的近似函数曲线精确无误地通过所有的点(xi,yi),就会使曲线保留着一切测试误差。当个别数据的误差较大时,插值效果显然是不理想的。此外,由实验或观测提供的数据个数往往很多,如果用插值法,势必得到次数较高的插值多项式，这样计算起来很烦琐。6曲线拟合的最小二乘法第五十七页，共九十九页，2022年，8月28日6曲线拟合的最小二乘法曲线拟合的问题：

设函数y=f(x)在n个互异点的观测数据为

求一个简单的近似函数φ(x)，使之“最好”地逼近f(x)，而不必满足插值原则。称函数y=φ(x)为拟合曲线或经验公式xix1x2…..xnyiy1y2…..yn第五十八页，共九十九页，2022年，8月28日换句话说:求一条曲线,使数据点均在离此曲线的上方或下方不远处,它既能反映数据的总体分布,又不至于出现局部较大的波动,更能反映被逼近函数的特性,使求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小,这就是最小二乘法。

两种逼近概念:插值:在节点处函数值相同.拟合:在数据点处误差平方和最小第五十九页，共九十九页，2022年，8月28日

与函数插值问题不同,曲线拟合不要求曲线通过所有已知点,而是要求得到的近似函数能反映数据的基本关系。在某种意义上,曲线拟合更有实用价值。在对给出的实验(或观测)数据作曲线拟合时,怎样才算拟合得最好呢？一般希望各实验(或观测)数据与拟合曲线的偏差的平方和最小,这就是最小二乘原理。第六十页，共九十九页，2022年，8月28日（注意它与插值法的不同）第六十一页，共九十九页，2022年，8月28日

函数插值是插值函数P(x)与被插函数f(x)在节点处函数值相同,即而曲线拟合函数不要求严格地通过所有数据点,也就是说拟合函数在xi处的偏差(亦称残差）不都严格地等于零。第六十二页，共九十九页，2022年，8月28日为了使近似曲线能尽量反映所给数据点的变化趋势,要求按某种度量标准最小。若记向量,即要求向量的某种范数最小,如的1-范数或∞-范数

即或最小第六十三页，共九十九页，2022年，8月28日为了便于计算、分析与应用，通常要求的2-范数

即为最小。这种要求误差（偏差）平方和最小的拟合称为曲线拟合的最小二乘法。第六十四页，共九十九页，2022年，8月28日例6.1某种纤维的强度与其拉伸倍数的关系.下表是实际测定的24个纤维样品的强度与相应的拉伸倍数的数据记录:编号拉伸倍数强度编号拉伸倍数强度11.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第六十五页，共九十九页，2022年，8月28日可以看出,纤维强度随拉伸倍数增加而增加并且24个点大致分布在一条直线附近该直线(拟合)称为这一问题的数学模型因此可认为强度与拉伸倍数之间的主要关系是线性关系第六十六页，共九十九页，2022年，8月28日怎样确定a,b,使得直线能较好地反映所给数据的基本“变化趋势”?一般情况各点误差总误差令问题转化为求参数使达到最小值。第六十七页，共九十九页，2022年，8月28日代入将第六十八页，共九十九页，2022年，8月28日编号拉伸倍数强度编号拉伸倍数强度11.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第六十九页，共九十九页，2022年，8月28日这种求线性函数y=a+bx的过程称为直线拟合。代入得正规方程组第七十页，共九十九页，2022年，8月28日

解:把表中所给数据画在坐标纸上将会看到数据点的分布可以用一条直线来近似地描述,设所求的拟合直线为例6.2设有某实验数据如下：i1234xi1.361.371.952.28yi14.09416.84418.47520.963用最小二乘法求以上数据的拟合函数第七十一页，共九十九页，2022年，8月28日记x1=1.36,x2=1.37,x3=1.95x4=2.28,y1=14.094,y2=16.844,y3=18.475,y4=20.963其中将以上数据代入上式正规方程组,得第七十二页，共九十九页，2022年，8月28日解得

即得拟合直线

第七十三页，共九十九页，2022年，8月28日

例6.3已知实验数据表,用最小二乘法拟合这组数据。解:作图看出接近一条直线,设公式为x2468y2112840正规方程组为解得得经验公式为y=-12.5+6.55xn=4,第七十四页，共九十九页，2022年，8月28日

多项式拟合有时所给数据点的分布并不一定近似地呈一条直线,这时仍用直线拟合显然是不合适的,可用多项式拟合。对于给定的一组数据寻求次数不超过m(m<<N)的多项式，

来拟合所给定的数据，与线性拟合类似，使偏差的平方和为最小第七十五页，共九十九页，2022年，8月28日由于Q可以看作是关于(j=0,1,2,…,m)的多元函数,故上述拟合多项式的构造问题可归结为多元函数的极值问题。令得

即有

第七十六页，共九十九页，2022年，8月28日这是关于系数的线性方程组，通常称为正规方程组。可以证明，正规方程组有惟一解。

（6.1）第七十七页，共九十九页，2022年，8月28日用最小二乘法求一个多项式拟合这组数据

i123456xi012345yi521123例6.4设某实验数据如下：解：将已给数据点描在坐标系中，可以看出这些点接近一条抛物线，因此设所求的多项式为第七十八页，共九十九页，2022年，8月28日由正规方程组（6.1）,经计算得

N=6其法方程组为

解之得

所求的多项式为

第七十九页，共九十九页，2022年，8月28日所求的多项式为

第八十页，共九十九页，2022年，8月28日（3）可化为线性拟合的非线性拟合有些非线性拟合曲线可以通过适当的变量替换转化为线性曲线，从而用线性拟合进行处理，对于一个实际的曲线拟合问题，一般先按观测值在直角坐标平面上描出散点图，看一看散点的分布同哪类曲线图形接近，然后选用相接近的曲线拟合方程。再通过适当的变量替换转化为线性拟合问题，按线性拟合解出后再还原为原变量所表示的曲线拟合方程。表6-1列举了几类经适当变换后化为线性拟合求解的曲线拟合方程及变换关系第八十一页，共九十九页，2022年，8月28日表6-1

曲线拟合方程变换关系变换后线性拟合方程第八十二页，共九十九页，2022年，8月28日几种常见的数据拟合情况。图(a)表示数据接近于直线，故宜采用线性函数拟合；图(b)数据分布接近于抛物线。可采拟合；二次多项式拟合；

(a)(b)第八十三页，共九十九页，2022年，8月28日图(c)的数据分布特点是开始曲线上升较快随后逐渐变慢,宜采用双曲线型函数或指数型函数图(d)的数据分布特点是开始曲线下降快,随后逐渐变慢,宜采用或或等数据拟合。(c)(d)第八十四页，共九十九页，2022年，8月28日用最小二乘法求拟合曲线

解:将已给数据点描在坐标系中下图所示,可以看出这些点接近指数曲线,因而可取指数函数作为拟合函数.例6.5设某实验数据如下:i123456xi00.511.522.5yi210.90.60.40.3第八十五页，共九十九页，2022年，8月28日对函数两边取对数得.令

则就得到线性模型

则正规方程组为

其中

第八十六页，共九十九页，2022年，8月28日将以上数据代入上式正规方程组，得由得代入于是得到拟合指数函数为解得

第八十七页，共九十九页，2022年，8月28日的图形如下所示第八十八页，共九十九页，2022年，8月28日例6.6求一个经验函数使它与观测数据拟合x12345678y14.320.527.436.649.164.687.8117.6解对公式两边取对数得正规方程组为则得到线性模型

第八十九页，共九十九页，2022年，8月28日第九十页，共九十九页，2022年，8月28日

（4）超定方程组的最小二乘解设线性方程组Ax=b中，,b是m维已知向量，x是n维解向量，当m＞n，即方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说，超定方程组无解（此时为矛盾方程组),这时需要寻求方程组的一个“最近似”的解.记,称使,即