数值计算方法(第二版)

第1章 引论 1.1 数值计算方法及其主要内容 数值计算方法是数学的一个分支， 也称为计算方法或数值分析. 数值计算方法以各类数学问题的数值解法为研究对象， 包括对方法的推导、描述以及对整个求解过程的分析， 并由此为计算机提供实际可行、理论可靠、计算复杂性好 (指占用内存空间少及运算次数少) 的各种数值算法. 数值计算方法是一门紧密联系实际的学科.随着计算机科学和技术的迅速发展， 科学和工程技术中遇到的各类数学问题都有可能通过数值计算方法加以解决.“科学与工程计算” 已经成为平行于理论分析和科学实验的第三种科学手段. 现今无论在传统学科领域还是在高新科技领域均少不了数值计算这一类工作. 数值模拟实验已成为代替耗资巨大的真实实验、优化产品或工程设计的一种重要手段. 从实际问题中抽象出来的数学问题， 即我们常说的数学模型， 大多都与求解微分方程、线性与非线性代数系统、数据处理、统计、优化问题等有关. 数值计算方法这门课程将围绕这些数学问题的解决提供给大家一些有关基本数值算法设计、分析的训练， 使读者对一些基本概念、基本原理、基本思想、基本技能技巧有较全面的掌握. 本书的内容包括函数的数值逼近 (代数插值与函数的*佳逼近) 及其在数值积分与数值微分的应用、数值代数 (线性代数方程组的解法与矩阵特征值问题的计算)、非线性 (代数与超越) 方程的数值解法、常微分方程 (初、边值问题) 数值解法及*优化方法. 除以上基本内容之外， 本书还用少量篇幅介绍了广泛应用于实际问题的随机统计方法之一的 Monte Carlo(蒙特卡罗) 方法， 以及当今求解大规模科学工程计算问题*有效的算法之一的多层网格法， 以便读者参考. 通过对它们的讨论， 能够使人们掌握设计数值算法的基本方法， 为在计算机上解决科学计算问题打好基础. 在学习数值计算方法的时候， 首先要注意掌握方法的基本原理和思想， 并要注意方法处理的技巧及其与计算机的结合; 此外还应认真进行必要的数值计算训练. 1.2 计算机中数的浮点表示 任何一个科学计算实际问题在运用数值计算方法形成数值算法后， 必须通过计算机进行加、减、乘、除及逻辑等运算来实现. 因此了解数在计算机中的表示形式及其运算规则是必须的. 1.2.1 以 β 为基的数系 以 β 为基的数 (β 进制数) 可表示为 这里， *为整数. (1) 十进制数 (β = 10). 例如， (2) 二进制数 (β = 2). 例如， (3) 十六进制数 (β = 16)， 十六个数字为 0， 1， 2， ， 9， A， B， C， D， E， F. 例如， 除此之外， 八进制也是一种常用的进制. 1.2.2 数的浮点表示 在科学计算中常把数， 如 等， 分别表示成 这样一来， 一个数的数量级就一目了然. 在这种表示方法中， 小数点的位置决定于后边那个 10 的指数 (称为阶码). 这种允许小数点位置浮动的表示方法称为数的浮点表示. 显然一个数可以有不同的浮点表示. 例如， 8253 可以表示成 0.8253 ×104， 也可以表示成 0.08253×105. 为了确定起见， 我们将浮点数的表示规格化， 即要求小数点后**位数字非零， 这样的浮点表示称为规格化的浮点数. β 进制下， 规格化的浮点数可以表示成 (1.1) 其中， * 称* 为浮点数的尾数部分，*大小不限制. c 为阶码， 它为 β 进制整数. 例如， 等， 都是规格化的二进制浮点数. 1.2.3 浮点数的计算机表示 计算机中参与运算的数也是用浮点表示的， 仍如 (1.1) 的形式. 但由于计算机位数的限制， 数的浮点表示尾数部分位数是固定的， 如 t 位， t 也称为计算机的字长. 阶码 c 的大小也有确定的范围：m . c . M， 一般 m = .M， 或 m = .M+1. 受具体计算机限制的浮点数称为机器数， 它们构成该机器的数系， 并由 (β， t，m，M) 所确定， 记为 F(β， t， m，M). 因此计算机的数系实际上仅是实数系 R 的一个小的离散子集. 设 f ∈ F(β， t， m，M)， 则有 当实数* 时， 机器就出现上溢而中断运算; 当*时， 称为下溢， 机器自动作为零处理. 对于绝对值属于区间 [βm.1， (1 . β.t)βM] 中的任一数 若*， 为了能在计算机中参与运算， 机器将自动用机器数 f 表示，记为 f = fl(x)， 这就定义了 G = [βm.1， (1 . β.t)βM] 到 F(β， t， m，M) 的函数fl(其中 fl 是 floating-point 的缩写， 表示浮点机器数). 任何实数 x ∈ G， 现有计算机是按下述两种方法之一得到 fl(x) 的. (1) 舍入. fl(x) 取成与 x *接近者 这种方法的 fl(x) 实际是这样得到的：若*，则将 at+1 以后各数舍去， 若*， 则将 at 改为 at + 1， 这实际上是通常的四舍五入规则. (2) 截断. fl(x) 取成为满足 |fl(x)| . |x| 之误差*小者： 这相当于在 x 的表示中截去 at+1 及其以后的所有数. 根据 F(β， t， m，M) 的定义， 有 (1) 舍入 (1.2) (2) 截断 (1.3) 每种计算机只采用其中一种规则. 若记 舍入， 截断， 则有 (1.4) 事实上， 由 x ∈ G 可知 x .= 0， 令 (1.5) 由于*以及式 (1.2) 和 (1.3)， 得 (舍入) 或者 (截断)， 于是*， 利用式*可得 对于计算机而言， 凡介于机器容许的*大数与*小数之间的任何数， 除恰好是机器数外， 一经送入计算机， 即成为近似数参与运算. 1.3 节讨论近似数运算的舍入误差时， 还将多次用到 (1.4) 式. 1.3. 误差的基本概念 1.3.1 误差的来源 利用计算机进行科学计算将要经历以下几个过程：首先要将实际问题建立数学模型， 其次选择数值计算方法设计数值算法， *后在计算机上实现算法得出数值结果. 数学模型是实际问题的数学描述， 它往往是抓住主要因素， 略去一些次要因素， 将实际问题理想化以后所进行的数学概括. 因而数学模型是近似的， 其误差称为模型误差. 此外在数学模型中往往包含了若干参变量， 如温度、长度、电压等，这些量往往是通过观测或实验得来的， 因此也带来了误差. 这种误差， 称为观测误差. 模型误差和观测误差不作为数值计算方法的讨论对象. 当实际问题的数学模型很复杂， 因而不能获得精确解时， 必须提供求近似解的数值算法， 这种算法是通过对原数学模型作某种近似而产生的， 模型的精确解与数值方法精确解之差称为截断误差或方法误差. 例 1.1 已知 x > 0， 求* 时， 由表达式 取部分和 作为 e.x 的近似值， 有 其中 *即为利用 e(x) 作为*近似值时所产生的截断误差. 例 1.1 很好地解释了 “截断误差” 一词的含义. 截取有限项之和近似无穷级数之和时所产生的误差即是截断误差. 许多数值方法的建立正是基于级数展开截取其若干主要的项而得到的. 截断误差是数值计算方法的重点讨论对象. *后， 在计算机上实现算法得出数值结果的过程中， 还应考虑初始数据误差在计算过程中的传播和计算机浮点运算误差的积累. 由于初始数据通常是从测量中得到， 往往带有一定的误差， 这种误差在计算过程中将不断积累*终对计算结果造成影响， 称这种误差为初始值运算的传播误差. 又由于计算机浮点 (机器) 数的有限字长， 计算过程中的数据以及初始数据都是按四舍五入或只舍不入规则截成有限位数的机器数， 由此而引起的计算结果误差， 我们把这种误差称为浮点运算舍入误差 (简称舍入误差). 传播误差和舍入误差也是数值计算方法讨论的对象，因为它们直接影响到计算结果的精度. 1.3.2 近似数的误差和有效数字 在科学计算中， 数据是*基本的. 任何复杂计算问题的误差分析， 本质上都将归结为数的误差估计. 定义 1.1 设数 x 是某个量的精确值， 数 x. 是该量的已知近似值， 记 称 E(x) 为近似数 x. 的绝对误差， 简称误差. 例如， 若取 1/3 的近似值为 0.3333， 则绝对误差为 一般说来， 求 E(x) 是比较困难的， 但往往可以估计出绝对误差的上限， 即可求出一个正数 η， 使得 满足式 (1.6) 的 η 称为近似数 x. 的绝对误差限. 有了绝对误差限就可得到 x(精确值) 的范围 (1.7) 例如， 某种手表出厂时说明每天快慢 5s 以内， 于是若记 t 为准确时间，*为手表所指的时间， 那么有 |t . t.| . 5s. 这里 η = 5s 即为 t. 的绝对误差限. 式 (1.7) 说明精确值 x 落在区间 [x η， x. + η] 内， 在应用中常用 来表示式 (1.7)， 以刻画 x. 的精度. 上面关于手表的精度也可以用 t = (t. ±5)s 来刻画. 从这个例子也可看出绝对误差是有量纲单位的. 衡量一个近似数的精确程度， 光有绝对误差是不够的. 例如， 测量一段路程，其长为 100km， 假定有 10m 的误差; 另外测量一条 10km 的路程， 也有 10m 的误差. 显然后者测量的精度要差得多. 这说明决定一个近似数的精度， 除了绝对误差以外， 还必须顾及这个数本身的大小. 这就需要引进相对误差的概念. 定义 1.2 近似数 x. 的绝对误差和精确值的比， 即