数值计算方法与算法(第四版)

绪论 0.1 数值计算方法与算法 数值计算方法，是一种研究数学问题的数值近似解方法，是在计算机上使用的解数学问题的方法，简称计算方法.它的计算对象是那些在理论上有解而又无法用手工计算的数学问题，以及没有解析解的数学问题.例如，解一个有300个未知量的线性方程组;计算6阶矩阵的全部特征值. 在科学研究和工程技术中都要用到各种计算方法.例如，在航天航空、地质勘探、汽车制造、桥梁设计、天气预报和汉字字体设计中都有计算方法的踪影.在20世纪70年代，大多数学校仅在数学系的计算数学专业和计算机系开设计算方法这门课程.随着计算机技术的迅速发展和普及，现在计算方法课程几乎已成为所有理工科学生的必修课程. 计算方法是一门理论性和实践性都很强的学科，计算方法既有数学类课程中理论上的抽象性和严谨性，又有实用性和实验性的技术特征.计算方法的先修课程是微积分、线性代数、常微分方程和一门计算机语言. 大多数人学习计算方法的目的是为了使用方法，在学习计算方法中，在套用计算公式、修改计算公式和创建计算公式中，都需要不同程度的专业知识和数学基础.要注重学习计算方法中的逼近和迭代等数学思想和常用手法，获取近似计算的能力，并能触类旁通地应用到各个领域中.一些有创造力的工程师不仅擅长使用某些计算方法，而且能创建出简便有效的计算方法.例如，样条函数、快速傅里叶变换和有限元方法都是有创造力的工程师们创建的，再由数学家们完善这些方法的理论基础，并从理论上进行提高和推广. 从方法的计算公式到在计算机上实际运行，两者之间还有距离，这是数学能力与计算机应用技术能力之间的距离，还与计算机的运行环境和编程工具有关，为了缩小两者之间的距离，本教材将给出部分计算公式的算法描述.用算法容易准确而简便地描述计算公式，在算法中能简洁地表达计算公式中的“循环和“迭代等操作.有了方法的算法，将它转化成 C 或 PASCAL 等语言的程序上机运行也就容易了. 在学习计算方法过程中，如果能用某种语言编制该方法的程序并运行通过，那么有利于准确而深刻地掌握该方法的计算步骤和过程.本教材中提供了部分上机作业题，在平时作业中布置一些上机编程题目，其目的是通过编程上机，加深对方法实施的理解和体会，训练和提高数学与计算机应用能力和水平. 0.2 误差与有效数字 1.绝对误差与绝对误差界 近似计算必然产生误差，误差表示精确值与近似值的距离. 定义0.1 设为精确值(或准确值)， x 是的一个近似值，称为近似值 x 的绝对误差或误差.绝对误差=精确值.近似值误差 e 的值可正可负，如果得不到精确值 x.，也就算不出绝对误差e的值. 常用限制误差绝对值的范围ε描述和控制误差的范围. 定义0.2 如果精确值 x.与近似值 x 的误差的绝对值不超过某正数ε，即.ε称ε为绝对误差限或误差限. 精确值 x.也可表示为.通常，在误差允许的范围内的近似值 x，即认为是精确值，这也是计算中控制循环中止的常用手段. 例0.1 若经四舍五入得到 x =123.456，对于数123.4559，123.4555，123.4561，123.4564的近似值都是 x =123.456，即第四位小数大于5时，必然进位到第三位小数;第四位小数小于5时，必然舍去.它的误差限是. 若，则它的误差限是. 2.相对误差与相对误差限 在很多情况下，绝对误差并不能全面地反映近似程度.例如，某电器公司两次进货的某型号电风扇分别为1000台和2000台，其中开箱不合格电风扇分别为8和12(绝对误差的值).不合格率分别为8/1000=0.8%和12/2000=0.6%(相对误差的值)，这说明该电风扇的质量有所提高.我们把绝对误差与准确值的比值定义为相对误差. 定义0.3 设为精确值， x 是的一个近似值，称为近似值 x 的相对误差. 在实际计算中，有时得不到精确值，当 er 较小时 x.可用近似值 x 代替，即相对误差 er 的值也可正可负，与绝对误差一样不易计算，常用相对误差限控制相对误差的范围. 定义0.4 如果有正数εr 使得，则称εr 为的相对误差限. 产生误差的因素很多，产生误差的原因主要如下. (1)原始误差. 由客观存在的模型抽象到物理模型产生的误差.包括模型误差和原始数据误差. (2)截断误差. 用有限项近似无限项时，由截取函数的部分项而产生的误差，称为截断误差.例如，在计算中用的截断误差. (3)舍入误差. 在数值计算中，通常都按有限位进行运算.例如，按照四舍五入的原则，2/3=0.666667或2/3=0.667，由舍入产生的误差，称为舍入误差. 在实际计算中的数据通常是近似值，它们由观察、估计或计算而得到，这些数在计算机表示后也会带来进一步误差，即误差的积累和传播.关于误差的传播似乎没有多少统一的理论，通常积累误差的界是以通例分析为基础而建立的. 3.有效位数 定义0.5当 x 的误差限为某一位的半个单位，则这一位到**个非零位的位数称为 x 的有效位数.例如， x =12.34， y =0.004067均有4位有效数字，而3.00与3.0000分别有3位和5位有效位数. 有效位的多少直接影响到近似值的绝对误差和相对误差，因此，在计算中也应注意保持一定的有效位数. 4.约束误差 数值计算的近似计算免不了有误差相随，只能尽量约束和控制误差. (1)选择收敛的稳定的方法. 对同一问题选择不同的数值计算方法，可能得到不同的计算结果.在计算方法中，除了给出方法的数值计算公式，还要讨论计算公式的收敛性、稳定性和截断误差的特性.选择收敛性要求低、稳定性好的方法是约束误差扩张*重要的措施. 例如，样条插值函数比高次多项式的效果好得多，是构造插值函数的首选方法. (2)提高数值计算精度. 数值在计算机中存放的位数称为字长.有限位的字长是带来舍入误差和抑制数值计算精度的根源.对同一种方法，在字长大的计算机上的计算效果要比在字长小的计算机上优越. 同一计算问题，简化计算步骤、减少运算次数、控制除法中分母的值等措施都会约束和减少舍入误差. 例如，将多项式表达式改写为. 在计算机上，用同一种数值计算方法对数据选用不同的数值类型，有时会直接影响到计算效果.例如，对病态的线性方程组，采用单精度数据的 Gauss 消元方法，其数据解大大失真，而用双精度数据 Gauss 列主元消元方法却可得到满意的数值解. 0.3 矩阵和向量范数 0.3.1 向量范数 1.向量范数的定义 在一维空间中，实轴上任意两点 a， b 的距离用两点坐标差的绝对值表示.绝对值是单变量的一种度量距离的定义. 范数是在广义长度意义下，对函数、向量和矩阵的一种度量定义.任何对象的范数值都是一个非负实数.使用范数可以测量两个函数、向量或矩阵之间的距离.向量范数是度量向量长度的一种定义形式.范数有多种定义形式，只要满足向量范数定义的三个条件即可定义一个范数. 对任一向量 X ∈ Rn，按照一个规则确定一个非负实数与它对应，记该实数为，若 满足下面三个性质: (1)任取，当且仅当 X =0时;(非负性) (2)任取 X ∈ Rn，α∈ R，有;(齐次性) (3)任取 X， Y ∈ Rn，有，(三角不等式) 那么称实数为向量 X 的范数. 定义0.6向量的 Lp 范数(范数)定义为 (0.1) 其中，经常使用的三种 Lp 向量范数是 p =1，2，∞，即范数(曼哈顿范数)范数(欧几里得范数). 注. 例0.2 计算向量 X =(1，3， a)T 的向量范数. 例0.3 设 A 是一个正定矩阵，对任何向量 X ∈ Rn，定义函数是一种向量范数. 例0.4 当0< p <1， 不是向量范数. 证明 取 所以0< p <1不是向量范数. 2.不同向量范数的关系 同一向量，在不同的范数定义下，得到不同的范数值.定理0.1给出有限维线性空间 Rn 中任意向量范数都是等价的.定理0.1若 R1(X)，R2(X)是 Rn 上两种不同的范数定义，则必存在，使，均有 (0.2) 或 (证明略) 可以验证，对于向量的1，2和∞范数有下列等价关系: 例0.5 R2中向量1范数、2范数、4范数和∞范数的单位“圆，如图0.1所示. 图0.1 范数的单位“圆