数值计算方法在计算机科学中的应用和误差序列试验课案

1、数值方法实验报告 数值计算方法在计算机科学中的应用和误差序列实验 郑发进 2012042020022 【摘要】计算数学也叫做数值计算方法或数值分析。主要内容包括代数方程、线性代数 方程组、微分方程的数值解法，函数的数值逼近问题，矩阵特征值的求法，最优化计算问题， 概率统计计算问题等等，还包括解的存在性、唯一性、收敛性和误差分析等理论问题。 测量 值与真实值之间的差异称为误差，物理实验离不开对物理量的测量，测量有直接的，也有间 接的。由于仪器、实验条件、环境等因素的限制，测量不可能无限精确，物理量的测量值与 客观存在的真实值之间总会存在着一定的差异， 这种差异就是测量误差。 误差是不可避免的，

2、只能减小。 关 键 词 数值计算方法、计算机科学、误差 、数值计算方法在计算机科学中的应用 、数值计算方法概述 （一）数值计算方法属于计算数学的范畴，是研究各种数学问题的数值方法设计、分析、 有关的数学理论和具体实现的一门学科。由于近几十年来计算机的迅速发展，数值计算方法 的应用已经普遍深入到各个科学领域，很多复杂的和大规模的计算问题都可以在计算机上进 行计算，新的、有效的数值计算方法不断出现。现在，科学与工程中的数值计算已经成为各 门自然科学和工程技术科学的一种重要手段， 成为与实验和理论并列的一个不可缺少的环节。 所以数值计算方法既是一个基础性的，同时也是一个应用性的数学学科，与其它学科的

3、联系 十分紧密。 由于大量的问题要在计算机上求解， 所以要对各种数值计算方法进行分析， 其内容包括： 误差、稳定性、收敛性、计算工作量、存贮量和自适应性，这些基本的概念用于刻画数值方 法的适用范围、可靠性、准确性、效率和使用的方便性等。 当代实际的科学与工程计算中，计算问题往往是复杂的和综合的。但是有一些最基础、 最常用的数值计算方法，它们成为通常大学数值计算方法课程的内容。本书主要讨论这些方 法及其分析，它们包括逼近问题 （函数的插值和逼近， 数值积分和微分） ，线性代数问题（方 程组和特征值问题） 和非线性方程及方程组的数值解法问题， 以及常微分方程的数值解法等。 这些是数值计算方法最基础

4、的内容，不仅可以直接应用于实际计算，同时也是其它数值计算 问题所用到的方法及其分析的基础。 （二）数值计算方法（或称计算方法）是研究数学问题求数值解的算法和有关理论的一门 学科，它的理论与方法随计算工具的发展而发展。在古代，人类研究的数学问题几乎总与计 算有关，而计算工具的简陋，使求解问题受到很大限制。现代科学技术日新月异，尤其是计 算机技术飞速发展，人类可以用计算机进行复杂的数值计算、数据处理（包括图形，图像， 声音，文字），计算机不仅是现代计算工具，而且已成了我们工作环境的一部分。计算方法 数值方法实验报告 所研究的内容是用计算机解决数学问题的方法（包括算法）和理论。用计算机进行数值计算

5、的核心是算法设计。算法是对解题方案的准确描述，是“解题的操作序列”。在研究算法时， 离不开误差分析，同时还需要考虑算法的稳定性、收敛性、计算工作量等问题。 （三）计算方法是计算数学的一个主要部分。而计算数学是数学科学的一个分支，它研究 用计算机求解数学问题的数值计算方法及其软件实现。计算数学几乎与数学科学的一切分支 有联系，它利用数学领域的成果发展了新的更有效的算法及其理论，反过来很多数学分支都 需要探讨和研究适用于计算机的数值方法。因此，计算方法的内容十分广泛。但本书作为计 算方法的基础，只介绍科学与工程计算中最常用的基本数值方法，包括线性方程组与非线性 方程求根、插值与最小二乘拟合、数值积

6、分与常微分方程数值解法等。这些都是计算数学中 最基础的内容。 近几十年来由于计算机的发展及其在各技术科学领域的应用推广与深化，新的计算性学 科分支纷纷兴起，如计算力学、计算物理、计算化学、计算经济学等等，不论其背景与含义 如何，要用计算机进行科学计算都必须建立相应的数学模型，并研究其适合于计算机编程的 计算方法。因此，计算数学是各种计算性科学的联系纽带和共性基础，是一门兼有基础性、 应用性和边缘性的数学学科。 、数值计算方法研究的对象、任务与特点 计算数学作为数学科学的一个分支，当然具有数学科学的抽象性与严密科学性的特点， 但它又具有广泛的应用性和边缘性特点。 现代科学发展依赖于理论研究、科学

