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

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