数值分析

第1章科学计算方法 人类计算能力的提高包括两个方面：一是计算机性能的提高；二是计算方法效率的提高.计算机和计算方法两个方面的进步，极大提高了人类的计算仿真能力.如果说伽利略(Galileo)和牛顿(Newton)在科学发展史上奠定了科学实验和理论研究这两个科学方法的基础，那么从冯 诺依曼(von Neumann)开始，科学计算逐步走上了人类科学活动的前沿，它已成为第三种科学研究方法.实际上，科学计算与科学实验、理论研究已经共同成为科学方法论的基本环节，它们互相补充，互相依赖，而又相对独立.用数学来解决实际问题通常包含分析实际问题、抽象出数学模型、求出模型的解或近似解，然后回到现实中进行检验，必要时还要修改模型使之更加切合实际，以便得到更广泛的应用.科学计算过程可以用下面流程图说明： 数值方法是研究求解数学模型的算法及有关理论，它伴随计算机的发展而发展.在工程计算中，用数值方法求解数学问题得到了广泛应用. 1.1绪论 一般来说，计算数学涵盖了构成科学计算技术基础的数学和方法论.这个领域的教材通常有两个名称：“计算方法”和“数值分析”.通常标题为“计算方法”的主题倾向于强调算法的实现，以解释该方法起作用的基础数学理论为目的；标题为“数值分析”的则倾向于强调这一基本的数学理论，以求解数学问题为目的.当然，*好的方法是将算法及其实现的研究与支持它们的数学理论研究适当地结合在一起.数值方法已被成功用来解决复杂的科学或工程问题，在诸如天气预报、飞行器设计、油藏模拟等方面，在金融市场和投资结构的研究、电视电影动漫场景设计和渲染等方面也取得了令人赞叹的成果. 在计算数学这个学科里面，我们通常会关注经常相互掣肘的两个问题. 准确性 对于复杂问题，由于很少能够计算出问题的确切答案，因此我们必须了解数值方法产生了多少误差，以及如何控制(甚至减少)这些误差. 效率 该数值算法是否占用过多的计算机时间和计算资源？数值方法通常有两种工作方式：一种是快速但准确性低，另一种是慢速但准确性高.一般在其他条件相同的情况下，我们更喜欢快速的方式. 之所以说这两个问题是相互掣肘的，是因为通常来说，为使算法更精确就需要采取更多、更复杂的计算方法和步骤，这会使成本更高，即效率变低. 计算科学中第三个重要的概念是稳定性. 稳定性 对于某数值方法，如果初始数据或中间结果发生微小的改变，会导致*后计算结果发生很大的改变，我们就说该方法是不稳定的，否则称为稳定的方法.由于不稳定的方法往往会产生不可靠的结果，所以数值分析追求能进行有效计算又非常稳定的方法. 下面简要介绍一下本书需要的一些微积分基础知识. 1.1.1课程相关的基础知识 虽然数值分析通常不需要太多的背景知识，但对背景知识的充分了解对理解数值方法是大有裨益的，这里用得比较多的是微积分知识，其中*重要的是各个中值定理. 定理1.1(带余项的泰勒定理)设fx在阶连续的导数，令，则有 (1.1) (1.2) (1.3) (1.4) 其中点x通常是由使用者决定的，常常取为0，ξ介于x和x0之间.泰勒公式中余项的两种0形式(1.3)和(1.4)是等效的. 泰勒定理之所以重要，是因为它允许我们用多项式精确地表示一个光滑函数.如果该多项式的阶数是指定的，则我们可以界定误差范围.这使我们能够在计算中使用更简单的多项式来替换这些复杂的函数，同时又能够限制所产生的误差，所以泰勒定理为我们提供了一个简单近似和便捷的误差估计方法.例如，考虑区间[.1，1]上指数函数的逼近问题. 泰勒定理告诉我们，我们可以使用具有(已知)余项的多项式来表示ex： 其中ξ是x和0之间的某一点.为简单起见，让我们用表示多项式部分，其余 部分用 Rx表示，这样上面的等式变为 假设我们希望此近似值的绝对误差精确到10.6以内，即我们想要 对于区间[.1，1]中的所有x都成立.这样，近似值的误差小于10.6*好的处理方法是为创建一个简单的上限，然后使用该上限确定进行运算所需的项数上限小于10.6即可.因此，我们进行如下计算： 这样一来，如果我们能找到的n满足 对于所有的，]均成立.通过少量计算可以看出，就可以获得所需的精度. 比如，图1.l显示了指数函数ex与近似值的图像；图1.2显示精度较好的的误差图像. 由于此时已经不可能用肉眼区分和的差异，因此我们提供了误差需要注意的是，只有在x接近x0时，的半对数图(图1.2).Px才能很好地近似于f()x，而随着x远离区间[.1，1]，准确性就越来越差.这个结果告诉我们，可以使用特定的多项式，将指数函数逼近10－6精度，并且该精度在指定区间内对所有x均成立.这样的近似思想在近似计算中是比较常用的. 定理1.2(中值定理)设为给定函数，在上连续，在(ab)上可微，则存在点使得 (1.5) 在微积分中，这个结果的重要性比较模糊.但是，从数值方法和分析的角度来看，中值定理的重要性可能仅次于泰勒定理.为什么？考虑一下(1.5)的另一种形式 (1.6) 上式表明，如果通过函数的导数进行缩放，则中值定理允许我们用参数值的差异替换函数值的差异.例如，因为余弦函数的导数是正弦函数，其绝对值以1为界，所以我们可以使用中值定理来估计 值得注意的是，中值定理只是泰勒定理对于的一种特殊情况. 定理1.3(中间值定理)设和，假设w是介于之间的，或者是一个数值，也就是说，那么就存在着一个点. 虽然这个定理只说明存在某个点，没有给我们太多有关其数值的信息，但这个定理却是我们找到方程根的**种方法(称为二分法)的基础. 定理1.4(积分中值定理)设中，并假设都在区间使得上不会变号，则存在一个点 (1.7) 此结果对于简化数值积分方法的一些误差估计很有用，另一个相关的结果是离散平均值定理. 定理1.5(离散平均值定理)令 1.1.2计算机代数入门 下面简要回顾计算机进行实际运算的过程.计算机运算通常是不精确的，尽管误差很小，但它们在某些情况下会累积并实际上支配了计算过程.因此，我们需要对计算机运算有足够的了解，预先预估并处理这种现象.计算机尽管细节因机器而异，但计算机语言都是使用浮点运算. 每个数字是用(固定的、有限的)二进制数表示，通常称为位(bit).下面是一个数据在计算机中表示的典型形式 这里的σ是数字的符号，用一位表示，是尾数或分数部分，β是内部数字系统的基础，通常是二进制是指数部分，即实际存储的值.是恢复实际指数所需的偏移. 例如，在较旧的“计算机”体系结构中，4个字节所代表的32位系统中常见的分配如下：分数或小数部分占24位，指数占7位，符号占1位.7位指数可以表示数的范围为：但是为了使正负指数的范围几乎相等，实际的数值范围是[63，63].因为在这种情况下p=63所以有偏移量 在这样的系统中，如果创建更大的指数数据就会导致溢出，同样创建过小的指数数据也会导致溢出.实际上小数的大小也受到可用位数的限制 计算科学中，由这种有限表示形式引起的错误的通用名称是舍入误差.由于浮点运算的近似表示，在计算的每一步通常会导致计算误差产生. 例如，考虑在上述32位系统的计算机中进行两个数字的简单加法.准确的答案当然是. 但是我们首先注意到，这些数字本身都无法在计算机中通过二进制准确表示.我们能做得*好的就是 这里的小数位数太长，无法仅用24位存储.具体处理办法根据机器的不同而不同，主要是直接舍弃或者根据大小向上或向下舍入.舍入当然更准确，但是直接舍弃更快.比如，如果我们四舍五入，在上述的浮点方案中，这两个数字将存储为. 因此，在加法发生之前，我们已经引入了误差.此外，在计算过程中，由于两个数字的大小有些不同，需要进行归一化以获得相等的指数，这又会引入误差.无论是截断还是四舍五入，两者之间的差异确实很小，很多时候可以忽略不计，但是有时候也需要特别当心.关于这一点，我们在下一节给出一个“大数吃小数”的例子来说明. 一般来说，机器位数的不同导致对数的近似和运算结果精度都不同，所以有时可以通过提高计算精度来消除舍入误差问题.过去浮点算术系统默认情况下对每个数字都使用单精度，所以人们在编程时通常需要专门设定用双精度(多精度)来提高计算的准确性.现在，大多数计算机高级语言默认都使用双精度进行计算. 下面我们看一个例子