数值分析(计算方法)

数值分析——插值、拟合与数值微积分主讲：刘敬刚2/4/20231

数值分析(计算方法)介绍考虑如下线性方程组

或者：其中,由克莱姆法则可知(1)有唯一的解，而且解为：(1)一、引例

2/4/20232若行列式用按行（列）展开的方法计算，用克莱姆法则求解（1）需做乘除法的次数:

当方程组阶数较高时，计算量很大，因此克莱姆法则通常仅有理论上的价值，计算线性方程组的解还要考虑:首先看一个简单的例子：（若是更高阶的方程组呢？）人类的计算能力是计算工具和计算方法效率的乘积，提高计算方法的效率与提高计算机硬件的效率同样重要。科学计算已用到科学技术和社会生活的各个领域中，成为继实验和理论研究之后的第三种研究方法。数值解法=算法+计算机。2/4/20233二、研究对象和主要内容2/4/20234数值计算方法，是一种研究如何求解数学问题数值近似解的方法，是在计算机上使用的解数学问题的方法，简称计算方法。包括直接方法和迭代方法!数值计算方法的计算对象是线性代数，微积分，常微分方程中的数学问题。内容包括：求解线性方程组的数值方法;计算矩阵特征值和特征向量的数值方法;非线性方程和非线性方程组的迭代解法;插值与拟合;数值微积分;常微分方程数值解等问题。

2/4/20235三、特点2/4/20236数值计算方法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性等技术特征，它是一门理论性和实践性都很强的课程。在20世纪70年代，大多数学校仅在数学系的计算数学专业和计算机系开设计算方法这门课程。随着计算机技术的迅速发展和普及，现在计算方法课程几乎已成为所有理工科大学生的一门必修课程。学习过程中应该注意以下几个方面：认清算法的计算对象；掌握基本的计算方法及其原理；用C++语言编制程序，在计算机上对算法进行验证；对于算法要勤思考多比较！2/4/20237参考书目：1钟尔杰.数值分析.高等教育出版社,2004.2颜庆津.数值分析.修订版.北京航空航天大学出版社,2000.3李庆扬.数值分析.清华大学出版社,2001.4白峰杉.数值计算引论.高等教育出版社,2004.5王能超.计算方法.北京:高等教育出版社,2005.2/4/202381、算法设计技术2、误差3、数值计算中需要注意的一些问题4、算法的稳定性5、病态问题内容:数值分析的基本概念2/4/20239§1.1

算法设计技术

古希腊哲学家Zeno(芝诺)在两千多年前提出过一个骇人听闻的命题：一个人不管跑得多快，也追不上爬在他前面的一只乌龟。这就是著名的Zeno悖论。Zeno在论证这个命题时采取了如下形式的逻辑推理：设人与龟同时同向起跑，如果龟不动，那么人经过某段时间便能追上它；但实际上在这段时间内龟又爬了一段路程，从而人又得重新追赶，如下图所示，这样每追赶一次所归结的是同样类型的追赶问题，因而这种追赶过程“永远”不会终结。

引例2/4/202310耐人寻味的是，尽管Zeno悖论的论断极其荒谬，但从算法设计思想的角度来看它却是极为精辟的。Zeno悖论将人龟追赶问题表达为一连串追赶步的逐步逼近过程。设人与龟的速度分别为与，记表示逼近过程的第步人与龟的间距，另以表示相应的时间，相邻两步的时间差。Zeno悖论将人龟追赶问题分解为一追一赶两个过程：追的过程：先令龟不动，计算人追上龟所费的时间赶的过程：再令人不动，计算龟在这段时间内爬行的路程tkSk-1SkVvtk-1vV图示:人龟追赶过程2/4/202311若以人和龟之间的距离定义问题的规模大小，则上述过程将问题规模压缩了倍：由于龟的速度远远小于人的速度，故很小，因此按上述步骤很快问题的规模就可以忽略不计，从而得到人追上龟所花时间，Zeno的解释可用如下过程表示：——Zeno算法可见，Zeno算法的设计思想是，将人龟追赶计算化归为简单的行程计算的重复，它的设计方法是逐步压缩计算模型的规模，这种“化大为小”的设计策略称为规模缩减技术，简称缩减技术。

算法的设计精髓：“简单”的重复生成复杂！2/4/202312则计算结果即为所求的和值：

（3）数列求和问题：

（1）1直接法的缩减技术若用bk表示前k项的部分和，则有

（2）2/4/202313这样，如果定义和式的项数为数列求和问题的规模，则所求和值为（1）的退化情形。因之，只要令和式的规模逐次减1，最终当规模为1时即可直接得出所求的和值，而这样设计出来的算法就是累加求和算法（2）。可见，上述累加求和算法的设计思想是将多项求和（1）化归为两项求和（2）的重复，最终加工成一项和式（3）（(1)的退化情形）,从而得出和值。2/4/202314考虑利用缩减技术可得如下算法：算法流程图——考虑问题12/4/2023152迭代法的校正技术易得人追上龟所花的时间是有些问题的“大事化小”过程似乎无法了结。Zeno悖论强调人“永远”赶不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓预报校正技术来处理。

设人龟起初相距，两者的速度分别为和，则有方程（1）2/4/202316注意到v是个小量，设△t也是个小量，则可从上式中略去v△t，即令校正量△t满足如下方程(近似)设解t*有某个预报值t0，希望提供校正量△t，使校正值t1=t0+△t能更好的满足所给方程（1），即使得求解上述方程即可定出校正值

2/4/202317进一步视t1为新的预报值，重复实施上述手续，求出新的校正值t2，再由t2定t3，如此反复可生成一系列近似值

