数值分析华电PPT

1、 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-81数数 值值 分分 析析主讲：刘敬刚刘敬刚 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-82 数值分析数值分析(计算方法计算方法)课程介绍课程介绍考虑如下线性方程组 bAx 或者：其中 ,0)det(A由克莱姆法则可知 (1)有唯一的解，而且解为：nnnnnnnbxaxabxaxa1111111

2、(1)nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,引例引例 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-83若行列式用按行（列）展开的方法计算 ，(1)(1) !nnn用克莱姆法则求解（1）需做乘除法的次数: 当方程组阶数较高时，计算量很大，因此克莱姆法则通常仅有理论上的价值，计算线性方程组的解还要考虑: 数值分析数值分析(计算方法计算方法)课程介绍课程介绍首先看一个简单的例子：1212120 xxxx 121

3、2xx（若是更高阶的 方程组呢？）人类的计算能力计算能力是计算工具计算工具和计算方法计算方法效率的乘积，提高计算方法的效率与提高计算机硬件的效率同样重要。科学计算科学计算已用到科学技术和社会生活的各个领域中，成为继实验实验和理论研究理论研究之后的第三种研究方法。数值解法数值解法 = 算法算法 + 计算机计算机。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-84 算算法法设设计计 实实际际问问题题 数数学学模模型型 程程序序设设计计 上上机机求求解解 应应用用数数学学

4、计计算算数数学学 研究对象和主要内容研究对象和主要内容 数值分析数值分析(计算方法计算方法)课程介绍课程介绍 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-85n数值计算方法，是一种研究如何求解数学问题数值近数值近似解似解的方法，是在计算机计算机上使用的解数学问题的方法，简称计算方法。包括直接方法直接方法和迭代方法迭代方法!n数值计算方法的计算对象是线性代数，微积分，常微分方程中的数学问题。内容包括：求解线性方程组的数值方法求解线性方程组的数值方法; ;计算矩阵特征值和

5、特征向量的数值方法计算矩阵特征值和特征向量的数值方法; ;非线性方程和非线性方程组的迭代解法非线性方程和非线性方程组的迭代解法; ;插值插值与与拟合拟合; ;数值微积分数值微积分; ;常微分方程数值解等问题。常微分方程数值解等问题。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-86 特特 点点 面面 向向 计计 算算 机机 有有 可可 靠靠 的的 理理 论论 分分 析析 有有 较较 好好 的的 计计 算算 复复 杂杂 性性 有有 数数 值值 实实 验验 收收 敛敛 性

6、性 稳稳 定定 性性 时时 间间 复复 杂杂 度度 空空 间间 复复 杂杂 度度 数值分析数值分析(计算方法计算方法)课程介绍课程介绍特点特点 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-87n学好本门课程需要做到：认清算法的计算对象；掌握基本的计算方法及其原理；编制程序，在计算机上对算法进行验证；对于算法要多思考多比较！ 数值分析数值分析(计算方法计算方法)课程介绍课程介绍数值计算方法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性等技术特征，它是一门理论

7、性理论性和实践性实践性都很强的课程。在20世纪70年代，大多数学校仅在数学系的计算数学专业计算数学专业和计算机系计算机系开设计算方法这门课程。随着计算机技术的迅速发展和普及，现在计算方法课程几乎已成为所有理工科大学生的一门必修课程理工科大学生的一门必修课程。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-88参考书目：参考书目：1 谷根代等，数值分析与应用，科学出版社，20112 钟尔杰.数值分析.高等教育出版社,2004.3 颜庆津.数值分析.修订版.北京航空航天大学

8、出版社,2000.4 李庆扬. 数值分析.清华大学出版社,2001.5 白峰杉.数值计算引论.高等教育出版社,2004.6 王能超.计算方法.北京: 高等教育出版社, 2005. Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-89第一章 绪论1、算法设计技术2、误差3、数值计算中需要注意的一些问题4、算法的稳定性5、病态问题内容内容: : Numerical Analysis J. G. Liu School of Math. & Phys. North Chi

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

10、Phys. North China Elec. P.U.2022-5-811耐人寻味的是，尽管Zeno悖论的论断极其荒谬，但从算法设计思想的角度来看它却是极为精辟的。Zeno悖论将人龟追赶问题表达为一连串追赶步的逐步逼近过程。设人与龟的速度分别为V与v，记Sk表示逼近过程的第k步人与龟的间距，另以tk表示相应的时间，相邻两步的时间差tk 。Zeno悖论将人龟追赶问题分解为一追一赶两个过程：1kkStVkkSv t 追的过程：追的过程：先令龟不动，计算人追上龟所费的时间赶的过程：赶的过程：再令人不动，计算龟在这段时间内爬行的路程tkSk-1SkVvtk-1vV 图示: 人龟追赶过程 Numeri

11、cal Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-812若以人和龟之间的距离 定义问题的规模规模大小，则上述过程将问题规模压缩了 倍：kSvV1kkvSSV由于龟的速度远远小于人的速度，故 很小，因此按上述步骤很快问题的规模 就可以忽略不计，从而得到人追上龟所花时间 ，Zeno的解释可用如下过程表示：vVkSkt01,1,2,kkvSS SSkVZeno算法可见，Zeno算法的设计思想是: “化大为小,化繁为简”，即将人龟追赶计算化为简单的行程计算的重复。算法的设计精髓：“简单简单”的

12、重复生成复杂！的重复生成复杂！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-813则计算结果即为所求的和值： （3）数列求和问题： （1）01nSaaa001,1,2,kkkbabbaknnSb1 直接法的缩减技术直接法的缩减技术若用bk表示前k项的部分和，则有 （2） Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-814这样，如果定义和式的项

13、数为数列求和问题的规模规模，则所求和值为（1）的退化情形。因之，只要令和式的规模逐次减1，最终当规模为1时即可直接得出所求的和值，而这样设计出来的算法就是累加求和算法（2）。可见，上述累加求和算法的设计思想是将多项求和（1）化归为两项求和（2）的重复，最终加工成一项和式（3）（(1)的退化情形）,从而得出和值。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-815考虑10110( ) nnnnnn kkkP xa xa xaxaa x00va(1,2,)k 1kkkvx

14、 va 利用缩减技术可得如下算法：算法流程图 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-8162 迭代法的校正技术迭代法的校正技术易得人追上龟所花的时间是有些问题的“大事化小”过程似乎无法了结。Zeno悖论强调人“永远”赶不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓预报校正技术预报校正技术来处理。 设人龟起初相距 ，两者的速度分别为 和 ，SVv则有方程VtvtS（1）*StVv Numerical Analysis J. G. Liu Schoo

15、l of Math. & Phys. North China Elec. P.U.2022-5-817注意到 v是个小量，设t也是个小量，则可从上式中略去vt ，即令校正量t满足如下方程(近似近似)设解t*有某个预报值预报值t0，希望提供校正量t，使校正值校正值t1= = t0+ t 能更好的满足所给方程（1），即使得00V ttv ttS00V ttvtS求解上述方程即可定出校正值 01SvttV Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-818进一步视

16、t1为新的预报值，重复实施上述手续，求出新的校正值 t2，再由 t2定 t3 ，如此反复可生成一系列近似值 t1,t2,t3,这就规定了一个迭代过程， 1,0,1,2,kkSvttkV(2)Zeno悖论所描述的逼近过程正是这种迭代过程，当k时，tk t* 。大家知道，任何形式的重复都可看成是“时间”的量度。Zeno在刻画人龟追赶问题中设置了两个“时钟”：一个是日常的钟，另外Zeno又将迭代次数视为另一种时钟，不妨称之为Zeno钟钟。Zeno公式（2）表明，当Zeno钟趋于时人才能追上龟，Zeno正是据此断言人永远追不上龟。 Numerical Analysis J. G. Liu School

17、 of Math. & Phys. North China Elec. P.U.2022-5-819给定 ，求开方值 的问题就是要求解方程 0a a20 xa设给定某个预报值 ，希望借助于某种简单方法确定校正量 ，使校正值0 xx10 xxx能够比较准确地满足方程（1），即使 成立，20 xxa设校正量 是个小量，舍去上式中的高阶小量 ，令 ，从中定出 ，继而可得校正值：x2x2002xxxa x（1）10012axxx利用校正技术，设计求解 （ ）的算法。0a a近似近似 Numerical Analysis J. G. Liu School of Math. & Phys.

18、 North China Elec. P.U.2022-5-82011,0,1,2,2kkkaxxkx反复实施这种预报校正手续，即可导出开方公式开方公式 ：从某个初值 出发，利用上式反复迭代，即可获得满足精度要求的开方值 。 00 x a校正技术的基本思想：删繁就简删繁就简，逐步求精逐步求精 ！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-821其中 ，3 算法优化的松弛技术算法优化的松弛技术10VvSttVvVvVv对于给定的预报值 ，校正值为01SvttV0t据此

19、有 ，两端同除以 ，有10VtvtSV v由于 为人龟追赶问题的精确解，*StVv10*(1)ttt再考察Zeno算法：可见，精确解等于任给预报值同它的校正值的加权平均加权平均：vVv Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-822即通过适当选取权系数 来调整校正量 ，以加工得到更高精度的 ，这种基于校正量的调整与松动的方法通常称为松弛技术松弛技术。 可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的精确解。这种加工效果是奇妙的。在实际计算中常常可以获得目

20、标值 F * 的两个相伴的近似值 F0 与 F1 ，将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作为改进值： 010101FFFFFF10FFF Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-823有一种情况特别引人注目：若所提供的一对近似值 与 有优劣之分，譬如 优而 劣，这时就采用如下松弛方式： 0F1F1F0F101,0FFF即在松弛过程中张扬 的优势而抑制 的劣势，这种设计策略称作外推松弛技术，简称超松弛超松弛。 1F0F总之，超松弛的设计机理是

21、优劣互补，化粗为精优劣互补，化粗为精。松弛技术的关键在于松弛因子的选取松弛因子的选取，而这往往是相当困难的。 返回 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-824 1.2 误差误差 1 误差的分类误差的分类 模模型型误误差差 观观测测误误差差 截截断断误误差差 舍舍入入误误差差 数数值值分分析析进进行行误误差差分分析析的的对对象象 按按来来源源分分类类 Numerical Analysis J. G. Liu School of Math. & Phys.

22、 North China Elec. P.U.2022-5-8252 误差和有效数字(1) (1) 误差误差 定义定义 设 是准确值， 是 的一个近似值，记 ，称 为近似值 的绝对误差绝对误差，简称误差。 axaxeeax若已知 的一个上界为 ，即 ，则称 为近似值 的绝对误差界绝对误差界，简称误差界（越小表示近似程度越高）。 eea注注: : 用绝对误差来刻画近似数的精确程度不能反映它在原数中所占的比例。 例例 , ，可是 与真值 相差一个数量级。 001. 0,0002. 0ax001. 0axeax Numerical Analysis J. G. Liu School of Math.

23、 & Phys. North China Elec. P.U.2022-5-826称 为近似值 的相对误差相对误差, xaxxeer记reaaaxaeer 的一个上界 ,称为近似值 的相对误界相对误界 reara上例中 ，易见近似程度并不高！8 . 0001. 0001. 00002. 0aaxer也可以记为 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-827(2) (2) 误差估计误差估计 n 函数计算的误差估计 121,nnkkknzf x xxxzfab

24、baa对 元函数，设准确值为 和 的近似值分别为 、 ，则 ,( ) |( )| ( )yf xxyabbfaa对一元函数设准确值 和 的近似值分别为 、 ，则 n 算数运算的误差估计121212211222121221aaaaaaaaaaaa aaaaa Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-828解解 绝对误差限是0.01的半个单位，且 ， 有三位有效数字，分别是1，3，8； 有一位有效数字，为3； 没有有效数字。 (3) 有效数字有效数字定义定义 设 是数

25、 的近似值，如果 的绝对误差限是它的某一位的半个单位某一位的半个单位，且从该位到 的第一位非零数字非零数字共有 位，则称 作为 的近似有 位有效数字。 axaanaxn例例 设近似值 ，其绝对误差限都是0.005，求各个近似值各有几位有效数字？41086. 03,0312. 02,38. 11aaa2a000086. 03 a1a3a同一真值的不同近似值，有效数字越多有效数字越多，它的绝对误差和相对误差都越小。 用单精度浮点型变量进行计算的结果至少有6位有效数字，双精度浮点型变量至少有15位有效数字。(注：IEEE754-1985)。注注： Numerical Analysis J. G. L

26、iu School of Math. & Phys. North China Elec. P.U.2022-5-8293 浮点数浮点数（1）浮点数）浮点数“数”在计算机中是以二进制表示的，一个非零二进制数的一般描述形式为：120.2std dd其中di（i=1,2,t）为0或1，称为尾数尾数，且d10；2为基数基数，s称为阶码阶码且满足L s U，这说明计算机只能表示有限个数且是有限精度有限个数且是有限精度，这个实数的子集称为浮点数，记作F。不难验证对于F中任意不为零的数 f，有,mfM其中m=2L-1，M=2U(1-2-t)，因此计算机上的计算会有溢出现象：上溢和下溢！浮点数在接近其

27、下界m处比较稠密，而在接近其上界M处比较稀疏！因此，在计算中通常都是使用相对误差相对误差来控制精度！由于计算机的有限精度而造成的误差称为舍入误差舍入误差！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-830则称近似数a具有n位有效数字位有效数字。若a的绝对误差满足： 120.10mntad ddd 1102m nxa设x的近似值a可表示为规格化浮点数形式 121,090td ddd 其中都是中的整数，且，定理定理 设 ，120.10mnad dd 1510nread反

28、之若近似数a的相对误差满足 15101nread则a至少有n位有效数字。若a是有n位有效数字的近似数，则它的相对误差满足 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-831例例1 要使的 近似值a的相对误差限不超过相对误差限不超过0.1，a应取几位有效数字？ 30例例2 已知 的近似数a相对误差限为相对误差限为0.5，试问a至少有几位有效数字?20参考答案：3参考答案：2 3115: 1010 ,30,5 3nreaddn解 由及对于 115: 0.00510 ,20

29、,4,1 2nreaddn解 由及对于 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-832（2） 截断误差和舍入误差截断误差和舍入误差考虑计算一元可微函数f(x)在x0处导数的近似方法：000000()()(),(1)()()(),(2)2f xhf xfxhf xhf xhfxh因此近似方法（1）的误差为20000()()()()()(4)2f xhf xfxfxhO hh考虑方法（1）：由泰勒展开，可得230000()()()()()(3)2fxf xhf xfx

30、hhO h从而有201()()(5)2fxThO h截断误差 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-833通过实验发现，随着h减小，通过（1）计算的导数近似值与真值的误差是先减小后增大先减小后增大，这种现象是什么原因造成的呢？（演示）其原因就在于计算机是有限精度的，随着h的减小，舍入误差逐渐被放大，并且最终成为引起误差的主导因素！（要求上机体会舍入误差的影响）要学好数值分析课程一定要真正理解舍入误差，特别是舍入误差在算法中的传播传播和对最终结果的影响！同理可以讨

31、论近似方法（2）的截断误差，以及随着h的减小，其误差的变化情况！返回那么是不是那么是不是h越小，计算误差就越小呢？越小，计算误差就越小呢？ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-83402468101214161820-3-2.5-2-1.5-1-0.500.5 向 前中 心300( ),1,()30.1,0.01,f xxxfxh算例： Numerical Analysis J. G. Liu School of Math. & Phys. North

32、 China Elec. P.U.2022-5-835 1.3 数值计算中需要注意的问题数值计算中需要注意的问题1 浮点数的加法浮点数的加法112.;stdd dd 21 2.stcc cc 设两个浮点数相加：两个浮点数相加：首先比较它们的阶码，若阶码相同则尾数相加，相加后若尾数大于1则阶码进位；若阶码不等，则以相对大的阶码为标准，将阶码小的浮点数进行移位，直到阶码一致，再按阶码相同时的规则进行相加！例1 假设计算机只能存放三位十进制数字，设 在该计算机上进行如下运算 001. 0,00. 1,01. 1321xxx（1）计算 与十个 之和，即 ，采用以下两种计算方法 1x3x331xxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-8361） ， ，则 即为所求， 10 xa )10, 1(31ixaaii10a计算得 （错）01. 110a 2） （正确） 02. 101. 001. 1)(331xxx（2） （错） 32311001. 100. 1001. 001. 1 xxx（3） （错） 02. 000. 102. 12221 xx （正确） 2212122211001. 201. 201