线性方程组与矩阵特征值求解的数值方法

1、第二章第二章 线性方程组与矩阵特征值线性方程组与矩阵特征值求解的数值方法求解的数值方法l 引言引言l 高斯消元法高斯消元法l 矩阵分解法矩阵分解法l 向量范数与矩阵范数向量范数与矩阵范数l 迭代法求解迭代法求解l 方程组的病态问题与误差分析方程组的病态问题与误差分析l 方阵特征值计算方阵特征值计算1 引言引言 在自然科学和工程技术中，有很多问题的解决都需要用到线性方程组的求解。因此，求解线性方程组的问题是一个在科学技术中常见的普遍问题。 一般地，这些线性方程组的系数矩阵大致可分为两类： 1）低阶稠密矩阵 2）大型稀疏矩阵解线性方程组的数值解法：有直接法直接法和迭代法和迭代法两类。直接法：计算过

2、程没有舍入误差，经过有限次四则运算直接法：计算过程没有舍入误差，经过有限次四则运算可求得方程组的精确解。可求得方程组的精确解。（实际计算有舍入误差）高斯消元法，矩阵分解法迭代法：核心是迭代求解的收敛条件和收敛速度。迭代法：核心是迭代求解的收敛条件和收敛速度。雅可比（Jacobi）迭代，高斯-赛德尔（Gauss-Seidel）迭代2 高斯消元法高斯消元法 )(11163)(1852)(174332123211321ExxxExxxExxx解：解： 1116318521741A313212)( 3)()( 2)(EEEEEE 基本思想方法基本思想方法：例例2.1 用消去法解方程组用消去法解方程组由

3、由行初等变换行初等变换将系数矩阵约化为三角将系数矩阵约化为三角矩阵；矩阵；用用回代回代的方法求解方程组。的方法求解方程组。（1）消元：）消元： 1741323)( 2)(EEE ， 163017411630 21060 0200高斯消元法高斯消元法是求解方程组的古典方法。(2.1)一、高斯消元法一、高斯消元法结论：结论：整个计算过程可分为两部分：（1）消元：把原方程组转化为系数矩阵为上三角矩阵的方程组；（2）回代：由系数矩阵为上三角矩阵的方程组求解对于一般情形对于一般情形： m个方程，个方程，n个未知数的线性方程组个未知数的线性方程组的高斯消元法的高斯消元法 mnmnmmnnnnbxaxaxa

4、bxaxaxabxaxaxa22112222212111212111(2.2)（2）回代求解，得：）回代求解，得：。03 x，312 x，311 x，其其系系数数矩矩阶阶 mnmmnnaaaaaaaaaA212222111211。 mbbbb21，)1()1()1(, )(bbaAAij 若记若记,21 mxxxx(1)(1)(2.2)Axb则可写为，即 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11mnmmnnaaaaaaaaa )1()1(2)1(1mbbb mxxx21（1）第）第1步步(k=1)，)2() 1(11) 1(11miaamii ，具体计算公

5、式为：具体计算公式为： njmiamaajijiji, 3 , 2, 3 , 2)1(11)1()2( ，（m-1)(n-1)次乘法运算次乘法运算高斯消元法高斯消元法： )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11mnmmnnaaaaaaaaa )1()1(2)1(1mbbb mxxx210)1(11 a设设 ，计算乘数，计算乘数 (m-1)次除法运算次除法运算对增广矩阵对增广矩阵 进行进行行初等变换行初等变换：，),3 , 2(11mirrmriii A), 3 , 2()1(11)1()2(mibmbbiii （m-1)次乘法运算次乘法运算(1)(1)(1

6、)(1)111211(1)(1)(1)(1)212222(1)(1)(1)(1)12nnmmmnmaaabaaabAaaab增广矩阵增广矩阵A)2()2(2)2(2)2(22mnmnaaaa记为记为(2)(2)Axb（2 2）第）第k步（步（ ）), 1min(, 2 , 1nmssk ， )1()1(bxA )1(1)1(12)1(11naaa， )2()2(2)1(1mbbb mxxx210, 0)1(1, 1)1(11 kkkaa设已完成上述消元过程第设已完成上述消元过程第1 1步，步，第第2步，步，第，第k-1-1步，且步，且 )1()1(bxA 得到与原方程组得到与原方程组 等价的方

7、程组。等价的方程组。( )( )kkAxb，其其中中 )2(2)2(22)1(1)1(12)1(11)(nnkaaaaaA。 )()()2(2)1(1)(kmkkkbbbbb)()()()(kmnkmkkknkkkaaaa于是，即有：，设设0)( kkka(1)(1)kkAxb，), 1()()(mkiaamkkkkikik 计算乘数计算乘数 对对 进行进行行初等变换行初等变换,使使 第第k列列 以下元素约为零以下元素约为零,)(kA)(kkka( )( )()kkAb,（m-k）次除法运算）次除法运算即即 ，得到与原方程组等价的方程组，得到与原方程组等价的方程组(1, )iik kirm r

8、r ikm 第第 k步具体计算：步具体计算：对于 ，则有： 其中其中 元素计算公式为：元素计算公式为： )1()1(, kkbA nkjmkiamaakkjikkjikji, 1, 1)()()1( ，), 1()()()1(mkibmbbkkikkiki 与与 前前k行元素相同，行元素相同， 的左上角的左上角k阶阵阶阵)1( kA)(kA)1( kA )()(1)1(11)(11kkkkkkaaaA为上三角阵。为上三角阵。（m-k)次乘法运算次乘法运算（m-k)(n-k)次乘法运算次乘法运算(1)(1)kkAxb)1()()1()(kkkkkkbbLAAL第第k步约化公式：步约化公式： （3

9、 3）继续上述约化过程，）继续上述约化过程，且设且设), 2 , 1(0)(skakkk (1)(1)ssAxb （i） 当当m n时，时，s = n，且设，且设 ，则，则), 2 , 1(0)(nkakkk ， （ii）当）当m = n时，时， s = n-1,且设且设 ，则，则) 1, 2 , 1(0)( nkakkk，直到完成第直到完成第S步计算，得到与原方程组等价的方程组步计算，得到与原方程组等价的方程组其中其中 为上梯形，具有以下三种情况（为上梯形，具有以下三种情况（讨论讨论）：）：)1( sAUaaaaaaAnmnnnnnS )()2(2)2(22)1(1112)1(11)1(0U

10、aaaaaaAnnnnnn )()2(2)2(22)1(1)1(12)1(11)( (iii) (iii)当当m n时，时，s = m-1，且设，且设 , ,则则 ) 1, 2 , 1(0)( mkakkk，UaaaaaaaaAmmnmmmmnnm )()()2(2)2(22)1(1)1(1)1(12)1(11)(说明：说明： (1)上述约化过程，可用矩阵变换来实现，即上述约化过程，可用矩阵变换来实现，即 1111, 1mkkkkmmL其其中中)1( kA), 1(mkimik )(kA 由由 约化到约化到 , ,实际上是由乘数实际上是由乘数 构成初构成初与与 相乘得到相乘得到 ，即即 )1(

11、 kA)(kA )1()()1()(kkkkkkbbLAAL等下三角阵等下三角阵kL )()(1)()(1)(11)(1)()(1)()1(1)1(11, 1)(1111kmnkmkkmkknkkkkkkkkknkkkkkknmkkkkkaaaaaaaaaaammAL)1( kA )()()1(1)1(11kknkkknaaaa)1()1(1)1(1)1(11 kmnkmkknkkkkaaaa 即即UALLLS 12为高斯变换，为高斯变换，sLLL,21其中其中，即即给给定定bxA ，在在), 2 , 1(0)(skakkk （上梯形）（上梯形）), 1(skLk 条件下存在高斯变换条件下存在

12、高斯变换 ，使将，使将A 约化为上梯形。约化为上梯形。（2）元素元素 称为称为约化的主元素约化的主元素，且原方程组约化为等价方，且原方程组约化为等价方)(kkka为为非非奇奇异异阵阵，特特别别当当nnRA 时时，且且)1, 1(0)( nkakkk bxA )(/nnnnnnabx) 1 , 2 , 2, 1( nni由由消元过程消元过程和和回代过程回代过程构成了构成了高斯消元法高斯消元法。)1()1( sSbxA程组程组 过程称为过程称为消元过程消元过程， )()2(2)1(121)()1(1)1(12)1(11nnnnnnnbbbxxxaaaa用用回代法回代法求解：求解：)(1)()(/

13、)(iiinijjiijiiiaxabx 因此上述约化过程，可用矩阵变换来描述为：因此上述约化过程，可用矩阵变换来描述为： （3 3）若）若Ax=b, ,其中其中 非奇异矩阵，若此时非奇异矩阵，若此时 为零。为零。nnRA )1(11a，但但0)det( A，),3 , 2(011 ,1miai 所以所以A第第1 1列一定存在元素列一定存在元素bA,11irr 此时可交换（此时可交换（ ）第）第1 1 行与第行与第i1行元素（即行元素（即 ）。）。然后进行消元计算。于是然后进行消元计算。于是 ，且，且 右下角矩阵为右下角矩阵为n-1)2()1(AA)2(A阶阶非奇异矩阵。当非奇异矩阵。当 时，

14、直接进行消元计算时，直接进行消元计算, ,), 3 , 2(0)(nkakkk ， （用高斯变换约化）：（用高斯变换约化）：，设设), 1min(,nmsRAnm 0)( kkka结论：结论：定理定理1 sLlL,21则存在初等下三角阵则存在初等下三角阵 ,使使UALLLs 12(上梯形上梯形)成立。成立。，), 2 , 1(sk 时，时，可采用上述方法同样处理。可采用上述方法同样处理。( )0 (2,3, )kkkakL n，当当，设设bxA ，其中其中nnRA 定理定理2 (1)如果如果 ，则通过高斯消去法（不进行，则通过高斯消去法（不进行), 2 , 1(0)(nkakkk ，交换两行的

15、初等变换）可交换两行的初等变换）可将将 化为等价的三角方程组。化为等价的三角方程组。bxA )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa 回代计算：回代计算： )()(/nnnnnnabx)1, 2 , 1( nk ), 1(/)()(nkiaamkkkkikik 消元计算：消元计算：), 1()()()1(nkibmbbkkikkjki nkjnkiamaakkjijkijkij, 1, 1)()()1( ；)(1)()(/ )(iiinijjiijiiiaxabx ) 1 , 2 , 2, 1( nni （2）如果）如果

16、A为非奇异矩阵，则可通过带行交换的高斯消去为非奇异矩阵，则可通过带行交换的高斯消去法，将法，将 化为等价的三角形方程组。化为等价的三角形方程组。bxA 即，即，Gauss消元法中消元法中, ,( )0kkka若，直接消元计算，若若0)( kkka注：注：则要求在算法中增加一判断，并进行则要求在算法中增加一判断，并进行行交换行交换。) ,2 , 1()( kakkk是否是零，可以根据顺序主子式来判断。是否是零，可以根据顺序主子式来判断。二、高斯主元消去法二、高斯主元消去法例例2.2 用高斯消去法解方程组用高斯消去法解方程组 9 . 07 . 0103 . 0212111xxxx精确到精确到101

17、0位真解位真解：Tx)7000000000. 0,2000000000. 0(* 9 . 0117 . 01103 . 0),(11bA解法解法1 1（高斯消去法）（高斯消去法）消元：消元：121121103333333333. 0103 . 01 m12103333333333. 011 舍去舍去/ /被被“吃吃”舍去舍去/ /被被“吃吃”12103333333333. 07 . 09 . 0 07 . 01103 . 01112103333333333. 0 12102333333333. 0 计算解：计算解： 。 0000000000. 07000000000. 012xx主元选择的重要

18、性主元选择的重要性要求用具有舍入的要求用具有舍入的1010位浮点数进行计算。位浮点数进行计算。绝对值很小绝对值很小计算解与真解相差太大计算解与真解相差太大, , 失败原因失败原因是用很小的数是用很小的数(1)11110.3 10a作除数，作除数，使得使得舍入误差舍入误差太大，从而计算结果不可靠。太大，从而计算结果不可靠。解法解法2 用行变换的高斯消去法用行变换的高斯消去法. .消元：消元： 7 . 01103 . 09 . 0111112rr)103 . 01103 . 0(111121 m 7 . 0109 . 011。 2000000000. 07000000000. 012xx计算解计算

19、解: : 7 . 0103 . 09 . 0211121xxxx 9 . 07 . 0103 . 0212111xxxx 该结果较好。该例子说明，在采用高斯消去法解方程组时，应该结果较好。该例子说明，在采用高斯消去法解方程组时，应 。对一般系数矩阵，最好保持乘数。对一般系数矩阵，最好保持乘数)(kkka元元素素避避免免采采用用绝绝对对值值很很小小主主| 1ikm，因此在高斯消去法中引进选主元素技巧。，因此在高斯消去法中引进选主元素技巧。 9 . 0117 . 01103 . 0),(11bA111 1 0.3 10 没有被舍去没有被舍去/ /被被“吃吃”1. 完全主元素消去法完全主元素消去法

20、选主元消元法：选主元消元法：。，0|max|1111 ijnjnijiaa11jxx 与与注注意意调调换换，设设bxA ，nnRA 为非奇异矩阵，为非奇异矩阵，第一步：第一步：。元元素素仍仍记记为为且且两两未未知知量量，并并作作记记录录，iijbabA,使使,11ji选选主主元元：)1(行行元元素素，行行与与第第第第交交换换时时即即当当交交换换行行列列111),(,1,)2(ibAi （3 3）消元计算：）消元计算：，), 3 , 2(1111niaamii ，), 3 , 2(1111niamaii ib列列元元素素。列列与与第第第第交交换换时时当当111),(,1jbAj 1 ia), 3

