数值分析第五章线性方程组直接解法

1、1第五章解线性方程组的直接方法数值分析 Gauss 消去法消去法2线性方程组直接解法线性方程组直接解法Axb l 自然科学和工程计算中自然科学和工程计算中, 很多问题最终都需要求解很多问题最终都需要求解一个线性代数方程组一个线性代数方程组(1) 直接法直接法: 适合低阶方程组或某些特殊大型稀疏方程组适合低阶方程组或某些特殊大型稀疏方程组l 目前使用的数值解法目前使用的数值解法:(2) 迭代法迭代法: 解大型稀疏方程组的主流算法解大型稀疏方程组的主流算法, n nnARbR 在本章中，我们总是假定在本章中，我们总是假定 A 是是 n 阶方阵阶方阵3Gauss 消去法消去法例：直接法解线性方程组例

2、：直接法解线性方程组123123123 222233 44 6 3xxxxxxxxx 解：解：1222( , )23344163A b 61121702128006 1789211222001 31x 23871xx1232222xxx 4Gauss 消去法消去法高斯消去法的主要思路：高斯消去法的主要思路：将系数矩阵将系数矩阵 A 化为上三角矩阵，然后回代求解。化为上三角矩阵，然后回代求解。11112211211222221122. .nnnnnnnnnna xa xa xba xa xa xba xa xa xb 考虑考虑 n 阶线性方程组：阶线性方程组：Axb 矩阵形式矩阵形式=5Gaus

3、s 消去法消去法第一步第一步：消去第一列：消去第一列依次将增广矩阵的依次将增广矩阵的 第第 i 行行 + mi1 第第 1 行行，得，得)1(1)1(1)1(12)1(11.baaan)2(A(2)b(1)110a (1)(1)1111(2, .,)iiianma 设设 ，计算，计算(2)(1)(1)11(2)(1)(1)11ijijijiiiaam abbm b 其中其中( ,2, ., )i jn 第二步第二步：消去第二列：消去第二列依次将上述矩阵的依次将上述矩阵的 第第 i 行行 + mi2 第第 2 行行，得，得(3)(2)(2)22(3)(2)(2)22ijijijiiiaam ab

4、bm b 其中其中( ,3, ., )i jn (2)(2)2222(3, .,)iiianma 设设 ，计算，计算(2)220a )1(1)1(1)1(12)1(11.baaan(3)A(3)b( 2 )( 2 )( 2 )2 222.naab记记(1)1(1)(1)(1)(1)(), ijn nnbAaA bbb ，即，即 。(1)(1), ijijiiaabb 6Gauss 消去法消去法高斯消去法高斯消去法第第 k 步步：消去第：消去第 k 列列依此类推，直到第依此类推，直到第 n-1 步，原方程化为步，原方程化为( )( )(1, .,)kkikikkkmakain 设设 ，计算，计算

5、( )0kkka (1)(1)(1)(1)1112111(2)(2)(2)22222( )( )nnnnnnnnaaabxxaabxba 回代求解：回代求解：( )( )nnnnnnxba 计算计算(1)( )( )(1)( )( )kkkijijikkjkkkiiikkaam abbm b ( i = k+1, , n )( )( )( )1()niiiiiijjiij ixba xa ( i = n-1, , 1 )7几点注记几点注记l 主元：主元：(1, 2, .,)in ( ) iiial Gauss 消去法能进行到底的条件：消去法能进行到底的条件：主元全不为主元全不为 0l Gaus

6、s 消去法的运算量消去法的运算量计算机中做乘除运算的时间远远超过做加减运算时间，计算机中做乘除运算的时间远远超过做加减运算时间，故我们只估计故我们只估计 乘除运算乘除运算 的次数的次数定理定理： （i=1, 2, ., n）的充要条件是）的充要条件是 A 的顺的顺序主子式不为零，即序主子式不为零，即( )0iiia 11111110, 0, 1,2,iiiiiaaDaDinaa 8运算量运算量第第 k 步：步：消去第消去第 k 列列( )( )(1, .,)kkikikkkmakain 计算计算计算计算(1)( )( )(1)( )( )kkkijijikkjkkkiiikkaam abbm

7、b ( i = k+1, , n )回代求解：回代求解：( )( )nnnnnnxba ( )( )( )1()niiiiiijjiij ixba xa ( i = k+1, , n )n k 次次(n k)2 次次n k 次次n (n+1)/2 次次乘除运算量为：乘除运算量为：3233nnn 9LU 分解分解q Gauss消去过程其实就是一个矩阵的消去过程其实就是一个矩阵的三角分解三角分解过程过程则则 A(k) 与与 A(k+1) 之间的关系式可以表示为：之间的关系式可以表示为：(1)( )kkkAL A 其中：其中：1,1111kkn kkmmL ( )( )kkikikkkmaa ( i

8、 = k + 1, , n )将将 Gauss 消去过程中第消去过程中第 k-1 步消元后的系数矩阵记为：步消元后的系数矩阵记为：(1)(1)(1)1111( )( )( )( )( )knkkkkkknkknknnaaaAaaaa ( k = 1, , n-1)10LU 分解分解LU 分解分解记：记： ，则，则111( )12, nnLL LLUA ALU 其中：其中：L - 单位下三角矩阵单位下三角矩阵，U - 上三角矩阵上三角矩阵LU 分解分解于是有：于是有：( )(1)121nnALL L A 1)1(1)(21()nnALLAAL 容易验证：容易验证：1,11111kkn kkmmL

9、 ( k = 1, , n-1)(杜利脱尔杜利脱尔Doolittle分解分解)11LU 分解存在唯一性分解存在唯一性LU 分解分解存在存在( )0kkka 高斯消去法不被中断高斯消去法不被中断定理定理：若：若 A 的所有顺序主子式不为零，则的所有顺序主子式不为零，则 A 存在存在唯一的唯一的 LU分解分解所有顺序主子式不为零所有顺序主子式不为零12列主元列主元 Gauss 消去法消去法Gauss 消去法有效的条件是：消去法有效的条件是： 主元全不为零主元全不为零例：解线性方程组例：解线性方程组12011101xx 先选取先选取列主元列主元：( )| =kki ka ( )max |0kikk

10、i na if ik k then 交换交换第第 k 行行和和第第 ik 行行 消元消元q 列主元列主元 Gauss 消去法消去法在第在第 k 步消元时，在第步消元时，在第 k 列的剩余部分选取主元列的剩余部分选取主元13列主元列主元 Gauss 消去法消去法算法算法 (列主元列主元Gauss消去法消去法 )for k=1 to n-1 ( )( )| =max |0kkki kikk i naa if then stop ( ) =0kki kaif ik k then swap k-th and ik-th row (including b)ikikkkmaa for i=k+1 to n

11、, 1,2,.,ijijikkjiiikkaam ajkknbbm b endend1, , 1,.,2,1()nnnniiijjiij ixb axba xain 14PLU 分解分解列主元列主元 Gauss 消去法对应的矩阵分解为消去法对应的矩阵分解为 PLU 分解分解定理定理：若：若 A 非奇异，则存在排列矩阵非奇异，则存在排列矩阵 P，使得，使得 PA = LU其中其中 L 为单位下三角矩阵，为单位下三角矩阵，U 为上三角矩阵为上三角矩阵l 列主元列主元 Gauss 消去法比普通消去法比普通 Gauss 消去法要多一些比消去法要多一些比较运算，但比普通高斯消去法稳定较运算，但比普通高斯

12、消去法稳定l 列主元列主元 Gauss 消去法是目前直接法的首选算法消去法是目前直接法的首选算法15全主元全主元Gauss消去法消去法q 全主元高斯消去法：全主元高斯消去法：第第 k 步消元时，在剩余的步消元时，在剩余的 n-k 阶子矩阵中选取主元阶子矩阵中选取主元 先选取先选取全主元全主元：( )| =k kki ja ( ),max |0kijk i j na if ik k then 交换交换第第 k 行行和和第第 ik 行行 if jk k then 交换交换第第 k 列列和和第第 jk 列列 消元消元l 列交换改变了列交换改变了 xi 的顺序，须记录交换次序，解完后的顺序，须记录交换

13、次序，解完后再换回来再换回来l 全主元高斯消去法具有更好的稳定性，但很费时，全主元高斯消去法具有更好的稳定性，但很费时，在实际计算中很少使用在实际计算中很少使用16解：解：例：采用十进制八位浮点数，分别用例：采用十进制八位浮点数，分别用Gauss消去法消去法和列主元和列主元Gauss消去法求解消去法求解: :12121 2xxxx 9(10 ) 精确解为精确解为.1000.00.1101191 x8个个.8999.99. 0212 xx8个个GaussGauss消去法：消去法：911212110/ aam1010102221111 100.100.0.00.110.010.00am 9个个10

14、1010221212100.100.0.00.110.010.00bm Gauss消去法例子消去法例子列主元列主元GaussGauss消去法：消去法： 21111109911 2101 1 1211xx 999101101010 211,0 xx Gauss消去法例子消去法例子18第五章解线性方程组的直接方法数值分析 矩阵三角分解法矩阵三角分解法191、LU分解分解将将 Gauss 消去过程中第消去过程中第 k-1 步消元后的系数步消元后的系数矩阵记为：矩阵记为：(1)(1)(1)1111( )( )( )( )( )knkkkkkknkknknnaaaAaaaa ( k = 1, , n-1

15、)LU 分解分解20则则 A(k) 与与 A(k+1) 之间的关系式可以表示为：之间的关系式可以表示为：(1)( )kkkAL A 其中：其中：1,1111kkn kkmmL ( )( ),kkikikkkmaa ( i = k+1, , n )LU 分解分解21LU 分解分解于是有：于是有：( )(1)121nnALL L A 1(1)11( )2()nnAALL LA 容易验证容易验证1,11111kkn kkmmL ( k = 1, , n-1)22记：记： ，则，则111( )12, nkLL LLUA ALU 这里这里: : L - 单位下三角矩阵，单位下三角矩阵，LU 分解分解 (

16、 (杜利脱尔杜利脱尔Doolittle分解分解) )U - 上三角矩阵上三角矩阵LU 分解存在分解存在( )0kkka 普通高斯消去普通高斯消去法不被中断法不被中断?LU 分解分解23若若A的所有顺序主子式不为零，则的所有顺序主子式不为零，则A存在唯一存在唯一的的LU分解分解. .证：存在性由证：存在性由Gauss消去法可得；消去法可得； 唯一性可用反证法证明唯一性可用反证法证明.( LU分解的唯一性分解的唯一性 )定理定理1 1类似的，还可以得到类似的，还可以得到定理定理2 2若若A的所有顺序主子式不为零，则的所有顺序主子式不为零，则A存在唯一存在唯一的的克洛脱克洛脱(Crout)分解分解:

17、 : ALU 其中：其中：L是下三角矩阵，是下三角矩阵，U是单位上三角矩阵是单位上三角矩阵LU 分解分解24计算计算 LU 分解分解利用矩阵乘法直接计算利用矩阵乘法直接计算 LU 分解分解111211112121222212221,1121 11nnnnnn nnnnnnnuuuaaaluuaaalluaaa L U = A比较等式两边的比较等式两边的第一行第一行得：得：u1j = a1j比较等式两边的比较等式两边的第一列第一列得：得：1111iilau 比较等式两边的比较等式两边的第二行第二行得：得：22211jjjual u 比较等式两边的比较等式两边的第二列第二列得：得： 2211222

18、iiilal uu ( j = 1, n )( i = 2, n )( j = 2, n )( i = 3, n )U 的第一行的第一行 L 的第一列的第一列 U 的第二行的第二行 L 的第二列的第二列 25计算计算 LU 分解分解第第 k 步：此时步：此时 U 的前的前 k-1 行和行和 L 的前的前 k-1 列已经求出列已经求出比较等式两边的比较等式两边的第第 k 行行得：得：比较等式两边的比较等式两边的第第 k 列列得：得：直到第直到第 n 步，便可求出矩阵步，便可求出矩阵 L 和和 U 的所有元素。的所有元素。 11111,1,kkjkiijikjkjkjk kkjual ulual

19、u ( j = k, , n ) 11,11,11ikikikiiikijjkkkkjkkkklal uluual uu ( i = k+1, , n )26LU 分解算法分解算法算法算法 ：(LU 分解分解 )for k = 1 to n-11 ,kkjkjkiijiual u 11 ,kikikijjkkkjlal uu endj = k, , ni = k+1, , nkjaika运算量：运算量：(n3 - n)/3为了节省存储空间，通常用为了节省存储空间，通常用 A 的绝对下三角部分来存放的绝对下三角部分来存放 L (对角线元素无需存储对角线元素无需存储)，用，用 A 的上三角部分来存

20、放的上三角部分来存放 U 27PLU 分解分解PALU 矩阵的矩阵的 PLU 分解分解for k = 1 to n-11 ,kikikijjkjaaa a endi = k, k+1, , nmax , ki kikk i naa ,kkji jaaj = 1, 2, , n,ikikkkaaa 11 ,kkjkjkiijkkiaaa aa i = k+1, , nj = k+1, , n28例例 求下列矩阵的求下列矩阵的LU分解分解312123221A 解解: 111213212223313233312112312211uuuluullu 设设1112133,1,2uuu LU 分解算法分解

21、算法29212223313233312131212312211luullu 213112,33ll 122233232333312131212312211uulu 222377,33uu LU 分解算法分解算法30177333232333312131212312211lu 32334,17lu LU 分解算法分解算法31ALU Ax = bxyyLbU ( i = n , , 1 )1,niiijjiij ixxyuu -11,iiiijjjyybl ( i = 1, , n )两次回代过程求出方程组的解：两次回代过程求出方程组的解：运算量运算量: n2加加LU分解分解总运算量：总运算量： 3

22、233nnnLU分解求解线性方程组分解求解线性方程组32解：解：例例 用用LU分解求线性方程组分解求线性方程组Ax=b的解，其中的解，其中123421491610, 1627644411681256190Ab令令A = LU，由，由LU分解可得分解可得11234112612, 131624176124LU 回代：解回代：解Ly = = b得：得：y =2, 8, 18, 24T解解Ux = y得：得：x =-1, 1, -1, 1TLU分解求解线性方程组分解求解线性方程组33对称正定矩阵的对称正定矩阵的Cholesky 分解分解设A为对称矩阵,且顺序主子式不为零，做LU分解1121111112

23、22320222211,1nnnnuuuuuuuuUDUuuu 000 , (), .TTTTALULDUAAUDLUL 由由分分解解的的唯唯一一性性，34 , ,.TAnAAALDLLD 对对称称矩矩阵阵的的三三角角分分解解设设 为为 阶阶对对称称矩矩阵阵且且 的的顺顺序序主主子子式式均均不不为为零零，则则 可可以以唯唯一一分分解解为为其其中中 为为单单位位下下三三角角阵阵， 为为对对角角阵阵 ( () )定定理理1110,/0,(2, ).iiidDdDDin 1111222211()()TTTTALDLLD D LLDLDL L 1122111nnndddDD Dddd 若A为对称正定矩

24、阵,则对称正定矩阵的对称正定矩阵的Cholesky 分解分解35n 对称正定矩阵对称正定矩阵的三角分解的三角分解Cholesky 分解分解定理：定理：设设 A 是对称矩阵，若是对称矩阵，若 A 的所有顺序主子式的所有顺序主子式都不为都不为 0，则，则 A 可唯一分解为可唯一分解为其中其中 L 为单位下三角阵，为单位下三角阵，D 为对角矩阵为对角矩阵A = LDLT定理：（定理：（Cholesky分解）分解）若若 A 对称正定，则对称正定，则 A 可唯可唯一分解为一分解为其中其中 L 为下三角实矩阵，且对角元素都大于为下三角实矩阵，且对角元素都大于 0A = LLT对称正定矩阵的对称正定矩阵的C

25、holesky 分解分解36计算计算 Cholesky 分解分解l Cholesky 分解的计算分解的计算直接比较等式两边的元素直接比较等式两边的元素1111211111212122222212221,112 nnnnnn nnnnnnnnnllllaaallllaaallllaaa 111jnijik jkik jkjj ijkkal ll ll l l 计算公式计算公式37Cholesky 分解分解算法算法for j = 1 to nend11221 ,jjjjjjkklal i = j +1, , n11 ,jijijik jkjjklal ll 算法算法 ：(Cholesky 分解分解

26、 )运算量运算量: :n3/6 +n2/2 +n /3 38Cholesky 分解分解算法算法例例 对矩阵对矩阵 作作Cholesky分解分解 41114.252.7512.753.5A 解解11112131212222323132333341114.252.7512.753.5llllllllllll 112131112,22lll 39Cholesky 分解分解算法算法112212222322132333324112214.252.7512.753.5llllll 22322,1.5ll 3333411220.50.514.252.750.5221.512.753.50.51.5ll 33

27、1l 20.520.51.51L 40平方根法平方根法Axb A 对称正定对称正定计算计算 A 的的 Cholesky 分解分解解方程：解方程：Ly = b 和和 LTx = yi = 2, 3, , n算法算法 ：(解对称正定线性方程组的解对称正定线性方程组的平方根法平方根法 )111111, ,iiiikkiikyb lybl yl i = n-1, , 2, 1 1 , nnnnniikikiik ixylxyl xl 41改进改进的的 Cholesky 分解分解121121221,11 11111nTnnn nndllldlALDLlld l 计算公式计算公式111jnijikk jk

28、ikk jkijjkkal d ll d ll d l 改进的改进的 Cholesky 分解分解42改进改进的的 Cholesky 分解分解for j = 1 to nend121 ,jjjjjkkkdal d i = j +1, , n11 ,jijijikk jkjklal d ld 算法算法 ：(改进的改进的 Cholesky 分解分解 )l 优点：优点：避免开方运算避免开方运算43改进的平方根法改进的平方根法Axb A 对称正定对称正定计算计算 改进的改进的 Cholesky 分解分解解方程：解方程：Ly = b 和和 DLTx = yi = 2, 3, , n算法算法 ：(解对称正定

29、线性方程组的解对称正定线性方程组的改进的平方根法改进的平方根法 )1111 , ,iiiikkkybybl y i = n-1, , 2, 1 1 , ,nnnniiikikk ixydxy dl x 44例例 利用改进平方根法求解方程组利用改进平方根法求解方程组 123411614.252.750.512.753.51.25xxx 解：解：1213121232313234111114.252.751112.753.511dllldllld 改进的平方根法改进的平方根法45求得求得140.251,40.250.7511LD 解线性方程组解线性方程组123160.2510.50.250.7511

30、.25yyy 1236,1,1yyy 改进的平方根法改进的平方根法46再解线性方程组再解线性方程组12310.250.256 410.751 411xxx 1232,1,1xxx 改进的平方根法改进的平方根法47追赶法追赶法111122211111nnnnnnbcacab n 对角占优的三对角矩阵对角占优的三对角矩阵的的 LU 分解分解l 计算公式计算公式1111111, bcc b 1iiiiba 1 iiiiiiiccba 1nnnnba i = 2, 3, , n-1iia 48追赶法追赶法Axf A 三对角矩阵（对角占优）三对角矩阵（对角占优）i = 2, 3, , n算法算法 ：(追

31、赶法追赶法 ) 11111 , iiiiiiiyfbyfa yba i = n-1, , 2, 1 1 , nniiiixyxyx 1111 , iiiiiiic bccba i = 2, 3, , n-1l 运算量：运算量：5n-42n -3 n-12(n1)+1+149第五章解线性方程组的直接方法数值分析 向量与矩阵范数向量与矩阵范数50本讲内容本讲内容n 向量范数与矩阵向量范数与矩阵n 矩阵范数矩阵范数l 向量范数的定义向量范数的定义l 常见的向量范数常见的向量范数l 向量范数的性质向量范数的性质l 矩阵范数的定义矩阵范数的定义l F-范数与算子范数范数与算子范数l 矩阵范数的性质、算子

32、范数的性质矩阵范数的性质、算子范数的性质51预备知识预备知识l 向量与矩阵向量与矩阵n 预备知识预备知识l 特征值与特征向量特征值与特征向量l 矩阵的谱：矩阵的谱： ()max()AA (A) = A 的所有特征值的所有特征值 l 矩阵的迹：矩阵的迹：l 矩阵的谱半径：矩阵的谱半径：1122tr()nnaaAa Axx (, , 0)nCxCx 52预备知识预备知识n 相关性质相关性质11AxxA xx 12tr()nA12det()nA A 与与 AT 有相同的特征值有相同的特征值53向量范数向量范数11,1,)nppipixxp n 向量范数向量范数11niixx 12221niixx 1

33、maxii nxx 无穷范数（最大范数）无穷范数（最大范数） 2-范数范数 1-范数范数54范数性质范数性质n 范数的性质范数的性质(1) 连续性连续性设设 f 是是 Rn 上的任意一个范数，则上的任意一个范数，则 f 关于关于 x 的每个分的每个分量是连续的量是连续的(2) 等价性等价性设设 | |s 和和 | |t 是是 Rn 上的任意两个范数，则存在上的任意两个范数，则存在常数常数 c1 和和 c2 ，使得对任意的，使得对任意的 x Rn 有有12stscxxcx 55范数性质范数性质(3) Cauchy-Schwarz 不等式不等式(4) 向量序列的收敛性向量序列的收敛性( )lim*

34、kkxx 22( , )x yxy( )lim*0kkxx l 矩阵的谱：矩阵的谱： ()max()AA (A) = A 的所有特征值的所有特征值 l 矩阵的谱半径：矩阵的谱半径：56矩阵范数矩阵范数设函数设函数 f : Rn n R，若，若 f 满足满足 f(A) 0， A Rn n , 且且 f(A) = 0 A = 0 f( A) = | | f(A) ， A Rn , R f(A+B) f(A) + f(B) f(AB) f(A)f(B)则称则称 f 为为 Rn n 上的（矩阵）范数，通常记为上的（矩阵）范数，通常记为 | | n 矩阵范数矩阵范数57矩阵范数矩阵范数n 常见的矩阵范数

