数值分析(计算方法).课件.ppt

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

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

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

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

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

6、点三、特点 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-307数值计算方法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性等技术特征，它是一门理论性理论性和实践性实践性都很强的课程。在20世纪70年代，大多数学校仅在数学系的计算数学专业计算数学专业和计算机系计算机系开设计算方法这门课程。随着计算机技术的迅速发展和普及，现在计算方法课程几乎已成为所有理工科大学生的一门必修课程理工科大学生的一门必修课程。n学习过程中应该注意以下几个方面：认清算法的计算对象；掌握基本的计

7、算方法及其原理；用C+语言编制程序，在计算机上对算法进行验证；对于算法要勤思考多比较！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-308参考书目：参考书目：1 钟尔杰.数值分析.高等教育出版社,2004.2 颜庆津.数值分析.修订版.北京航空航天大学出版社,2000.3 李庆扬. 数值分析.清华大学出版社,2001.4 白峰杉.数值计算引论.高等教育出版社,2004.5 王能超.计算方法.北京: 高等教育出版社, 2005. Numerical Analysis J. G.

8、 Liu School of Math. & Phys. North China Elec. P.U.2022-5-3091、算法设计技术2、误差3、数值计算中需要注意的一些问题4、算法的稳定性5、病态问题内容内容: :数值分析的基本概念 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3010 1.1 算法设计技术算法设计技术 古希腊哲学家Zeno(芝诺)在两千多年前提出过一个骇人听闻的命题：一个人不管跑得多快，也追不上爬在他前面的一只乌龟。这就是著名的Zeno悖论。Zeno在

9、论证这个命题时采取了如下形式的逻辑推理：设人与龟同时同向起跑，如果龟不动，那么人经过某段时间便能追上它；但实际上在这段时间内龟又爬了一段路程，从而人又得重新追赶，如下图所示，这样每追赶一次所归结的是同样类型的追赶问题，因而这种追赶过程“永远”不会终结。 引例引例 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3011耐人寻味的是，尽管Zeno悖论的论断极其荒谬，但从算法设计思想的角度来看它却是极为精辟的。Zeno悖论将人龟追赶问题表达为一连串追赶步的逐步逼近过程。设人与龟的速度

10、分别为与，记表示逼近过程的第步人与龟的间距，另以表示相应的时间，相邻两步的时间差。Zeno悖论将人龟追赶问题分解为一追一赶两个过程：1kkStVkkSv t 追的过程：追的过程：先令龟不动，计算人追上龟所费的时间赶的过程：赶的过程：再令人不动，计算龟在这段时间内爬行的路程tkSk-1SkVvtk-1vV 图示: 人龟追赶过程 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3012若以人和龟之间的距离 定义问题的规模规模大小，则上述过程将问题规模压缩了 倍：kSvV1kkvSSV

11、由于龟的速度远远小于人的速度，故 很小，因此按上述步骤很快问题的规模 就可以忽略不计，从而得到人追上龟所花时间 ，Zeno的解释可用如下过程表示：vVkSkt01,1,2,kkvSS SSkVZeno算法可见，Zeno算法的设计思想是，将人龟追赶计算化归为简单的行程计算的重复，它的设计方法是逐步压缩计算模型的规模，这种“化大为小”的设计策略称为规模缩减技术规模缩减技术，简称缩减技术缩减技术。 算法的设计精髓：“简单简单”的重复生成复杂！的重复生成复杂！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec.

12、P.U.2022-5-3013则计算结果即为所求的和值： （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-3014这样，如果定义和式的项数为数列求和问题的规模规模，则所求和值为（1）的退化情形。因之，只要令和式的规模逐次减1，最终当规模为1时即可直接得出所求的和值，而这样设计出来的算法就是累加求和算法（2）。可见，上述累

13、加求和算法的设计思想是将多项求和（1）化归为两项求和（2）的重复，最终加工成一项和式（3）（(1)的退化情形）,从而得出和值。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3015考虑10110( ) nnnnnn kkkP xa xa xaxaa x00va(1,2,)k 1kkkvx va 利用缩减技术可得如下算法：算法流程图考虑问题1 Numerical Analysis J. G. Liu School of Math. & Phys. North China Ele

14、c. P.U.2022-5-30162 迭代法的校正技术迭代法的校正技术易得人追上龟所花的时间是有些问题的“大事化小”过程似乎无法了结。Zeno悖论强调人“永远”赶不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓预报校正技术预报校正技术来处理。 设人龟起初相距 ，两者的速度分别为 和 ，SVv则有方程VtvtS（1）*StVv Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3017注意到 v是个小量，设t也是个小量，则可从上式中略去vt ，即令校正量t满足如下方程

15、(近似近似)设解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-3018进一步视 t1为新的预报值，重复实施上述手续，求出新的校正值 t2，再由 t2定 t3 ，如此反复可生成一系列近似值 t1,t2,t3,这就规定了一个迭代过程， 1,0,1,2,kkSvttkV(2)Zeno悖

