第五章线性方程组的直接解法

1、第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现第五章第五章 解线性代数方程组的直接方法解线性代数方程组的直接方法第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理 第三节第三节 高斯主元素消元法高斯主元素消元法第四节第四节 矩阵三角分解法矩阵三角分解法第五节第五节 向量和矩阵的范数向量和矩阵的范数线性代数方程组的一般形式线性代数方程组的一般形式(1)mnAxbAR 用用矩矩阵阵形形式式表表示示为为其其增增广广矩矩阵阵记记为为 11112211211222221122 nnnnmmmnnma xa xa xba xa xaxbaxaxaxb 111211212

2、22212,nnmmmnmaaabaaabAA baaab 第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理AxbAA 线线性性方方程程组组 有有解解的的充充分分必必定定理理1 1 （线线性性代代数数方方程程组组要要条条件件是是：秩秩（ ）= =秩秩有有解解判判定定理理（别别）(1)( )( ),AxbAArnAxb 线线性性方方程程组组有有解解（即即相相容容）时时，秩秩定定理理2 2秩秩则则方方程程组组存存在在唯唯一一解解。(2) ( )( ),r Ar ArnAxb 方方程程组组有有无无穷穷多多解解。通通解解原原方方程程组组一一个个特特解解对对应应齐齐次次方方程程组组

3、的的基基础础解解系系的的线线性性组组合合。222,|min|mnAxbxxxxAxb 常常见见是是，称称为为欠欠定定方方程程组组（方方程程数数少少于于未未知知数数）此此时时，从从的的无无穷穷多多个个解解中中需需求求出出范范数数最最小小的的解解。即即求求使使， 满满足足。22()()()|minr Ar AAxbmnbAR AxxbAx 方方程程组组无无解解（即即不不相相容容）。常常见见是是，称称为为超超定定方方程程组组（又又称称矛矛盾盾方方程程组组）此此时时，向向量量 不不在在 的的列列空空间间之之中中，原原方方程程组组无无解解，但但可可求求出出最最小小二二乘乘意意义义下下的的解解 。即即求求

4、 使使MATLAB实现实现: x=Ab11112211211222221122 nnnnnnnnnnna xa xa xba xa xaxba xaxaxb 本本章章介介绍绍求求解解 阶阶线线性性方方程程组组的的数数值值方方法法 数值求解方法有以下三条途径（三种框架数值求解方法有以下三条途径（三种框架） 直接法：利用直接法：利用Gauss消元或消元或矩阵分解，通过有限次运算矩阵分解，通过有限次运算 可求出精确解。可求出精确解。迭代法：构造迭代格式，产生迭代序列，通过无限迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。次迭代过程求解。有限次截断得近似解。极小化方

5、法：构造二次模函数，用迭代过程求二次极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经模函数的极小化问题，即变分法（经n 次运算，理论上得精确解）要求次运算，理论上得精确解）要求A 对称正定对称正定(S.P.D) 用增广矩阵表示为用增广矩阵表示为同解同解初等变换初等变换组组化为同解的上三角方程化为同解的上三角方程将原方程组将原方程组求解求解gUxbAxgUxbAxRAbAxnn 第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现 A b U g )1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnn

6、nnbaaabaaabaaa )()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa 三角形方程组包括上三角形方程组和下三角三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一。上三角形方程组，是最简单的线性方程组之一。上三角方程组的一般形式是方程组的一般形式是： ),.,2 , 1(0.111112222211212111niabxabxaxabxaxabxaxaxaiinnnnnnnnnnnnnnn 其其中中1242343444573131313131xxxxxxxxx 用用回回代代法法求求解解线线性性方方程程组组例例43

7、424314212341(1313)/ 30( 75)( 750)244121,)(1 ,2,0:,1)TTxxxxxxxxxxxxx 所所以以，解解为为（解解1 , 1/ )(/1 niaxabxabxnikiikikiinnnn 为求解上三角方程组，从最后一个方程入手，先为求解上三角方程组，从最后一个方程入手，先解出解出 x xn n=b=bn n/a/annnn, , 然后按方程由后向前的顺序，从方然后按方程由后向前的顺序，从方程中依次解出程中依次解出x xn-1n-1,x,xn-2n-2,x,x1 1。这样就完成了上三角方这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算

8、步程组的求解过程。这个过程被称为回代过程其计算步骤如下：骤如下：11212322232429xxxxxx 用用回回代代法法求求解解线线性性例例 、方方程程组组1231232/ 21(21)/11(93121)/ 41,)(1 ,1 , ):1xxxxxx 所所以以，解解为为（解解21111)(1)22ninin nn 求解一个三角形方程组需 次除法与求解一个三角形方程组需 次除法与（次乘法。（次乘法。12111111,/()/(2,3, )niiiikkiikxxxxbaxba xain 下下三三角角形形方方程程组组可可以以参参照照上上三三角角形形方方程程组组的的解解法法来来求求解解，下下三三

