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

《数值分析(计算方法)介绍.ppt》由会员分享，可在线阅读，更多相关《数值分析(计算方法)介绍.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.数数 值值 分分 析析插值、拟合与数值微积分插值、拟合与数值微积分主讲：刘敬刚刘敬刚2/17/20231 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.数值分析数值分析(计算方法计算方法)简介简介考虑如下线性方程组 或者：其中 ,由克莱姆法则可知(1)有唯一的解，而且解为：(1)引例引例 2/17/20232 Numerical Analysis J.G.Liu S

2、chool of Math.&Phys.North China Elec.P.U.若行列式用按行（列）展开的方法计算，用克莱姆法则求解（1）需做乘除法的次数:当方程组阶数较高时，计算量很大，因此克莱姆法则通常仅有理论上的价值，计算线性方程组的解还要考虑数值解法数值解法=算法算法+计算机计算机。首先看一个简单的例子：（若是更高阶的方程组呢？）人类的计算能力计算能力是计算工具计算工具和计算方法计算方法效率的乘积，提高计算方法的效率与提高计算机硬件的效率同样重要。科学计算科学计算已用到科学技术和社会生活的各个领域中，成为继实验实验和理论研究理论研究之后的第三种研究方法。2/17/20233 Nume

3、rical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.研究对象和主要内容研究对象和主要内容2/17/20234 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.n数值分析（数值计算方法）的计算对象是线性代数，微积分，常微分方程中的数学问题。内容包括：求解线性方程求解线性方程组的组的数值解法数值解法、计算矩阵特征值和特征向量、计算矩阵特征值和特征向量、非线性方程、非线性方程和非线性方程组的迭代解法、和非线性方程组的迭代解法、插值插值

4、与与拟合、数值微积分和拟合、数值微积分和常微分方程数值解等问题。常微分方程数值解等问题。直接解法直接解法 若计算过程没有舍入误差，经过有限次算术运算就能求出问题精确解的数值方法。迭代解法迭代解法 若计算过程没有舍入误差，也不能经过有限次算术运算求得问题的精确解，而只能是逐步逼近逼近的数值方法。n数值分析（数值计算方法），是一种研究如何求解数学问题数值近似解数值近似解的方法，是在计算机计算机上使用的解数学问题的方法，简称计算方法。包括直接方法直接方法和迭代方法迭代方法!2/17/20235 Numerical Analysis J.G.Liu School of Math.&Phys.North

5、 China Elec.P.U.特点特点2/17/20236 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.n学习过程中应该注意以下几个方面：认清算法的计算对象；掌握基本的计算方法及其原理；用C+语言编制程序，在计算机上对算法进行验证；对于算法要勤思考多比较！数值分析（数值计算方法）既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性等技术特征，它是一门理论性理论性和实践性实践性都很强的课程。在70年代，大多数学校仅在数学系的计算数学专业计算数学专业和计算机系计算机系开设计算方法这门课程。随着计算

6、机技术的迅速发展和普及，现在计算方法课程几乎已成为所有理工科大学生的一门必修课程理工科大学生的一门必修课程。2/17/20237 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.参考书目：参考书目：1 钟尔杰.数值分析.高等教育出版社，2004.2 颜庆津.数值分析.修订版.北京航空航天大学出版社,2000.3 李庆扬.数值分析.清华大学出版社，2001.4 白峰杉.数值计算引论.高等教育出版社,2004.5 王能超.计算方法.北京:高等教育出版社,20052/17/20238 Numerical Ana

7、lysis J.G.Liu School of Math.&Phys.North China Elec.P.U.数值分析的基本概念算法设计技术误差数值计算中需要注意的一些问题算法的稳定性病态问题内容内容:2/17/20239 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.算法设计技术算法设计技术 古希腊哲学家Zeno在两千多年前提出过一个骇人听闻的命题：一个人不管跑得多快，也追不上爬在他前面的一只乌龟。这就是著名的Zeno悖论。Zeno在论证这个命题时采取了如下形式的逻辑推理：设人与龟同时同向起跑，如果

8、龟不动，那么人经过某段时间便能追上它；但实际上在这段时间内龟又爬了一段路程，从而人又得重新追赶，如下图所示，这样每追赶一次所归结的是同样类型的追赶问题，因而这种追赶过程“永远”不会终结。引例引例2/17/202310 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.耐人寻味的是，尽管Zeno悖论的论断极其荒谬，但从算法设计思想的角度来看它却是极为精辟的。Zeno悖论将人龟追赶问题表达为一连串追赶步的逐步逼近过程。设人与龟的速度分别为V与v，记Sk表示逼近过程的第k步人与龟的间距，另以tk表示相应的时间，相

