解线方程组的直接方法

《解线方程组的直接方法》由会员分享，可在线阅读，更多相关《解线方程组的直接方法（56页珍藏版）》请在装配图网上搜索。

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

2、数排成的矩形表，称为 行 列矩阵. mnnnxxxxRx21称为 维列向量. n第3页/共56页5,21naaaA其中 为 的第 列. iaAi,21TmTTbbbA其中 为 的第 行. TibAi 也可写成行向量的形式 写成列向量的形式第4页/共56页6 (5) 单位矩阵 矩阵的基本运算： (1) 矩阵加法 ,BAC (2) 矩阵与标量的乘法 .,ijijacAC (3) 矩阵与矩阵乘法 ).R,R,R(1pmpnnmnkkjikijCBAbac,ABC)R,(nmijijijCBAbac (4) 转置矩阵.,RijijTnmacACA,R21nnneeeI第5页/共56页7 (6) 非奇异

3、矩阵 设.R,RnnnnBA则称 是B 如果 存在，1A则称 为非奇异矩阵. A 如果 均为非奇异矩阵，nnBAR,其中 ., 2, 1,0, 0, 1 , 0, 0nkeTk, IBAAB如果A的逆矩阵，,1A记为.)()(11TTAA且.)(111ABAB则 (7) 矩阵的行列式 设,RnnA则 的行列式可按任一行(或列)展开，A第6页/共56页8),2, 1()(det1niAaAnjijij其中 为 的代数余子式，ijAija,)1(ijjiijMA 行列式性质：.R,),()det(det)(det a)(nnBABAAB即 ija 的余子式. .R),(det)(det (b)nn

4、TAAA.RR,),(det)(det (c)nnnAcAccA.0)(det (d)是非奇异矩阵AA为元素ijM第7页/共56页9 设 .R)(nnijaA (1) 对角矩阵 (2) 三对角矩阵.01ijaji，如果当 (3) 上三角矩阵 .0ijaji，时如果当 (4) 上海森伯格（Hessenberg）阵 .01ijaji，时如果当 (5) 对称矩阵 .AAT如果.0ijaji，时如果当第8页/共56页10 (6) 埃尔米特矩阵 .,CAAAHnn如果设 (7) 对称正定矩阵 , (a) AAT如果. 0),(,R (b) AxxxAxxTn对任意非零向量 (8) 正交矩阵 .1TAA如

5、果 (9) 酉矩阵 .,CH1AAAnn如果设 (10) 初等置换阵 由单位矩阵 交换第 行与第 行(或交换第 列与第 列)，得到的矩阵记为 ,且 IijijijI第9页/共56页11 (11) 置换阵 定理定理1 1设 ，nnAR(1) 对任何 方程组 有唯一解. ,RnbbAx AAIij（为交换 第 行与第 行得到的矩阵）；Aij（为交换 第 列与第 列得到的矩阵）；iAjBAIij由初等置换阵的乘积得到的矩阵. 则下述命题等价： (2) 齐次方程组 只有唯一解 .0Ax0 x(4) 存在. 1A(5) 的秩A.)(nArank.0)det(A(3)第10页/共56页12 定理定理2 2

6、设 为对称正定阵，则 nnAR (1) 为非奇异矩阵，且 亦是对称正定阵. A1A (2) 记 为 的顺序主子阵，则 kAA).,2, 1(1111nkaaaaAkkkkk),2, 1(nkAk亦是对称正定矩阵，其中 (3) 的特征值 A).,2, 1(0nii (4) 的顺序主子式都大于零，即 A)., 2 , 1(0)det(nkAk第11页/共56页13 定理定理3 3设 为对称矩阵. nnAR), 2 , 1(nk或 的特征值A),2, 1(0nii则 为A 定理定理4 4(Jordan标准型)设 为 阶矩阵，则存在一个An非奇异矩阵 使得 P,)()()(22111rrJJJAPP0

7、)(detkA如果对称正定阵.第12页/共56页14其中 .),2,1(111)(1nnrinJriiinniiiiiiii且为若当（Jordan）块. (1) 当 的若当标准型中所有若当块 均为一阶时，AiJ此标准型变成对角矩阵. 第13页/共56页15 (2) 如果 的特征值各不相同，则其若当标准型必为A).,(21ndiag对角阵第14页/共56页16第15页/共56页17 设有线性方程组 .,22112222212111212111mnmnmmnnnnbxaxaxabxaxaxabxaxaxa（2.1）或写为矩阵形式 ,2121212222111211mnmnmmnnbbbxxxaaa

8、aaaaaa第16页/共56页18简记为 .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.5)上去，消去方程第17页/共56页19(2.5)中的未知数,2x得到与原方程组等价的三角形方程组 .62)6.2(,54,6332321xxxxxx显然，方程组(2.6)是容易求解的，解为 .)3,2, 1(Tx 上述过程相当于 112251406111bA111405

9、1406111第18页/共56页20620051401111331)2(rrr332rrr其中用 表示矩阵的第 行. iri 由此看出，用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组 化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法. bAx 上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的问题转化为求解简单方程组的问题. 第19页/共56页21 或者说，对系数矩阵 施行一些左变换(用一些简单矩阵)将其约化为上三角矩阵. A 下面讨论求解一般线性方程组的高斯消去法. 将(2.1)记为 其中 ,)1()1(bxA.)