9、角角形形方方程程组组的的求求解解顺顺序序是是从从第第一一个个方方程程开开始始，按按从从上上到到下下的的顺顺序序，依依次次解解出出：其其计计算算公公式式为为：如如上上解解三三角角形形方方程程组组的的方方法法称称为为回回代代法法. .1111211222211220,1,2,nnnnnniia xbaxaxbaxaxaxbain 下下三三角角方方程程组组的的一一般般形形式式为为：其其中中 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法, ,由它改进得到由它改进得到的选主元法的选主元法, ,是目前计算机上常用于求低阶稠密矩阵是目前计算机上常用于求低阶稠密矩阵方程组的有效方法方程组的有效方法

10、, ,其特点就是通过消元将其特点就是通过消元将一般线性一般线性方程组方程组的求解问题转化为的求解问题转化为三角方程组三角方程组的求解问题的求解问题。 高斯消元法的求解过程高斯消元法的求解过程, ,可大致分为两个阶段可大致分为两个阶段: :首先首先, ,把原方程组化为上三角形方程组把原方程组化为上三角形方程组, ,称之为称之为“消消元元”过程过程; ;然后然后, ,用逆次序逐一求出上三角方程组用逆次序逐一求出上三角方程组( (原原方程组的等价方程组方程组的等价方程组) )的解的解, ,称之为称之为“回代回代”过程过程. . 高斯高斯“消消元元”过程过程可通过矩阵运算来实现。具可通过矩阵运算来实现