9、邻两步的时间差为tk。Zeno悖论将人龟追赶问题分解为一追一赶两个过程：追的过程：追的过程：先令龟不动，计算人追上龟所费的时间赶的过程：赶的过程：再令人不动，计算龟在这段时间内爬行的路程tkSk-1SkVvtk-1vV 图示:人龟追赶过程2/17/202311 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.若以人和龟之间的距离 定义问题的规模规模大小，则上述过程将问题规模压缩了 倍：由于龟的速度远远小于人的速度，故 很小，因此按上述步骤很快问题的规模 就可以忽略不计，从而得到人追上龟所花时间 ，Zeno

10、的解释可用如下过程表示：Zeno算法可见，Zeno算法的设计思想是，将人龟追赶计算化归为简单的行程计算的重复，它的设计方法是逐步压缩计算模型的规模，这种“化大为小”的设计策略称为规模缩减技术规模缩减技术，简称缩减技术缩减技术。算法的设计精髓精髓：“简单”的重复生成复杂！2/17/202312 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.数列求和问题：（1）是最简单的计算模型。若记表示前n项的部分和，则有 （2）则计算结果即为所求的和值：（3）这样，如果定义和式的项数为数列求和问题的规规模模，则所求和值

11、为（1）的退化情形。因之，只要令和式的规模逐次减1，最终当规模为1时即可直接得出所求的和值，而这样设计出来的算法就是累加求和算法（2）。直接法的缩减技术直接法的缩减技术可见，上述累加求和算法的设计思想是将多项求和（1）化归为两项求和（2）的重复，最终加工成一项和式（3）（(1)的退化情形）,从而得出和值。2/17/202313 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.考虑利用缩减技术可得如下算法：算法流程图问题问题1:编程实现任意阶多项式的计算!2/17/202314 Numerical Anal

12、ysis J.G.Liu School of Math.&Phys.North China Elec.P.U.迭代法的校正技术迭代法的校正技术易得人追上龟所花的时间是注意到 v是个小量，设t也是个小量，则可从上式中略去vt，即令校正量t满足如下方程(近似近似)有些问题的“大事化小”过程似乎无法了结。Zeno悖论强调人“永远”赶不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓预预报校正技术报校正技术来处理。设人龟起初相距 ，两者的速度分别为 和 ，则有方程（1）设解t*有某个预报值预报值t0，希望提供校正量t，使校正值校正值t1=t0+t 能更好的满足所给方程（1），即使得2/17

13、/202315 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.进一步视 t1为新的预报值，重复实施上述手续，求出新的校正值 t2，再由 t2定 t3，如此反复可生成一系列近似值 t1,t2,t3,这就规定了一个迭代过程，求解上述方程即可定出校正值(2)Zeno悖论所描述的逼近过程正是这种迭代过程，当当k时，时，tk t*（问题问题2:2:证明该结论！）。大家知道，任何形式的重复都可看成是“时间”的量度。Zeno在刻画人龟追赶问题中设置了两个“时钟”：一个是日常的钟，另外Zeno又将迭代次数视为另一种时钟

14、，不妨称之为Zeno钟钟。Zeno公式（2）表明，当Zeno钟趋于时人才能追上龟，Zeno正是据此断言人永远追不上龟。2/17/202316 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.给定 ，求开方值 的问题就是要求解方程 设给定某个预报值 ，希望借助于某种简单方法确定校正量 ，使校正值能够比较准确地满足方程（1），即使 成立，设校正量 是个小量，舍去上式中的高阶小量 ，令 ，从中定出 ，继而可得校正值：（1）反复实施这种预报校正手续，即可导出开方公式开方公式：从某个初值 出发，利用上式反复迭代，即

15、可获得满足精度要求的开方值 。利用校正技术，设计求解 （）的算法。校正技术的基本思想：删繁就简删繁就简，逐步求精逐步求精！近似近似问题问题3:编程实现编程实现!要要求：画出流程图，求：画出流程图，初始值由键盘输入。初始值由键盘输入。2/17/202317 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.算法优化的松弛技术算法优化的松弛技术对于给定的预报值 ，校正值为据此有有 ，两端同除以 ，有由于 为人龟追赶问题的精确解，再考察Zeno算法：由此可见，精确解等于任给预报值同它的校正值的加权平均加权平均：其

16、中 ，可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的精确解。这种加工效果是奇妙的。2/17/202318 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.在实际计算中常常可以获得目标值 F*的两个相伴的近似值 F0 与 F1，将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作为改进值：即通过适当选取权系数 来调整校正量 ，以加工得到更高精度的 ，这种基于校正量的调整与松动的方法通常称为松弛技术松弛技术。有一种情况特别引人注目：若所提供的一对近似值 与 有优劣之分，譬如 优而 劣，这