35、常见的矩阵范数(1) F-范数范数 (Frobenious 范数范数)12211nnijFijAa (2) 算子范数算子范数 (从属范数、诱导范数从属范数、诱导范数)其中其中 | | 是是 Rn 上的任意一个范数上的任意一个范数10supmaxnxx RxAxAAxx 58算子范数算子范数111maxnijj niAa n 常见的算子范数常见的算子范数2()TAA A 无穷范数（行范数）无穷范数（行范数） 2-范数（谱范数）范数（谱范数） 1-范数（列范数）范数（列范数）11maxniji njAa 例：例：设设 计算计算1234A 12,FAAAA 59矩阵范数性质矩阵范数性质n 矩阵范数的

36、性质矩阵范数的性质(1) 连续性：连续性：设设 f 是是 Rn n 上的任一矩阵范数，则上的任一矩阵范数，则 f 关于关于 A 的每个分量是连续的的每个分量是连续的(2) 等价性：等价性：设设 | |s 和和 | |t 是是 Rn n 上的任意两个矩阵上的任意两个矩阵范数，则存在常数范数，则存在常数 c1 和和 c2 ，使得对任意的，使得对任意的 A Rn n 有有12stscAAcA (3) 若若 A 是对称矩阵，则是对称矩阵，则2( )AA 60定理：定理：设设 | | 是是 Rn 上的任一向量范数，其对应的上的任一向量范数，其对应的算子范数也记为算子范数也记为 | | ，则有，则有算子范

37、数性质算子范数性质AxAx n 算子范数的性质算子范数的性质定理：定理：设设 | | 是任一算子范数，则是任一算子范数，则( )AA 定理：定理：对任意对任意 0, 总存在一算子范数总存在一算子范数 | | ，使得，使得 | | (A)61算子范数性质算子范数性质定理：定理：设设 | | 是任一算子范数，若是任一算子范数，若 |B| 1 ，则，则 IB 非奇异，且非奇异，且 111IBB 62第五章线性方程组直接解法数值分析 扰动分析扰动分析63线性方程组的线性方程组的病态矩阵病态矩阵考虑线性方程组考虑线性方程组 Ax=b，如果，如果 A 或或 b 的的微小微小变化会变化会导致解的导致解的巨大巨大变化，则称此线性方程组是变化，则称此线性方程组是病态病态的，的，并称矩阵并称矩阵 A 是是病态病态的，反之则是的，反之则是良态良态的。的。n 病态矩阵病态矩阵例：例：1211211.00012xx 1220 xx 122.00011211.0 010 1xx 1211xx