7、实验与科学计算三种主要手段，它们相辅相成，互 相独立， 可以互相补充又都不可缺少， 作为三种科学研究手段之一的科学计算是一门工具性。 方法性、边缘性的新学科，发展迅速，它的物质基础是计算机（包括其软硬件系统），其理 论基础主要是计算数学。 计算数学与计算工具发展密切相关，在计算机出现以前，数值计算方法只能计算规模小的问 题，并且也没形成单独的学科，只有在计算机出现以后，数值计算才得以迅速发展并成为数 学科学中一个独立学科计算数学。当代计算能力的大幅度提高既来自计算机的进步，也 来自计算方法的进步，计算机与计算方法的发展是相辅相成、互相促进的。计算方法的发展 启发了新的计算机体系结构，而计算机的

8、更新换代也对计算方法提出了新的标准和要求。例 如为在计算机上求解大规模的计算问题、提高计算效率，诞生并发展了并行计算机。自计算 机诞生以来，经典的计算方法业已经历了一个重新评价、筛选、改造和创新的过程，与此同 时，涌现了许多新概念、新课题和能充分发挥计算机潜力、有更大解题能力的新方法，这就 构成了现代意义下的计算数学。这也是数值分析的研究对象与特点。 概括地说，计算方法是研究适合于在计算机上使用的实际可行、理论可靠、计算复杂性 好的数值计算方法。具体说就是： 第一，面向计算机，要根据计算机特点提供实际可行的算法，即算法只能由计算机可执 行的加减乘除四则运算和各种逻辑运算组成。 第二，要有可靠的

9、理论分析，数值分析中的算法理论主要是连续系统的离散化及离散型 方程数值求解。有关基本概念包括误差、稳定性、收敛性、计算量、存储量等，这些概念是 刻画计算方法的可靠性、准确性、效率以及使用的方便性。 第三，要有良好的复杂性及数值试验，计算复杂性是算法好坏的标志，它包括时间复杂 性（指计算时间多少）和空间复杂性（指占用存储单元多少）对很多数值问题使用不同算法， 数值方法实验报告 3 其计算复杂性将会大不一样，例如对 20 阶的线性方程组若用代数中的 Cramer法则作为算法 求解，其乘除法运算次数需要 9.7 1020次，若用每秒运算 1 亿次的计算机计算也要 30 万年， 这是无法实现的，而用计

10、算方法中介绍的 Gauss消去法求解，其乘除法运算次数只需 3060 次， 这说明选择算法的重要性。当然有很多数值方法不可能事先知道其计算量，故对所有数值方 法除理论分析外，还必须通过数值试验检验其计算复杂性。本课程虽然只着重介绍计算方法 及其理论，一般不涉及具体的算法设计及编程技巧，但作为基本要求仍希望读者能适当做一 些计算机上的数值试验，它对加深算法的理解是很有好处的。 三、数值计算方法与计算机科学 计算机的飞速发展，正在日益影响着人们对传统数值分析（即计算方法）的认识。近几 十年来，人们越来越认识到计算方法的学习与研究离不开计算机，仅仅只依靠数学理论的演 绎和推导还不能解决实际中的数值问

11、题，只有与计算机科学相结合，才能研制出实用的好算 法。而且好的算法必须变成数值软件后才有可能为社会创造更大的财富。当代实践证明，计 算方法正在日趋明显地成为数学与计算机科学的交叉性学科。 数学与计算机科学的密切关系，历史已作了回答，可以说计算机科学是吸吮着数学的乳 汁而成长起来的。德国数学家 Leibniz 在研究组合数学时发现的二进制编码是电子计算机诞 生的基础； VOn Nellmsnll 提出了用流程图描述计算机运行过程后，软件的开发研究才得以 发展和遍地开花；流行一时的结构化程序设计也是 Bohm和 JacoPini 证明的一条数学原理 “任何单入口和单出口， 且没有“死循环”的程序，

12、 都能由三种最基本的控制结构构造出来” 的产物。另一方面，计算机的诞生和发展，给数学增加了新的血液，对数学的发展产生了不 可估量的影响。借助于计算机可以证明玄妙的数学定理、揭示某些数学规律，以及求解许多 原来令人一筹莫展的数学模型问题；由于并行计算机的诞生和发展，促使数学工作者去研究 适应新一代计算机发展需要的算法并行算法。总之，由于计算机科学的发展，可以使数 学上灵活的推演和运算改变成遵循某种规律的算法设计，从而为发展数值软件奠定了基础。 因此，计算方法也得到更快发展，大量适合计算机求解的现代数值方法随之产生，并被广泛 使用，成为当代科学计算的主要方法。 使用传统的计算方法解决实际问题，不但

13、要求使用者具有一定的数学修养，而且还应具 有相当的编程能力，因而使计算方法的广泛应用受到了影响。为解决这些问题，科学计算工 作者经过长时间努力，将数值方法设计成算法，进而编制成数值软件，并逐步形成数值软件 产业，为广大用户打开了方便之门。当今，已有不少集各种数值算法于一体的综合数学软件 库（包括数值软件）。在国内外具有代表性的部分综合数学软件库（包）分别为： IMSL（International Mathematics and Statistics Library）是美国 IMSL 公司研制的 大型数学和统计软件库，自研制至今已更新了十多个版本，是目前国内外流传最广，影响最 大的数值软件库之一

14、。 NAGmumerical Algorithm GrOUP ）是英国政府研究机构联合几所大学共同研制成功的大 型综合性数值软件库，它用多种语言写成，可移植性非常好，普遍流行于欧洲，在我国也有 用户。 “ Mathematica ”是 1988 年美国 IllilloiS大学开发成功的综合数学软件包，它把符号 演算、数值计算、图形演示以及人机交互接口有机地结合在一起，几乎包括大学本科的所有 数学演算和数值计算，为研究和应用数学理论和方法提供了先进的环境，目前是国内外广泛 流行的数学软件包。 数值方法实验报告 STYR（是“数学、统计、应用、软件”的汉语拼音的首字母人是中国科学院计算中心等 单位

15、在“七五”期间联合开发的综合性数值软件库，是我国开发的第一个大型综合数值软件 库，在国内有一定影响。 CUMS（S China University Mathematics and Statistics Software的缩写）是 1987年 由原国家教委的六所高校联合开发成功的综合性数学与统计软件库，是我国迄今第一个正式 出版的大型综合数值软件库。 数学软件库（包）的引进与开发，给工程技术人员使用数值方法求解各种数值问题带来 了极大的方便。但是，如果工程技术人员仅知道如何使用这些数值软件，一旦出现问题就难 于解决；再者，有不少工程技术人员需要结合各自的具体需求灵活使用软件库，或者自己设 计专

16、用算法。因此，虽然有了各种软件库， 工程技术人员掌握数值方法和算法设计基础还是 很有必要的，这可以使他们真正成为使用数学软件库的“主人”。为此，本教程不追求完美 的数学演绎、论证以及详尽的公式推导，也不以数学课程的类别为序来讲述数值计算方法， 而尽量以数值计算方法间的内在联系为主线，着重介绍数值计算方法及它们之间的关系与结 构，力求少而精，使读者用较少的学时能对一般常用数值计算方法有较多的了解与掌握，并 为进一步研究新算法奠定基础；内容以研究计算机上常用数值计算方法为主要对象，尽可能 缩小数值计算方法与程序设计之间的距离，通过对一些有代表性的算法设计介绍，使读者了 解数值计算方法与算法之间的关

17、系与差别，初步掌握算法设计技术，为使用计算机求解数学 模型问题架好桥梁；通过课堂教学与计算实习，使读者尽可能多地了解算法设计与程序设计 之间的关系，进而培养用计算机解决实际问题的技能。 以计算机为工具来求解各种数学模型，无论使用何种方法，均需要经历三个中间过程： 总体设计（模型的细化等），详细设计（主要为算法设计）和程序设计等。计算机数值计算 方法主要是研究将数学模型变成数值问题，并研究求解数值问题的数值计算方法，进而设计 数值计算算法。 二、误差序列实验 一）、实验描述 参照 1.25 对 3 个差分方程计算出前十个数值的近似值，构造列表和图 形。误差算法分别为 xn rn, xn pn,

