矩陣三角分解的探討

文/王亞梅

摘 要：矩陣是數學中最重要的基本概念之一，是代數的一個主要研究對象，也是數學研究及應用的一個重要工具。對矩陣三角分解的相關內容進行系統的介紹，給出分解的思想、分解方法、分解的存在性及分解的條件等相關內容，然后就矩陣三角分解思想研究它在解決具體問題中的應用。

關鍵詞：矩陣；三角分解；LU分解

在近代數學、工程技術、經濟理論管理科學中，大量涉及矩陣理論的知識，很多問題都可以歸結為矩陣并最終通過矩陣來解決。經查閱發現，目前關于矩陣三角分解的應用研究不少，但對三角分解缺乏系統的研究。

矩陣三角分解法是指高斯消去法解線性方程組的變形解法。其實質就是將系數矩陣A分解為兩個三角形矩陣L和U相乘，即A=LU。

一、矩陣的直接三角分解

矩陣的直角三角分解即可以不經過消元步驟，直接將矩陣進行分解。

定義1 設A∈Rn×n，若A能分解為一個下三角矩陣L與一個上三角矩陣U的乘積，即A=LU，則稱這種分解為矩陣A的三角分解。

（1）如果A可分解為A=LDU，其中L是單位下三角矩陣，D是對角矩陣，U是單位上三角矩陣，則稱A可作LDU分解；

（2）如果在A=LU中，L是單位下三角矩陣，U為上三角矩陣，則稱此三角分解為杜利特（Doolittle）分解；

（3）如果在A=LU中，L是下三角矩陣，U是單位上三角矩陣，則稱此三角矩陣為克勞特（Crout）分解。

定理1 n階方陣A非奇異的充要條件為（或A經行、列變換后）存在LDU分解。其中L為n階單位下三角矩陣，D為n階非奇異對角陣，U為n階單位上三角矩陣。

推論1 奇異矩陣不能進行LDU分解。

推論2 若矩陣A有奇異主子矩陣，則A不能直接進行LDU分解。

定理2 方陣A的LDU分解唯一的充要條件為A的各主子矩陣非奇異。

推論1 設n階矩陣A的各階順序主子式皆不為零，則A存在唯一Crout的分解。

推論2 設n階矩陣A的各順序主子式皆不為零，則A存在唯一的分解A=LDU

其中L為單位下三角矩陣，D為對角矩陣，U為單位上三角矩陣。

二、常用的三角分解公式及其應用

1.杜利特（Doolittle）分解

下面直接用矩陣乘法求L及U的元素，由

A=a11 a12…a1na21 a22…a2n■ ■ ■an1 an2…ann=1a21 1■ ■■1an1 an2…lnn-1 1u11 u12…u1nu22…u2n■■unn

步驟如下：步驟1 u1i=a1i，i=2，3，…n l1i=a1i／u11，i=2，3，…n

計算U第r行，L的第r列元素，r=2，3，…n

步驟2 uri=ari-■lrkuki（i=r，r+1，…n）

步驟3 lir=（ari-■likukr）／urr（i=r，r+1，…n，r≠n）

求解Ly=b，Ux=y計算公式。

步驟4 y1=b1y1=b1-■likyk（i=2，3，…n）

步驟5 xn=yn=unnxi=（yi-■uikxk）／uii（i=n-1，n-2，…，1）

【例】 用直接三角分解法解2 1 11 3 21 2 2x1x2x3=465

解：由計算公式，得A=11／2 11／2 3／5 12 1 1 5／2 3／2 3／5=LU.

求解Ly=（4，6，5）T，得y=（4，4，3／5）T，

求解Ux=（4，4，3／5）T，得x=（1，1，1）T.

2.克勞特（Crout）分解

直接三角分解法Ax=b（要求A所有順序主子式都不為零）克勞特分解的計算公式如下：

步驟1 u1i=a1i（i=1，2，…n），lil=ail／u11（i=2，3，…n）

