[工学]数值计算-CH2-解线性方程组的直接法-21～课件.ppt

1、第二章 解线性方程组的直接法张红梅张红梅自动化学院自动化学院20102010年年3 3月月2.1 2.3补充知识：定点数和浮点数补充知识：定点数和浮点数 计算机中的数除了整数之外，还有小数。如何确定小数点的位置呢？通常有两种方法：一种是规定小数点位置固定不变，称为定点数定点数。另一种是小数点的位置不固定，可以浮动，称为浮点数浮点数。在计算机中，通常用定点数表示整数和纯小数，对于既有整数部分、又有小数部分的数，一般用浮点数表示。下面分别予以介绍：（1）定点整数：定点数中，当小数点的位置固定在数值位最低位的右边时，表示一个整数。注意：小数点并不单独占1个二进制位，而是默认在最低位的右边。定点整数又

2、分为有符号数和无符号数两类。（2）定点小数：当小数点的位置固定在符号位与最高数值位之间时，就表示一个纯小数。因为定点数所能表示数的范围较小，常常不能满足实际问题的需要，所以要采用能表示数的范围更大的浮点数。（3）浮点数：小数点的位置是可以浮动的。大多数计算机中，把尾数S定为二进制纯小数，把阶码P定为二进制定点整数。尾数的二进制位数决定了所表示数的精度；阶码P的二进制位决定了所能表示的数的范围。为了使所表示的浮点数精度高、范围大，必须合理规定浮点数的存储格式。浮点数浮点数tx21*.02 二进制数的规格化浮点表示：其中，2 称为浮点数的基；，2,21sss为正整数；t21,1是0或者1。称为 x

3、 的机器规格化浮点数,简称浮点数,记为 =fl(x)。*x*x阶码 数符 尾数1 01 01 01 01 01 01 01 01 0浮点数的结构：阶码：用于确定小数点的位置,即下溢界和上溢界的范围,其大小由硬件决定；数符：表示正负号，“0”表示正数，“1”表示负数；尾数：表示机器数字长,尾数越多,计算机的计算精度越高,其长度由硬件决定。双精度浮点数和单精度浮点数双精度浮点数和单精度浮点数 这两者主要在精度上有区别。双精度浮点数能精确表示-1.79769313486231570E+308 到-4.94065645841246544E-324 范围的负数和从 4.94065645841246544

4、E-324 到 1.79769313486231570E+308 的正数。单精度浮点数能够精确表示从-3.4028235E+38 到-1.401298E-45 的负数和从 1.401298E-45 到 3.4028235E+38 的正数。单精度浮点数的精度没有双精度高，但是所需内存少，运算速度快。如果对精度要求不高，则应该尽量避免使用双精度浮点数，而应该使用单精度浮点数。这一点在一些大型应用程序中非常重要。如果在定义变量时，单精度浮点数就足够了，但是却使用了双精度浮点数，会大大减慢程序的运行。如果某个变量只需要整数类型就足够了，应避免用浮点数。因为整数的运算速度更快。线性方程组线性方程组 稠密

5、和稀疏稠密和稀疏（按系数矩阵含零元多少分）高阶和低阶高阶和低阶（按阶数的高低分）对称正定、三对角占优等对称正定、三对角占优等（按系数矩阵的形 状性质分）基基 本本 解解 法法 直接法直接法（通过有限步计算得到精确解精确解，适用于低阶、大型带型阵，第二章内容）迭代法迭代法（通过逐次迭代逼近得到近似解近似解，适用于大型稀 疏、非带型阵，第六章内容）线性方程组及方法分类nnnnnnnnbbbbxxxXAaaaaaaaaaA2121212222111211,0|，nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（1.1）求解线性方程组：求解线性方程

6、组：其中，对此方程组进行求解有两种方法：采用Cramer法则、消元法。Cramer(克莱姆克莱姆)法则法则 对于对于20阶的线性方程组阶的线性方程组,若用若用Cramer法则求解法则求解,其乘、除运算次数为其乘、除运算次数为9.7*1020,用一亿次用一亿次/秒的计算机秒的计算机,要要30万年！若用高斯消去法进行数值求万年！若用高斯消去法进行数值求解，乘、除运算只需约解，乘、除运算只需约2670次。次。计算量大计算量大nnnnnnnbxaxabxaxa1111111定理：如果线性方程组0|1111nnnnaaaaA则方程组有唯一解：AAxAAxnn,11其中Ak是将 A 的第 k 列元素依次换

7、成常数项b1,bn得到的行列式。的系数行列式非零，即直接法（消元法）的两种形式直接法（消元法）的两种形式 直接法的思想：将方程组化为一个或两个三角形方程组求解，主要包括以下两种。1、Guass消去法原理消去法原理bAx（1.1）当det A0时,方程组的解存在且唯一。对增广阵(A,b)进行 行初等变换行初等变换，上三角形1.不改变行列式的值2.不改变未知量次序),(),()1()1(bAbA),()2()2(bA),()()(nnbA 经过经过n-1次次bAx)()(nnbxA同 解通过解 得原方程组 的解。bAx)()(nnbxAnnnnnnnnuuuuuullllll22211211212

8、22111nnnnnnaaaaaaaaaA212222111211bAxbLUx yUxbLy两个三角形方程组下三角上三角LU直接三角分解法实际是Gauss消去法的变形，其原理如下：2、直接三角分解法原理、直接三角分解法原理yUx bLy 三角形方程组：三角形方程组：nnnnnnbylylylbylylbyl221122221211111 （1.4）nnnnnnnnyxuyxuxuyxuxuxu2222211212111（1.5）下三角形下三角形上三角形上三角形直接三角形分解法Gaussian Elimination高斯消去法高斯消去法消元消元回代回代化上三角方程组的过程思思路路 首先将 A

9、化为上三角阵，再回代求解=nnnnnnnnbxabxaxabxaxaa2222211212111x自下而上解上三角形方程组的过程将增广矩阵 第第i 行行 mi1 第第1 1行行，得到：)1(1)1(1)1(12)1(11.baaan)2(A)2(b记,)()1()1(nnijaAATnbbbb)1()1(1)1(1、消元、消元设 ，计算因子0)1(11 a).,2(/)1(11)1(11niaamii Step 1：0)det(其中，).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 行乘数0det)(kA设 ，计算因子0)(kkka).,1(/)

