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

n个方程，n个未知数的线性方程组的高斯消去法：nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111，其系数矩阶nnnnnnaaaaaaaaaA212222111211。nbbbb21,21nxxxx3.1高斯消元法第k步0,,0)1(1,1)1(11kkkaa。)()(kkbxA，其中)2(2)2(22)1(1)1(12)1(11)(nnkaaaaaA。)()()2(2)1(1)(knkkkbbbbb设已完成上述消元过程第1步，第2步，…，第k-1步，（设)1()1(bxA）得到与原方程组等价的方程组)()()()(knnknkkknkkkaaaa，设0)(kkka。)1()1(kkbxA其中元素计算公式为：)1()1(,kkbAnkjnkiamaakkjikkjikji,,1,,1)()()1(，，，),,1()()(nkiaamkkkkikik计算乘数对施行行初等变换,使第k列以下元素约化为零，)(kA)(kkka)()()(kkbA，),,1()()()1(nkibmbbkkikkiki即，得到与原方程组等价的方程组),,1(nkirrmrikiki回代计算：)1,,2,1(nk),1(/)()(nkiaamkkkkikik)()(/nnnnnnabx消元计算：),,1()()()1(nkibmbbkkikkjkinkjnkiamaakkjijkijkij,,1,,1)()()1(；)(1)()(/)(iiinijjiijiiiaxabx)1,2,,2,1(nni3.2完全主元素消去法一选主元消元法：。，0||max||1111ijnjnijiaa11jxx与注意调换，设bxA，nnRA为非奇异矩阵，)1.4(第一步：。元素仍记为且两未知量，并作记录，iijbabA,,使,,11ji选主元：)1(行元素，行与第第交换时即当交换行列111),(,1,)2(ibAi（3）消元计算：，),,3,2(1111niaamii，),,3,2(1111niamaiiib列元素。列与第第交换时当111),(,1jbAj1ia),,3,2(11nibmbii在A中选取绝对值最大的元素作为主元素，即确定第k步：重复进行，设已完成第1步—第k-1的选主元，使[A，]增广阵。b[A，]约化为:bnnnnkkknkknkkbaabaababaaabAbA222111211)()(],[],[第k步的步骤：。步选主元区域方框为第1,,2,1nkk使选主元：即确定,,)1(kkji0maxijnjknikjiaakk，行元素，行与第第交换时即当交换行列kkkkikbAki),(,,)2()()(（3）消元计算：),,1(nkiaamkkikik),,1,(nkjiamakjikijib列元素。列与第第交换时当kkkkjkbAkj),(,)()(ija),,1(nkibmbkiki设已完成第1步~第k-1步计算，得到与原方程组等价的方程组，其中)()(kkbxA)()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()(],[nnknnknkkknknkkknnkkbaabaabaabaaabA方框内为第k步选主元素区域。3.3列主元素消去法以下步骤类似完全选主元素消去法。定理3-3nnRA设，)1,,2,1(0nkDk，如果A顺序主子式其中L为单位下三角阵，U为上三角矩阵。则A可唯一分解为两个三角矩阵相乘，即。LUA1.A=LU—Doolittle分解。L:单位下三角阵,U:上三角阵。2.A=LU—克路特分解。L:下三角阵,U:单位上三角阵。矩阵的三角分解分解计算.1nr,,3,22）（),,1,()111nrriulaurkkirkriri),,1(/)()211nrnriuulalrrrkkrikirir且求解计算.2，),,2(,)11111niylbybyikkikii。)1,2,,1(/)(/)21niuxuyxuyxiinikkikiinnnn的计算公式（步骤）：bxA),,2(/1111niualii，iiau11)1(行第rU列第rLYUXbLYnnnnnnuuuuuulll222112112121111ijaAbAX的元素排列如下：和的方法，把下面给出便于记忆公式UL11u12u13u14u)(11iiau1y22u23u24u2y41l31l21l1111aalii32l42l33u34u3y43l44u4y②①③④⑤⑥⑦用直接三角分解法解方程组bxAxxx或1111163852741321，LUA，，7,4,11)1(131312121111auauaur，，313212113131112121ualual解：，，)3,2(,2)2(12122iulauriii，则342512212222ulau，2/)(2212313232uulal，2)(,3)3(233213313333ululaur，672813212323ulau。从而LUA2637411231211163852741、分解计算：1，，得求解TybyL)0,1,1()4(。，得方程组的解求解TxyxU)0,3/1,3/1()5(、求解计算：2333323122322211131211baaabaaabaaa131211uuu3121ll2322uu32l33u1y2y3y3.2.2平方根法平方根法：对称正定矩阵及其三角分解法，有且0),(,0)2(xxAxRxn对称正定矩阵的一种三角分解方法。1、定义及性质定义)(对称正定阵满足：如果设ARAnn,为对称正定阵。则称A；AAT)1(定理3-4A为对称正定阵(4)A的特征值。),,2,1(0)(niAi(1)A是非奇异矩阵，且A-1亦是对称正定阵；(2)A的顺序主子阵Ak是对称正定阵(k=1,2,…,n)；；),,2,1(0)det(nkAk(3)A的顺序主子式都大于零，即1、性质定理3-5为对称正定若nnRA（对称正定矩阵的Cholesky分解）。TLLA阵，则存在唯一的具有正对角元的下三角阵L，使得思路：；为分解对称正定阵TLLAA)1(..xyxLybyLT，求，求bxLLbxAT求解求解)2(求解方程组nnnnnnaaaaaaaaaA212222111211令设n阶对称正定矩阵A有分解,先用待定系数法求L的元TLLAnnnnnnnnllllllllllll2221211121222111该分解称为（Cholesky）分解。ijl素。求解对称正定方程组Ax=b的平方根法(计算公式)：1．分解计算：TLLA),,2,1(ni2/1112)()2(ikikiiiilal,)()1(11jjjkjkikijijlllal))(1,,2,1(ijij求解计算.2，),,2,1()()3(11nilylbyiiikkikii。)1,2,,1,()()4(1nnilxlyxiinikkkiiixyxLybyLT求，求，jjijjkjkiknkjkikijlllllla111),,2,1(ni，时，当)0(jkljknnnnnnaaaaaaaaaA212222111211令1111112121212121nnnnnllldddlllTTLnnndddlll212121111LDT改进的平方根法求解对称正定方程组Ax=b的改进平方根法(计算公式)：1．分解计算：TLDLA，111)1(ad,,,3,2)2(时当ni11)1,,2,1(,)1jkjkikijijijlTaT)1,,2,1(,)2ijdTljijij11)3ikikikiiilTad求解计算.2xyDxLybyLT求，求，1nnnnnnaaaaaaaaaA2122221112111111112121212121nnnnnllldddlllTLDLbxLDLbxAT求解求解,),,2(,)11111niylbybyikkikii.)1,2,,1()21nixldyxdyxnikkkiiiinnn例用改进的平方根法求解方程组131101110400141030003520002321002254321xxxxx分析：对称很显然，需验证正定，可通过验证各顺序主子式大解1、分解TLA2/1111212212/11300120111即,TLDLA2、求解计算，得求解byL，Ty)2/1,1,4,2,1(到方程组的解：。Tx)1,1,1,1,1(得，求解yDxLT11311011122121130012011154321yyyyy114221121231102121001154321xxxxx于零。三对角线方程组的一般形式：nninninnnnniiifffffxxxxxbacbacbacbacb12112111122211fAx或追赶法nniiibacbac