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

1第5章解线性方程组的直接方法25.1引言与预备知识5.1.1引言线性方程组的数值解法一般有两类：1.直接法经过有限步算术运算，可求得方程组精确解的方法(若计算过程中没有舍入误差).但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解.32.迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法.45.1.2向量和矩阵用表示全部实矩阵的向量空间，表示全部复矩阵的向量空间.nmRnmnmCnmmnmmnnijnmaaaaaaaaaaAA212222111211)(R这种实数排成的矩形表，称为行列矩阵.mnnnxxxxRx21称为维列向量.n5,21naaaA其中为的第列.iaAi,21TmTTbbbA其中为的第行.TibAi也可写成行向量的形式写成列向量的形式6(5)单位矩阵矩阵的基本运算：(1)矩阵加法,BAC(2)矩阵与标量的乘法.,ijijacAC(3)矩阵与矩阵乘法).R,R,R(1pmpnnmnkkjikijCBAbac,ABC)R,,(nmijijijCBAbac(4)转置矩阵.,,RijijTnmacACA,R21nnneeeI7(6)非奇异矩阵设.R,RnnnnBA则称是B如果存在，1A则称为非奇异矩阵.A如果均为非奇异矩阵，nnBAR,其中.,,2,1,0,,0,1,0,,0nkeTk,IBAAB如果A的逆矩阵，,1A记为.)()(11TTAA且.)(111ABAB则(7)矩阵的行列式设,RnnA则的行列式可按任一行(或列)展开，A8),,,2,1()(det1niAaAnjijij其中为的代数余子式，ijAija,)1(ijjiijMA行列式性质：.R,),()det(det)(deta)(nnBABAAB即ija的余子式..R),(det)(det(b)nnTAAA.RR,),(det)(det(c)nnnAcAccA.0)(det(d)是非奇异矩阵AA为元素ijM95.1.3特殊矩阵设.R)(nnijaA(1)对角矩阵(2)三对角矩阵.01ijaji，如果当(3)上三角矩阵.0ijaji，时如果当(4)上海森伯格（Hessenberg）阵.01ijaji，时如果当(5)对称矩阵.AAT如果.0ijaji，时如果当10(6)埃尔米特矩阵.,CAAAHnn如果设(7)对称正定矩阵,(a)AAT如果.0),(,R(b)AxxxAxxTn对任意非零向量(8)正交矩阵.1TAA如果(9)酉矩阵.,CH1AAAnn如果设(10)初等置换阵由单位矩阵交换第行与第行(或交换第列与第列)，得到的矩阵记为,且IijijijI11(11)置换阵定理1设，nnAR(1)对任何方程组有唯一解.,RnbbAxAAIij~（为交换第行与第行得到的矩阵）；Aij（为交换第列与第列得到的矩阵）；iAjBAIij由初等置换阵的乘积得到的矩阵.则下述命题等价：(2)齐次方程组只有唯一解.0Ax0x(4)存在.1A(5)的秩A.)(nArank.0)det(A(3)12定理2设为对称正定阵，则nnAR(1)为非奇异矩阵，且亦是对称正定阵.A1A(2)记为的顺序主子阵，则kAA).,,2,1(1111nkaaaaAkkkkk),,2,1(nkAk亦是对称正定矩阵，其中(3)的特征值A).,,2,1(0nii(4)的顺序主子式都大于零，即A).,,2,1(0)det(nkAk13定理3设为对称矩阵.nnAR),,,2,1(nk或的特征值A),,,2,1(0nii则为A定理4(Jordan标准型)设为阶矩阵，则存在一个An非奇异矩阵使得P,)()()(22111rrJJJAPP0)(detkA如果对称正定阵.14其中.),,,2,1(111)(1nnrinJriiinniiiiiiii且为若当（Jordan）块.(1)当的若当标准型中所有若当块均为一阶时，AiJ此标准型变成对角矩阵.15(2)如果的特征值各不相同，则其若当标准型必为A).,,,(21ndiag对角阵165.2高斯消去法175.2.1高斯消去法设有线性方程组.,,22112222212111212111mnmnmmnnnnbxaxaxabxaxaxabxaxaxa（2.1）或写为矩阵形式,2121212222111211mnmnmmnnbbbxxxaaaaaaaaa18简记为.bAx例1)4.2(.122)3.2(,54)2.2(,632132321xxxxxxxx解消去(2.4)中的未知数得到,1x将方程(2.2)乘上加到方程(2.4)上去，2)5.2(.11432xx第2步.用消去法解方程组第1步.将方程(2.3)加到方程(2.5)上去，消去方程19(2.5)中的未知数,2x得到与原方程组等价的三角形方程组.62)6.2(,54,6332321xxxxxx显然，方程组(2.6)是容易求解的，解为.)3,2,1(Tx上述过程相当于112251406111bA111405140611120620051401111331)2(rrr332rrr其中用表示矩阵的第行.iri由此看出，用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法.bAx上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的问题转化为求解简单方程组的问题.21或者说，对系数矩阵施行一些左变换(用一些简单矩阵)将其约化为上三角矩阵.A下面讨论求解一般线性方程组的高斯消去法.将(2.1)记为其中,)1()1(bxA.),()()1()1()1(bbaaAijij(1)第1步).1(k设首先计算乘数,0)1(11a.),,3,2(/)1(11)1(11miaamii用乘(2.1)的第一个方程，加到第个方程上，1imi),,3,2(mi消去(2.1)的从第二个方程到第个方程中m22).,,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(11mnmnmnnbbbxxxaaaaaaa简记为,)2()2(bxA其中的元素计算公式为)2()2(,bA)1(11)1()2(jiijijamaa),,,2;,,2(njmi)1(11)1()2(bmbbiii23(2)第次消元k)).,1min(,,2,1(nmsk设上述第1步，…，第步消元过程计算已经完成，1k（2.8）,)()()2(2)1(121)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnkknkkmnkmkkknkkknknkbbbbxxxxaaaaaaaaaaa即已计算好与(2.1)等价的方程组简记为.)()(kkbxA24)()()1(kkjikkijkijamaa),,,1;,,1(nkjmki).,,1(mki设计算乘数,0)(kkka.),,1(/)()(mkiaamkkkkikik加到第个方程i),,,1(mki用乘(2.8)的第个方程，ikmk消去从第个方程到第个方程中的未知数得到与m,kx1k元素的计算公式为)1()1(,kkbA显然中从第1行到第行与相同.)1(kAk)(kA.)1()1(kkbxA(2.1)等价的方程组)()()1(kkikkikibmbb25(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(11nnnnnnnnbbbxxxaaaaaa26如果是非奇异矩阵，且nnAR),1,,2,1(0)(nkakkk由(2.1)约化为(2.10)的过程称为消元过程.求解三角形方程组(2.10)，得到求解公式,/)()(nnnnnabx).1,,2,1(nnk（2.11）(2.10)的求解过程(2.11)称为回代.)(1)()(/)(kkknkjjkkjkkkaxabx如果由于为非奇异矩阵，所以的第一列一定有元素不等于零.,011aAA27例如于是交换两行元素(即），将调到(1,1)位置，然后进行消元计算，这时右下角矩阵为阶非奇异矩阵.,011ia11irr11ia)2(A1n继续这过程，高斯消去法照样可进行计算.28定理5设其中,bAx.RnnA(1)如果),,,2,1(0)(nkakkk将约化为等价的三角形方程组(2.10)，且计算公式为：bAx则可通过高斯消去法(a)消元计算)1,,2,1(nk),,,1(/)()(nkiaamkkkkikik),,,1,()()()1(nkjiamaakkjikkijkij).,,1()()()1(nkibmbbkkikkiki29(b)回代计算,/)()(nnnnnabx).1,,2,1(/)()(1)()(nniaxabxiiinijjiijiii(2)如果为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组约化为(2.10).AbAx30算法1(高斯算法)),,,2,1(0)(skakkk本算法用高斯方法将约化为上梯形，A且覆盖，乘数覆盖.A)(kAikmika对于sk,,2,1(1)如果则计算停止,0kka(2)对于mki,,1(a)kkikikikaama/(b)对于nkj,,1.*kjikijijamaa),,1min(),1(RnmsmAnm设如果31上三角阵，算法1第步需要作次除法，次乘法，kkm))((knkm因此，本算法(从第1步到第步消元计算总的计算量)s当时，总共大约需要次乘法运算.nm3/3n数称为约化的主元素.)(kkka算法2(回代算法)设其中为非奇异,bUxnnUR本算法计算的解.bUx对于1,,ni(1)iibx大约需要次乘法(对相当大的).mnssnms2/)(3/23s32(2)对于nij,,1jijiixuxx*(3)iiiiuxx/这个算法