三角分解解线性方程组的公式

February3,[e-mail]1的求解过程为:bxAyxUbyL可推导求解单位下三角形方程组的递归公式为:byL11kmmkmkkylbynk,,3,2求解上三角形方程组的递归公式为:yxUkknkmmkmkkuxuyx11,,2,1nnk•三角分解解线性方程组的公式11bynnnnuyx/February3,[e-mail]2,11kmmjkmkjkjulau11kmmkmkkylby直接三角分解法发现计算的规律与计算的规律相同,因此计算的求方程组的过程可用三角分解的紧凑格式取代。事实上，这只要把做为A的第n＋1列进行直接三角分解即可。kykjuybReamrk：上述直接三角分解法所对应的是Gauss顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。续February3,[e-mail]3设对的分解已完成k-1步，即L的前k-1列,U之的前k-1行已求出：bA1,1,211,1,211,1,11,12,11,11,221,222211,111,11211nnnkknnnnkkkkkkknkkkkkkknkknkkaalllaallluuulluuuuluuuuu第k步计算：先选主元，再计算列，最后计算行3.3列主元直接三角分解法参选主元量.,1,11nkkiulaskmmkimikikkkkmmkkmkkkkikkkuulasss11,max则无需交换，且若1,1,,,,,,1,/nkkkkkikikuuuknkissl的其它元素行中之后按原公式计算第若,则需将第k行与第ik行完全交换，这样满足前面情形，按第一种情形实施计算。ikkisskmaxkkkmmkimikikkmmjkmkjkjuulalulau1111nki,11,1,nkkjFebruary3,[e-mail]51.正定矩阵的Cholesky分解定义：设A为n阶对称正定矩阵，L是非奇异下三角矩阵，称为矩阵A的Cholesky分解。2nTLLA定理:n阶对称正定矩阵A一定存在分解:其中L为单位下三角阵，D是对角元全为正的对角阵且这种分解式唯一;其中L为下三角阵，当限定L的对角元为正时的分解式唯一（Cholesky分解）.2nTLDLA1TLLA23.4平方根法（Cholesky分解）February3,[e-mail]6证明：nnnnuuullA11112111因为0,2,102211kkkkkunkuuu因为A对称正定，故其顺序主式，nkk,2,10有唯一的Doolittle分解从而A平方根法（Cholesky分解）LDRuuuuuuuuulllAnnnnnn11111222111111222112121定理证明February3,[e-mail]7AAT)()(DRLDLRLDRLDRTTTTTT（D可逆）DRDLLRTTTTLRRL平方根法（Cholesky分解）即,由Doolittle分解的唯一性，及的分解过程可知该分解式的唯一性。TLDLADRU续1由Doolittle分解的唯一性有February3,[e-mail]8改写nnnnuuuuDDD111则TTTLLDLDLLDDLA这时为一般的下三角矩阵，故，若的对角元全为正时，由Doolittle分解的唯一性及上述分解的推理过程，可以得到Cholesky分解的唯一性。LTLLALDLL平方根法（Cholesky分解）续2February3,[e-mail]9第一步：11111111111121111/lalllaallaiiiini3,2nnnnnnllllllllllA22121111222111平方根法（Cholesky分解）：分解公式设L前k-1列元素已求出，则第k步21121kkkmkmnmkmkmkklllla112kmkmkkkklalkikkikkmkmimnkmkmimkkikkmkmimnmkmimiklllllllllllla111111February3,[e-mail]101111kmkkkmkmimikikkkikkmimiklllalllllankki,,2,1平方根法（Cholesky分解）nnnnnnnnnnnnllllllllllllllllllllllllllllllA444343332423222141312111432144434241333231222111February3,[e-mail]11•在分解过程中有n次开方运算，故Cholesky分解法也称为平方根法。•用Gauss顺序消去法求解对称正定的方程组Ax＝b，kmkmkkla12•由iinikkkmaal12max用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。),,2,1(maxmax,1)(,1nkaaiinjikijnji这表明用Gauss顺序消去法求解对称正定方程组也不用选主元。几点说明February3,[e-mail]12323612961nnnn•从运算量的角度看，平方根法是有利的，用平方根法解Ax＝b所需乘除法的运算次数为：令有n次开方运算。n次开方运算一般使用迭代法，所需乘除法的运算次数大约为n的常数倍。故平方根法总的乘除法运算次数大约为32361961ncnnn•为避免开方运算，也可对A做分解。TLDLA续February3,[e-mail]13•矩阵对角占优的概念若满足矩阵nnijaA类似地，也可定义按列对角占优和按列严格对角占优的概念。通常的对角占优是指按行或者按列。则称矩阵A按行严格对角占优。,1iaanijjijii且若满足,1iaanijjijii且nijjjiiiaai000010且使得有且存在某一则称矩阵A按行对角占优。3.5三对角线性方程组求解February3,[e-mail]14满足严格对角占优条件11cbiiicab1,,3,2ninnab严格对角占优的矩阵行列式不等于零，故该系数矩阵的各级顺序主子式不等于零。nninninnnnniiiddddddxxxxxxbacbacbacbacbacb1321132111133322211•追赶法解三对角方程组February3,[e-mail]15nnnnnnnnnucucuculllbacbacbacb11221132111222111111若A为上述三对角阵时，则A有三角分解：追赶法解三对角方程组11ub1iiiulaiiiiuclb11111iiiiiiiclbuualbuni,,3,2分解公式dxAdxLUyxUdyLFebruary3,[e-mail]16追赶法解三对角方程组由得nnndddyyyll21212111111iiiiyldydyni,,3,2由得nnnnyyyxxxucucu21211211iiiiinnnuxcyxuyx11,2,,1ni方程求解公式February3,[e-mail]17追赶法解三对角方程组Remark：只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为5n－4。上述方法称为解三对角方程组的追赶法，又称为Thomas方法。说明February3,[e-mail]18nninninnnnniiiddddddxxxxxxBACBACBACBACBACB1321132111133322211其中Ai，Bi，Ci均为q阶矩阵，，是q维向量。对于这种方程组，可以类似地建立追赶法。ixid•追赶法解块状三对角方程组February3,[e-mail]19追赶法解块状三对角方程组ppppppppppUCUCUCUILILILIBACBACBACB1122111111122211其中I为q阶单位矩阵，Li和Ui是q阶矩阵。根据矩阵的分块运算，容易求得块三对角方程组的追赶法如下：续February3,[e-mail]20追赶法解块状三对角方程组),,3,2(11111piCLBUUALBUiiiiiii),,3,2(111piyLdydyiiii)1,,2,1()(111ppixCyUxdUxiiiiippp续2February3,[e-mail]214.1向量范数1.定义：设的某个实值函数满足nRxx(3).（三角不等式）yxyx(2).（齐次性）c为任意实数xcxc(1).（非负性)当且仅当时有＝00x0xx则称是上的一个向量范数。xnR4矩阵的条件数和方程组的性态niixx112112212niiTxxxxinixx1maxFebruary3,[e-mail]22证明：yyxyyxxyxyxxxyxxyyyxxy故必有yxyxyxyx