数值分析第5章1-3节课件.ppt

1、第第5 5章章 解线性方程组的直接方法解线性方程组的直接方法15.1 引言与预备知识引言与预备知识 5.1.1 引言引言 线性方程组的数值解法一般有两类：1.直接法 经过有限步算术运算，可求得方程组精确解的方法(若计算过程中没有舍入误差).但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解.2 2.迭代法 是用某种极限过程去逐步逼近线性方程组精确解的方法.3 5.1.2 向量和矩阵向量和矩阵 用 表示全部 实矩阵的向量空间，表示全部 复矩阵的向量空间.nmRnm nmCnm mnmmnnijnmaaaaaaaaaa212222111211)(RAA这种实数排成的矩形表，

2、称为 行 列矩阵.mnnnxxx21Rxx称为 维列向量.n4,n21aaaA其中 为 的第 列.iaAi,TmT2T1bbb其中 为 的第 行.TibAi 也可写成行向量的形式 写成列向量的形式5 (5)单位矩阵 矩阵的基本运算：(1)矩阵加法,BAC (2)矩阵与标量的乘法.ijijacA,C (3)矩阵与矩阵乘法).R,R,R(1pmpnnmnkkjikijbacCBA,ABC)R(nmijijijbacCB,A,(4)转置矩阵.,RTijijnmacACA,R21nnneeeI6 (6)非奇异矩阵 设.R,RnnnnBA 如果 存在，1A则称 为非奇异矩阵.A 如果 均为非奇异矩阵，n

3、n RBA,其中.,2,1,0,0,1,0,0Tnkke,IBAAB如果则称 是BA的逆矩阵，,1A记为.)()(1TT1AA且.)(111ABAB则 (7)矩阵的行列式 设,RnnA则 的行列式可按任一行(或列)展开，A7),2,1()(det1nianjijijAA其中 为 的代数余子式，ijAija,)1(ijijMAji 行列式性质：.R,),()det(det)(det a)(nnBABAAB即.R),(det)(det (b)TnnAAA.RR,),(det)(det (c)nnncccAAA.0)(det (d)是非奇异矩阵AAija 的余子式.为元素ijM8 5.1.3 特殊矩

4、阵特殊矩阵 设.R)(nnijaA (1)对角矩阵 (2)三对角矩阵.01ijaji，如果当 (3)上三角矩阵.0ijaji，时如果当 (4)上海森伯格（Hessenberg）阵.01ijaji，时如果当 (5)对称矩阵.TAA如果.0ijaji，时如果当9 (6)埃尔米特矩阵.,CAAAH如果设nn (7)对称正定矩阵 ,(a)AAT如果.0)(,R (b)AxxxAx,xTn对任意非零向量 (8)正交矩阵.T1AA如果 (9)酉矩阵.,CH1AAA如果设nn (10)初等置换阵 由单位矩阵 交换第 行与第 行(或交换第 列与第 列)，得到的矩阵记为 ,且 IijijijI10 (11)置换

5、阵 定理定理1 1设 ，nn RA(1)对任何 方程组 有惟一解.,RnbbAxAAIij（为交换 第 行与第 行得到的矩阵）；Aij（为交换 第 列与第 列得到的矩阵）；iAjBAIij由初等置换阵的乘积得到的矩阵.则下述命题等价：(2)齐次方程组 只有惟一解 .0Ax0 x(4)存在.1A(5)的秩A.)(ranknA.0)det(A(3)11 定理定理2 2设 为对称正定阵，则 nn RA (1)为非奇异矩阵，且 亦是对称正定阵.A1A (2)记 为 的顺序主子阵，则 kAA).,2,1(1111nkaaaakkkkkA),2,1(nkkA亦是对称正定矩阵，其中 (3)的特征值 A).,

