分解法解線性方程組初探

【摘要】通過引例引出系數矩陣A能分解成兩個三角形矩陣U和L的乘積，并得到L和U的計算公式.

【關鍵詞】線性方程組；系數矩陣；三角形矩陣；初等行變換

一、引 言

解線性方程組a11x1+a12x2+…+a1nxn=b1，a21x1+a22x2+…+a2nxn=b2，……an1x1+an2x2+…+annxn=bn，即解AX=b，通過將系數矩陣A分解成兩個三角形矩陣的乘積LU將解AX=b的問題轉化為LY=b，UX=Y的求解問題.

二、LU解法

1.三角形矩陣L與U的引出

消元法實質是對增廣矩陣作初等行變換，初等行變換是可以用矩陣的運算來進行的.下面就n=3的情況分析順序消元法的消元過程，得到有用的結論.設三元線性方程組AX=b，它的增廣矩陣［Ab］=a11a12a13b1a21a22a23b2a31a32a33b3記作A(0)b(0)」①，將①式作初等行變換，得a(0)11a(0)12a(0)13b(0)10a(1)22a(1)23b(1)20a(1)32a(1)33b(1)3=A(1)b(1)」②，由初等矩陣的運算性質知，上述初等行變換運算，可以表示為M(2)M(1)［Ab］=A(1)b(1)」，其中M(1)=100-a21a1110001，M(2)=100010-a31a1101，均為初等矩陣.因此只要對矩陣②左乘初等矩陣M(3)=1000100-a(1)32a(1)221，得到a(0)11a(0)12a(0)13b(0)10a(1)22a(1)23b(1)200a(2)33b(2)3=［UY］，由此知，消元過程相當于下述矩陣乘法運算，M(3)M(2)M(1)［Ab］=［UY］，因此，由矩陣的分塊乘法，得M(3)M(2)M(1)A=U，M(3)M(2)M(1)B=Y.令L=(M(3)M(2)M(1))-1=(M(1))-1(M(2))-1(M(3))-1，可以直接計算得到L=100l2110l31l321，其中l21=a21a11，l31=a31a11，l32=a(1)32a22，于是有A=LU③，LY=b④.

可見，只要消元過程能進行到底，就有以下等價關系AX=bA=LULUX=b令Y=UXLY=b，UX=Y⑤，即消元過程相當于把矩陣A分解為單位下三角矩陣L和上三角矩陣U的乘積，解方程組LY=b，回代過程就是解方程組UX=Y.

以上分析和結論可以推廣到n元線性方程組，相應的式③中的L為n階單位下三角矩陣，U為n階上三角矩陣，即L=100…0l2110…0l31l321…0…ln1ln2ln3…1，U=a11a12a13…a1n0a(1)22a(1)23…a(1)2n00a(2)33…a(2)3n…000…a(n-1)nn，式③稱為系數矩陣A的LU分解.等價關系⑤說明，要解線性方程組AX=b，可利用矩陣A的LU分解轉化為解兩個三角方程組，這種解線性方程組的方法稱為LU解法.

2.LU解法的公式

定理 若A是非奇異矩陣，則A能分解為LU的充分必要條件是A的順序主子式均不為0，即detA1=|a11|≠0，detA2=a11a12a21a22≠0，…，detAn=|A|≠0，證明從略.

由A=LU，即a11a12a13…a1na21a22a23…a2na31a32a33…a3n…an1an2an3…ann=100…0l2110…0l31l321…0…ln1ln2ln3…1#8226;u11u12u13…u1n0u22u23…u2n00u33…u3n…000…unn，可得lij和uij的計算公式.

（1）計算U的第一行，L的第一列：u1j=a1j（j=1，2，…，n）；li1=ai1u11（i=2，…，n）⑦.

（2）計算U的第r行，L的第r列：

urj=arj-∑r-1k=1lrkukj(j=r，r+1，…，n)，

lir=air-∑r-1k=1likukrurr(i=r+1，…，n).⑧

三、例 子

用LU分解法求解線性方程組123252315x1x2x3=141820 .

解 用公式⑦，⑧計算得到A=123252315=1002103-5112301-400-24=LU，解方程組LY=141820，得Y=14-10-72；再解UX=Y=14-10-72，得X=123 .

四、結束語

用LU分解法解線性方程組，其系數矩陣A為一般稠密型，即零元素占很小比例，計算公式容易記憶，但計算量大，當系數矩陣A的階數較高時適用于計算機運算.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文