計算U第r行，L的第r列元素，i=2，3，…n

步驟2 lli=aij-■likukj，i=1，2，…n，j=1，2，…i，

步驟3 uij=aij-■likuiii=1，2…n-1，j=i+1，…，n

【例】試將下列矩陣進行克勞特分解：A=4 8 42 7 21 2 3

解 首先我們約定，當上限小于下限時，和號“■”取0，根據上式有l11=a11=4，

u12=a12／l11=2，u13=a13／l11=1，

l21=a21=2，

l22=a22-l21u12=3，u23=（a23-l21u13）／l22=0，

l31=a31=1，

l32=a32-l31u12=0，

l33=a33-l31u13-l32u23=2，

則有A=LU=4 2 32 3 01 0 21 2 1 1 0 1

3.三對角方程組的追趕法

在許多科學計算問題中，常常所要求解的方程組為三對角方

程組，即Ax=f

其中A=b1 c1a2 b2 c2 ■■■ cn-1an bn，f=f1f2■fn

并滿足條件b1＞c1＞0bi≥ai+ci，aibn＞an＞0ci≠0，i=2，3，…，n-1

稱A為對角占優的三對角矩陣，將A分解為下三角矩陣L及單位上三角矩陣U的乘積，即A=LU，即

b1 c1a2 b2 c2 ■ ■ ■■ an-1bn-1 cn-1 anbn=l1a2 l2 ■ ■ anln1u1 ■ ■ ■ un-1 1

直接由矩陣充分公式可得

?酌i=ai，?琢1=b1，?琢i=bi-ai?茁i-1，i=2，3，…，n?茁i=Ci/ai，i=1，2，…，n-1

4.平方根法

求解線性方程組時，系數矩陣大多數是對稱正定的，而平方根法就是利用對稱正定矩陣的三角分解而得到的求對稱正定的方程組的一種有效方法，目前在計算機上廣泛應用平方根法解此類方程組，它比一般的分解法大約節省一半的計算量和存儲單元。

定理1 設A為n階對稱陣，且A的所有順序主子式均不為零，則A可唯一分解為A=LDLT

其中L為單位下三角陣，D為對角陣。

定理2 如果A為n階對稱正定矩陣，則存在一個實的非奇異下三角矩陣L使A=LLT，當限定L的對角元素為正時，這種分解是唯一的。

平方根法，其計算步驟如下：

步驟1 ljj=（ajj-■ljk2）1／2，（j=1，2，…，n）

步驟2 lij=（aij-■likljk）／ljj，（i=j+1，…，n）

求解Ax=b，即求如下兩個方程組：

（1）Ly=b，求y； （2）LTx=y，求x；

步驟3 yi=（bi-■likyk）／lii，（i=2，3，…，n）

步驟4 xi=（yi-■lkixk）／lii，（i=n-1，…，1）

另外，由于■ljk2=ajj（j=1，2，…，n）而ljj＞0（j=1，2，…，n）

故有■≤■■

這表明分解過程中矩陣中元素的數量級不增長，因此平方根法計算是數值穩定的。

5.改進平方根法

Cholesky分解法要用到開方運算，為避免開方運算，可將A分解為A=LDLT（其中為單位下三角矩陣），再分別解方程組，這種方法為改進平方根法。

endprint

將對稱正定矩陣A=（aij）n×n進行LDLT分解，則可避免開方運算。其中D=diag（di），且di>0，L為單位下三角矩陣，則

a11 … a1n■ aij ■an1 … ann=1l21 1■■ ■ln1ln2 … 1d1d2 ■dn1 l21 l31 … ln11 l32 … ln2■ ■1

由矩陣乘法，當i≥j時aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對于i=1，2，…，n有lij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復計算，做如下變換A=LDLT=TLT

其中T=LD，即有

1l21 1■ln11d1 d2■ dn1 l21…ln11 ■1=d1t21 d2■■tn1 tn2…dn1 l21…ln1 1 ■ ■ 1

輔助變量tij=lijdj代入（*）式，對i=1，2，…n計算

tij=aij-■tikljk，j=1，2，…，i-1 lij=■，j=1，2，…，i-1di=aii-■tiklik（**）

利用上式得到按行計算L、D各元素的公式，計算順序

d1→l21→d2→l31→l32→d3→l41→l42→l43→……

按照這種方式進行分解，乘法運算次數與LLT分解相當，且不需要開方運算。

計算行列式時，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

等價于求解L（DLTx）=b，可分解成由Ly=b求y，再由DLTx=y求x，這種方法稱為改進平方根法。其計算公式

yi=bi-■likyk，i=1，2，…，nxi=■-■lkixk，i=n，n-1，…，1

【例】用改進平方根法解線性方程組.

3 3 53 5 95 9 17x1x2x3=0-2-4

解：可知系數矩陣對稱正定，設有

3 3 53 5 95 9 17=1l21 1l31 l32 1d1 d2d31 l21 l311 l321

由（**）式可得i=1 di=a11=3

i=2 t21=a21=3，l21=■=■=1

d2=a22-t21l21=5-3×1=2

i=3 t31=a31=5

t32=a32-t31l21=9-5×1=4

l31=■=■

l32=■=■=2

d3=a33-t31l31-t32l32=17-5×■-4×2=■

因此L=11 1■ 2 1D=3 2■

由改進平方根法有11 1■ 2 1y1y2y3=0-2-4

y1=0，y2=-2，y3=0

1 1 ■1 21x1x2x3=d1-1 d2-1d3-10-20=0-10

x1=1，x2=-1，x3=0

矩陣的三角分解是矩陣分解中最基礎的一種，應用領域十分廣泛，它是線性代數的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡化某些復雜方程組的計算過程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規模稀疏或病態矩陣，但利用矩陣的三角分解就可以解決這些問題，因此，矩陣三角分解應用廣泛，我們應該進一步研究。

參考文獻：

［1］沈忱.矩陣的三角分解及其應用研究［J］.長江大學學報，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應用［J］.長春工業大學學報，2011，32（01）:122-154.

編輯 郭曉云

endprint

將對稱正定矩陣A=（aij）n×n進行LDLT分解，則可避免開方運算。其中D=diag（di），且di>0，L為單位下三角矩陣，則

a11 … a1n■ aij ■an1 … ann=1l21 1■■ ■ln1ln2 … 1d1d2 ■dn1 l21 l31 … ln11 l32 … ln2■ ■1

由矩陣乘法，當i≥j時aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對于i=1，2，…，n有lij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復計算，做如下變換A=LDLT=TLT

其中T=LD，即有

1l21 1■ln11d1 d2■ dn1 l21…ln11 ■1=d1t21 d2■■tn1 tn2…dn1 l21…ln1 1 ■ ■ 1

輔助變量tij=lijdj代入（*）式，對i=1，2，…n計算

tij=aij-■tikljk，j=1，2，…，i-1 lij=■，j=1，2，…，i-1di=aii-■tiklik（**）

利用上式得到按行計算L、D各元素的公式，計算順序

d1→l21→d2→l31→l32→d3→l41→l42→l43→……

按照這種方式進行分解，乘法運算次數與LLT分解相當，且不需要開方運算。

計算行列式時，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

等價于求解L（DLTx）=b，可分解成由Ly=b求y，再由DLTx=y求x，這種方法稱為改進平方根法。其計算公式

yi=bi-■likyk，i=1，2，…，nxi=■-■lkixk，i=n，n-1，…，1

【例】用改進平方根法解線性方程組.

3 3 53 5 95 9 17x1x2x3=0-2-4

解：可知系數矩陣對稱正定，設有

3 3 53 5 95 9 17=1l21 1l31 l32 1d1 d2d31 l21 l311 l321

由（**）式可得i=1 di=a11=3

