西安交通大学计算方法(c)讲义.doc

1计算方法（计算方法（C））目目 录录第第 1 章章 绪论绪论1.1 数值计算数值计算1.2 数值方法的分析数值方法的分析1.2.1计算机上数的运算1.2.2算法分析第第 2 章章 线性代数方程组线性代数方程组2.1 Gauss 消去法消去法2.1.1消去法2.1.2主元消去法2.2 矩阵分解矩阵分解2.2.1Gauss 消去法的矩阵意义2.2.2矩阵的 LU 分解及其应用2.2.3其他类型矩阵的分解2.2.4解三对角矩阵的追赶法2.3线性方程组解的可靠性线性方程组解的可靠性2.3.1向量和矩阵范数2.3.2残向量与误差的代数表征2.4解线性方程组解的迭代法解线性方程组解的迭代法2.4.1基本迭代法2.4.2迭代法的矩阵表示2.4.3收敛性第第 3 章章 数据近似数据近似3.1 多项式插值多项式插值3.1.1插值多项式3.1.2Lagrange 插值多项式3.1.3Newton 插值多项式3.1.4带导数条件的插值多项式3.1.5插值公式的余项3. 2 最小二乘近似最小二乘近似3.2.1 最小二乘问题的法方程3.2.2 正交化算法第第 4 章章 数值微积分数值微积分24.1 内插求积，内插求积，Newton-Cotes 公式公式4.1.1Newton-Cotes 公式4.1.2复化求积公式4.1.3步长的选取4.1.4Romberg 方法4.1.5待定系数法4.2数值微分数值微分4.2.14.2.1 插值公式方法4.2.2Taylor 公式方法 (待定系数法)4.2.3外推法第第 5 章章 非线性方程求解非线性方程求解5.1 解一元方程的迭代法解一元方程的迭代法5.1.1简单迭代法5.1.2Newton 法5.1.3割线法5.1.4区间方法5.2 收敛性问题收敛性问题5.2.1简单迭代——不动点5.2.2收敛性的改善5.2.3Newton 法的收敛性5.2.4收敛速度3第第 1 章章 绪论绪论1.1 数值计算数值计算现代科学的发展，已导致科学与技术的研究从定性定性前进到定量定量，尤其是现代现代数字计算机数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。

通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务一、一、本课程的任务：本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等将高等数学的问题回归到初等数学（算术）的方法求解数学（算术）的方法求解——了解计算的基础方法，基本结构基础方法，基本结构（否则只须知道数值软件）——并研究其性质立足点：面向数学——解决数学问题面向计算机——利用计算机作为工具充分发挥计算机的功能，设计算法，解决数学问题例如：迭代法、并行算法二、二、问题的类型问题的类型1、离散问题：例如，求解线性方程组 ——从离散数据：矩阵 A 和bAx 向量 b，求解离散数据 x；2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解；3、离散问题的连续化处理：例如，数据近似，统计分析计算；1.2 数值方法的分析数值方法的分析在本章中我们不具体讨论算法，首先讨论算法分析的基础——误差一般来讲，误差主要有两类、三种（对科学计算）：1）公式误差——“截断误差” ，数学计算，算法形成——主观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差” ； ——以后讨论2）舍入误差及输出入误差——计算机，算法执行——客观（机器）：由于计算机的存储器、运算器的字长有限，在运算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。

