[工学]数值计算_CH2 解线性方程组的直接法—21～.ppt

第二章 解线性方程组的直接法,数值计算方法,张红梅 自动化学院 2010年3月,2.1 2.3,补充知识：定点数和浮点数,计算机中的数除了整数之外，还有小数。如何确定小数点的位置呢？通常有两种方法：一种是规定小数点位置固定不变，称为定点数。另一种是小数点的位置不固定，可以浮动，称为浮点数。 在计算机中，通常用定点数表示整数和纯小数，对于既有整数部分、又有小数部分的数，一般用浮点数表示。下面分别予以介绍： （1）定点整数：定点数中，当小数点的位置固定在数值位最低位的右边时，表示一个整数。注意：小数点并不单独占1个二进制位，而是默认在最低位的右边。定点整数又分为有符号数和无符号数两类。 （2）定点小数：当小数点的位置固定在符号位与最高数值位之间时，就表示一个纯小数。因为定点数所能表示数的范围较小，常常不能满足实际问题的需要，所以要采用能表示数的范围更大的浮点数。 （3）浮点数：小数点的位置是可以浮动的。大多数计算机中，把尾数S定为二进制纯小数，把阶码P定为二进制定点整数。尾数的二进制位数决定了所表示数的精度；阶码P的二进制位决定了所能表示的数的范围。为了使所表示的浮点数精度高、范围大，必须合理规定浮点数的存储格式。,浮点数,二进制数的规格化浮点表示：,阶码：用于确定小数点的位置, 即下溢界和上溢界的范围, 其大小由硬件决定； 数符：表示正负号，“0”表示正数，“1”表示负数； 尾数：表示机器数字长, 尾数越多, 计算机的计算精度越高, 其长度由硬件决定。,双精度浮点数和单精度浮点数,这两者主要在精度上有区别。 双精度浮点数能精确表示 -1.79769313486231570E+308 到-4.94065645841246544E-324 范围的负数和从 4.94065645841246544E-324 到 1.79769313486231570E+308 的正数。 单精度浮点数能够精确表示从 -3.4028235E+38 到 -1.401298E-45 的负数和从 1.401298E-45 到 3.4028235E+38 的正数。 单精度浮点数的精度没有双精度高，但是所需内存少，运算速度快。 如果对精度要求不高，则应该尽量避免使用双精度浮点数，而应该使用单精度浮点数。这一点在一些大型应用程序中非常重要。如果在定义变量时，单精度浮点数就足够了，但是却使用了双精度浮点数，会大大减慢程序的运行。 如果某个变量只需要整数类型就足够了，应避免用浮点数。因为整数的运算速度更快。,线性方程组,稠密和稀疏（按系数矩阵含零元多少分） 高阶和低阶（按阶数的高低分） 对称正定、三对角占优等（按系数矩阵的形 状性质分）,基 本 解 法,直接法（通过有限步计算得到精确解，适用于低阶、 大型带型阵，第二章内容） 迭代法（通过逐次迭代逼近得到近似解，适用于大型稀 疏、非带型阵，第六章内容）,1 直接法与三角形方程组求解,（1.1）,求解线性方程组： AX = b,其中，,对此方程组进行求解有两种方法：采用Cramer法则、消元法。,Cramer(克莱姆)法则,对于20阶的线性方程组, 若用Cramer法则求解, 其乘、除运算次数为9.7*1020, 用一亿次/秒的计算机, 要30万年！若用高斯消去法进行数值求解，乘、除运算只需约2670次。,计算量大,定理：如果线性方程组,则方程组有唯一解：,其中Ak是将 A 的第 k 列元素依次换成常数项b1,bn得到的行列式。,的系数行列式非零，即,直接法（消元法）的两种形式,直接法的思想：将方程组化为一个或两个三角形方程组求解，主要包括以下两种。,1、Guass消去法原理,对增广阵(A ,b)进行 行初等变换，,上三角形,1. 不改变行列式的值 2. 不改变未知量次序,两个三角 形方程组,下三角,上三角,直接三角分解法实际是Gauss消去法的变形，其原理如下：,2、直接三角分解法原理,三角形方程组：,（1.4）,（1.5）,下三角形,上三角形,直接三角形分解法,2 高斯消去法,Gaussian Elimination,高斯消去法,消元,回代,化上三角方程组的过程,自下而上解上三角形方程组的过程,将增广矩阵 第i 行 mi1第1行，得到：,记,1、消元,其中，,行乘数,其中，,将增广矩阵 第i 行 mik第k行，得到：,共进行 ？ 步,n 1,例：,当 时，采取类似的处理措施。,2、回代,有唯一解。,从而得方程 的解。,(n k) 次,Step k：设 ，计算因子 且计算,共进行 n 1 步,(n k)2 次,(n k) (n k + 2) 次,1 次,(n i +1) 次,Gauss消去法的运算量分析,(n k) 次,当 n = 20 时，Gauss 消去法乘除法约为 2700 次,而如果用 Cramer 法则的乘除法运算次数约为：,Gauss 消去法算法流程,1、输入：矩阵阶数 n，增广矩阵 A(n,n+1),2、对于,3、回代计算：,(2)消元：,(1)如果 ，找非零元 ，交换第 k 行和第 i 行， 若不存在非零元，算法停止;,(1)若 ，算法停止,(2) 回代：,不存在唯一解！,我们必须找到整数 k i 使 , 然后交换第 k 行和第 i 行.,不存在唯一解！,实际上，只要 A 非奇异, 即 A的逆存在, 则可通过逐次消元及行交换, 将方程组化为三角形方程组, 求出唯一解。,关于解的存在性的说明：,引例：,用Gauss消去法解线性方程组(用3 位十进制浮点数计算）,3 高斯列主元素消去法,解:,-9999,主元,-9998,回代后求得：,而其精度较高的解为,如果在求解时将1,2行交换, 即,0.9999,0.9998,回代后可得:,绝对值最大 不需换行,事实上, 方程组的准确解为:,上述方法是在Ga