21、 , 2(11nibmbii 在在A中选取绝对值最大的元素作为主元素，即确定中选取绝对值最大的元素作为主元素，即确定 第第k 步：重复进行，设已完成第步：重复进行，设已完成第1 1步步第第k-1 的选主元，使的选主元，使 A， 增广阵。增广阵。b A， 约化为约化为:b nnnnkkknkknkkbaabaababaaabAbA222111211)()(,第第k步的步骤：步的步骤：。步步选选主主元元区区域域方方框框为为第第1,2, 1 nkk使使选选主主元元：即即确确定定,)1(kkji0max ijnjknikjiaakk，行行元元素素，行行与与第第第第交交换换时时即即当当交交换换行行列列k

22、kkkikbAki),(,)2()()( （3 3）消元计算：）消元计算：), 1(nkiaamkkikik ), 1,(nkjiamakjikij ib列列元元素素。列列与与第第第第交交换换时时当当kkkkjkbAkj),(,)()( ija), 1(nkibmbkiki 回代求解：回代求解：调调换换后后的的次次序序。则则是是未未知知数数其其中中nnxxxyyy,2121 ) 1 , 2 , 1(/ )(/1niayabyabyiinijjijiinnnn对于完全选主元素消去法：对于完全选主元素消去法：计算量大。计算量大。 nnnnnnbbbyyyaaaaaa212122211211经过上述

23、过程，方程组约化为：经过上述过程，方程组约化为：。该该方方法法数数值值稳稳定定)1( kim缺点：缺点：优点：优点：改进方法改进方法：。且此时且此时1 kim列主元消去列主元消去法，法，讨论：讨论：设已完成第设已完成第1步步第第k-1步计算，得到与原方程步计算，得到与原方程组组等价的方程组等价的方程组 ，其其中中)()(kkbxA )()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()(,nnknnknkkknknkkknnkkbaabaabaabaaabA方框内为第方框内为第k步选主元素区域。步选主元素区域。2 列主元素消去法列主元素消去法以下步骤类似完

24、全选主元素消去法。以下步骤类似完全选主元素消去法。例例2.3 用列主元素消去法解方程组用列主元素消去法解方程组 分析：分析：由精确解看出有两位有效数字，因此，用由精确解看出有两位有效数字，因此，用4 4位浮点数进位浮点数进 021313222226321321321xxxxxxxxx。精精确确解解：)0 . 5, 8 . 3, 6 . 2(321 xxx 012113333. 06667. 022226,bA)1667. 0,3333. 0(3121 mm 3334. 0333. 1667. 10667. 13333. 00001. 00222632rr 667. 13333. 00001.

25、003334. 0333. 1667. 102226解解 ：消元：消元： )00005999. 06667. 10001. 0(32 m 667. 13333. 0003334. 0333. 16667. 1022263334. 000005999. 0667. 1 舍去或着说被舍去或着说被“吃吃”行计算。行计算。 回代计算解：回代计算解： 602. 2801. 3003. 5123xxx高斯选主元消去法的步骤：高斯选主元消去法的步骤： 667. 13333. 0003334. 0333. 16667. 102226bA，注：注：该解若取两位有效数字，则与真解完全相同。该解若取两位有效数字，则

26、与真解完全相同。优点：优点：数值稳定。数值稳定。修正方法：修正方法：消元消元；回代回代。列主元高斯列主元高斯- -约当（约当（Gauss-Jordam）消去法）消去法, ,将将A A化成一个单位矩阵，不需回代。化成一个单位矩阵，不需回代。缺点：缺点：既消元；又回代。既消元；又回代。3 矩阵分解矩阵分解法法 一、一、 矩阵的三角分解矩阵的三角分解 列主元高斯消去法实质上是对方程组进行等价变形，即是对列主元高斯消去法实质上是对方程组进行等价变形，即是对定理定理3 3 系数矩阵施行系数矩阵施行行初等变换行初等变换，这些，这些初等变换初等变换又可以用矩阵表示。因此又可以用矩阵表示。因此矩阵的矩阵的三角

27、分解三角分解是列主元高斯消去法的另一种表示方法，或着说是列主元高斯消去法的另一种表示方法，或着说高斯消去法的变形，即是高斯消去法高斯消去法的变形，即是高斯消去法紧凑格式紧凑格式的矩阵表示（矩阵的的矩阵表示（矩阵的nnRA 设设，) 1, 2 , 1( 0 nkDk，如果，如果A顺序主子式顺序主子式其中，其中，L为单位下三角阵，为单位下三角阵，U为上三角矩阵。为上三角矩阵。说明：说明：则则A可可唯一唯一分解为两个三角矩阵相乘，即分解为两个三角矩阵相乘，即。LUA A为非奇异为非奇异阵阵, ,则则A可唯一分解为两个三角矩阵相乘可唯一分解为两个三角矩阵相乘, ,否则，分解不是唯一的。否则，分解不是唯

28、一的。三角分解），它在解方程组的直接法中起着重要的作用。三角分解），它在解方程组的直接法中起着重要的作用。 对矩阵对矩阵A A实行初等行变换相当于用初等矩阵左乘实行初等行变换相当于用初等矩阵左乘A A，于，于是对是对Ax=bAx=b做第一次消元后，做第一次消元后， 化为化为 化为化为 ，即，即 ，其中，其中(1)(2)(1)(2)11,L AALbb(1)(2)(1)(2),AAbb矩阵的三角分解矩阵的三角分解 LULU分解分解2113111000100010001nmLmm (1)(1)(1)(1)1111211(1)(1)(1)(1)2212222(1)(1)(1)(1)12nnnnnnn

29、nxaaabxaaabxaaab第第k k步的初等矩阵为步的初等矩阵为1,10000100010001kkknkLmm 1kkkL AA 1kkkL bb并且并且重复这一过程，最后得到重复这一过程，最后得到 11211121nnnnLL L AALL Lbb将上三角矩阵将上三角矩阵 记为记为U U，则，则 ，其中，其中 nA111121nAL LL ULU21111313212112,11111nnnn nmmmLL LLmmm则，则，L L为单位下三角矩阵。为单位下三角矩阵。 高斯消去法实质上是产生了一个将高斯消去法实质上是产生了一个将A A分解为两个三角形分解为两个三角形矩阵相乘的因式分解

30、。如果矩阵相乘的因式分解。如果A A是非奇异阵，则是非奇异阵，则LULU分解是唯一分解是唯一的，否则分解不唯一。的，否则分解不唯一。直接三角分解法解线性方程组（直接三角分解法解线性方程组（ ）的具体流程：）的具体流程：11(1,2, )iiuainAxb1111(1, )iilauin 1.2. 计算U的第r行，L的第r列元素 r=2,3,n11(,1, )rririrkkikual uir rn3.11(,1, ;)riririkkrrrklal uuir rn rn( (一一)LU)LU分解分解，先先求求、LUA 11111;(2,3, );iiiikkkybybl yin1;(1,2,1

31、);nnnnniiikkiik ixyuxyu xuinn ( (二二)x)x的计算的计算。再再求求解解、 yxUbyL2例例 用直接三角分解法解方程组用直接三角分解法解方程组 1231471258136111xxx 1111121213131,4,7uauaua111111212111313111/1/1 121 231 3laula ula u，解解:(:(一一) )矩阵矩阵LULU分解分解111111;(1, );(1,2, )iiiiuainlauin(1)(1)故：故：222221 12232321 13222221 1222323231 1222333331 1332 233333

32、31 1332 235 2 438 2 76()/(5 2*4)/( 3) 1()/2() 11 3*7 2*( 6) 2()/2 1ual uual ulal uulal uuual ul ulal ul u 1111(,1, )(,1, ;)rririrkkikriririkkrrrkual uir rnlal uuir rn rn(2)(2)经计算：经计算：1471147258213636113212ALU (3)(1, 1,0)TLyby求解，得，(4)( 1/3,1/3,0)TUxyx 求解，得方程组的解。( (二二) )求解求解x x：从而从而1111;(2,3, );iiiikk

33、kybybl yin1;(1,2,1);nnnnniiikkiik ixyuxyu xuinn 311173121A例例 设设 ，试将，试将A进行三角分解。进行三角分解。解解： 由高斯消去法得到由高斯消去法得到 11131211mmL 111322mL， 11131 11111113133121 mm，11132 m，则有则有 20041012112UALLULLAA1211 可可以以写写成成ULLA112)( 也也可可以以写写成成U 111111131U 111131。UU 1111311141311LU（1 1）方法比较）方法比较，先先求求、LUA 1消元法：消元法：。即即解解后后回回代代

34、、bLxU1,2 消元法的公式只有一组，便于计算机计算。消元法的公式只有一组，便于计算机计算。需需要要乘乘除除法法的的次次数数其其中中直直接接三三角角分分解解法法解解)(nnRAbxA 消元法与三角分解法间的关系：消元法与三角分解法间的关系： 。阶阶顺顺序序主主子子式式不不等等于于零零至至的的，设设对对nAbxA1 三角分解法三角分解法：。再再求求解解、 yxUbyL2，即即先先消消元元、),(),(),(),(1111bLUbALbLUbA （2 2）计算次数）计算次数次次乘乘除除法法。同同高高斯斯消消去去法法，大大约约33n注：注： ，只只需需求求解解分分解解，对对不不同同的的的的完完成成

35、), 2 , 1(mjbxAjLUAj 问问题题，因因为为一一旦旦三三角角分分解解法法适适合合解解), 2 , 1(mjbxAj 。即即求求解解 jjjjyxUbyL)(2次次乘乘除除法法n讨讨论论高斯高斯-约当约当法除外法除外次次乘乘法法222)1(211nnnnknk 次次乘乘除除法法222)1(21nnnnknk CholeskyCholesky分解分解：，有有且且0),(, 0)2( xxAxRxn对称正定矩阵对称正定矩阵的一种三角分解方法。的一种三角分解方法。对称正定阵的定义及性质：对称正定阵的定义及性质：定义定义)(对对称称正正定定阵阵满满足足：如如果果设设ARAnn, 为为对对称

36、称正正定定阵阵。则则称称 A；AAT ) 1 (A为对称为对称正定阵正定阵(4)(4)A的特征值的特征值 。), 2 , 1( 0)(niAi (1 1)A是非奇异矩阵，且是非奇异矩阵，且A-1亦是对称正定阵；亦是对称正定阵；(2 2)A的顺序主子阵的顺序主子阵Ak 是对称正定阵是对称正定阵(k=1,2,n)；), 2 , 1( 0)det(nkAk (3 3)A的顺序主子的顺序主子式都大于零，即式都大于零，即 对称正定阵的判别方法对称正定阵的判别方法( (充分条件充分条件) )正正定定阵阵为为对对称称AA为对称矩阵为对称矩阵0)( AAi 的的特特征征值值A为对称矩阵为对称矩阵，), 2 ,

