数值计算方法在计算机科学中的应用和误差序列实验.doc

数值计算方法在计算机科学中的应用和误差序列实验【摘要】计算数学也叫做数值计算方法或数值分析。主要内容包括代数方程、线性代数方程组、微分方程的数值解法，函数的数值逼近问题，矩阵特征值的求法，最优化计算问题，概率统计计算问题等等，还包括解的存在性、唯一性、收敛性和误差分析等理论问题。测量值与真实值之间的差异称为误差，物理实验离不开对物理量的测量，测量有直接的，也有间接的。由于仪器、实验条件、环境等因素的限制，测量不可能无限精确，物理量的测量值与客观存在的真实值之间总会存在着一定的差异，这种差异就是测量误差。误差是不可避免的，只能减小。 关 键 词 数值计算方法、计算机科学、误差一、数值计算方法在计算机科学中的应用1、 数值计算方法概述 （一）数值计算方法属于计算数学的范畴，是研究各种数学问题的数值方法设计、分析、有关的数学理论和具体实现的一门学科。由于近几十年来计算机的迅速发展，数值计算方法的应用已经普遍深入到各个科学领域，很多复杂的和大规模的计算问题都可以在计算机上进行计算，新的、有效的数值计算方法不断出现。现在，科学与工程中的数值计算已经成为各门自然科学和工程技术科学的一种重要手段，成为与实验和理论并列的一个不可缺少的环节。所以数值计算方法既是一个基础性的，同时也是一个应用性的数学学科，与其它学科的联系十分紧密。 由于大量的问题要在计算机上求解，所以要对各种数值计算方法进行分析，其内容包括：误差、稳定性、收敛性、计算工作量、存贮量和自适应性，这些基本的概念用于刻画数值方法的适用范围、可靠性、准确性、效率和使用的方便性等。 当代实际的科学与工程计算中，计算问题往往是复杂的和综合的。但是有一些最基础、最常用的数值计算方法，它们成为通常大学数值计算方法课程的内容。本书主要讨论这些方法及其分析，它们包括逼近问题（函数的插值和逼近，数值积分和微分），线性代数问题（方程组和特征值问题）和非线性方程及方程组的数值解法问题，以及常微分方程的数值解法等。这些是数值计算方法最基础的内容，不仅可以直接应用于实际计算，同时也是其它数值计算问题所用到的方法及其分析的基础。 （二）数值计算方法（或称计算方法）是研究数学问题求数值解的算法和有关理论的一门学科，它的理论与方法随计算工具的发展而发展。在古代，人类研究的数学问题几乎总与计算有关，而计算工具的简陋，使求解问题受到很大限制。现代科学技术日新月异，尤其是计算机技术飞速发展，人类可以用计算机进行复杂的数值计算、数据处理（包括图形，图像，声音，文字），计算机不仅是现代计算工具，而且已成了我们工作环境的一部分。计算方法所研究的内容是用计算机解决数学问题的方法（包括算法）和理论。用计算机进行数值计算的核心是算法设计。算法是对解题方案的准确描述，是“解题的操作序列”。在研究算法时，离不开误差分析，同时还需要考虑算法的稳定性、收敛性、计算工作量等问题。 （三）计算方法是计算数学的一个主要部分。而计算数学是数学科学的一个分支，它研究用计算机求解数学问题的数值计算方法及其软件实现。计算数学几乎与数学科学的一切分支有联系，它利用数学领域的成果发展了新的更有效的算法及其理论，反过来很多数学分支都需要探讨和研究适用于计算机的数值方法。因此，计算方法的内容十分广泛。但本书作为计算方法的基础，只介绍科学与工程计算中最常用的基本数值方法，包括线性方程组与非线性方程求根、插值与最小二乘拟合、数值积分与常微分方程数值解法等。这些都是计算数学中最基础的内容。 近几十年来由于计算机的发展及其在各技术科学领域的应用推广与深化，新的计算性学科分支纷纷兴起，如计算力学、计算物理、计算化学、计算经济学等等，不论其背景与含义如何，要用计算机进行科学计算都必须建立相应的数学模型，并研究其适合于计算机编程的计算方法。因此，计算数学是各种计算性科学的联系纽带和共性基础，是一门兼有基础性、应用性和边缘性的数学学科。 2、 数值计算方法研究的对象、任务与特点 计算数学作为数学科学的一个分支，当然具有数学科学的抽象性与严密科学性的特点，但它又具有广泛的应用性和边缘性特点。 现代科学发展依赖于理论研究、科学实验与科学计算三种主要手段，它们相辅相成，互相独立，可以互相补充又都不可缺少，作为三种科学研究手段之一的科学计算是一门工具性。方法性、边缘性的新学科，发展迅速，它的物质基础是计算机（包括其软硬件系统），其理论基础主要是计算数学。 计算数学与计算工具发展密切相关，在计算机出现以前，数值计算方法只能计算规模小的问题，并且也没形成单独的学科，只有在计算机出现以后，数值计算才得以迅速发展并成为数学科学中一个独立学科计算数学。当代计算能力的大幅度提高既来自计算机的进步，也来自计算方法的进步，计算机与计算方法的发展是相辅相成、互相促进的。计算方法的发展启发了新的计算机体系结构，而计算机的更新换代也对计算方法提出了新的标准和要求。例如为在计算机上求解大规模的计算问题、提高计算效率，诞生并发展了并行计算机。自计算机诞生以来，经典的计算方法业已经历了一个重新评价、筛选、改造和创新的过程，与此同时，涌现了许多新概念、新课题和能充分发挥计算机潜力、有更大解题能力的新方法，这就构成了现代意义下的计算数学。这也是数值分析的研究对象与特点。 概括地说，计算方法是研究适合于在计算机上使用的实际可行、理论可靠、计算复杂性好的数值计算方法。具体说就是： 第一，面向计算机，要根据计算机特点提供实际可行的算法，即算法只能由计算机可执行的加减乘除四则运算和各种逻辑运算组成。 第二，要有可靠的理论分析，数值分析中的算法理论主要是连续系统的离散化及离散型方程数值求解。有关基本概念包括误差、稳定性、收敛性、计算量、存储量等，这些概念是刻画计算方法的可靠性、准确性、效率以及使用的方便性。 第三，要有良好的复杂性及数值试验，计算复杂性是算法好坏的标志，它包括时间复杂性（指计算时间多少）和空间复杂性（指占用存储单元多少）对很多数值问题使用不同算法，其计算复杂性将会大不一样，例如对20阶的线性方程组若用代数中的Cramer法则作为算法求解，其乘除法运算次数需要9.71020次，若用每秒运算1亿次的计算机计算也要30万年，这是无法实现的，而用计算方法中介绍的Gauss消去法求解，其乘除法运算次数只需3060次，这说明选择算法的重要性。当然有很多数值方法不可能事先知道其计算量，故对所有数值方法除理论分析外，还必须通过数值试验检验其计算复杂性。本课程虽然只着重介绍计算方法及其理论，一般不涉及具体的算法设计及编程技巧，但作为基本要求仍希望读者能适当做一些计算机上的数值试验，它对加深算法的理解是很有好处的。 三、数值计算方法与计算机科学 计算机的飞速发展，正在日益影响着人们对传统数值分析（即计算方法）的认识。近几十年来，人们越来越认识到计算方法的学习与研究离不开计算机，仅仅只依靠数学理论的演绎和推导还不能解决实际中的数值问题，只有与计算机科学相结合，才能研制出实用的好算法。而且好的算法必须变成数值软件后才有可能为社会创造更大的财富。当代实践证明，计算方法正在日趋明显地成为数学与计算机科学的交叉性学科。 数学与计算机科学的密切关系，历史已作了回答，可以说计算机科学是吸吮着数学的乳汁而成长起来的。德国数学家Leibniz在研究组合数学时发现的二进制编码是电子计算机诞生的基础；VOn Nellmsnll提出了用流程图描述计算机运行过程后，软件的开发研究才得以发展和遍地开花；流行一时的结构化程序设计也是Bohm和 JacoPini证明的一条数学原理“任何单入口和单出口，且没有“死循环”的程序，都能由三种最基本的控制结构构造出来”的产物。另一方面，计算机的诞生和发展，给数学增加了新的血液，对数学的发展产生了不可估量的影响。借助于计算机可以证明玄妙的数学定理、揭示某些数学规律，以及求解许多原来令人一筹莫展的数学模型问题；由于并行计算机的诞生和发展，促使数学工作者去研究适应新一代计算机发展需要的算法并行算法。总之，由于计算机科学的发展，可以使数学上灵活的推演和运算改变成遵循某种规律的算法设计，从而为发展数值软件奠定了基础。因此，计算方法也得到更快发展，大量适合计算机求解的现代数值方法随之产生，并被广泛使用，成为当代科学计算的主要方法。 使用传统的计算方法解决实际问题，不但要求使用者具有一定的数学修养，而且还应具有相当的编程能力，因而使计算方法的广泛应用受到了影响。为解决这些问题，科学计算工作者经过长时间努力，将数值方法设计成算法，进而编制成数值软件，并逐步形成数值软件产业，为广大用户打开了方便之门。当今，已有不少集各种数值算法于一体的综合数学软件库（包括数值软件）。在国内外具有代表性的部分综合数学软件库（包）分别为： IMSL（International Mathematics and Statistics Library）是美国IMSL公司研制的大型数学和统计软件库，自研制至今已更新了十多个版本，是目前国内外流传最广，影响最大的数值软件库之一。 NAGmumerical Algorithm GrOUP）是英国政府研究机构联合几所大学共同研制成功的大型综合性数值软件库，它用多种语言写成，可移植性非常好，普遍流行于欧洲，在我国也有用户。 “Mathematica”是1988年美国IllilloiS大学开发成功的综合数学软件包，它把符号演算、数值计算、图形演示以及人机交互接口有机地结合在一起，几乎包括大学本科的所有数学演算和数值计算，为研究和应用数学理论和方法提供了先进的环境，目前是国内外广泛流行的数学软件包。STYR（是“数学、统计、应用、软件”的汉语拼音的首字母人是中国科学院计算中心等单位在“七五”期间联合开发的综合性数值软件库，是我国开发的第一个大型综合数值软件库，在国内有一定影响。 CUMSS（China University Mathematics and Statistics Software的缩写）是1987年由原国家教委的六所高校联合开发成功的综合性数学与统计软件库，是我国迄今第一个正式出版的大型综合数值软件库。 数学软件库（包）的引进与开发，给工程技术人员使用数值方法求解各种数值问题带来了极大的方便。但是，如果工程技术人员仅知道如何使用这些数值软件，一旦出现问题就难于解决；再者，有不少工程技术人员需要结合各自的具体需求灵活使用软件库，或者自己设计专用算法。因此，虽然有了各种软件库， 工程技术人员掌握数值方法和算法设计基础还是很有必要的，这可以使他们真正成为使用数学软件库的“主人”。为此，本教程不追求完美的数学演绎、论证以及详尽的公式推导，也不以数学课程的类别为序来讲述数值计算方法，而尽量以数值计算方法间的内在联系为主线，着重介绍数值计算方法及它们之间的关系与结构，力求少而精，使读者用较少的学时能对一般常用数值计算方法有较多的了解与掌握，并为进一步研究新算法奠定基础；内容以研究计算机上常用数值计算方法为主要对象，尽可能缩小数值计算方法与程序设计之间的距离，通过对一些有代表性的算法设计介绍，使读者了解数值计算方法与算法之间的关系与差别，初步掌握算法设计技术，为使用计算机求解数学模型问题架好桥梁；通过课堂教学与计算实习，使读者尽可能多地了解算法设计与程序设计之间的关系，进而培养用计算机解决实际问题的技能。 以计算机为工具来求解各种数学模型，无论使用何种方法，均需要经历三个中间过程：总体设计（模型的细化等），详细设计（主要为算法设计）和程序设计等。计算机数值计算方法主要是研究将数学模型变成数值问题，并研究求解数值问题的数值计算方法，进而设计数值计算算法。2、 误差序列实验 （一）、实验描述 参照1.25对3个差分方程计算出前十个数值的近似值，构造列表和图 形。误差算法分别为,. （二）、实验内容 对下列三个差分方程计算出前10个数值近似值。在每种情况下引入一个小的初始误差。如果没有初始误差，则每个差分方程将生成序列。用MATLAB构造生成图表。 (a),其中n=1,2, (b) ，其中n=2,3, (c), 其中n=2,3, （三）、实验结果及分析按附件的代码得到下面的图表。 表 1 序列=以及近似值，和n01.0000000000000000.994000000000000 1.000000000000000 1.000000000000000 10.500000000000000 0.497000000000000 0.4970000000000000.49700000000000020.2500000000000000.2485000000000000.2455000000000000.24250000000000030.1250000000000000.1242500000000000.119750000000000 0.11525000000000040.0625000000000000.0621250000000000.056875000000000 0.05162500000000050.0312500000000000.0310625000000000.025437500000000 0.01981250000000060.0156250000000000.0155312500000000.0097187500000000.00390625000000070.007812500000000 0.0077656250000000.001859375000000-0.00404687500000080.0039062500000000.003882812500000-0.002070312500000-0.00802343750000090.001953125000000 0.001941406250000-0.004035156250000-0.010011718750000100.0009765625000000.000970703125000-0.005017578125000-0.011005859375000 表 2 误差序列,和 00.006000000000000 0.000000000000000 0.000000000000000 10.0030000000000000.0030000000000000.00300000000000020.0015000000000000.004500000000000 0.00750000000000030.0007500000000000.0052500000000000.01575000000000040.0003750000000000.0056250000000000.03187500000000050.0001875000000000.0058125000000000.06393750000000160.0000937500000000.0059062500000000.12796875000000170.0000468750000000.0059531250000000.25598437500000380.0000234375000000.0059765625000000.51199218750000590.0000117187500000.0059882812500001.023996093750010100.0000058593750000.0059941406250002.047998046875021 是误差稳定的，且按指数级递减，相差不大较为稳定，说明该序列和等比序列较为接近。的误差不大较为稳定，但误差呈递增状态，所以其逼近效果不如。的误差是不稳定的，变化幅度较大，即n越大，误差越大，说明当时，误差可能比数值更大。以下就是差分方程的的图形图 1 稳定递减的误差序列 图 2 稳定的误差序列图 3 不稳定的误差序列 （四）、结论通过对于差分方程的求解可知，不同的差分方程的初始误差传播会随着其表达式的不同有很大差异性。因此，对于不同差分方程的选取问题和计算问题应慎重选择，选择稳定算法。附件（代码）：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/2for n=2:10r(n)=r(n-1)/2;%-r(n) is the general term of xnendr0,r(b)p0=1;p(1)=0.497;p(2)=3*p(1)/2-p0/2;for n=3:10p(n)=3*p(n-1)/2-p(n-2)/2;%-p(n) is the general term of pnendp0,p%- show all the items of pn(c)q0=1;q(1)=0.497;q(2)=5*q(1)/2-q0;for n=3:10q(n)=3*q(n-1)/2-q(n-2)/2;%-r(n) is t