6、2,1(0nii (4)的顺序主子式都大于零，即 A).,2,1(0)det(nkkA12 定理定理3 3设 为对称矩阵.nn RA),2,1(nk或 的特征值A),2,1(0nii 定理定理4 4(Jordan标准型)设 为 阶矩阵，则存在一个An非奇异矩阵 使得 P,)()()(22111rrJJJAPP0)(detkA如果则 为A对称正定阵.13其中.),2,1(111)(1nnrinriiinniiiiiii且iJ为若当（Jordan）块.(1)当 的若当标准型中所有若当块 均为一阶时，AiJ此标准型变成对角矩阵.14 (2)如果 的特征值各不相同，则其若当标准型必为A).,(diag

7、21n对角阵155.2 高斯消去法高斯消去法16 5.2.1 高斯消去法高斯消去法 设有线性方程组，mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111,（2.1）或写为矩阵形式,2121212222111211mnmnmmnnbbbxxxaaaaaaaaa17简记为.bAx 例例1 1)4.2(.122)3.2(,54)2.2(,632132321xxxxxxxx 解解消去(2.4)中的未知数 得到,1x将方程(2.2)乘上 加到方程(2.4)上去，2)5.2(.11432xx 第2步.用消去法解方程组 第1步.将方程(2.3)加到方程(2.

8、5)上去，消去方程(2.5)中的未知数,2x18得到与原方程组等价的三角形方程组.62)6.2(,54,6332321xxxxxx显然，方程组(2.6)是容易求解的，解为.)3,2,1(Tx 上述过程相当于 112251406111bA111405140611119620051401111331)2(rrr332rrr其中用 表示矩阵的第 行.iri 由此看出，用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组 化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法.bAx 上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的问

9、题转化为求解简单方程组的问题.20 或者说，对系数矩阵 施行一些左变换(用一些简单矩阵)将其约化为上三角矩阵.A 下面讨论求解一般线性方程组的高斯消去法.将(2.1)记为,)1()1(bxA.),()()1()1()1(bbAijijaa (1)第1步 ).1(k 设 首先计算乘数,0)1(11a.),3,2(/)1(11)1(11miaamii.,22112222212111212111mnmnmmnnnnbxaxaxabxaxaxabxaxaxa（2.1）其中用 乘(2.1)的第一个方程，加到第 个方程上，1imi,3,2i 消去(2.1)的从第2个方程到第 个方程中的未知数m，m,21)