11、。具体过程如下：体过程如下：12312312323623493263Gaussxxxxxxxxx 用用消消元元法法求求解解方方程程例例组组11/1/21/2/01, 362319432632111313111212111)1( aamaamanbAA增增广广矩矩阵阵：解：解：11121,:11L AxL b 1 1L L = =, ,完完成成第第一一步步消消元元 得得(2)(2)(2)223232222212110,/1/( 1)111,11amaaLL L AxL L b = =, ,完完成成第第二二步步消消元元 得得 3332632332321xxxxxx3231231233 /31( 3

12、2)( 321)16236213111,1,1xxxxxxxxx 回回代代求求得得故故所所求求解解为为 011032106321)2(A 330032106321)3(A将方程组将方程组Ax=b的系数矩阵与右端项合并为的系数矩阵与右端项合并为 11121121222212,nnnnnnnaaabaaabA bAaaab (1)(1)(1)1111(1)(1)(1)(1)(1)12(1)(1)(1)1.,.,.nnnnnnaabAAbaab记记 (1)(1)1(1)11111,0,.,0.TALLa 对的第一列构对的第一列构造使造使1(1)11111110,2,.,iiaamina（ ）（ ）（

13、 ）（ ）：设取：设取第一步第一步2111111nmLm (1)(1)(1)(1)111211(2)(2)(2)(1)(2)(2)(2)(2)(2)2222112(2)(2)(2)2.0.,.,0.nnnnnnnaaabaabL AAbaab (2)(1)(1)1 1(2)(1)(1)1 12, ,2,2,ijijijiiiaam ain jnbbm bin (1)(1)1(1)(1)11AxbLL AxL b 对对方方程程组组从从左左边边乘乘以以(1)(1)(1)1111(1)211(1)(1)(1)111.1.1nnnnnnaabmL Aaabm (2)(2)2222(2)2203,.,i

14、iaamina：设，：设，第二步第二步取取(2)(2)32222(1)(1)(1)(1)(1)1112131,1(2)(2)(2)(2)22232,2(2)(1)(3)(3)(3)(3)221333,3(3)(3)(3)3,111,100000nnnnnn nnmALmaaaabaaabL AL L AaaAbaab - -对的第二列构造对的第二列构造- -使使(2)22(2)22,iiama (1)(1)2121L L AxL L b (3)(2)(2)22(3)(2)(2)22,3,3,4,.,ijijijiiiaam ai jnbbm bin (1)(1)(1)(1)111211(2)(

15、2)(2)(2)2222322(2)(2)(2)22(1)(1)(1)(1)1112131,(2)(2)(2)22232,(3)(3)333,(331.10.10.100000nnnnnnnnnnnaaabaabmL Aaabmaaaaaaaaaa - - -(1)1(2)2(3)(3)3)(3)(3),n nnbbAbab 进行到第进行到第k步消元时步消元时( )(1)( )kkkAAAk 下下一一步步消消元元，从从，将将的的第第 列列的的对对角角元元以以下下的的元元素素化化为为零零。(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333

16、()()()()1()()()1,1,11()()()(),1.nnnkkkkkkkkkkkkkkkkkkkkknkn knnnaaaabaaabaabAaabaabaaab ( )( )( )0,(1,., )kkikkkkikkkkaamaiknGaussL 设设取取，构构造造变变换换阵阵,111111Tkkkkn kIl emm (1)()kkkAL A 消消元元计计算算递递推推公公式式：()(1,2,1)kkkakn 称称为为主主元元素素. .( )( )(1)( )( )(1)( )( )1,1/21,3kkikikkkkkkijijikkjkkkiiikkiknmaaaam ajk

17、nbbm b （）（ ），（ ）(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb 即即 用回代过程求解上三角方程组，即可得解向量用回代过程求解上三角方程组，即可得解向量 ( x1*,x2*, ,xn* ) )T T. .是是高高斯斯消消元元的的前前提提。)1,2, 1( ,0)( nkakkk(1)(1)121121nnLL L AxLL L b (1)(1)(1)(1)111211(2)(2)(2)()2222()()000nnnnnnnnaaabaabAab 最最后后得得求解的全过程包括两个步骤：消元和回代求解的

18、全过程包括两个步骤：消元和回代1 . 1 . 顺序消元顺序消元2 . 回代求解回代求解( )( )( )( )( )1/()/1,2,1nnnnnnnkkkkkkjjkkj kxbaxbaxaknn ( )( )(1)( )( )(1)( )( )1,11,1/21,3kkikikkkkkkijijikkjkkkiiikkkniknmaaaam ajknbbm b （）（ ），（ ）步步消消元元计计算算后后，第第的的二二维维数数组组存存放放一一个个用用用用动动态态存存储储方方式式。最最初初在在计计算算机机中中计计算算时时，采采存存储储方方式式kAnn ), 1;, 1(), 1()1()()(

19、nkjnkiaankimakijkijikkik )()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.knnkknknkkkkkkkkkkkkknnnkaaaaaaaaaaaaaaaaAikm) 1( kijaUIL 消元过程全部完成后，原来的二维数组中存放的消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为元素实际上是一个新的矩阵，记为FAFAA用动态形式表示为用动态形式表示为)(1,321)3(3)3(1, 3)3(333231)2(2)2(1,2)2(23)2(2221)1(1)1(1

20、, 1)1(13)1(12)1(11nnnnnnnnnnnnnnFammmmaaammaaaamaaaaaA 选主元基本思想选主元基本思想 用高斯消元法求解线性方程组时用高斯消元法求解线性方程组时, ,为避免小的主元为避免小的主元. .在进在进行第行第k k步消元前步消元前, ,应该在第应该在第k k列元素列元素 ( (i=k,ni=k,n) )中找出第中找出第一个出现的绝对值最大者一个出现的绝对值最大者, ,例如例如 ， 再把第再把第i ik k个方程与第个方程与第k k个方程组进行交换个方程组进行交换, ,使使 成为主元成为主元. .我们我们称这个过程为选主元称这个过程为选主元. .由于只

21、在第由于只在第k k列元素中选主元列元素中选主元, ,通常通常也称为也称为按列选主元按列选主元. . )(kika()()maxkkki kikkinaa )(kija 如果在第如果在第k k步消元前步消元前, ,在第在第k k个方程到第个方程到第n n个方程所有个方程所有的的x xk k到到x xn n的系数的系数 ( (i=k,n;j=k,ni=k,n;j=k,n) )中中, ,找出绝对值找出绝对值最大者最大者, ,例如例如 ( )kki ka 第三节第三节 高斯主元素消元法高斯主元素消元法 再交换第再交换第k k, ,ikik两个方程和第两个方程和第k k, ,jkjk列列, ,使使 成

22、为主成为主元元. . 称这个过程为称这个过程为完全选主元完全选主元. 不论是哪种方式选出主元不论是哪种方式选出主元, ,而后再按上面介绍的计而后再按上面介绍的计 算步骤进行消元的计算算步骤进行消元的计算, ,一般都称为选主元的高斯消元一般都称为选主元的高斯消元法法. .在实际计算中在实际计算中, ,常用按列选主元的高斯消元法常用按列选主元的高斯消元法. .( )k kki ja( )( ),maxk kkki jijk i j naa ( )( )( )( )( )()()| max|,1,(1),(,2kkkkkkkkkkki kikk i nkkkkkkji jkjkji ji jkikk

23、iikikinaaAAbikTikaajk knTaaaaTbbTb bbbT 对对每每一一步步 第第 步步 消消元元，分分两两步步确确定定使使对对增增广广矩矩阵阵使使列列主主元元高高斯斯消消元元法法具具体体做做法法是是：选选列列主主元元换换行行在在计计算算机机上上，用用一一个个工工作作单单元元来来完完成成，对对，包包括括消消元元计计算算算法算法 列主元高斯消元法解线性方程组列主元高斯消元法解线性方程组 Ax = bAx = b停停机机。信信息息输输出出失失败败则则认认为为如如果果使使确确定定、选选列列主主元元步步。循循环环执执行行到到第第对对、置置, , 0det , 0 ,max 2 51

24、, 2 , 1 1det 1 kikiiknikkikkkkaaaaink detdet , ), 1,( , 4 , 3 kkikjikjkbbnkkjaaki否否则则交交换换行行步步转转出出执执行行第第、如如果果具体执行行交换要通过工作单元具体执行行交换要通过工作单元 T。TbbbbTTaaaaTkkkkiikkjijikjkj ; ; ; ;。、输输出出解解向向量量、否否则则停停机机。输输出出失失败败信信息息则则认认为为如如果果、回回代代求求解解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabbaaadet, ,),( 8detdet7)1 , 2

25、, 2, 1( / )( / , 0,6detdet 5211 (3) ), 1( (2) /(1) , 2, 14kikiikjikijijkkikikikbabbnkjaaaaaamankki 、消消元元计计算算假设求解是在四假设求解是在四位浮点十进制数位浮点十进制数的计算机上进行的计算机上进行0.0001x1+x2=1 x1+x2=2将两个方程对调，得将两个方程对调，得 x1+x2=2 0.0001x1+x2=1在四位浮点十进制数的计算机上在四位浮点十进制数的计算机上,上式为上式为 x1+x2=2 即即 x1+x2=2 (0.1000101-0.00001 101x2=1 x2=1（1-

26、0.0001) x2=1x1+x2=2消元，得消元，得解得：解得： x1=1， x2=1现在我们再用列主元法解下列问题现在我们再用列主元法解下列问题例例 用列主元消去法解方程组用列主元消去法解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a a3131(1)(1), ,故先作行交换故先作行交换E E1 1 E E3 3, ,然后进行然后进行消元计算可得消元计算可得-0.002x1+2x2+2x3 =0.4 x1+0.78125x2 =1.38163.996x1+5.5625x2+4x3=7.4178 -0.002 2 2 0.4 A(1) |b(1) = 1 0.78125 0

27、 1.3816 3.996 5.5625 4 7.4178 3.996 5.5625 4 7.4178 A(2) |b(2) = 0 -0.61077 -1.0010 -0.47471 0 2.0029 2.0020 0.40371 由此回代由此回代, ,得得x x=(1.9272,-0.69841,0.90038)=(1.9272,-0.69841,0.90038)T T与与精确解精确解 x x=(1.9273,-0.69850,0.90042)=(1.9273,-0.69850,0.90042)T T相比较是比较相比较是比较准确的准确的. . 3.996 5.5625 4 7.4178A(

28、3) |b(3) = 0 2.0029 2.0020 0.40371 0 0 -0.39050 -0.35160 第二次消元对第二次消元对 A A(2)(2) | |b b(2)(2) , ,因列主元素为因列主元素为a a3232(2)(2) , ,故故先作行交换先作行交换E E2 2 E E3 3, ,然后进行消元计算可得然后进行消元计算可得uLLLLAKK1121)( 记记11)( LLLK，则，则LUA 上上三三角角）（下下三三角角 三角因子分解三角因子分解GaussGauss消元，初等行变换，化原方程组为上三角型消元，初等行变换，化原方程组为上三角型. .一一. .高斯消去法与三角分解

29、高斯消去法与三角分解uALLLLKK 121gubALLLLkk 121)|()|(gubA )g |()|()|(第四节第四节 矩阵三角分解法矩阵三角分解法高斯消去法高斯消去法求解线性方程组：求解线性方程组：, bbxyMLxAUyxxyyxL ULUbAU=分解代入 求解下三角方程组求解上三角方程组设 注：注：其中其中A(k, k) 主元如果过小则分解得到的主元如果过小则分解得到的 L和和U偏大，偏大， 最终造成解有很大误差最终造成解有很大误差. 若若 A A 的各阶顺序主子式不为零的各阶顺序主子式不为零, A , A 能做三角分解能做三角分解. .定义定义1 1 A=LUA=LU 称作称

30、作A A的三角（因子）分解，其的三角（因子）分解，其中中L L是下三角，是下三角，U U是上三角是上三角. .三角分解不唯一三角分解不唯一, ,为此引入为此引入定义定义2 2 A=LUA=LU， 若若L L是单位下三角，是单位下三角，U U是上三角，是上三角，称作称作A A的的 Doolittle Doolittle 分解分解. .定义定义3 3 A=LUA=LU， 若若L L是下三角，是下三角，U U是单位上三角，是单位上三角，称作称作A A的的 CroutCrout 分解分解. . nnnnnnnbyylylylbyylby1122112212111 Ly=b为为 若矩阵若矩阵A A能分解

31、为一个单位下三角矩阵能分解为一个单位下三角矩阵L与一与一个上三角矩阵个上三角矩阵U的乘积的乘积 A=LU 则线性方程组则线性方程组Ax=b 可化为两个线性可化为两个线性方程组的求解方程组的求解 Ly=b 与与 Ux=y 1 , 2 , 1,1 nkuxuyxuyxkknkiikikknnnnnkylbybykiikikk, 3 , 2,1111 解出解出 nnnnnnnnyxuyxuxuyxuxuxu2222211212111 Ux=y为为下面导出下面导出 L, U L, U 的元素的元素, , 因为因为 nnnnnnaaaaaaaaa212222111211 1112121nnlll nnn

32、nuuuuuu22211211niijulauauikkjikijijjj, 1,1111 则则nijauulalualijiiikkijkjijijj, 1,111111 1212359,674xAbxxxx例如 求解二阶方程组 TT 41458/914/3xxyyyyxyxLUULUbbL b再代入方程组为 ，设 代入得 先解下三角方程组 求出 ，最后解上三角方程组 求出解 。35103567210310352103 LULULUAA首先 三角分解 即 ，下三角 和上三 角1 4 71 0 02 -3 -62 1 03 2 13 2 11 4 7 0 -3 -60 0 1 LAU即，例例T

33、1 4 7, 2 5 8(1,1,1)3 6 10AbxbA求解 其中 ，解解：1231 0 02 1 0 , , (1, 1, 1)3 2 1b Ly TTyyy112123 , 2+ , 3+ 2+(1, 1, 1)TTyyyyyy1213121, 1 - 2-1, 1-3-20yyyyyy 1,-1, 0y T1231 4 70 -3 -6 1, 1, 00 0 1Uxy TTxxx12323347, 36,1, 1, 0TTxxxxx x11 , , 033 xT323212311=0, 3=-1+6=, =1-4-733xxxxxxx nnnnnnaaaaaaaaa212222111

34、211nnnnllllll212221111112112nnuuunijalulaulauijiiikkjikijijjj, 1,111111 niijulalalikkijkjijijj, 1,1111 若若A=LU， L是下三角，是下三角，U是单位上三角，是单位上三角，称作称作A的的 Crout (克洛特克洛特)分解分解1 , 1,1 nnixuyxnikkikiinilylbyiiikkikki, 2 , 1,11 解出解出 若矩阵若矩阵A A能分解为一个下三角矩阵能分解为一个下三角矩阵L L与与一个单位上三角矩阵的乘积一个单位上三角矩阵的乘积 A A= =LULU 则线性方程组则线性方

35、程组 AxAx= =b b 可化为两个线性方可化为两个线性方程组的求解程组的求解 LyLy= =b b 与与 UxUx= =y y 选主元的三角分解法,1100.000111110.000110,00099990 LUALAUbx分解例如 求解二阶方程组 其中 011100.000110.00010.99911091110 PLUPPA PPLU置换分解可通过置换阵 来交换矩阵 的行从而克服其小主元困难 即 。iiliiliiuiiu思路思路：当：当 ( (或或 )=0)=0时时, ,计算将中断计算将中断, ,或者当或者当 ( (或或 ) )绝绝对值很小时对值很小时, ,会引起舍入误差的增长会

36、引起舍入误差的增长. .但如果但如果A A非奇异非奇异, ,为减为减小方程组求解误差可通过小方程组求解误差可通过A A 的行交换来实现的行交换来实现PAPA的的 LULU三三角分解角分解, ,其中其中P P为交换为交换( (排列排列) )矩阵。矩阵。 但其计算过程不稳定，不适于求解较大规但其计算过程不稳定，不适于求解较大规模的线性代数方程组。模的线性代数方程组。 列选主元方法：列选主元方法： （行交换的技巧）（行交换的技巧） 设设 A AR Rn nx xn n ，通过行交换在其原主元以下部，通过行交换在其原主元以下部分所在列中选主元分所在列中选主元. .为了避免用较小的数为了避免用较小的数l

37、 lii ii 作除作除法法, ,引进量引进量jjkiikjkjijuulas 11rjnjiss max设设 将第将第i i行与第行与第r r行交换行交换, ,同时交换常数项同时交换常数项b bi i 与与b bj j , ,再作第再作第i i步分解步分解. .11111001181201042100171010061812102201811/ 301/062623EEMM EAA先选，再定，。例例 列选主元三角分解法列选主元三角分解法3171024261812A例如221122211101618182200101601002100618120108101/ 4006160AAEE M EM

38、M E M E又选使，再定。三对角方程组与追赶法 系数矩阵除对角线及两侧有非零元素外系数矩阵除对角线及两侧有非零元素外, ,其其余元素均为零余元素均为零, ,这样的线性方程组称为这样的线性方程组称为三对角形三对角形方程组方程组. . nnnbaccbacbA122211 ndddd21若若AXAX= =d d , ,其中其中 若A=LU ,则 nnnbaccbacb122211 nnlmlml221 111121nuuu, 3 , 2,1,1111niumblamlcubliiiiiii 则则, 1, 3 , 2, nilcuiii1 , 2 , 1,1 nixuyxyxiiiinnnilym

39、dyldyiiiki, 3 , 2,1111 解出解出( (赶赶) )(追赶法追赶法)( (追追) ) 若求出矩阵若求出矩阵A A的克洛特分解的克洛特分解, , 即即 A A= =LULU 则线性方程组则线性方程组 AxAx= =b b 可化为两个线性方程组的求解可化为两个线性方程组的求解 Ly=b 与与 Ux=y例例 用追赶法用追赶法 解方程组解方程组 100121001210012100124321xxxx1,1,1123 xxx4/33/2,2/1321 uuu1,4/1,3/1,2/14321 yyyy解解 (1) 计算计算 :iu :iy(2) 计算计算 :ix(3) 求解计算求解计

40、算对称正定方程组的平方根法对称正定方程组的平方根法一、平方根法一、平方根法 1112121nnlll nnnnuuuuuu22211211 nnnnnnaaaaaaaaa212222111211 若若A A为为对称正定矩阵对称正定矩阵，则各阶顺序主子，则各阶顺序主子式大于零，可以分解，即式大于零，可以分解，即A=LUA=LU 1112121nnlll nnnnuuuuuu22211211若将若将U U进一步分解为进一步分解为 nnnnuuuuuuU22211211 11122211111122211uuuuuuuuunnnn1DU A=LULLDALUEUL 111,LDULDUA 11111

41、1 ULDULD nnuuu2211 nnuuu2211 1*1*1 1*1*1 nnuuu*2211 1*1*1右边矩阵中*为零)(11LDLDA ndddD21221 nddd21D LLALDL 1: nijlllaijlaliiikikjkjiikikiiji, 1,)(1111212可以解出可以解出 称为称为对称正定矩阵的乔列斯基分解对称正定矩阵的乔列斯基分解 nilylbyiikikikii, 2 , 1,11 解出解出 1 , 1,1 nnilxlyxiiknikkiii平平方方根根法法)61(3n优优点点：运运算算量量小小 则线性方程组则线性方程组 AxAx= =b b 可化为

42、两个线性方程组的求解可化为两个线性方程组的求解 LyLy= =b b 和和UxUx= =y y LLALDL 1:若求出若求出对称正定矩阵的乔列斯基分解对称正定矩阵的乔列斯基分解, ,即即缺点：开方运算。缺点：开方运算。LDLLDL 及其改进分解及其改进分解1985. 2,4495. 262211ll解解（1 1）分解计算）分解计算A=LLA=LLT T91096858137576321xxx例例 用平方根法解方程组用平方根法解方程组9285. 0,0412. 2653331ll9856. 0,8577. 2673221llTx) 2 , 1, 1 (*精确解精确解 9285. 09856.

43、00412. 21985. 28577. 24495. 2L(2)(2)解解bLy (3)(3)解解yUx Ty)8570. 1 ,2273. 0,6742. 3(Tx)0 . 2, 0 . 1, 0 . 1 (改进的平方根法改进的平方根法A 1112121nnlll nddd21Tnnlll 1112121则则, 2 , 1,112 idladkikikiiinijdldlaliikkikjkjiji, 1,11 LLDA 若若A A为对称正定矩阵为对称正定矩阵, , 可以分解为可以分解为: :1 , 1,1 nnixldyxknikkiiii若对称正定矩阵分解为若对称正定矩阵分解为LLDA

44、 则线性方程组则线性方程组 AxAx= =b b 化为两个线性方程组的求解化为两个线性方程组的求解 LyLy= =b b 和和 L L x x= =D D-1-1y y niylbykikikii, 2 , 1,11 解出解出 解解（1 1）分解计算）分解计算A=LDLA=LDLT T，得，得例例 用改进的平方根法解方程组用改进的平方根法解方程组d1=5l21=-0.8l31=0.2d2=2.8l32=-1.14286d3=2.14285(2)(2)解解 LyLy= =b b y1=2, y2=0.6, y3=-0.714284(3)(3)解解 L L x x= =DD-1-1y y x3=-

45、0.333333x2=-0.166667x1=0.333333 1641464245321321321xxxxxxxxx1-1-范数范数: :nxxxx 2112-2-范数范数: :222212nxxxx - -范数范数: :inixx 1max(Euclid(Euclid欧氏欧氏- -范数范数) ) 14)321(33 , 2 , 1max63212122221 xxx例例 设设 计算三种范数计算三种范数. .解解,)3 . 2 , 1(Tx 一、向量的范数第五节第五节 向量和矩阵的范数向量和矩阵的范数 二、矩阵的范数(3) (3) 三角不等式三角不等式, ,BABA 则称则称 为方阵为方阵

46、 的的范数范数. . AA(1) ,(1) ,等号成立当且仅当等号成立当且仅当0 A0 A(2) (2) 对任意实数对任意实数 , ,有有 AaaA aBAAB (4)(4)ppppxAAxY A定义定义 对任意对任意n n阶方阵阶方阵A A , ,若对应一个非负实数若对应一个非负实数 , , 满足条件满足条件为为方阵方阵 的的 范数范数. . pxppxpAxxAxAp10supsup A p(1) (1) 列范数列范数 niijnjaA111max212)(之之最最大大特特征征值值方方阵阵AAA (2)(2)(欧氏欧氏-范数范数) )定理定理 设设 , ,则则)(,ijnnaARA njijniaA11max(3) (3) 行范数行范数可以验证该范数满足定