10、,()()1()1()1(bbaaAijij (1) 第1步 ).1(k 设 首先计算乘数 ,0)1(11a. ),3,2(/)1(11)1(11miaamii用 乘(2.1)的第一个方程，加到第 个方程上，1imi),3,2(mi消去(2.1)的从第二个方程到第 个方程中m第20页/共56页22).,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(jiij

11、ijamaa),2;,2(njmi)1(11)1()2(bmbbiii第21页/共56页23 (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(11nnkknkkmnkmkkknkkknknkbbbbxxxxaaaaaaaaaaa即已计算好与(2.1)等价的方程组简记为 .)()(kkbxA第22页/共56页24)()()1(kkjikkijkijamaa), 1;, 1(nkjmki)., 1(mki 设 计算乘数 ,0)

12、(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第23页/共56页25 (3) 继续上述过程，且设),2, 1(0)(skakkk直到完成第 步消元计算.s 最后得到与原方程组等价的简单方程组 ,)1()1(ssbxA其中 为上梯形. )1( sA 特别当 时，与原方程

13、组等价的方程组为 nm,)()(nnbxA即 （2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa第24页/共56页26 如果 是非奇异矩阵，且nnAR),1,2, 1(0)(nkakkk由(2.1)约化为(2.10)的过程称为消元过程. 求解三角形方程组(2.10)，得到求解公式 ,/)()(nnnnnabx ).1 ,2, 1(nnk（2.11）(2.10)的求解过程(2.11)称为回代. )(1)()(/ )(kkknkjjkkjkkkaxabx 如果 由于 为非奇异矩阵，所以 的第一列一定有元素不等于零. ,0

14、11aAA第25页/共56页27 例如 于是交换两行元素(即 ），将 调到(1,1)位置，然后进行消元计算，这时 右下角矩阵为 阶非奇异矩阵. ,011ia11irr 11ia)2(A1n 继续这过程，高斯消去法照样可进行计算.第26页/共56页28 定理定理5 5设 其中 ,bAx.RnnA (1) 如果),2, 1(0)(nkakkk将 约化为等价的三角形方程组(2.10)，且计算公式为：bAx则可通过高斯消去法 (a) 消元计算 )1,2, 1(nk), 1(/)()(nkiaamkkkkikik), 1,()()()1(nkjiamaakkjikkijkij)., 1()()()1(n

15、kibmbbkkikkiki第27页/共56页29 (b) 回代计算 ,/)()(nnnnnabx).1 ,2, 1(/ )()(1)()(nniaxabxiiinijjiijiii (2) 如果 为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组 约化为(2.10).AbAx第28页/共56页30 算法算法1 1(高斯算法),2, 1(0)(skakkk本算法用高斯方法将 约化为上梯形，A且 覆盖 ，乘数 覆盖 .A)(kAikmika 对于sk,2, 1 (1) 如果 则计算停止,0kka (2) 对于 mki, 1 (a)kkikikikaama/ (b) 对于 nkj,

16、1.*kjikijijamaa), 1min(),1(RnmsmAnm设如果第29页/共56页31上三角阵， 算法1第 步需要作 次除法， 次乘法，kkm)(knkm因此，本算法(从第1步到第 步消元计算总的计算量)s 当 时，总共大约需要 次乘法运算. nm3/3n 数 称为约化的主元素主元素. )(kkka 算法算法2 2(回代算法)设 其中 为非奇异,bUxnnUR本算法计算 的解. bUx 对于1 ,ni (1) iibx 大约需要 次乘法(对相当大的 ). mnssnms2/)(3/23s第30页/共56页32 (2) 对于 nij, 1jijiixuxx* (3) iiiiuxx/

17、 这个算法需要 乘除法运算. 2/ )1( nn 高斯消去法对于某些简单的矩阵可能会失败，.0110A由此，需要对算法1进行修改，例如 ).,2, 1(0)(kakkk在什么条件下才能保证 A首先需要研究原来的矩阵第31页/共56页33 定理定理6 6约化的主元素 的充要条件),2, 1(0)(kiaiii是矩阵 的顺序主子式A).,2, 1(0kiDi,0111aD即（2.12）).,2, 1(01111kiaaaaDiiiii 证明证明 显然，当 时，定理6成立.1k 现设定理6充分性对 是成立的，求证定理6充分性对 亦成立. 1kk首先利用归纳法证明定理6的充分性. 第32页/共56页3

18、4 设),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(112aaaaaD第33页/共56页35.)()2(22)1(11)()1(1)1(11kkkkkkkkaaaaaaD（2.13） 由设),2, 1(0kiDi定理6充分性对 亦成立. k 显然，由假设),2, 1(0)(kiaiii利用(2.13)式，,0)(

19、kkka则有利用(2.13)式亦可).,2, 1(0kiDi推出 第34页/共56页36 推论推论如果 的顺序主子式A),1,2, 1(0nkDk,1)1(11Da则 )., 3,2(/1)(nkDDakkkkk第35页/共56页37于是对(2.1)施行第一次消元后化为(2.7)， 下面借助矩阵理论进一步对消去法作些分析，从而建立高斯消去法与矩阵因式分解的关系. 设(2.1)的系数矩阵 的各顺序主子式均不为零. nnAR由于对 施行行的初等变换相当于用初等矩阵左乘 ，AA这时 化为)1(A,)2(A化为 ，)1(b)2(b,)2()1(1)2()1(1bbLAAL即 第36页/共56页38其中

20、 .1111131211nmmmL 一般第 步消元，k化为 , )(kA)1( kA化为 ，)(kb)1( kb,)1()()1()(kkkkkkbbLAAL相当于 其中 第37页/共56页39.1111,1knkkkmmL重复这过程，最后得到 ;)()1(121nnAALLL（2.14）.)()1(121nnbbLLL 记上三角矩阵 为 ，由(2.14)得到 )(nAU第38页/共56页40,111211LUULLLAn其中 111211nLLLL为单位下三角矩阵. 这就是说，高斯消去法实质上产生了一个将 分解为两个三角形矩阵相乘的因式分解，于是得到如下重要定理，它在解方程组的直接法中起着重

21、要作用. A1111321323121nnnmmmmmm第39页/共56页41 定理定理7 7设 为 阶矩阵，An如果 的A顺序主子式),1,2, 1(0niDi则 可分解为一个单位A下三角矩阵 和一个上三角矩阵 的乘积，LU 证明证明现在在 为非奇异矩阵的假定下证明唯一性， A 设 ,11ULLUA其中 为单位下三角矩阵， 为上三角矩阵. 1,LL1,UU(矩阵的LU分解)且这种分解是唯一的. 根据以上高斯消去法的矩阵分析，存在性已得证， 第40页/共56页42.1111UULL上式右边为上三角矩阵，左边为单位下三角矩阵， 例例2 2,122140111A 由高斯消去法，, 1,2,0323

22、121mmm 由于 存在，故 11U从而上式两边都必须等于单位矩阵，唯一性得证. ,11UULL故对于例1，系数矩阵 故 第41页/共56页43200140111112010001A.LU第42页/共56页44 例例3 3 由高斯消去法知道，在消元过程中可能出现 0)(kkka 即使主元素 但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠. ,0)(kkka.000.3000.2000.1643.5072.1000.2623.4712.3000.1000.3000.2001.0321xxx这时消去法将无法进行；求解方程组 第43页/共56页45用4位

23、浮点数进行计算. 精确解舍入到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第44页/共56页46计算解为 .)0.4000 0.09980, 0.400,(Tx,000.2000.5001002300520040000

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

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

26、页/共56页49 本节主要介绍列主元消去法，并假定(2.1)的 为非奇异的. nnAR第48页/共56页50 设方程组(2.1)的增广矩阵为 .21212221111211nnnnnnnbaaabaaabaaaB 首先在 的第一列中选取绝对值最大的元素作为主元素，A,0max1,11,1iniiaa例如 第49页/共56页51重复上述过程，设已完成第 步的选主元素，交换两行1k,)(222211111211)()(nnnnkkknkknknkkkbaabaabaaabaaaabA).()()2()2(bAbA然后交换 的第1行与第 行，经第1次消元计算得 B1i)(bA约化为及消元计算，第50

27、页/共56页52其中 的元素仍记为 , 的元素仍记为 . )(kAija)(kbib 第 步选主元素(在 右下角方阵的第1列内选)，k)(kA即确定 ，使 ki.0max,iknikkiaak交换 第 行与 行的元素，再进行消元计算，)()()(kkbAkki最后将原方程组化为 .212122211211nnnnnnbbbxxxaaaaaa第51页/共56页53回代求解,/nnnabx).1 ,2, 1(/ )(1nniaxabxiinijjijii 算法算法3 3(列主元素消去法) 设 . 本算法用具有行交换的列主元素消去法，bAx 消元结果冲掉 ，乘数 冲掉 ，计算解 冲掉常数项Aijmi

28、jax,b行列式存放在 中.det1. 1det第52页/共56页54 2. 对于 1,2, 1nk (1) 按列选主元 iknikkiaakmax, (2) 如果 ，则计算停止 0,kika )0(detA (3) 如果 则转(4) kik 交换行： detdet), 1,(,kkikjikjbbnkkjaa (4) 消元计算 对于 nki, 1第53页/共56页55 (a)kkikikikaama/ (b) 对于 nkj, 1.*kjikijijamaa (c)kikiibmbb* (5) det*detkka 3. 如果 ，则计算停止 0nna )0(detA 4. 回代求解 nnnnabb/ (1)1 ,2, 1 (2)ni对于iinijjijiiababb/)*(1第54页/共56页56,)2()1(,11)2()1(,1111bbILAAILii 5. det*detnna 例3的解法2用的就是列主元素消去法. 列主元素消去法也可用矩阵运算描述： .,)1()(,)1()(,kkikkkkikkbbILAAILkk（3.1）其中 的元素满足kL),1,2, 1(1nkmikkikI,是初等置换阵. 第55页/共56页