10、.,2(mi得到与(2.1)等价的方程组,ix（2.7）.00)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11mnmnmnnbbbxxxaaaaaaa简记为,)2()2(bxA其中 的元素计算公式为)2()2(,bA)1(11)1()2(jiijijamaa),2;,2(njmi)1(11)1()2(bmbbiii22 (2)第 次消元 k).,1min(,2,1(nmsk 设上述第1步，第 步消元过程计算已经完成，1k（2.8）,)()()2(2)1(121)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnkknkkmnk

11、mkkknkkknknkbbbbxxxxaaaaaaaaaaa即已计算好与(2.1)等价的方程组简记为.)()(kkbxA23)()()(kkjikkijkijamaa1),1;,1(nkjmki).,(mki1 设 计算乘数,0)(kkka.),1(/)()(mkiaamkkkkikik加到第 个方程i),1(mki用 乘(2.8)的第 个方程，ikmk消去从第 个方程到第 个方程中的未知数 得到与m,kx1k 元素的计算公式为)1()1(,kkbA 显然 中从第1行到第 行与 相同.)1(kAk)(kA.)1()1(kkbxA(2.1)等价的方程组)()()1(kkikkikibmbb(2

12、.9)24 (3)继续上述过程，且设),2,1(0)(skakkk直到完成第 步消元计算.s 最后得到与原方程组等价的简单方程组 ,)1()1(ssbxA其中 为上梯形.)1(sA 特别当 时，与原方程组等价的方程组为 nm,)()(nnbxA即（2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa25 如果 是非奇异矩阵，且nn RA),1,2,1(0)(nkakkk由(2.1)约化为(2.10)的过程称为消元过程消元过程.求解三角形方程组(2.10)，得到求解公式,/)()(nnnnnabx).1,2,1(nnk（2

13、.11）(2.10)的求解过程(2.11)称为回代回代.)(1)()(/)(kkknkjjkkjkkkaxabx 如果 由于 为非奇异矩阵，所以 的第一列一定有元素不等于零.,011aAA26 例如 于是交换两行元素(即 ），将 调到(1,1)位置，然后进行消元计算，这时 右下角矩阵为 阶非奇异矩阵.,011ia11irr 11ia)2(A1n 继续这过程，高斯消去法照样可进行计算.27 定理定理5 5设 其中,bAx.RnnA (1)如果),2,1(0)(nkakkk将 约化为等价的三角形方程组等价的三角形方程组(2.10).bAx则可通过高斯消去法 (a)消元计算 )1,2,1(nk),1

14、(/)()(nkiaamkkkkikik),1,()()()1(nkjiamaakkjikkijkij).,1()()()1(nkibmbbkkikkiki（2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa且计算公式如下：28 (b)回代计算,/)()(nnnnnabx).1,2,1(/)()(1)()(nniaxabxiiinijjiijiii (2)如果 为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组 约化为(2.10).AbAx（2.10）.)()2(2)1(121)()2(2)2(22)1(

15、1)1(12)1(11nnnnnnnnbbbxxxaaaaaa29 算法算法1 1(高斯算法)对于sk,2,1 (1)如果 则计算停止,0kka (2)对于 mki,1 (a)kkikikikaama/(b)对于 nkj,1.*kjikijijamaa 本算法用高斯方法将 约化为上梯形，且覆盖 ，乘数 覆盖 .),2,1(skAA)(kAikmika),1min(),1(RnmsmnmA设如果0)(kkka30 当 时，总共大约需要 次乘法运算.nm 3/3n 数 称为约化的主元素主元素.)(kkka 算法算法2 2(回代算法)上三角阵，设 其中 为非奇异,bUxnn RU本算法计算 的解.b

16、Ux 对于1,ni (1)iibx 算法1第 步需要作 次除法，次乘法，因此，本算法(从第1步到第 步消元计算总的计算量)大约需要 次乘法(对相当大的 ).kkm)(knkmsmnssnms2/)(3/23s31 (2)对于 nij,1 jijiixuxx*(3)iiiiuxx/这个算法需要 乘除法运算.2/)1(nn 高斯消去法对于某些简单的矩阵可能会失败，.0110A由此，需要对算法1进行修改，例如).,2,1(0)(kakkk在什么条件下才能保证 A首先需要研究原来的矩阵32 定理定理6 6 约化的主元素 的充要条件),2,1(0)(kiaiii是矩阵 的顺序主子式A).,2,1(0ki

17、Di,0111 aD即（2.12）).,2,1(01111kiaaaaDiiiii 证明证明 显然，当 时，定理6成立.1k 现设定理6充分性对 是成立的，求证定理6充分性对 亦成立.1kk首先利用归纳法证明定理6的充分性.33 设),2,1(0kiDi),1,2,1(ki可用高斯消去法将 约化到 ，)1(A)(kA,)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()1(knnknkkknkkknknkkaaaaaaaaaaaAA且有 0)(iiia于是由归纳法假设有即,0)2(22)1(11)2(22)1(12)1(112aaaaaD34.)()2(22)1

18、(11)()1(1)1(11kkkkkkkkaaaaaaD（2.13）由设),2,1(0kiDi定理6充分性对 亦成立.k 显然，由假设),2,1(0)(kiaiii利用(2.13)式，,0)(kkka则有利用(2.13)式亦可).,2,1(0kiDi推出 35 推论推论,)1(111Da如果 的顺序主子式A),1,2,1(0nkkD则).,3,2(/)(nkakkk1kkDD36于是对(2.1)施行第一次消元后化为(2.7)，5.2.2 矩阵的三角分解矩阵的三角分解 下面借助矩阵理论进一步对消去法作些分析，从而建立高斯消去法与矩阵因式分解的关系.设(2.1)的系数矩阵 的各顺序主子式均不为零

19、.nn RA由于对 施行行的初等变换相当于用初等矩阵左乘 ，AA这时 化为)1(A,)2(A化为)1(b，)2(b,)2()1(1)2()1(1bbLAAL即 37其中.1111131211nmmmL 一般第 步消元，k化为 ,)(kA)1(kA化为 ，)(kb)1(kb,)1()()1()(kkkkkkbbLAAL相当于 其中 38.1111,1knkkkmmL重复这过程，最后得到;)()1(121nnAALLL（2.14）.)()1(121nnbbLLL 记上三角矩阵 为 ，由(2.14)得到)(nAU39,111211LUULLLAn其中 111211nLLLL为单位下三角矩阵.这就是说

20、，高斯消去法实质上产生了一个将 分解为两个三角矩阵相乘的因式分解，于是得到如下重要定理，它在解方程组的直接法中起着重要作用.A1111321323121nnnmmmmmm40 定理定理7 7设 为 阶矩阵，An 证明证明现在在 为非奇异矩阵的假定下证明惟一性，A 设,11ULLUA其中 为单位下三角矩阵，为上三角矩阵.1,LL1,UU(矩阵的LU分解)如果 的A顺序主子式),1,2,1(0niiD则 可分解为一个单位A下三角矩阵 和一个上三角矩阵 的乘积，LU且这种分解是惟一的.根据以上高斯消去法的矩阵分析，存在性已得证，41.1111 UULL上式右边为上三角矩阵，左边为单位下三角矩阵，从而

21、上式两边都必须等于单位矩阵，例例2 2,122140111A由高斯消去法，,1,2,0323121mmm 由于 存在，故 11U,11UULL故 惟一性得证.对于例1，系数矩阵 故 42200140111112010001A.LU43 例例3 35.3 高斯主元素消去法高斯主元素消去法 由高斯消去法知道，在消元过程中可能出现 ，0)(kkka 即使主元素 但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠.,0)(kkka.000.3000.2000.1643.5072.1000.2623.4712.3000.1000.3000.2001.0321xx

22、x这时消去法将无法进行；求解方程组 44用4位浮点数进行计算.,)0.3675 0.05104,0.4904,(*Tx 解法解法1 1000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0bA用高斯消去法 2000001.0/000.21000001.0/000.13121mm20036006400101002300520040000.1000.3000.2001.0997.12004/400123m精确解舍入到4位有效数字为 45计算解为.)0.4000 0.09980,0.400,(Tx,000.2000.500100230

23、0520040000.1000.3000.2001.0显然计算解是一个很坏的结果，不能作为方程组的近似解.其原因是我们在消元计算时用了小主元 0.001，使得约化后的方程组元素数量级大大增长，经再舍入使得在计算(3,3)元素时发生了严重的相消情况，因此经消元后得到的三角形方程组就不准确了.46 解法解法2 2000.1000.3000.2001.0000.2623.4712.3000.1000.3643.5072.1000.231rrbA 交换行，避免绝对值小的主元作除数.0005.05000.03121mm 002.1003.3001.205000.0801.1176.30000.3643.

24、5072.1000.26300.032m,6870.0868.1005000.0801.1176.30000.3643.5072.1000.2 47得计算解为.*)0.3678 0.05113,0.4900,(Txx 这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能产生麻烦，故应避免采用绝对值小的主元素.)(kkka 对一般矩阵来说，最好每一步选取系数矩阵(或消元后的低阶矩阵)中绝对值最大的元素作为主元素，以使高斯消去法具有较好的数值稳定性.这就是全主元素消去法全主元素消去法.在选主元时要花费较多机器时间，目前主要使用的是列主元消去法列主元消去法.48 本节主要介绍列主元消去法，并假定

25、(2.1)的 为非奇异的.nn RA49 5.3.1 列主元素消去法列主元素消去法 设方程组(2.1)的增广矩阵为.21212221111211nnnnnnnbaaabaaabaaaB 首先在 的第一列中选取绝对值最大的元素作为主元素，A,0max1,11,1iniiaa例如 50重复上述过程，,)(222211111211)()(nnnnkkknkknknkkkbaabaabaaabaaaabA).()()2()2(bAbA然后交换 的第1行与第 行，经第1次消元计算得 B1i)(bA约化为设已完成第 步的选主元素，交换两行1k及消元计算，51其中 的元素仍记为 ,的元素仍记为 .)(kAi

26、ja)(kbib 第 步选主元素(在 右下角方阵的第1列内选)，k)(kA即确定 ，使 ki.0max,iknikkiaak交换 第 行与 行的元素，再进行消元计算，)()()(kkbAkki最后将原方程组化为.212122211211nnnnnnbbbxxxaaaaaa52回代求解,/nnnabx).1,2,1(/)(1nniaxabxiinijjijii 算法算法3 3(列主元素消去法)设 .本算法用具有行交换的列主元素消去法，bAx 消元结果冲掉 ，乘数 冲掉 ，计算解 冲掉常数项Aijmijax,b行列式存放在 中.det1.1det 53 2.对于 1,2,1nk (1)按列选主元

27、iknikkiaak max,(2)如果 ，则计算停止 0,kika)0(detA (3)如果 则转(4)kik 交换行：detdet),1,(,kkikjikjbbnkkjaa (4)消元计算 对于 nki,1 54 (a)kkikikikaama/(b)对于 nkj,1.*kjikijijamaa (c)kikiibmbb*(5)det*detkka 3.如果 ，则计算停止 0nna)0(detA 4.回代求解 nnnnabb/(1)1,2,1 (2)ni对于iinijjijiiababb/)*(155 5.det*detnna 例3的解法2用的就是列主元素消去法.列主元素消去法也可用矩阵

28、运算描述：,)2()1(,11)2()1(,1111bbILAAILii.,)1()(,)1()(,kkikkkkikkkkbbILAAIL（3.1）其中 的元素满足 是初等置换阵.kL),1,2,1(1nkmikkik,I56 利用(3.1)得到)(,11,22,11121niiinnnAAILILIL则有,)(nbbPUAP若记.121,11,22,11iiinnnILILILPAILILILAU123,11,22,33)4(iii.U)(322333,3,21,2,3,32,33iiiiiiIILIIILIL 考虑 时的 .4nP,)(123,1,2,3123PALLLAIIIiii（3

29、.2）,)2()1(,11)2()1(,1111bbILAAILii.,)1()(,)1()(,kkikkkkikkkkbbILAAIL（3.1）57,3223,3,21,2,31iiiiIILIIL 为单位下三角阵，其元素的绝对值不超过1.)3,2,1(kkL 记,1231LLLL由(3.2)得到.LUPA 其中 为排列矩阵，为单位下三角阵，为上三角阵.PLU其中,33,32,32iiILIL,33LL.123,1,2,3iiiIIIP 58 这说明对(2.1)应用列主元素消去法相当于对 先进行一系列行交换后对 再应用高斯消去法.)(bAPbPAx,LUPA 定理定理8 8如果 为非奇异矩阵

30、，A则存在排列矩阵 使P其中 为单位下三角阵，为上三角阵.LU 编程时，的元素存放在数组 的下三角部分，的元素存放在 的上三角部分，由记录主行的整型数组 可知 的情况.LAUA)(IpnP 而在实际计算中只能在计算过程中做行的交换.(列主元素的三角分解定理)59 5.3.2 高斯高斯-若当消去法若当消去法 高斯消去法中，若同时消去对角线下方和上方的元素，设用高斯-若当消去法已完成 步，化为等价1kbAx方程组 ，其中)()(kkbxA.101001)(,1,1,1222111)()(nnnknknkkkknkkknknkkkbaabaabaabaabaabA这种方法称为高斯高斯-若当若当(Ga

31、uss-Jordan)消去法消去法.60在第 步计算时 对上述矩阵第 行的上、下都进行消元.k),2,1(nkk 1.按列选主元素，即确定 使 ki.max,iknikkiaak 2.换行(当 时)交换 第 行与第 行元素.kik)(bAkki 3.计算乘数),2,1(/kinkaamkkikik且 (可保存在存放 的单元中).ikmika./1kkkkam61,1,2,1nkjkinkamaakjikijij且.,2,1kinkbmbbkikii且 5.计算主行),1,(nkkjmaakkkjkj上述过程结束后有.111)()(21)1()1(nkkbbbbAbA 4.消元计算.kkkkmb

32、b62 用高斯-若当方法将 约化为单位矩阵，计算解就在常数项位置得到，用不着回代求解，计算量大约需要 次乘除法，比高斯消去法大，但用高斯-若当方法求矩阵的逆矩阵还是比较合适的.A2/3n 定理定理9 9设 为非奇异矩阵，A方程组 的增广矩阵为 .nIAX)(nIAC 如果对 应C用高斯-若当方法化为 ，)(TIn则 .TA1 事实上，求 的逆矩阵 ，即求 阶矩阵 ，A1AnX,nIAX其中 为单位矩阵.nI(高斯-若当法求逆矩阵)使63于是求解 等价于求解 个方程组 nIAXn.,2,1,njjj eAx可用高斯-若当方法求解.nIAX将 按列分块X,2121nneeeIxxxX64 例例4

33、4653542321A的逆矩阵.解解 100653010542001321C3/10113/103/21013/203/10023/51第1次消元3c用高斯-若当方法求 00132101054210065331rr6502/112/10012/302/31022/502/101第2次消元2c012100133010231001第3次消元1c且,),(3T3121111cmmmm).(1AnI,),(2T3222122cmmmm.),(1T3323133cmmmm66 为了节省内存单元，可不必存放单位矩阵，经消元计算，最后再调整一下列就可在 的位置得到 .A1A注意第 步消元时，由 的第 列 kAkT1),(nkkkkkaaaa计算,),1,(T11kknkkkkkkaaaaam且冲掉.ka存放在 的第二列位置，2cA存放在 的1cA3c存放在A 的第1列，第3列.67 在 位置最后得到矩阵 (其中 为排列阵)的逆矩阵 ，A1APA P11A.111PAA于是 68