37、 1( 0)det(nkAk 二、二、 矩阵矩阵CholeskyCholesky分解分解定理定理4为为对对称称正正定定若若nnRA （对称正定矩阵的（对称正定矩阵的Cholesky分解）分解）。TLLA 阵，则存在唯一的具有正对角元的下三角阵阵，则存在唯一的具有正对角元的下三角阵L ，使得，使得平方根法解线性方程组：平方根法解线性方程组：( (与直接三角分解法类似与直接三角分解法类似) )思路思路：；为为分分解解对对称称正正定定阵阵TLLAA )1( .xyxLybyLT，求求，求求bxLLbxAT 求求解解求求解解)2(求求解解方方程程组组 nnnnnnaaaaaaaaaA212222111

38、211令令jjijjkjkiknkjkikijlllllla 111则则。的的元元素素ijlL设设n阶对称正定矩阵阶对称正定矩阵A有分解有分解 ,先用先用待定系数法待定系数法求求L的元的元TLLA nnnnnnnnllllllllllll2221211121222111，时时，当当)0( jkljk步步可可直直接接求求得得经经n该分解称为乔勒斯基（该分解称为乔勒斯基（CholeskyCholesky）分解。）分解。 ijl素素 。求解对称正定方程组求解对称正定方程组Ax=b的的平方根法平方根法( (计算公式计算公式) ) ：分解计算：分解计算： ：TLLA ), 2 , 1(ni 2/1112

39、)()2( ikikiiiilal,)()1(11jjjkjkikijijlllal )(1, 2 , 1(ijij ，), 2 , 1()() 3(11nilylbyiiikkikii 。) 1 , 2 , 1,()() 4(1 nnilxlyxiinikkkiii xyxLybyLT求求，求求，jjijjkjkiknkjkikijlllllla 111), 2 , 1(ni 优点：优点： 1 1、数值稳定。、数值稳定。 2 2、计算量小，大约为、计算量小，大约为 次乘除法，是一般矩阵次乘除法，是一般矩阵A的的LU分解计算量的一半。分解计算量的一半。63n 缺点：缺点：计算计算lii时要开平

40、方。时要开平方。求解：求解： 通过改进方法避免通过改进方法避免(0)jkjkl当时，yxyx 4 向量范数与矩阵范数向量范数与矩阵范数 向量、向量、矩阵与线性方程组有着密切的关系，矩阵与线性方程组有着密切的关系，向量、矩阵范数向量、矩阵范数是是解方程组以及研究与探讨解方程组以及研究与探讨方程组方程组本身性质的工具。本身性质的工具。定义定义（向量范数）：（向量范数）： 的的某某个个实实值值非非负负或或对对于于向向量量nnCxRx （1）正定性）正定性 ；或或记记为为 00,0 xxx（2）齐次性）齐次性 ；或或，其其中中)(CRxx （3）三角不等式）三角不等式 。或或nnCRyxyxyx ,

41、。或或模模一一个个向向量量范范数数或或上上是是称称nnCRxxN|)( 一、向量范数的定义一、向量范数的定义 ，若若满满足足：函函数数xxN 常用的向量范数常用的向量范数：)(),(1nnTnCxRxxx 或或设设；inixxxN 1max|)(； niixxxN111|)(（1）向量的）向量的“”范数：范数：（2）向量的）向量的“1”范数：范数：；2/1122/122)(),()( niixxxxxN,nRx 称为向量的称为向量的能量范数能量范数。（3）向量的）向量的“2”范数：范数：（4）向量的能量范数：）向量的能量范数：为为对对称称正正定定阵阵，设设nnRA 211,2/1)(),()(

42、 njijiijAAxxaxxAxxN二、向量序列的极限二、向量序列的极限设有向量序列设有向量序列 )(kx，Tnxxx),(1 若若n个数列收敛，即个数列收敛，即，收收敛敛于于则则称称*)(xxk，记记为为 xxkk)(lim对对应应分分量量。分分量量收收敛敛到到即即是是*)(xxk设有向量序列设有向量序列，), 2 , 1(102102)(nkxkkk 则有则有 。 22lim)(kkx定义定义1. 定义定义例例4.1，及及向向量量 x), 1(lim)(nixxikik 或说向量序列或说向量序列 的收敛的收敛)(kx，设设nRyx ,称非负实数称非负实数 之间之间yx,为为|),(yxy

43、xd 2. 距离距离为向量的任何一种意义下为向量的任何一种意义下范数范数。| 距离，距离，其中其中且记且记 ，Tknkkxxx),()()(1 定理定理5)(kx设设为为Rn中一向量序列，且中一向量序列，且 ，则则nRx v| 其其中中为向量的任一种范数。为向量的任一种范数。 证明：证明：), 1(limlim)()(nixxxxikikkk )( 0max)(1 kxxikini当当。当当)(0)( kxxk ,0lim)()( kxxxxvkkk当当时时，当当 v), 1(0lim)(nixxikik 由范数的等价性有：由范数的等价性有： ,0lim2)()( kxxxxkkk当当 。当当

44、 kxxxxkkk0lim1)()(对对v =1也可采用以下证法也可采用以下证法), 1( 0limlim)()(nixxxxikikkk 0)( ikixx01)( niikixx。当当)(01)( kxxk注：注：), 1(ni 定义定义 （矩阵范数）（矩阵范数）nnRA 矩矩阵阵的某个非负实值函数的某个非负实值函数，AAN )(若对任意的若对任意的nn矩阵矩阵A，B满足下述条件：满足下述条件：，0 A；且且00 AA；RAA ,。BABA 。模模上上的的一一个个矩矩阵阵范范数数是是则则称称)()(nnRAN 由于在许多应用问题中，矩阵和向量是由于在许多应用问题中，矩阵和向量是相联系的，现

45、引进一种相联系的，现引进一种和向量范数是相容的，即对和向量范数是相容的，即对 ，nnnRARx ,有不等式有不等式xAxA （1） 正定性正定性 ： （2） 齐次性齐次性 ： （3） 三角不等式三角不等式 ： 1. 矩阵范数的一般定义矩阵范数的一般定义(类似于向量范数类似于向量范数)矩阵的矩阵的算子范数算子范数。它是由向量范数。它是由向量范数诱导诱导出来的，并且这种矩阵范数出来的，并且这种矩阵范数矩阵范数与向量范数的相容性条件矩阵范数与向量范数的相容性条件三、矩阵的范数三、矩阵的范数 2. 矩阵的算子范数矩阵的算子范数 ，设设nnnRARx ,且有一且有一向量范数向量范数相应的定义一个矩阵的非

46、负函数：相应的定义一个矩阵的非负函数：vvRxxvxxAAANn 0max)(（最大比值）（最大比值） 为矩阵为矩阵A的关于向量范数的关于向量范数定理定理6 向量范数，则向量范数，则 上上是是nnvRAAN )(一个一个矩阵范数矩阵范数且满足且满足相容条件相容条件： ；vvvxAxA )1(。),()2(nnvvvRBABAAB 的的算子范数算子范数或或诱导范数诱导范数。vx)(AN称称上上的的为为设设nvRx定义定义 ( 矩阵的算子范数矩阵的算子范数)v| （i）因为）因为 ，0 x。0, 0 vvxxA, 0 vvxxA所所以以00, 0 xAAx且且证明：证明： 上上是是先先证证nnRA

47、AN 一个矩阵范数一个矩阵范数( 满足三个条件满足三个条件)， 。00 vAA 0 x0 A，0max0 vvRxxvxxAAn0 vxA0 vA（ii） vvxvxxAA 0max RAxxAvvvx ,max0,nnRBA vvxvxxBABA|max0 。vvvvvxBAxxBxA 0max（iii） 以下证明满足相容性：以下证明满足相容性：，因因为为vvxvxxAA0max ，所所以以vvvAxxA （1）vvvAxAx即。（2） vvxBAxAB)()( vvvvBAxxAB )(所所以以成成立立，0 xvvvvvxBAxBA 由由x的任意性知的任意性知 。vvvvxvBAxxABA

48、B )(max0诱导范数的诱导范数的矩阵相容性矩阵相容性诱导范数与其相应诱导范数与其相应的向量范数相容的向量范数相容，则则设设nnnRARx ,； njijnixaxxAA110maxmax)1(； niijnjxaxxAA111101maxmax)2(。)(max)3(max2202AAxxAATx 的的最最大大特特征征值值。为为其其中中AAAATT)(max A的行范数的行范数的列范数的列范数的的“2”范数范数或或的谱范数的谱范数3. 矩阵范数公式矩阵范数公式4. 矩阵范数的等价性矩阵范数的等价性，则则设设nnRA ， |1) 1 (2AnAAn。 |1) 2(1AnAAnnnRA 设设的

49、特征值为的特征值为|max)(1iniA 称称为为A的谱半径。的谱半径。，设设nnRA )1(，则则|)(AA | A其其中中向量相容性条件的矩阵范数（算子范数）。向量相容性条件的矩阵范数（算子范数）。nnRA 设设)2(为对称矩阵，则为对称矩阵，则。)(|2AA 四、谱半径四、谱半径1. 1. 矩阵谱半径定义：矩阵谱半径定义： nii3 , 2 , 1 2. 特征值界：特征值界：证明：证明：（1），0 x，使使xxA ，|xA ，即即|A 。所所以以|)(AA 设设 为为A的任一特征值，于是，存在的任一特征值，于是，存在 |xAxx 且且为满足矩阵、为满足矩阵、注注：1）由于矩阵的）由于矩阵

50、的2范数与谱半径有关，常称范数与谱半径有关，常称“2”范数为谱模。范数为谱模。若若 为为A的特征值，的特征值， (2)ATA=A2,且且ATA也是也是对称的，对称的，设设|)(0 A最最大大特特征征根根，必必是是220A 222maxmax00|()()|( )TAA AAA。2）谱模（范数）是对称矩阵）谱模（范数）是对称矩阵A特征值的上界。特征值的上界。则则 为为A2 的特征根，的特征根，2 又又A为对称矩阵，则为对称矩阵，则5 迭代法求解迭代法求解迭代法迭代法是一种不断套用一个迭代公式，逐步逼近方程组的是一种不断套用一个迭代公式，逐步逼近方程组的精确精确解（真解）的方法。解（真解）的方法。

51、适合解大型稀疏线性方程组适合解大型稀疏线性方程组。直接法：解低阶稠密线性方程组直接法：解低阶稠密线性方程组迭代法优点：迭代法优点：计算量小，近似解精度高计算量小，近似解精度高。占用内存单元较少占用内存单元较少。设计程序简单（适合计算机计算）。设计程序简单（适合计算机计算）。定义定义（1 1）用逐步代入）用逐步代入(0)(1)(0)(1)( ),(1,2,)kkxxB xfxBxfk+=+=+=L任取初始向量求近似解的方法，称为求近似解的方法，称为迭代法迭代法（或称为（或称为一阶定常迭代法一阶定常迭代法）。）。 迭代法的定义：迭代法的定义：B是迭代矩阵是迭代矩阵nnRA 设设为非奇异阵，为非奇异

52、阵， 方程组方程组 的精确解为的精确解为 即即。bAx *，*xbAx 是是 的的k步近似步近似*x)(kx)(kx（构造向量序列（构造向量序列 ） （2 2）如果对任意初始近似）如果对任意初始近似 ，都有，都有 称迭代法称迭代法)0(x，*)(limxxkk 迭代法研究的问题：迭代法研究的问题： （1 1）构造各种解构造各种解 的的有效迭代法有效迭代法(有效：有效： 收敛收敛)。bAx )(kx为为收敛收敛，否则称迭代法为，否则称迭代法为发散发散。（2 2）研究迭代法的研究迭代法的收敛性收敛性及及收敛速度收敛速度。 一、基本迭代法构造一、基本迭代法构造 基本思想：基本思想： ，令令0, ii

53、nnijaaA将将A分离（裂）为三部分，即分离（裂）为三部分，即用迭代法解线性方程组用迭代法解线性方程组 。bAx 0001,121,2211nnnnnaaaaaaA 000, 1112nnnaaaULD 常用的是将常用的是将A分裂为分裂为 NMA 问题问题：其中其中 为可选择的非奇异阵使为可选择的非奇异阵使 容易求解容易求解, ,一般一般 选为选为 的某的某dMx AMM种种近似近似, ,于是于是bNxMxbAx 。或或bMNxMx11 若记若记)(11AMMNMB ，则则并并取取初初始始向向量量)0( x(0)(1)( )11(0,1,)kkx xBxfkBIM AfM b+-=+=-=

54、L（可任意取）注：注： 的选法不同，得的选法不同，得到各种不同的迭代法。到各种不同的迭代法。M，bM f1 A MI,1 二、二、Jacobi迭代法迭代法1.1.理论分析：理论分析： 若取若取 ( (对角阵对角阵) )，则有，则有 , ,DM NDA 于是于是 ADIB1 ，J ULDADD 11称为称为JacobiJacobi迭迭代法的迭代阵代法的迭代阵Jacobi迭代法迭代法： bDfJULDBkfBxxxkk11)() 1() 0()(), 1 , 0(bDbMf11 于是，有于是，有 ，即，即bxULDxkk )()1()( ni , 2 , 1 ,1111)()()1( nijjkj

55、ijiijnijkjijkjijikiiixabxaxabxa若若 则得到则得到JacobiJacobi迭代计算公式迭代计算公式 0 iia2.2.求解求解 的的Jacobi迭代法计算公式：迭代法计算公式： Axb= xabaxxx xnijjkjijiiikiTn)(1),(1)() 1()0()0(1)0( ni, 2 , 1 表表示示迭迭代代次次数数。, 1 , 0 k注：注：(1)(1)Jacobi迭代法迭代法, ,每迭代一次主要是计算一次矩阵乘向量每迭代一次主要是计算一次矩阵乘向量 。)(kBx(2)(2)计算过程中，原始数据计算过程中，原始数据A始终不变。始终不变。(3)(3)计算

56、中需要两组工作单元计算中需要两组工作单元 用来保存用来保存 及及 。 )(),(nynx)(kx)1( kx解向量初值解向量初值说明说明：(1)(1)Jacobi迭代法实际上是由近似解迭代法实际上是由近似解Tknkikkxxxx),()()()(1)( Tknkikkxxxx),() 1() 1() 1(1) 1( 的的n-1-1分量分量)()(1)(1)(1,knkikikxxxx 计算计算的第的第i（i=1,2,n）个分量。个分量。更更接接近近于于比比，则则收收敛敛于于若若*)()1(*)()2(xxxxxkkk 更更比比则则)()1(kikixx 。接接近近于于*ix三、三、 高斯高斯-

57、塞德尔迭代法（塞德尔迭代法（G-S） 取分裂阵取分裂阵 ( (下三角阵下三角阵),),则有则有LDM NLDA ，于是，于是ALDIB1)( bLDfGULDBfBxxxkk11)()1()0()()(其中其中G 称为称为G- -S迭代法的迭代阵迭代法的迭代阵于是，有于是，有 或或bUxxLDkk )()1()(bUxLxDxkkk )()1()1(当当 时得到以下时得到以下解解 的的G-SG-S迭代法计算公式迭代法计算公式: : 0 iiabAx 其中其中k =1,2,=1,2,表表示迭代次数示迭代次数), 2 , 1(ni )(1),(1)(11)1()1()0()0(1)0(nijkji

58、jijkjijiiikiTnxaxabaxxxxGULDALDLD 11)()()(G-S迭代法可看作迭代法可看作JacobiJacobi迭代法的一种修正或改进。迭代法的一种修正或改进。 (1) (1)由由(2.8)(2.8)可知可知, ,计算计算 第第i个分量时个分量时, ,利用已经计算出的最利用已经计算出的最新新)1( kx优点：优点：(2)(2)G-S迭代法每迭代一次主要计算一次矩阵乘向量。迭代法每迭代一次主要计算一次矩阵乘向量。计算量小计算量小(3)(3)当当J-J-迭代与迭代与G-SG-S迭代都收敛时，迭代都收敛时，G-S迭代的收敛速度快迭代的收敛速度快。用用G-S迭代法解只需要一组

59、工作单元，用来保存迭代法解只需要一组工作单元，用来保存 或或 分量。分量。)1( kx)(kx分量分量 ，因此，计算，因此，计算 就可冲掉就可冲掉 , ,于是利于是利)1, 2 , 1()1( ijxkj)1( kix)( kixG-S迭代存贮少。迭代存贮少。 351110288321321321xxxbAxxxxxxx或或Tx)1 , 1 , 1( 精确解精确解例例5.1 用用Jacobi迭代法，迭代法，G-S迭代法解下述方程组迭代法解下述方程组（1）Jacobi迭代公式：迭代公式： 5/ )3(10/ )211(8/ )8()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkk

60、kkkkkkxxxxxxxxx其中，其中， ，计算结果见表，计算结果见表1。 ), 1 , 0( ,),()(3)(2)(1)( kxxxxTkkkk表表1 ( )(0)(1)(2)(3)(4)(5)( )1( )2( )301.01.06250.99250.998125 1.000693801.10.960.98951.001951.00001500.61.021.00450.99641.000015kkkkxxxxxxxxxx且有且有 0007. 0)5( xx 5/ )3(10/ )211(8/ )8()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkx