第3章301高斯消元法,列主元法

1、第第3 3章章 线性代数方程组的数值解法线性代数方程组的数值解法3.1 3.1 高斯消去法高斯消去法3.2 3.2 矩阵三角分解法矩阵三角分解法3.3 3.3 平方根法平方根法3.4 3.4 向量和矩阵的范数向量和矩阵的范数3.5 3.5 迭代法迭代法3.6 3.6 迭代法的收敛性迭代法的收敛性3.7 3.7 方程组的形态和误差分析方程组的形态和误差分析 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 矩阵形式矩阵形式 Ax=b,其中其中1112111212222212,nnnnnnnnaaaxbaaaxbxaaaxbAbn n个未知量个

2、未知量n n个方程的线性代数方程组个方程的线性代数方程组11,2,nijjija xbin或写成或写成 若矩阵A非奇异，方程组有惟一解，可用克莱姆（Cramer）法则求解 kkDxD， （1,2,kn） 其中detDA，kD是用向量b代替A的第k列后所得矩阵的行 列式。 克莱姆法则解线性方程组的计算量（乘法次数） (1)! (1)(1) !(1)nSnnnnn 例如20n ，乘法次数为2110。计算量很大！ 两类数值解法：两类数值解法： 直接解法直接解法: :假定计算过程没有舍入误差的情况下，假定计算过程没有舍入误差的情况下，经过有限步算术运算后能求得线性方程组精确解的经过有限步算术运算后能求

3、得线性方程组精确解的方法。经过有限步运算就能求得精确解的方法，但方法。经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也只能实际计算中由于舍入误差的影响，这类方法也只能求得近似解；例如：求得近似解；例如：高斯消去高斯消去法法、三角分解、三角分解法等。法等。 迭代解法迭代解法: : 构造适当的向量序列，用某种极限构造适当的向量序列，用某种极限过程去逐步逼近精确解。例如：过程去逐步逼近精确解。例如：雅可比迭代雅可比迭代法、法、高高斯斯- -赛德尔迭代赛德尔迭代法等。法等。上三上三 角形方程组角形方程组 回代求解，得回代求解，得 3211,0,1xxxnnnnnnnnyx

4、uyxuxuyxuxuxu22222112121114 5 6 10 2 3 3 7 71232334561023377xxxxxx33232132112532yxyxxyxxx2/32/12/1321 xxx1121237723245610 xxxxxx1231,0,1xxx下三角形方程组下三角形方程组 顺代可求得顺代可求得 7 72 3 24 5 6 10323721321211yyyyyy1891321 yyy1223345423377xxxxx3211,0,1xxx上二对角方程组上二对角方程组 回代求解，得回代求解，得 4 5 0 4 2 3 3 7 7nnnnnndxdxcxdxcx

5、dxcx1112322121111121222321,11,nnnnnnnuuduuduuud1122377464233xxxxx1231,0,1xxx下二对角方程组下二对角方程组 顺代可求得顺代可求得 7 7 6 0 440 2 3 33.1 高斯消去法高斯消去法 3.1.1 顺序顺序高斯消去法高斯消去法 ( (按方程和未知量的自然顺序进行按方程和未知量的自然顺序进行) )基本思想：用逐次消去未知数的方法把原方程组化为基本思想：用逐次消去未知数的方法把原方程组化为上三角形上三角形方程组进行求解方程组进行求解 。求解求解 分成两步：分成两步： 1.1.消元消元过程：用过程：用初等行变换初等行变

6、换将原方程组的系数矩阵将原方程组的系数矩阵化为上三角形矩阵（简称上三角阵）。化为上三角形矩阵（简称上三角阵）。 2.2.回代回代过程：对上三角形方程组的最后一个方程求过程：对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。解，将求得的解逐步往上一个方程代入求解。 顺序高斯消去法消元过程顺序高斯消去法消元过程: : 依从左到右、自上而下的次序将主对角元下方的元素化为零。依从左到右、自上而下的次序将主对角元下方的元素化为零。 1 1 不作行交换。不作行交换。 2 2 用不等于零的数乘某行，加至另一行。用不等于零的数乘某行，加至另一行。 用高斯消去法解下列线性方程组 52262

