《西安交通大学计算方法(C)讲义分享》由会员分享,可在线阅读,更多相关《西安交通大学计算方法(C)讲义分享(71页珍藏版)》请在金锄头文库上搜索。
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.1 Gauss消去法的矩阵意义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
2、.1.1 插值多项式3.1.2 Lagrange插值多项式3.1.3 Newton插值多项式3.1.4 带导数条件的插值多项式3.1.5 插值公式的余项3. 2 最小二乘近似 3.2.1 最小二乘问题的法方程 3.2.2 正交化算法第4章 数值微积分4.1 内插求积,Newton-Cotes公式4.1.1 Newton-Cotes公式4.1.2 复化求积公式4.1.3 步长的选取4.1.4 Romberg方法4.1.5 待定系数法4.2 数值微分4.2.1 插值公式方法4.2.2 Taylor公式方法 (待定系数法)4.2.3 外推法第5章 非线性方程求解5.1 解一元方程的迭代法5.1.1
3、简单迭代法5.1.2 Newton法5.1.3 割线法5.1.4 区间方法5.2 收敛性问题5.2.1 简单迭代不动点5.2.2 收敛性的改善5.2.3 Newton法的收敛性5.2.4 收敛速度第1章 绪论1.1数值计算现代科学的开展,已导致科学与技术的研究从定性前进到定量,尤其是现代数字计算机的出现及迅速开展,为复杂数学问题的定量研究与解决,提供了强有力的根底。通常我们面对的理论与技术问题,绝大多数都可以从其物理模型中抽象出数学模型,因此,求解这些数学模型已成为我们面临的重要任务。一、 本课程的任务:寻求解决各种数学问题的数值方法如何将高等数学的问题回归到初等数学算术的方法求解了解计算的根
4、底方法,根本构造否那么只须知道数值软件并研究其性质。立足点:面向数学解决数学问题面向计算机利用计算机作为工具充分发挥计算机的功能,设计算法,解决数学问题 例如:迭代法、并行算法二、 问题的类型1、离散问题:例如,求解线性方程组 从离散数据:矩阵A和向量b,求解离散数据x;2、连续问题的离散化处理:例如,数值积分、数值微分、微分方程数值解;3、离散问题的连续化处理:例如,数据近似,统计分析计算;1.2数值方法的分析在本章中我们不具体讨论算法,首先讨论算法分析的根底误差。一般来讲,误差主要有两类、三种对科学计算:1公式误差“截断误差,数学计算,算法形成主观人为:数学问题-数值方法的转换,用离散公式
5、近似连续的数学函数进展计算时,一般都会发生误差,通常称之为“截断误差; 以后讨论2舍入误差及输出入误差计算机,算法执行客观机器:由于计算机的存储器、运算器的字长有限,在运算和存储中必然会发生最末假设干位数字的舍入,形成舍入误差;在人机数据交换过程中,十进制数和二进制数的转换也会导致误差发生,这就是输入误差。这两种误差主要是由于计算机的字长有限,采用浮点数系所致。首先介绍浮点数系 1.2.1 计算机上的运算浮点运算 面向计算机设计的算法,那么先要讨论在计算机上数的表示。科学记数法浮点数:约定尾数中小数点之前的数全为零,小数点后第一个数不能为零。 目前,一般计算机都采用浮点数系,一个存储单元分成首
6、数和尾数: 首数 尾数(位)其中首数存放数的指数或“阶局部,尾数存放有效数字。对于b进制,尾数字长为t位的浮点数系中的浮点数,可以用以下形式表示:此处,指数称为阶限制在范围内。以下记实数系中的实数为,它在浮点数系中对应的浮点数记为进制,尾数位数,阶的范围。几乎所有近代计算机都采用“二进制即:位、字节和字分别是指位数不同的二进制数。例如十进制转换二进制10000 000120000 001040000 010080000 100090000 1001100000 101027位是一个二进制数即0或1;字节是8个二进制数字;上表的最后一列是字节。单精度浮点数single precision按32位
7、存储,双精度浮点数double precision按64位存储。精度用于指明每个浮点数保存多少位以及尾数和阶数各分配多少位。单精度浮点数的尾数为23位、阶数为8位;双精度浮点数的尾数为53位包含符号位、阶数为11位包含符号位。双精度浮点数的等价二进制数如下所示: 浮点数的特点:1、 实数转换到浮点数浮点化,缺点:总会产生误差除极个别的情况:按 四舍五入,绝对误差:举例,优点:浮点化产生的相对误差有界与数字本身的数量级无关 注:设实数,那么按进制可表达为:按四舍五入的原那么,当它进入浮点数系时,假设,那么 假设,那么 对第一种情况:对第二种情况:就是说总有: 另一方面,由浮点数要求的 , 有,将
8、此两者相除,便得2、 每一个浮点数系的数字有限: 3、 浮点数系中的运算非自封闭,因为数字有限、尾数字长有限、指数数字有限等例:在中,运算和,的结果显然已不在此浮点数系内,而或也不在此浮点数系内,需结果才在此浮点数系内。浮点运算应注意:1) 防止产生大结果的运算,尤其是防止小数作为除数参加运算;2) 防止“大“小数相加减;3) 防止相近数相减,防止大量有效数字损失;4尽可能简化运算步骤,减少运算次数。原因:记,由,可得: “。表示任意一种四那么运算此处 是由机器字长实质上是尾数字长的大小确定的常数它反映了实际运算的精度。显然,假设要求运算的舍入误差小,应使运算结果如:较小。尤其是小分母运算:,
9、小大误差。其次,当浮点数系中两个数量级相差较大的数相加或减,注意到由于浮点数系中数字字长的有限性,可能导致“大数吃小数。例如,中,那么似乎没有参加运算。 第三,同样,由于浮点数系中数字字长的有限性,当两个相近数相减时:例如,在中,两数相减:,计算结果仅剩2位有效数字,而原来参加运算的数字有8位有效数字,这将严重影响最终计算结果的精度。1.2.2 算法分析作为一个可用的算法,必须考虑其效率和可靠性,定义:计算机完成一个乘法和一个加法,称为一个浮点运算记为flop;注:由于计算机在运算时,加减法所耗时间远少于乘除法,所以通常只须计算乘法的次数,因此也有“一个算法需要多少个乘法这一提法。1、计算效率
10、可计算性计算复杂性空间、时间例:解线性方程组的Grammar 方法:,其中是方程组系数矩阵对应的行列式,而那么是以右端向量替代的第列所得矩阵对应的行列式。由线性代数知识可知,假设,那么,其中是由变换到所需的置换次数。可见每计算一个行列式,需要个浮点运算;因此,按Grammar方法解方程组约需 个浮点运算。当时,用一个运算速度为的计算机进展求解,约需年日前报道我国计算机已到达秒,这仍需近10年。而n=20的方程组应该说是一个小型的方程组。因此Grammar方法是一个不能承受的算法,它缺乏可计算性。第二章将介绍的Gauss消去法和迭代法就有较高的效率,具有很好的可计算性。2、计算可靠性作为算法,除
11、了考虑其效率外,必须重视可靠性,它包括两方面:问题的性态 和 方法的稳定性l 问题的性态所计算的问题当原始数据发生小扰动时,问题的解一般也发生扰动。问题的性态问题的解对原始数据发生变化的敏感性。原始数据小扰动问题解 例:线性方程组: 的解是:假设将方程组的系数改写成具有2位有效数字的小数: 的解那么变成:;这是一个典型的病态方程组。一般:由原始数据 计算结果, 扰动后的数据 计算结果,假设对问题存在常数m,满足关系式: 或 那么称相对误差之比的上界m为该问题的条件数,记作 ;由微积分中值定理知识容易计算出,当时, 。稍后我们在第二章将对线性方程组的性态作进一步的分析。l 算法的数值稳定性:例:
12、计算;解:由微积分知识,可得计算公式, ,我们将准确值与计算结果列表如下:方法准确值.6321.3679.2642.2073.1709.1455.1268.1124.1010.6321.3679.2642.2074.1704.1480.1120.2160-.7280.6320.3680.2643.2073.1709.1455.1268.1124.1010由上表可见,方法中,原始步的误差,随着计算步数的增加被严重地放大,特别是竟变成负数注意:被积函数是非负函数,而方法那么相反;这是因为方法中,假设前步有误差:,那么,说明的误差,经一步计算后被扩大了倍,随着的增大,误差将被大大地扩大;而通过同样的
13、分析可知:方法中的误差那么被缩小倍。算法的数值稳定性:算法对初始误差导致的最终误差的可控性,如果最终误差被有效地控制,那么称算法是稳定的,否那么就是不稳定的。第二章 线性方程组求解线性方程组:其中2.1 消去法 2.1.1 消去法 设计方法原那么:面向计算机事先未知元素,编制程序,例: 根本思想:降维N维问题转化为N-1维问题逐次降维,依次进展消去过程对方程组2.1由上而下逐步消去对角元 以下的 ,使之转化为如下等价形式,到达目标: 从而,可进入回代过程,再由下而上,逐步解得 :这儿的主元对问题2.1设,目标:将第2n方程的的系数转化为0;方法:“第个方程-“第1个方程,得到现在只须关心由第2n方程形成的n-1维方程组,以后可仿此进展。消去:第步:设,以第行为基准,消去以下各行中列以下的,令 施行:第行第行新的第行,元素变化:,经过步消去注意:以下无元可消,得到式。注意:每计算1个仅需1个浮点运算回代:第一步 , 第二步 ,第步 运算量:消元:n元方程组:第1步消元:对第行,共n-1行;每1行:计算,1个乘除法或“浮点运算,计算新的共 个乘除法或“浮点运算,第1