16、论所描述的逼近过程正是这种迭代过程，当k时，tk t* （ 考虑问题2 ）。大家知道，任何形式的重复都可看成是“时间”的量度。Zeno在刻画人龟追赶问题中设置了两个“时钟”：一个是日常的钟，另外Zeno又将迭代次数视为另一种时钟，不妨称之为Zeno钟钟。Zeno公式（2）表明，当Zeno钟趋于时人才能追上龟，Zeno正是据此断言人永远追不上龟。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3019给定 ，求开方值 的问题就是要求解方程 0a a20 xa设给定某个预报值 ，希

17、望借助于某种简单方法确定校正量 ，使校正值0 xx10 xxx能够比较准确地满足方程（1），即使 成立，20 xxa设校正量 是个小量，舍去上式中的高阶小量 ，令 ，从中定出 ，继而可得校正值：x2x2002xxxa x（1）10012axxx利用校正技术，设计求解 （ ）的算法。0a a近似近似 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-302011,0,1,2,2kkkaxxkx反复实施这种预报校正手续，即可导出开方公式开方公式 ：从某个初值 出发，利用上式反复迭代，即

18、可获得满足精度要求的开方值 。 00 x a校正技术的基本思想：删繁就简删繁就简，逐步求精逐步求精 ！考虑问题3 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3021其中 ，3 算法优化的松弛技术算法优化的松弛技术10VvSttVvVvVv对于给定的预报值 ，校正值为01SvttV0t据此有 ，两端同除以 ，有10VtvtSV v由于 为人龟追赶问题的精确解，*StVv10*(1)ttt再考察Zeno算法：可见，精确解等于任给预报值同它的校正值的加权平均加权平均：vVv Nu

19、merical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3022即通过适当选取权系数 来调整校正量 ，以加工得到更高精度的 ，这种基于校正量的调整与松动的方法通常称为松弛技术松弛技术。 可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的精确解。这种加工效果是奇妙的。在实际计算中常常可以获得目标值 F * 的两个相伴的近似值 F0 与 F1 ，将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作为改进值： 010101FFFFFF10FFF Numerical Analysi

20、s J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3023有一种情况特别引人注目：若所提供的一对近似值 与 有优劣之分，譬如 优而 劣，这时就采用如下松弛方式： 0F1F1F0F101,0FFF即在松弛过程中张扬 的优势而抑制 的劣势，这种设计策略称作外推松弛技术，简称超松弛超松弛。 1F0F总之，超松弛的设计机理是优劣互补，化粗为精优劣互补，化粗为精。松弛技术的关键在于松弛因子的选取松弛因子的选取，而这往往是相当困难的。 返回 Numerical Analysis J. G. Liu School of Math

21、. & Phys. North China Elec. P.U.2022-5-3024 1.2 误差误差 1 误差的分类误差的分类 模模型型误误差差 观观测测误误差差 截截断断误误差差 舍舍入入误误差差 数数值值分分析析进进行行误误差差分分析析的的对对象象 按按来来源源分分类类 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-30252 误差和有效数字(1) (1) 误差误差 定义定义 设 是准确值， 是 的一个近似值，记 ，称 为近似值 的绝对误差绝对误差，简称误差。 axax

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

23、上例中 ，易见近似程度并不高！8 . 0001. 0001. 00002. 0aaxer也可以记为 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3027(2) (2) 误差估计误差估计 n 函数计算的误差估计 121,nnkkknzf x xxxzfabbaa对 元函数，设准确值为 和 的近似值分别为 、 ，则 ,( ) |( )| ( )yf xxyabbfaa对一元函数设准确值 和 的近似值分别为 、 ，则 n 算数运算的误差估计121212211222121221aaa

24、aaaaaaaaa aaaaa Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3028解解 绝对误差限是0.01的半个单位，且 ， 有三位有效数字，分别是1，3，8； 有一位有效数字，为3； 没有有效数字。 (3) 有效数字有效数字定义定义 设 是数 的近似值，如果 的绝对误差限是它的某一位的半个单位某一位的半个单位，且从该位到 的第一位非零数字非零数字共有 位，则称 作为 的近似有 位有效数字。 axaanaxn例例 设近似值 ，其绝对误差限都是0.005，求各个近似值各有几

25、位有效数字？41086. 03,0312. 02,38. 11aaa2a000086. 03 a1a3a同一真值的不同近似值，有效数字越多有效数字越多，它的绝对误差和相对误差都越小。 用单精度浮点型变量进行计算的结果有七位有效数字，双精度浮点型变量有16位有效数字注注： Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-30293 浮点数浮点数（1）浮点数）浮点数“数”在计算机中是以二进制表示的，一个非零二进制数的一般描述形式为：12.2std dd其中di（i=1,2,t）为0或