7、342321321321xxxxxxxxx 解解 对 线 性 方 程 组 第 1 次 消 元 ，0211a， 确 定 乘 数5 . 021112121aam，5 . 021113131aam，则有 ) 1 ()3() 1 ()2(3121mm35 . 15 . 1045 . 15 . 2042321321321xxxxxxxxx，第 2 次消元，05 . 222a，确定乘数6 . 05 . 25 . 1223232aam，有 )2()3(32 m6 . 06 . 00045 . 15 . 2042332321xxxxxx 回代 3211,1,1xxx 系数行列式的计算：系数行列式的计算： (1

8、)(2)( )1122detnnnAa aa例例 211132122A消元过程消元过程 主元为主元为 2，2.5，0.6 det A = 22.50.6 = 3 2112.51.50.6A 引进记号 (1)(1)(1)11121(2)(2)222( )( )( )( )( )nnkkkkkknkkknnnaaaaaAaaaa ，(1)1(2)2( )( )( )kkkknbbbbb，(1,2, )kn 矩阵形式 ( )( )kkAxb，(1,2, )kn 设 主元(1)(2)( )11220,0,0nnnaaa 消元过程 ( )( )(1,2,1),(1,2, ) ( )kikikkkkika

9、mknikknaimki 消元过程消元过程设 主元(1)(2)( )11220,0,0nnnaaa 消元过程 ( )( )(1)( )( )()( )( )(1,2,1)( ,1,2, ) kikikkkkkkkijijikkjkkkiiikkamknaaam ai jkknbbm b 回代过程回代过程上三角形方程组( )( )nnA xb求解过程 ( )( )( )( )1( )nnnnnnniiiijjj iiiiibxaba xxa ， （1,2,1inn ） 顺序高斯消去法的顺序高斯消去法的使用条件使用条件 使用条件之一使用条件之一 定理定理 线性方程组系数矩阵线性方程组系数矩阵A A

10、的顺序主子矩的顺序主子矩阵阵A Ak k ( (k k=1,2,=1,2,n n) )非奇异非奇异 ，则顺序高斯消去法能，则顺序高斯消去法能实现方程组的求解。实现方程组的求解。 即方程组能用顺序高斯消去法求解的即方程组能用顺序高斯消去法求解的充要条件充要条件是是系数行列式的顺序主子式非零系数行列式的顺序主子式非零。 高斯消去法能按顺序进行到底的充要条件是高斯消去法能按顺序进行到底的充要条件是 在原方程组的系数矩阵中如何反映出这个条件呢在原方程组的系数矩阵中如何反映出这个条件呢?( )0,1,2,kkkaknA的的k阶顺序主子矩阵阶顺序主子矩阵Ak的行列式的行列式 (1)1112111121(2

11、)(2)21222(1)(2)( )2221122( )120det00kkkkkkkkkkkkkkkaaaaaaaaaaaAa aaaaaa，nk, 2 , 1 使用条件之二使用条件之二 n阶矩阵A为严格对角占优矩阵是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即niaanijjjiii, 2 , 1,1 一阶严格对角占优矩阵指一个非零数。 定理 方程组系数矩阵A为严格对角占优矩阵则可实现用顺序高斯消去法求解。 顺顺序序高高斯斯消消去去法法的的计计算算量量 消元中各步需乘除法次数 第i步 乘法次数 除法次数 1 2(1)n 1n 2 2(2)n 2n 1n 1 1 合计 (1) (

12、 21)6nnn (1)2n n 3.1.2 列主元高斯消去法列主元高斯消去法 为什么列选主：数值不稳定 当高斯消去法的主元当高斯消去法的主元 时时 , 尽管尽管“当当 A A 非奇异时，非奇异时，det A0det A0，方程组有唯一解，方程组有唯一解”，也不能实现，也不能实现高斯消去法求高斯消去法求解。解。 例例 ， A A 非奇异，非奇异，det A0det A0，方程组有，方程组有唯一解，但唯一解，但 ，不能实现，不能实现高斯消去法求解。高斯消去法求解。( )0kkka0111A(1)110a 高斯消去法的主元 ，但绝对值很小时，用绝对值小的数做除数，会导致其它元素数量级的严重增长和舍

13、入误差的扩大。 ( )0kkka经过1k 次消元后得到增广矩阵( )( )(|)kkAb，在此增广矩阵的第k列的元素( )( )( )1,kkkkkkknkaaa中选取绝对值最大的一个， 记为( )krka， 然后交换( )( )(|)kkAb中的第k行与第r行后，再进行第k次消元。 列选主元高斯消去法 ：避免用绝对值小的元素，作除数。每次消元前选取一列中绝对值最大的元素作为主元素。用这个主元素作除数，这样便可以减少舍入误差。 列选主元高斯消去法的优越性，不增加求解过程的运算量，而大大减小误差。例例 用列主元高斯消去法求解方程组用列主元高斯消去法求解方程组(用三位有效数字计算用三位有效数字计算

14、)解解123123123354157324422xxxxxxxxx 12rr 22113311rmrrmr 选主元选主元选主元选主元3215m 31m 455 7 3 23 5 4 -1 4 4 2 23 5 4 -1 , 5 7 3 2 4A b 4 2 25 7 3 200.8 2.2 -2.2 0.6.4 0.4 -1 -032rr573201.60.4 0.400.82.22.2320.80.51.6m 3322r m r 12323357321.60.40.422xxxxxx 3211,0,1xxx 消元过程完成，得到上三角形方程组消元过程完成，得到上三角形方程组 再作回代可求得再作回代可求得 573201.60.40.40022 行列式的计算：行列式的计算： (1)(2)( )1122d