1 数值分析(计算方法)介绍

Numerical Analysis,J. G. Liu,School of Math. & Phys.,North,China Elec. P.U.,*,*,数 值 分 析,插值、拟合与数值微积分,主讲：,刘敬刚,9/13/2024,1,数值分析,(,计算方法,),简介,考虑如下线性方程组,或者：,其中,由克莱姆法则可知,(1),有唯一的解，而且解为：,(1),引例,9/13/2024,2,若行列式用按行（列）展开的方法计算,，,用克莱姆法则求解（,1,）需做乘除法的次数,:,当,方程组阶数较高时，计算量很大，因此,克莱姆法则通常仅有理论上的价值，计算线性方程组的解还要考虑,数值解法,=,算法,+,计算机,。,首先看一个简单的例子：,（若是更高阶的方程组呢？）,人类的,计算能力,是,计算工具,和,计算方法,效率的乘积，提高计算方法的效率与提高计算机硬件的效率同样重要。,科学计算,已用到科学技术和社会生活的各个领域中，成为继,实验,和,理论研究,之后的第三种研究方法。,9/13/2024,3,研究对象和主要内容,9/13/2024,4,数值分析（数值计算方法）,的,计算,对象是线性代数，微积分，常微分方程中的数学问题。内容包括：,求解线性方程组的,数值解法,、计算矩阵特征值和特征向量,、非线性方程和非线性方程组的迭代解法、,插值,与,拟合、数值微积分和常微分方程数值解等问题。,直接解法,若计算过程没有舍入误差，经过有限次算术运算就能求出问题精确解的数值方法。,迭代解法,若计算过程没有舍入误差,，,也不能经过有限次算术运算求得问题的精确解，而只能是逐步,逼近,的数值方法。,数值分析（数值计算方法）,，是一种研究,如何求,解数学问题,数值近似解,的,方法，是在,计算机,上使用的解数学问题的方法，简称计算方法。,包括,直接方法,和,迭代方法,!,9/13/2024,5,特点,9/13/2024,6,学习过程中应该注意以下几个方面：,认清,算法,的计算对象,；,掌握基本的计算方法及其,原理；,用,C+,语言编制程序，在计算机上对算法进行验证,；,对于算法要勤思考多比较！,数值分析（数值计算方法）既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性等技术特征，它是一门,理论性,和,实践性,都很强的课程。在,70,年代，大多数学校仅在数学系的,计算数学专业,和,计算机系,开设计算方法这门课程。随着计算机技术的迅速发展和普及，现在计算方法课程几乎已成为所有,理工科大学生的一门必修课程,。,9/13/2024,7,参考书目：,1,钟尔杰,.,数值分析,.,高等教育出版社，,2004.,2,颜庆津,.,数值分析,.,修订版,.,北京航空航天大学出版社, 2000.,3,李庆扬,.,数值分析,.,清华大学出版社，,2001,.,4,白峰杉,.,数值计算引论,.,高等教育出版社, 2004.,5,王能超,.,计算方法,.,北京,:,高等教育出版社, 2005,9/13/2024,8,数值分析的基本概念,算法设计技术,误差,数值计算中需要注意的一些问题,算法的稳定性,病态问题,内容,:,9/13/2024,9,算法设计技术,古希腊哲学家,Zeno,在两千多年前提出过一个骇人听闻的命题：一个人不管跑得多快，也追不上爬在他前面的一只乌龟。这就是著名的,Zeno,悖论。,Zeno,在论证这个命题时采取了如下形式的逻辑推理：设人与龟同时同向起跑，如果龟不动，那么人经过某段时间便能追上它；但实际上在这段时间内龟又爬了一段路程，从而人又得重新追赶，如下图所示，这样每追赶一次所归结的是同样类型的追赶问题，因而这种追赶过程,“,永远,”,不会终结。,引例,9/13/2024,10,耐人寻味的是，尽管,Zeno,悖论的论断极其荒谬，但从算法设计思想的角度来看它却是极为精辟的。,Zeno,悖论将人龟追赶问题表达为一连串追赶步的逐步逼近过程。设人与龟的速度分别为,V,与,v,，记,S,k,表示逼近过程的第,k,步人与龟的间距，另以,t,k,表示相应的时间，相邻两步的时间差为,t,k,。,Zeno,悖论将人龟追赶问题分解为一追一赶两个过程：,追的过程：,先令龟不动，计算人追上龟所费的时间,赶的过程：,再令人不动，计算龟在这段时间内爬行的路程,t,k,S,k-,1,S,k,V,v,t,k-,1,v,V,图示,:,人龟追赶过程,9/13/2024,11,若以,人和龟之间的距离 定义问题的,规模,大小，则上述过程将问题规模,压缩了 倍：,由于龟的速度远远小于人的速度，故 很小，因此按上述步骤很快,问题的规模 就可以忽略不计，从而得到人追上龟所花时间 ，,Zeno,的,解释可用如下过程表示：,Zeno,算法,可见，,Zeno,算法的设计思想是，将人龟追赶计算化归为简单的行程计算的重复，它的设计方法是逐步压缩计算模型的规模，这种,“,化大为小,”,的设计策略称为,规模缩减技术,，简称,缩减技术,。,算法的设计,精髓,：,“简单”的重复生成复杂！,9/13/2024,12,数列求和问题：,（,1,）,是最简单的计算模型。若记表示前,n,项的部分和，则有,（,2,）,则计算结果即为所求的和值：,（,3,）,这样，如果定义和式的项数为数列求和问题的,规模,，则所求和值为（,1,）,的退化情形。因之，只要令和式的规模逐次减,1,，最终当规模为,1,时即可直接得出所求的和值，而这样设计出来的算法就是累加求和算法（,2,）。,直接法的缩减技术,可见，上述累加求和算法的设计思想是将多项求和（,1,）化归为两项求和（,2,）的重复，最终加工成一项和式（,3,）（,(1),的退化情形）,从而得出和值。,9/13/2024,13,考虑,利用缩减技术可得如下算法：,算法流程图,问题,1:,编程实现任意阶多项式的计算,!,9/13/2024,14,迭代法的校正技术,易得人追上龟所花的时间是,注意到,v,是个小量，设,t,也是个小量，则可从上式中略去,v,t,，即令校正量,t,满足如下方程,(,近似,),有些问题的,“,大事化小,”,过程似乎无法了结。,Zeno,悖论强调人,“,永远,”,赶不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓,预报校正技术,来处理。,设人龟起初相距 ，两者的速度分别为 和 ，,则有方程,（,1,）,设解,t,*,有某个,预报值,t,0,，,希望提供校正量,t,，,使,校正值,t,1,=,t,0,+,t,能更好的满足所给方程（,1,），即使得,9/13/2024,15,进一步视,t,1,为新的预报值，重复实施上述手续，求出新的校正值,t,2,，再由,t,2,定,t,3,，如此反复可生成一系列近似值,t,1,t,2,t,3,这就规定了一个迭代过程，,求解上述方程即可定出校正值,(2),Zeno,悖论所描述的逼近过程正是这种迭代过程，,当,k,时，,t,k,t,*,（,问题,2:,证明该结论！,）。大家知道，任何形式的重复都可看成是,“,时间,”,的量度。,Zeno,在刻画人龟追赶问题中设置了两个,“,时钟,”,：一个是日常的钟，另外,Zeno,又将迭代次数视为另一种时钟，不妨称之为,Zeno,钟,。,Zeno,公式（,2,）表明，当,Zeno,钟趋于,时人才能追上龟，,Zeno,正是据此断言人永远追不上龟。,9/13/2024,16,给定 ，求开方值 的问题就是要求解方程,设给定某个预报值 ，希望借助于某种简单方法确定校正量 ，使校正值,能够比较准确地满足方程（,1,），即使 成立，,设校正量 是个小量，舍去上式中的高阶小量 ，令 ，从中定出 ，继而可得校正值：,（,1,）,反复实施这种预报校正手续，即可导出,开方公式,：,从某个初值 出发，利用上式反复迭代，即可获得满足精度要求的开方值 。,利用校正技术，设计求解 （ ）的算法。,校正技术的基本思想：,删繁就简,，,逐步求精,！,近似,问题,3:,编程实现,!,要求：画出流程图，初始值由键盘输入。,9/13/2024,17,算法优化的松弛技术,对于给定的预报值,，校正值为,据此,有,，两端同除以,，有,由于 为人龟追赶问题的精确解，,再考察,Zeno,算法：,由此可见，精确解等于任给预报值同它的校正值的,加权平均,：,其中,，,可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的精确解。这种加工效果是奇妙的。,9/13/2024,18,在实际计算中常常可以获得目标值,F,*,的两个相伴的近似值,F,0,与,F,1,，,将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作为改进值：,即通过适当选取权系数 来调整校正量 ，以加工得到更高精度的 ，这种基于校正量的调整与松动的方法通常称为,松弛技术,。,有一种情况特别引人注目：若所提供的一对近似值 与 有优劣之分，譬如 优而 劣，这时就采用如下松弛方式：,即在松弛过程中张扬 的优势而抑制 的劣势，这种设计策略称作外推松弛技术，简称,超松弛,。,总之，超松弛的设计机理是,优劣互补，化粗为精,。松弛技术的关键在于,松弛因子的选取,，而这往往是相当困难的。,返回,9/13/2024,19,误差,误差的分类,9/13/2024,20,误差和有效数字,(1),误差,定义,设 是准确值， 是 的一个近似值，记 ，称 为近似值 的,绝对误差,，简称误差。,若已知 的一个上界为 ，即 ，则称 为近似值 的,绝对误差界,，简称误差界（越小表示近似程度越高,）。,注,:,用绝对误差来刻画近似数的精确程度不能反映它在原数中所占的比例。,例,，,可是 与真值 相差一个数量级。,记 ，称 为近似值 的,相对误差,，也可以记为,的一个上界,称为近似值 的,相对误界,上例中 ，易见近似程度并不高！,9/13/2024,21,(2),有效数字,例,设近似值,，其绝对误差限都是,0.005,，,求各个近似值各有几位有效数字？,解,绝对误差限是,0.01,的半个单位，且 ，,有三位有效数字，分别是,1,，,3,，,8,； 有一位有效数字，为,3,；,没有有效数字。,同一真值的不同近似值，,有效数字越多,，它的绝对误差和相对误,差都越小。, 用单精度浮点型变量进行计算的结果有七位有效数字，双精度浮,点型变量有,16,位有效数字,注,：,定义,设 是数 的近似值，如果 的绝对误差限是它的,某一位的半个单位,，且从该位到 的第一位,非零数字,共有 位，则称 作为 的近似有 位有效数字。,9/13/2024,22,浮点数,（,1,）浮点数,“,数”在计算机中是以二进制表示的，一个非零二进制数的一般描述形式为：,其中,d,i,（,i,=1,2,t,）为,0,或,1,，称为,尾数,，且,d,1,0,；,2,为,基数,，,s,称为,阶码,且满足,L,s,U,，,这说明计算机只能表示,有限个数且是有限精度,，这个实数的子集称为浮点数，记作,F,。,不难验证对于,F,中,任意不为零的数,f,，,有,其中,m,=,2,L,-,1,，,M,=,2,U,(,1,-,2,-,t,),，,因此计算机上的计算会有溢出现象：上溢和下溢！,浮点数在接近其下界,m,处,比较稠密，而在接近其上界,M,处,比较稀疏！,因此，在计算中通常都是使用,相对误差,来控制精度！,由于计算机的有限精度而造成的误差称为,舍入误差,！,9/13/2024,23,（,2,） 截断误差和舍入误差,考虑计算一元可微函数,f,(,x,),在,x,0,处,导数的近似方法：,因此近似方法,（,1,）的,误差为,考虑方法（,1,）：由泰勒展开，可得,从而有,截断误差,问题,4,：计算近似方法（,2,）的截断误差！,9/13/2024,24,通过实验发现，随着,h,减小，通过（,1,）计算的导数近似值与真值的误差是,先减小后增大,，这种现象是什么原因造成的呢？,其原因就在于计算机是有限精度的，随着,h,的,减小，舍入误差逐渐被放大，并且最终成为引起误差的主导因素！,要,学好数值分析课程一定要真正理解舍入误差，特别是舍入误差在算法中的,传播,和对最终结果的影响！,同理可以讨论近似方法（,2,）的截断误差，以及随着,h,的,减小，其误差的变化情况！,返回,那么是不是,h,越小，计算误差就越小呢？,9/13/2024,25,数值计算中需要注意的问题,浮点数的加法,设,两个,浮点数相加：,首先比较它们的阶码，若阶码相同则尾数相加，相加后若尾数大于,1,则阶码进位；若阶码不等，则以相对大的阶码为标准，将阶码小的浮点数进行移位，直到阶码一致，再按阶码相同时的规则进行相加！,例,1,假设计算机只能存放三位十进制数字，设,，,在该计算机上进行如下运算,（,1,）计算 与十个 之和，即 ，采用以下两种计算方法,1,） ， ，则 即为所求，,计算得 （错）,2,） （正确）,9/13/2024,26,（,2,） （错）,（,3,） （错）,（正确）,例,2,计算,-,只需要做,12,次乘法,9/13/2024,27,数值计算的一些基本原则,（,1,）由于计算机字长的限制, 防止小数加到大数上；, 防止除数过小；, 防止相近的数相减,(,会损失有效数字,),；,（,2,）由于计算机的计算原理, 要尽量减少乘除法的运算次数,返回,9/13/2024,28,算法的稳定性,首先来看一个例子，考虑积分序列：,（,1,）,显然 ，且计算可得 ，对 进行分部积分得,并且,为了估计积分序列 ，我们构造如下方法：,方法,1,(,直接应用（,2,）,),（,2,）,（,3,）,方法,2,（考虑到结果（,3,）,考虑舍入误差，,方法,1,不可取！,若,在计算过程中,误差被无限制放大,，则称该算法,不稳定,，,否则称之为稳定算法。,返回,9/13/2024,29,病态问题,例子,其中,a,分别取,0.99,和,0.991,，算得结果分别为,可见,系数的微小变化,，引起了,结果比较大的改变,！我们称该问题是,病态问题,！,求解方程组,，,和,一般的，我们称对误差敏感的问题为,病态问题,，否则称为,良态,的！,返回,常规的算法对于病态问题的求解通常是无效的，因此在求解时要特别引起注意！,9/13/2024,30,