26、1，称为尾数尾数，且d10；2为基数基数，s称为阶码阶码且满足L s U，这说明计算机只能表示有限个数且是有限精度有限个数且是有限精度，这个实数的子集称为浮点数，记作F。不难验证对于F中任意不为零的数 f，有,mfM其中m=2L-1，M=2U(1-2-t)，因此计算机上的计算会有溢出现象：上溢和下溢！浮点数在接近其下界m处比较稠密，而在接近其上界M处比较稀疏！因此，在计算中通常都是使用相对误差相对误差来控制精度！由于计算机的有限精度而造成的误差称为舍入误差舍入误差！ Numerical Analysis J. G. Liu School of Math. & Phys. North China

27、 Elec. P.U.2022-5-3030（2） 截断误差和舍入误差截断误差和舍入误差考虑计算一元可微函数f(x)在x0处导数的近似方法：000000()()(),(1)()()(),(2)2f xhf xfxhf xhf xhfxh因此近似方法（1）的误差为20000()()()()()(4)2f xhf xfxfxhO hh考虑方法（1）：由泰勒展开，可得230000()()()()()(3)2fxf xhf xfxhhO h从而有201()()(5)2fxThO h截断误差考虑问题4 Numerical Analysis J. G. Liu School of Math. & Phys

28、. North China Elec. P.U.2022-5-3031通过实验发现，随着h减小，通过（1）计算的导数近似值与真值的误差是先减小后增大先减小后增大，这种现象是什么原因造成的呢？其原因就在于计算机是有限精度的，随着h的减小，舍入误差逐渐被放大，并且最终成为引起误差的主导因素！（要求上机体会舍入误差的影响）要学好数值分析课程一定要真正理解舍入误差，特别是舍入误差在算法中的传播传播和对最终结果的影响！同理可以讨论近似方法（2）的截断误差，以及随着h的减小，其误差的变化情况！返回那么是不是那么是不是h越小，计算误差就越小呢？越小，计算误差就越小呢？考虑问题5 Numerical Anal

29、ysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3032 1.3 数值计算中需要注意的问题数值计算中需要注意的问题1 浮点数的加法浮点数的加法112.;stdd dd 21 2.stcc cc 设两个浮点数相加：两个浮点数相加：首先比较它们的阶码，若阶码相同则尾数相加，相加后若尾数大于1则阶码进位；若阶码不等，则以相对大的阶码为标准，将阶码小的浮点数进行移位，直到阶码一致，再按阶码相同时的规则进行相加！例1 假设计算机只能存放三位十进制数字，设 在该计算机上进行如下运算 001. 0,00. 1,01. 1

30、321xxx（1）计算 与十个 之和，即 ，采用以下两种计算方法 1x3x331xxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-30331） ， ，则 即为所求， 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 （正确） 2212122211

31、001. 201. 201. 0)(xxxxxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3034例2 计算 127x -只需要做12次乘法 643216842127xxxxxxxx2 2 数值计算的一些基本原则数值计算的一些基本原则（1）由于计算机字长的限制 防止小数加到大数上； 防止除数过小； 防止相近的数相减(会损失有效数字)；（2）由于计算机的计算原理 要尽量减少乘除法的运算次数 返回 Numerical Analysis J. G. Liu School of

32、Math. & Phys. North China Elec. P.U.2022-5-3035 1.4 算法的稳定性算法的稳定性首先来看一个例子，考虑积分序列：110,1,2,nxnEx edxn（1）显然 ，且计算可得 ，对 进行分部积分得0nE 11Ee2n 11101,2,3,nxnnEx edxnEn并且 1110010,()1nxnnEx edxx dxnn为了估计积分序列 ，我们构造如下方法：nE（2）（3） Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3036方

33、法方法1(直接应用（2）) 111,1,2,3,nnEEnEne方法方法2（考虑到结果（3）110,1,2nNnEEEnN Nn 考虑舍入误差，方法1不可取！若在计算过程中误差被无限制放大误差被无限制放大，则称该算法不稳不稳定定，否则称之为稳定算法。返回 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3037 5 病态问题病态问题例子例子 其中a分别取0.99和0.991，算得结果分别为可见系数的微小变化，引起了结果比较大的改变！我们称该问题是病态问题病态问题！121210 x

34、axaxx求解方程组1250.25,49.75xx 1255.8155.30 xx一般的，我们称对误差敏感的问题为病态问题病态问题，否则称为良态良态的！返回 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-3038思考题:121,10 ,10 ,xxh计算的数值解 步长观察数值解与精确解的近似程度，并分析原因!问题问题4：计算近似方法（2）的截断误差！ 问题问题3:编程实现!要求：画出流程图，初始值由键盘输入。问题问题2: 证明该结论！问题问题1:编程实现任意阶多项式的计算!问题5：