17、时就采用如下松弛方式：即在松弛过程中张扬 的优势而抑制 的劣势，这种设计策略称作外推松弛技术，简称超松弛超松弛。总之，超松弛的设计机理是优劣互补，化粗为精优劣互补，化粗为精。松弛技术的关键在于松弛因子的选取松弛因子的选取，而这往往是相当困难的。返回2/17/202319 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.误差误差 误差的分类误差的分类2/17/202320 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U

18、.误差和有效数字(1)(1)误差误差 定义定义 设 是准确值，是 的一个近似值，记 ，称 为近似值 的绝对误差差，简称误差。若已知 的一个上界为 ，即 ，则称 为近似值 的绝对误差界绝对误差界，简称误差界（越小表示近似程度越高）。注注:用绝对误差来刻画近似数的精确程度不能反映它在原数中所占的比例。例 ，可是 与真值 相差一个数量级。记 ，称 为近似值 的相对误差相对误差，也可以记为 的一个上界 ,称为近似值 的相对误界相对误界 上例中 ，易见近似程度并不高！2/17/202321 Numerical Analysis J.G.Liu School of Math.&Phys.North Chi

19、na Elec.P.U.(2)有效数字有效数字例例 设近似值 ，其绝对误差限都是0.005，求各个近似值各有几位有效数字？解解 绝对误差限是0.01的半个单位，且 ，有三位有效数字，分别是1，3，8；有一位有效数字，为3；没有有效数字。同一真值的不同近似值，有效数字越多有效数字越多，它的绝对误差和相对误 差都越小。用单精度浮点型变量进行计算的结果有七位有效数字，双精度浮 点型变量有16位有效数字注注：定义定义 设 是数 的近似值，如果 的绝对误差限是它的某一某一位的半个单位位的半个单位，且从该位到 的第一位非零数字非零数字共有 位，则称 作为 的近似有 位有效数字。2/17/202322 Nu

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

21、其上界M处比较稀疏！因此，在计算中通常都是使用相对误差相对误差来控制精度！由于计算机的有限精度而造成的误差称为舍入误差舍入误差！2/17/202323 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.（2）截断误差和舍入误差截断误差和舍入误差考虑计算一元可微函数f(x)在x0处导数的近似方法：因此近似方法（1）的误差为考虑方法（1）：由泰勒展开，可得从而有截断误差问题4：计算近似方法（2）的截断误差！2/17/202324 Numerical Analysis J.G.Liu School of Math

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

23、ool of Math.&Phys.North China Elec.P.U.数值计算中需要注意的问题数值计算中需要注意的问题 浮点数的加法浮点数的加法设两个浮点数相加：两个浮点数相加：首先比较它们的阶码，若阶码相同则尾数相加，相加后若尾数大于1则阶码进位；若阶码不等，则以相对大的阶码为标准，将阶码小的浮点数进行移位，直到阶码一致，再按阶码相同时的规则进行相加！例1 假设计算机只能存放三位十进制数字，设 ，在该计算机上进行如下运算（1）计算 与十个 之和，即 ，采用以下两种计算方法 1），则 即为所求，计算得 （错）2）（正确）2/17/202326 Numerical Analysis J.

24、G.Liu School of Math.&Phys.North China Elec.P.U.（2）（错）（3）（错）（正确）例2 计算 -只需要做12次乘法 2/17/202327 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.数值计算的一些基本原则数值计算的一些基本原则（1）由于计算机字长的限制 防止小数加到大数上；防止除数过小；防止相近的数相减(会损失有效数字)；（2）由于计算机的计算原理 要尽量减少乘除法的运算次数 返回2/17/202328 Numerical Analysis J.G.Li

25、u School of Math.&Phys.North China Elec.P.U.算法的稳定性算法的稳定性首先来看一个例子，考虑积分序列：（1）显然 ，且计算可得 ，对 进行分部积分得并且 为了估计积分序列 ，我们构造如下方法：方法方法1(直接应用（2）)（2）（3）方法方法2（考虑到结果（3）考虑舍入误差，方法1不可取！若在计算过程中误差被无限制放大误差被无限制放大，则称该算法不稳定不稳定，否则称之为稳定算法。返回2/17/202329 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.病态问题病态问题例子例子 其中a分别取0.99和0.991，算得结果分别为可见系数的微小变化系数的微小变化，引起了结果比较大的改变结果比较大的改变！我们称该问题是病态问题病态问题！求解方程组 ，和一般的，我们称对误差敏感的问题为病态问题病态问题，否则称为良态良态的！返回常规的算法对于病态问题的求解通常是无效的，因此在求解时要特别引起注意！2/17/202330