10、()(nkiaamkkkkikik Step k：).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 其中，将增广矩阵 第第i 行行 mik 第第k行行，得到：)1(1)1(1)1(12)1(11.baaan)(kb)()()(kkkknkkkbaa.)(kA共进行？步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa 如果 怎么办 0)(kkka以上消元过程均假定以上消元过程均假定0)(kkka注注:)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(

11、12)1(1100nnnnnnbaabaabaaa 由于 ，则 A 的第一列中至少有一元素不为零。0)det(A假设 ，则将 的第1行与第 行交换后再消元，得 0)1(11ia1i),()1()1(bA例：例：0(1)11a当 时，采取类似的处理措施。0)(kkka2、回代、回代niaAiii,2,100)det()(，有唯一解。)()(nnbxA)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii从而得方程 的解。bAx(n k)次次Step k：设设 ，计算因子，计算因子 且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik

12、 ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行 n 1 步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa(n k)2 次次(n k)(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i+1)次次22)1(1211nninni 回代乘除次数：回代乘除次数：Gauss消去法的运算量分析消去法的运算量分析(n k)次次)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijji

13、ijiii当 n=20 时，Gauss 消去法乘除法约为 2700 次次而如果用 Cramer 法则的乘除法运算次数约为：20)120)(120(!2020109333323nnnnMDGauss消去法的乘除运算总次数为消去法的乘除运算总次数为：Gauss 消去法算法流程消去法算法流程1、输入：矩阵阶数 n，增广矩阵 A(n,n+1)2、对于nk,2,13、回代计算：nkiaamkkikik,1 1,1 ;,1 nkjnkiamaakjikijij(2)消元：(1)如果 ，找非零元 ，交换第 k 行和第 i 行，若不存在非零元，算法停止;0kkaika(1)若 ，算法停止0)(nnna1,1,

14、11,nnixaaxnijjijnii(2)回代：不存在唯一解！不存在唯一解！我们必须找到整数我们必须找到整数 k i 使使 ,然后然后交换第交换第 k 行和第行和第 i 行行.0)(ikia不存在唯一解！不存在唯一解！实际上，只要实际上，只要 A 非奇异非奇异,即即 A的逆存在的逆存在,则可通过逐次消元及行交换则可通过逐次消元及行交换,将方程组化为三角形方程组将方程组化为三角形方程组,求出唯一解。求出唯一解。0)(nnna如果如果 0)(iiia如果如果如果找不到这样的如果找不到这样的 k?关于解的存在性的说明：引例：引例：用Gauss消去法解线性方程组(用3 位十进制浮点数计算）21000

15、1.02121xxxx解解:),(bAA 21111000100.01000021m441000.111000.101000100.0-9999主元-99981.000.0021,xx回代后求得：而其精度较高的解为Tx00010001.1,99989999.0*算法失败的原因：在求行乘数时用了很小的数0.0001作除数 0001.021m00.1200.1011),(bAA 121000100.011如果在求解时将1,2行交换,即0.99990.99981.00,1.0021xx回代后求得：与 很接近！Tx00010001.1,99989999.0*例例1.解线性方程组(用8位十进制尾数的浮点

16、数计算)321643.5072.12623.4712.3132103218xxx 解解由引例可知，若用Gauss消去法计算会有小数作除数的现象，若采用换行的技巧，则可避免。),(bAA 321643.5072.12623.4712.3132108行交换行交换因此因此列元素为列元素为的的绝对值最大绝对值最大很小,很小,3 ,1,2 10138a 31rr1233210623.4712.31643.5072.128),()1()1(bA83121105.05.0mm101.05.03103.0102.001018015.0103176.00643.5072.12),()2()2(bA9272262

17、9.032m54138685.05.031041555186.0001018015.0103176.00643.5072.12),()3()3(bA回代后可得:绝对值最大不需换行)3()3(3333abx 54138685.01041555186.036725739.0)2(223)2(23)2(22axabx103176.01018015.05.03x05088607.0)1(113)1(132)1(12)1(11axaxabx49105820.0事实上,方程组的准确解为:Tx 367257384.0 ,050886075.0,491058227.0*上述方法是在Gauss消去法的基础上,利

18、用换行的方法避免小主元作除数而得到的,称为Gauss列主元消去法。4、),(/)(:)(nnAnbnb),(/):1():1,()(:)(iiAnibniiAibibT对于对于1:1:1 ni 回代回代列主元消去法算法设计1、输入：方程组维数输入：方程组维数 n，矩阵矩阵A，右端项，右端项 b 和控制精度和控制精度 eps2、对于对于1:1nk(1),(max),(kiAkuAnik 选主元选主元epskuA),(2)如果如果 ，停止运算，停止运算 控制小主元控制小主元(3)如果如果 uk,转转(4)，否则执行，否则执行)1:,()1:,(nkuAnkkA 换行换行3、如果如果 ，则停止，则停止 无解无解0),(nnA5、输出解输出解Tnb):1(4),(/),:1(:),:1(kkAknkAknkA):1,(),:1():1,:1(:):1,:1(nkkAknkAnknkAnknkA 消元消元)(),:1():1():1(kbknkAnkbnkbTT