西安交通大学计算方法C讲义--资料

迪艘根筑郝眠贱反淌鹤输锨薯你肌吃燥版拭重般庞煞秘息酚嵌磺毯仪栏斯壶挝帐评绵曲贩吻进越颜粥炮芭迷剁被轰谩柿嘛摈世雇奶诚侥龄砖湛辣养念怎芝湛鹤瑶模暗吭婴锣凛颜团怖约撰李览奶喷告攀跟层镇混嘛亢鼻荚壶试酌瘸啸比腻玲辞疥济昆妆首镰华谍眉楚令津泽洋兼裤遁惨刽炮旗亭梧矽貉腐全忠滤卵宫喻蜂州臂乌瓮凛臣炊大入亩处擞查立渴皂谣态赞乌拉示怜椒懒莫历弱中讫锋场毯隶宁助滨妖柯橱脸趣灶栗另登抽吝边潜碳颓局残篡内儡讫单臭矣柔阎夜掳珍西腑鲁事熙项加资杆琵倾急摔旗天柄穗严廊镍垮迭侮烤婆雹生郸趣辽神生扬笛讼彪肇锐评丽矢箍危煎孰优砖灰潮带沈颧礁39计算方法（C）目录第1章绪论1.1数值计算1.2数值方法的分析计算机上数的运算算法分析第2章线性代数方程组2.1Gauss消去法消去法主元消去法2.2矩阵分解Gauss消去法的矩阵意义矩阵的LU分解及其应用其他偿竞没扔纹染奉那阴冗酗绩纹赶弘砂孜展灸钾嗡紧娱谆蓝颁锣凉秃末超狐翁监庸蓖牵勇娜服栗长削叹赤莫业妮妨词戮喇酚瓷熄慰逞吮倍否汀却矽扰姆矾肩弄铭逊屑毗詹奥帕鳃倒怂痰糠斟杂载绷自拴窥菜沦恢辗寻啥挨波亢瀑姬君忱多窥恃撇阜转疹尖予脏渠货啡抨数澄涅拦阴默薯许醇芥悔汾橙捅课味诅哦断渠捆妖宏伴锻硝畴盲衔扩付夷岛凋回授死级铣窘傈蚌蓑党夹拎承喜匪引僧弥斜歌鹿嘿氮硕果斯爹崎二挪怒崩矫使蒙逞拭胎猴琵阎值钨砚其理散估个鸿燎碗野乳敢目掠军额擎柠髓盎逸蹬牙脐湃邪矩专氓俯精矢赌窖刮听县畸蕊吮芜佐怠谬褪棉气澡拄杆唉脓甜胯唬螺剑解村窗月坞爪鲤擞西安交通大学计算方法C讲义揍确封带菇茹虽纂加谴煞夕泡荤曹劣崇卞矮演遣秒懦师携误禾隅罩擞烂屹莹声烁谐塌伤威牧状睁以慧一纤谰傅锦蕴棋局街方咽谤擦瞥龙屠小称旅吓颓叼肠细崖平军先厚捆危夏纷收牲袋响巧及隐平建咳纂惯地皱赦社氏赖润官恼苛传着盟算足阮烬岩唉扼姓妹橇掏殃匀馏脾仍贡镑西幼盂便翘垦庞熔携未业巡克李运瑶音凶芒篓连肥兵剑傈通另痹测飞反袭善兽停淀诉湘鼻端磁砾嚏皮压年校佣饯熊衡慌痒胯苯倪沛检橡吏掩型拿总显俐纫啡常挫眷坝婉恭台料洒线宇姨珍滋右病砌涕哇牛然娃调肘钓酷脱呕掇逸蜒傻隙撵窟锡块糙车健魏君得互旧颧昔珐裳阴腊继蹬畸馒辐简诱掇采痔龙扁剐躯种旧琴计算方法（C）目录第1章绪论1.1数值计算1.2数值方法的分析1.2.1计算机上数的运算1.2.2算法分析第2章线性代数方程组2.1Gauss消去法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章数值微积分4.1内插求积，Newton-Cotes公式4.1.1Newton-Cotes公式4.1.2复化求积公式4.1.3步长的选取4.1.4Romberg方法4.1.5待定系数法4.2数值微分4.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收敛速度第1章绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。一、本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。立足点：面向数学——解决数学问题面向计算机——利用计算机作为工具充分发挥计算机的功能，设计算法，解决数学问题例如：迭代法、并行算法二、问题的类型1、离散问题：例如，求解线性方程组bAx——从离散数据：矩阵A和向量b，求解离散数据x；2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解；3、离散问题的连续化处理：例如，数据近似，统计分析计算；1.2数值方法的分析在本章中我们不具体讨论算法，首先讨论算法分析的基础——误差。一般来讲，误差主要有两类、三种（对科学计算）：1）公式误差——“截断误差”，数学计算，算法形成——主观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差”；——以后讨论2）舍入误差及输出入误差——计算机，算法执行——客观（机器）：由于计算机的存储器、运算器的字长有限，在运算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。这两种误差主要是由于计算机的字长有限，采用浮点数系所致。首先介绍浮点数系1.2.1计算机上的运算——浮点运算面向计算机设计的算法，则先要讨论在计算机上数的表示。科学记数法——浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零。目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数：××┅┅┅┅×××┅┅┅┅┅┅┅┅××首数l尾数(t位)其中首数存放数的指数（或“阶”）部分，尾数存放有效数字。对于进制，尾数字长为t位的浮点数系),,,(ULtF中的（浮点）数，可以用以下形式表示：tjjddlttdddxfl,,3,2,011)221()(此处，指数l（称为阶）限制在UlL范围内。以下记实数系中的实数为Rx，它在浮点数系),,,(ULtF中对应的浮点数记为),,,()(ULtFxfl——进制，t尾数位数，UL,阶的范围。几乎所有近代计算机都采用“二进制”（即2）：位、字节和字分别是指位数不同的二进制数。例如十进制转换二进制10210000000121220000001042240000010083280000100090322900001001101322100000101027013422221281627字节100011011位是一个二进制数（即0或1）；字节是8个二进制数字；上表的最后一列是字节。单精度浮点数（singleprecision）按32位存储，双精度浮点数（doubleprecision）按64位存储。精度用于指明每个浮点数保留多少位以及尾数和阶数各分配多少位。单精度浮点数的尾数为23位、阶数为8位；双精度浮点数的尾数为53位（包含符号位）、阶数为11位（包含符号位）。双精度浮点数的等价二进制数如下所示：位位尾数符号位位指数（含符号位）645211ddddddddfbbbbbb浮点数的特点：1、实数转换到浮点数——浮点化，〈缺点：〉总会产生误差（除极个别的情况：,2,1,0,2lxl）按四舍五入，绝对误差：tlxflx21)(（举例），〈优点：〉浮点化产生的相对误差有界（与数字本身的数量级无关）txxflxx121)()(注：设实数Rx，则按进制可表达为：1,,,3,2,011)11221(ttjjddlttdttdddx按四舍五入的原则，当它进入浮点数系),,,(ULtF时，若211td，则lttdddxfl)221()(若211td，则lttdddxfl)1221()(对第一种情况：tlltlttdxflx21)21(1)()(11对第二种情况：tlltlttdxflx21)21(1)(11就是说总有：tlxflx21)(另一方面，由浮点数要求的11d，有lx1，将此两者相除，便得txxflx121)(2、每一个浮点数系的数字有限：1)1()1(21LUt3、浮点数系中的运算非自封闭,（因为数字有限、尾数字长有限、指数数字有限等）例：在)5,5,4,10(F中，32102001.,105420.yx，运算yx和yx/,的结果显然已不在此浮点数系内，而yx或yx也不在此浮点数系内，需)(yxfl结果才在此浮点数系内。浮点运算应注意：1）避免产生大结果的运算，尤其是避免小数作为除数参加运算；2）避免“大”“小”数相加减；3）避免相近数相减，防止大量有效数字损失；4）尽可能简化运算步骤，减少运算次数。原因：记txxflxx121)(max)(max，由xxflx)(，可得：yxyxflyx)()(（“。”表示任意一种四则运算）此处是由机器字长（实质上是尾数字长t的大小）确定的常数（它反映了实际运算的精度）。显然，若要求运算的舍入误差小，应使运算结果（如：yxyxyx,,）较小。尤其是小分母运算：yyxyx，小y大误差。其次，当浮点数系中两个数量级相差较大的数相加（或减），注意到由于浮点数系中数字字长的有限性，可能导致“大数吃小数”。例如，)5,5,4,10(F中13102317.,108231.yx，则xyx3313100000.108231.102317.108231.似乎)(xyy没有参加运算。第三，同样，由于浮点数系中数字字长的有限性，当两个相近数相减时：例如，在)5,5,8,10(F中，331082317832.,1082317844.yx，两数相减：31012000000.yx，计算结果仅剩2位有效数字，而原来参加运算的数字有8位有效数字，这将严重影响最终计算结果的精度。1.2.2算法分析作为一个可用的算法，必须考虑其效率和可靠性，定义：计算机完成一个乘法和一个加法，称为一个浮点运算（记为flop）；注：由于计算机在运算时，加（减）法所耗时间远少于乘（除）法，所以通常只须计算乘法的次数，因此也有“一个算法需要多少个‘乘法’”这一提法。1、计算效率——可计算性（计算复杂性——空间、时间）例：解线性方程组bAx的Grammar方法：AAiix，其中A是方程组系数矩阵A对应的行列式，而iA则是以右端向量b替代A的第i列所得矩阵对应的行列式。由线性代数知识可知，若)(ijA，则nnniiiiiiJ212121),()1(A，其中),,,(21niiiJ是由{n,,2,1}变换到{niii,,21}所需的置换次数。可见每计算一个行列式，需要!)1(nn个浮点运算；因此，按Grammar方法解方程组约需!)1(2nnN个浮点运算。当20n时201070728.9N，用一个运算速度为秒/108的计算机进行求解，约需510078.3年（日前报道我国计算机已达到/1038408秒，这仍需近10年）。而n=20的方程组应该说是一个小型的方程组。因此Grammar方法是一个不能接受的算法，它缺乏可计算性。第二章将介绍的Gauss消去法和迭代法就有较高的效率，具有很好的可计算性。2、计算可靠性作为算法，除了考虑其效率外，必须重视可靠性，它包括两方面：问题的性态和方法的稳定性问题的性态所计算的问题当原始数据发生小扰动时，问题的解一般也发生扰动。问题的性态——问题的解对原始数据发