t1,t2,t3,…这就规定了一个迭代过程，

(2)Zeno悖论所描述的逼近过程正是这种迭代过程，当k→∞时，tk→t*（——考虑问题2

）。大家知道，任何形式的重复都可看成是“时间”的量度。Zeno在刻画人龟追赶问题中设置了两个“时钟”：一个是日常的钟，另外Zeno又将迭代次数视为另一种时钟，不妨称之为Zeno钟。Zeno公式（2）表明，当Zeno钟趋于∞时人才能追上龟，Zeno正是据此断言人永远追不上龟。

2/4/202318给定，求开方值的问题就是要求解方程

设给定某个预报值，希望借助于某种简单方法确定校正量，使校正值能够比较准确地满足方程（1），即使成立，设校正量是个小量，舍去上式中的高阶小量，令，从中定出，继而可得校正值：（1）利用校正技术，设计求解（）的算法。近似2/4/202319反复实施这种预报校正手续，即可导出开方公式：从某个初值出发，利用上式反复迭代，即可获得满足精度要求的开方值。

校正技术的基本思想：删繁就简，逐步求精！——考虑问题32/4/202320其中，3算法优化的松弛技术对于给定的预报值

，校正值为据此有

，两端同除以

，有由于为人龟追赶问题的精确解，再考察Zeno算法：可见，精确解等于任给预报值同它的校正值的加权平均：2/4/202321即通过适当选取权系数来调整校正量，以加工得到更高精度的，这种基于校正量的调整与松动的方法通常称为松弛技术。

可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的精确解。这种加工效果是奇妙的。在实际计算中常常可以获得目标值F*的两个相伴的近似值F0与F1，将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作为改进值：

2/4/202322有一种情况特别引人注目：若所提供的一对近似值与有优劣之分，譬如优而劣，这时就采用如下松弛方式：

即在松弛过程中张扬的优势而抑制的劣势，这种设计策略称作外推松弛技术，简称超松弛。

总之，超松弛的设计机理是优劣互补，化粗为精。松弛技术的关键在于松弛因子的选取，而这往往是相当困难的。

返回2/4/202323§1.2误差

1误差的分类2/4/2023242误差和有效数字(1)误差

定义设是准确值，是的一个近似值，记，称为近似值的绝对误差，简称误差。

若已知的一个上界为，即，则称为近似值的绝对误差界，简称误差界（越小表示近似程度越高）。

注:用绝对误差来刻画近似数的精确程度不能反映它在原数中所占的比例。

例,，可是与真值相差一个数量级。

2/4/202325称为近似值的相对误差的一个上界,称为近似值的相对误界

上例中，易见近似程度并不高！也可以记为2/4/202326(2)误差估计

函数计算的误差估计算数运算的误差估计2/4/202327解

绝对误差限是0.01的半个单位，且，

有三位有效数字，分别是1，3，8；有一位有效数字，为3；没有有效数字。

(3)有效数字定义设是数的近似值，如果的绝对误差限是它的某一位的半个单位，且从该位到的第一位非零数字共有位，则称作为的近似有位有效数字。

例

设近似值

，其绝对误差限都是0.005，求各个近似值各有几位有效数字？同一真值的不同近似值，有效数字越多，它的绝对误差和相对误差都越小。

②用单精度浮点型变量进行计算的结果有七位有效数字，双精度浮点型变量有16位有效数字注：2/4/2023283浮点数（1）浮点数“数”在计算机中是以二进制表示的，一个非零二进制数的一般描述形式为：其中di（i=1,2,…,t）为0或1，称为尾数，且d1≠0；2为基数，s称为阶码且满足L≤s

≤U，这说明计算机只能表示有限个数且是有限精度，这个实数的子集称为浮点数，记作F。不难验证对于F中任意不为零的数f，有其中m=2L-1，M=2U(1-2-t)，因此计算机上的计算会有溢出现象：上溢和下溢！浮点数在接近其下界m处比较稠密，而在接近其上界M处比较稀疏！因此，在计算中通常都是使用相对误差来控制精度！由于计算机的有限精度而造成的误差称为舍入误差！2/4/202329（2）截断误差和舍入误差考虑计算一元可微函数f(x)在x0处导数的近似方法：因此近似方法（1）的误差为考虑方法（1）：由泰勒展开，可得从而有——截断误差考虑问题42/4/202330通过实验发现，随着h减小，通过（1）计算的导数近似值与真值的误差是先减小后增大，这种现象是什么原因造成的呢？其原因就在于计算机是有限精度的，随着h的减小，舍入误差逐渐被放大，并且最终成为引起误差的主导因素！（要求上机体会舍入误差的影响）要学好数值分析课程一定要真正理解舍入误差，特别是舍入误差在算法中的传播和对最终结果的影响！同理可以讨论近似方法（2）的截断误差，以及随着h的减小，其误差的变化情况！返回那么是不是h越小，计算误差就越小呢？——考虑问题52/4/202331§1.3

数值计算中需要注意的问题1浮点数的加法设两个浮点数相加：首先比较它们的阶码，若阶码相同则尾数相加，相加后若尾数大于1则阶码进位；若阶码不等，则以相对大的阶码为标准，将阶码小的浮点数进行移位，直到阶码一致，再按阶码相同时的规则进行相加！例1假设计算机只能存放三位十进制数字，设在该计算机上进行如下运算

（1）计算与十个之和，即，采用以下两种计算方法

2/4/2023321），，则即为所求，

计算得（错）

2）（正确）

（2）（错）

（3）（错）

（正确）

2/4/202333例2计算