i=2 t21=a21=3，l21=■=■=1

d2=a22-t21l21=5-3×1=2

i=3 t31=a31=5

t32=a32-t31l21=9-5×1=4

l31=■=■

l32=■=■=2

d3=a33-t31l31-t32l32=17-5×■-4×2=■

因此L=11 1■ 2 1D=3 2■

由改進平方根法有11 1■ 2 1y1y2y3=0-2-4

y1=0，y2=-2，y3=0

1 1 ■1 21x1x2x3=d1-1 d2-1d3-10-20=0-10

x1=1，x2=-1，x3=0

矩陣的三角分解是矩陣分解中最基礎的一種，應用領域十分廣泛，它是線性代數的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡化某些復雜方程組的計算過程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規模稀疏或病態矩陣，但利用矩陣的三角分解就可以解決這些問題，因此，矩陣三角分解應用廣泛，我們應該進一步研究。

參考文獻：

［1］沈忱.矩陣的三角分解及其應用研究［J］.長江大學學報，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應用［J］.長春工業大學學報，2011，32（01）:122-154.

編輯 郭曉云

endprint

將對稱正定矩陣A=（aij）n×n進行LDLT分解，則可避免開方運算。其中D=diag（di），且di>0，L為單位下三角矩陣，則

a11 … a1n■ aij ■an1 … ann=1l21 1■■ ■ln1ln2 … 1d1d2 ■dn1 l21 l31 … ln11 l32 … ln2■ ■1

由矩陣乘法，當i≥j時aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對于i=1，2，…，n有lij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復計算，做如下變換A=LDLT=TLT

其中T=LD，即有

1l21 1■ln11d1 d2■ dn1 l21…ln11 ■1=d1t21 d2■■tn1 tn2…dn1 l21…ln1 1 ■ ■ 1

輔助變量tij=lijdj代入（*）式，對i=1，2，…n計算

tij=aij-■tikljk，j=1，2，…，i-1 lij=■，j=1，2，…，i-1di=aii-■tiklik（**）

利用上式得到按行計算L、D各元素的公式，計算順序

d1→l21→d2→l31→l32→d3→l41→l42→l43→……

按照這種方式進行分解，乘法運算次數與LLT分解相當，且不需要開方運算。

計算行列式時，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

等價于求解L（DLTx）=b，可分解成由Ly=b求y，再由DLTx=y求x，這種方法稱為改進平方根法。其計算公式

yi=bi-■likyk，i=1，2，…，nxi=■-■lkixk，i=n，n-1，…，1

【例】用改進平方根法解線性方程組.

3 3 53 5 95 9 17x1x2x3=0-2-4

解：可知系數矩陣對稱正定，設有

3 3 53 5 95 9 17=1l21 1l31 l32 1d1 d2d31 l21 l311 l321

由（**）式可得i=1 di=a11=3

i=2 t21=a21=3，l21=■=■=1

d2=a22-t21l21=5-3×1=2

i=3 t31=a31=5

t32=a32-t31l21=9-5×1=4

l31=■=■

l32=■=■=2

d3=a33-t31l31-t32l32=17-5×■-4×2=■

因此L=11 1■ 2 1D=3 2■

由改進平方根法有11 1■ 2 1y1y2y3=0-2-4

y1=0，y2=-2，y3=0

1 1 ■1 21x1x2x3=d1-1 d2-1d3-10-20=0-10

x1=1，x2=-1，x3=0

矩陣的三角分解是矩陣分解中最基礎的一種，應用領域十分廣泛，它是線性代數的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡化某些復雜方程組的計算過程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規模稀疏或病態矩陣，但利用矩陣的三角分解就可以解決這些問題，因此，矩陣三角分解應用廣泛，我們應該進一步研究。

參考文獻：

［1］沈忱.矩陣的三角分解及其應用研究［J］.長江大學學報，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應用［J］.長春工業大學學報，2011，32（01）:122-154.

編輯 郭曉云

endprint