18、xn qn . 数值方法实验报告 二)、实验内容 对下列三个差分方程计算出前 10 个数值近似值。在每种情况下引入一个小的初始误 1 差。如果没有初始误差，则每个差分方程将生成序列1n。用 MATLAB构造生成图表 2n n=1 1 (a) r0 =0.994; rn = 2 rn -1 ,其中 n=1,2, 31 (b) p0=1,p1=0.497,pn= 2 pn-1- 2 pn-2 ，其中 n=2,3, 5 (c) q0 =1, q1 =0.497, qn = 2q n-1 -qn-2 , 其中 n=2,3, (三)、实验结果及分析 按附件的代码得到下面的图表。 表 1 序列= xn 1

19、/ 3n以及近似值 rn， pn和qn n xn rn pn qn 0 1.00000000000 0.99400000000 1.000000000000 1.000000000000 0000 0000 000 000 1 0.50000000000 0.49700000000 0.497000000000 0.497000000000 0000 0000 000 000 2 0.25000000000 0.24850000000 0.245500000000 0.242500000000 0000 0000 000 000 3 0.12500000000 0.12425000000 0.

20、119750000000 0.115250000000 0000 0000 000 000 4 0.06250000000 0.06212500000 0.056875000000 0.051625000000 0000 0000 000 000 5 0.03125000000 0.03106250000 0.025437500000 0.019812500000 数值方法实验报告 0000 0000 000 000 6 0.01562500000 0.01553125000 0.009718750000 0.003906250000 0000 0000 000 000 7 0.0078125

21、0000 0.00776562500 0.001859375000 -0.00404687500 0000 0000 000 0000 8 0.00390625000 0.00388281250 -0.00207031250 -0.00802343750 0000 0000 0000 0000 9 0.00195312500 0.00194140625 -0.00403515625 -0.01001171875 0000 0000 0000 0000 1 0.00097656250 0.00097070312 -0.00501757812 -0.01100585937 0 0000 5000

22、5000 5000 表 2 误差序列 xn rn , xn pn和 xn qn n xn rn xn pn xn qn 0 0.00600000000 0.000000000000 0.000000000000000 0000 000 1 0.00300000000 0.003000000000 0.003000000000000 0000 000 2 0.00150000000 0.004500000000 0.007500000000000 0000 000 3 0.00075000000 0.005250000000 0.015750000000000 0000 000 4 0.0003

23、7500000 0.005625000000 0.031875000000000 0000 000 5 0.00018750000 0.005812500000 0.063937500000001 0000 000 6 0.00009375000 0.005906250000 0.127968750000001 0000 000 7 0.00004687500 0.005953125000 0.255984375000003 0000 000 8 0.00002343750 0.005976562500 0.511992187500005 0000 000 9 0.00001171875 0.

24、005988281250 1.023996093750010 0000 000 10 0.00000585937 0.005994140625 2.047998046875021 5000 000 数值方法实验报告 rn 是误差稳定的，且按指数级递减，相差不大较为稳定，说明该序列和等比序列较为 接近。 pn 的误差不大较为稳定，但误差呈递增状态，所以其逼近效果不如 rn。 qn的误 差是不稳定的，变化幅度较大，即 n 越大，误差越大，说明当 n 时，误差可能比数值更 大。 以下就是差分方程的的图形 -3 x 10 7 nr-n 图 1 稳定递减的误差序列 xn rn 数值方法实验报告 -3 n

25、p-n 图 2 稳定的误差序列 xn pn 数值方法实验报告 5 1 np-nx 0.5 0 01 2 3 4 5 6 7 8 9 10 图 3 不稳定的误差序列 xn qn （四）、结论 通过对于差分方程的求解可知，不同的差分方程的初始误差传播会随着其表达式的不同 有很大差异性。因此，对于不同差分方程的选取问题和计算问题应慎重选择，选择稳定算法 附件(代码)： n=0:10; xn=1./(2.n) %-n is the input-sequence %-xn is the value of the sequence (a) r0=0.994;r(1)=r0/2 for n=2:10 r(n)=r(n-1)/2; %-r(n) is the general term of xn end r0,r 数值方法实验报告 10 (b) p0=1;p(1)=0.497;p(2)=3*p(1)/2-p0/2; for n=3:10 p(n)=3*p(n-1)/2-p(n-2)/2; %-p(n) is the general term of pn end p0,p %- show all the items of pn (c) q0=1;q(1)=0.497;q(2)=5*q(