这两种误差主要是由于计算机的字长有限，采用浮点数系所致4首先介绍浮点数系1.2.1 计算机上的运算计算机上的运算————浮点运算浮点运算面向计算机设计的算法，则先要讨论在计算机上数的表示科学记数法——浮点数浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数：× ×┅┅┅┅× × ×┅┅┅┅┅┅┅┅× ×首数 尾数( 位)lt其中首数存放数的指数（或“阶” ）部分，尾数存放有效数字对于进制，尾 数字长为 t 位的浮点数系中的（浮点）数，可以用以下形式表示：),,,(ULtFtjjddl ttddd xfl,, 3 , 2,011 )221()(   此处，指数 （称为阶）限制在范围内lUlL以下记实数系中的实数为实数为，它在浮点数系中对应的浮点数对应的浮点数Rx ),,,(ULtF 记为——进制， 尾数位数，阶的范围),,,()(ULtFxfl tUL,几乎所有近代计算机都采用“二进制” （即）：位、字节和字分别是2指位数不同的二进制数。

例如十进制转换二进制10210000 00012122 0000 00104224 0000 01008328 0000 10009032290000 1001101322100000 101027013422221281627   字节100011011位是一个二进制数（即 0 或 1） ；字节是 8 个二进制数字；上表的最后一列 是字节单精度浮点数（single precision）按 32 位存储，双精度浮点数（double precision）按 64 位存储精度用于指明每个浮点数保留多少位以及尾数和阶数各分配多少位单精度浮点数的尾数为 23 位、阶数为 8 位；双精度浮点数的尾数为 53 位（包含符号位） 、阶数为 11 位（包含符号位） 双精度浮点数的等价二进制数如下所示：5   位位尾数符号位位指数（含符号位）645211ddddddddfbbbbbb浮点数的特点浮点数的特点：1、实数转换到浮点数实数转换到浮点数————浮点化，浮点化， 〈〈缺点：缺点：〉〉总会产生误差（总会产生误差（除极个别的 情况：）, 2, 1, 0,2lxl按 四舍五入，四舍五入，绝对误差：（举例） ，tlxflx   21)(〈〈优点：优点：〉〉浮点化浮点化产生的相对误差有界相对误差有界（与数字本身的数量级无关）t xxflxx1 21)()(注：设实数，则按进制可表达为：Rx 1,,, 3 , 2,011 )11 221( ttjjddl ttdttddd x  按四舍五入的原则，当它进入浮点数系时，若，则),,,(ULtF211  tdl ttddd xfl )221()(若，则 211  tdl ttddd xfl  )1221()(对第一种情况：tll tl ttdxflx           21)21(1)()(11对第二种情况：tll tl ttdxflx             21)21(1)(11就是说总有： tlxflx   21)(另一方面，由浮点数要求的 ， 有，将此两者相除，便得  11dlx1 t xxflx   1 21)(2、每一个浮点数系的数字有限：数字有限： 1) 1() 1(21     LUt3、浮点数系中的运算非自封闭运算非自封闭,（因为数字有限、尾数字长有限、指数数字有限等）例：在中，，运算和)5,5,4,10( F32102001.,105420.     yxyx6,的结果显然已不在此浮点数系内，而或也不在此浮点数系内，yx/yx yx 需结果才在此浮点数系内。

)(yxfl浮点运算应注意：浮点运算应注意：1）避免产生大结果的运算，尤其是避免小数作为除数参加运算；2）避免“大” “小”数相加减；3）避免相近数相减，防止大量有效数字损失；4）尽可能简化运算步骤，减少运算次数原因：原因：记，由，可得：t xxflxx     1 21)(max)(maxxxflx  )(（“ ”表示任意一种四则运算）yxyxflyx  )()(此处 是由机器字长（实质上是尾数字长 的大小）确定的常数（它反映t了实际运算的精度） 显然，若要求运算的舍入误差小，应使运算结果（如：）较yxyxyx,, 小尤其是小分母运算：，小大误差yyx yx   y其次，当浮点数系中两个数量级相差较大的数相加（或减） ，注意到由于浮点数系中数字字长的有限性，可能导致“大数吃小数” 例如，中)5, 5, 4,10(F，则13102317.,108231.yxxyx3313100000.108231.102317.108231.似乎没有参加运算)(xyy第三，同样，由于浮点数系中数字字长的有限性，当两个相近数相减时：例如，在中，，两数相减：)5, 5, 8,10(F331082317832.,1082317844.yx，计算结果仅剩 2 位有效数字，而原来参加运算的数字有31012000000. yx8 位有效数字，这将严重影响最终计算结果的精度。

1.2.2 算法分析算法分析作为一个可用的算法，必须考虑其效率效率和可靠性可靠性，定义定义：计算机完成一个乘法和一个加法，称为一个浮点运算浮点运算（记为 flop） ；注：由于计算机在运算时，加（减）法所耗时间远少于乘（除）法，所以通常只须计算乘法的次数，因此也有“一个算法需要多少个‘乘法’ ”这一提法71、计算效率、计算效率————可计算性（计算复杂性可计算性（计算复杂性————空间、时间）空间、时间）例：解线性方程组的 Grammar 方法：，其中是方程bAx AAi ix A组系数矩阵对应的行列式，而则是以右端向量 替代的第 列所得矩阵AiAbAi对应的行列式由线性代数知识可知，若，则)(ijA， nnniiiiiiJ212121),() 1(A其中是由{}变换到{}所需的置换次数可见每),,,(21niiiJn,, 2,1niii,,21计算一个行列式，需要个浮点运算；因此，按 Grammar 方法解方程组!) 1(nn约需 个浮点运算当时，用一个运!) 1(2nnN20n201070728. 9N算速度为的计算机进行求解，约需年（日前报道我国计算机秒/108510078. 3已达到秒，这仍需近 10 年） 。

而 n=20 的方程组应该说是一个小型的/1038408 方程组因此 Grammar 方法是一个不能接受的算法，它缺乏可计算性第二章将介绍的 Gauss 消去法和迭代法就有较高的效率，具有很好的可计算性2、计算可靠性、计算可靠性作为算法，除了考虑其效率外，必须重视可靠性，它可靠性，它包括两方面：问题的性态问题的性态 和 方法的稳定性方法的稳定性问题的性态问题的性态所计算的问题当原始数据发生小扰动时，问题的解一般也发生扰动问题问题的性态的性态——问题的解对原始数据发生变化的敏感性问题的解对原始数据发生变化的敏感性原始数据小扰动问题解   —问题是病态的—大变化—问题是良态的—小扰动例：线性方程组：的解是：6047 51 41 31121。