矩陣三角分解的探討

文/王亞梅

摘 要：矩陣是數(shù)學(xué)中最重要的基本概念之一，是代數(shù)的一個(gè)主要研究對(duì)象，也是數(shù)學(xué)研究及應(yīng)用的一個(gè)重要工具。對(duì)矩陣三角分解的相關(guān)內(nèi)容進(jìn)行系統(tǒng)的介紹，給出分解的思想、分解方法、分解的存在性及分解的條件等相關(guān)內(nèi)容，然后就矩陣三角分解思想研究它在解決具體問(wèn)題中的應(yīng)用。

關(guān)鍵詞：矩陣；三角分解；LU分解

在近代數(shù)學(xué)、工程技術(shù)、經(jīng)濟(jì)理論管理科學(xué)中，大量涉及矩陣?yán)碚摰闹R(shí)，很多問(wèn)題都可以歸結(jié)為矩陣并最終通過(guò)矩陣來(lái)解決。經(jīng)查閱發(fā)現(xiàn)，目前關(guān)于矩陣三角分解的應(yīng)用研究不少，但對(duì)三角分解缺乏系統(tǒng)的研究。

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

一、矩陣的直接三角分解

矩陣的直角三角分解即可以不經(jīng)過(guò)消元步驟，直接將矩陣進(jìn)行分解。

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

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

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

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

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

推論1 奇異矩陣不能進(jìn)行LDU分解。

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

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

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

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

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

二、常用的三角分解公式及其應(yīng)用

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

計(jì)算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計(jì)算公式。

步驟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

解：由計(jì)算公式，得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所有順序主子式都不為零）克勞特分解的計(jì)算公式如下：

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

計(jì)算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

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

解 首先我們約定，當(dāng)上限小于下限時(shí)，和號(hào)“■”取0，根據(jù)上式有l(wèi)11=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.三對(duì)角方程組的追趕法

在許多科學(xué)計(jì)算問(wèn)題中，常常所要求解的方程組為三對(duì)角方

程組，即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為對(duì)角占優(yōu)的三對(duì)角矩陣，將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.平方根法

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

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

其中L為單位下三角陣，D為對(duì)角陣。

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

平方根法，其計(jì)算步驟如下：

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

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

求解Ax=b，即求如下兩個(gè)方程組：

（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）

故有■≤■■

這表明分解過(guò)程中矩陣中元素的數(shù)量級(jí)不增長(zhǎng)，因此平方根法計(jì)算是數(shù)值穩(wěn)定的。

5.改進(jìn)平方根法

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

endprint

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

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

由矩陣乘法，當(dāng)i≥j時(shí)aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對(duì)于i=1，2，…，n有l(wèi)ij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復(fù)計(jì)算，做如下變換A=LDLT=TLT

其中T=LD，即有

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

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

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

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

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

按照這種方式進(jìn)行分解，乘法運(yùn)算次數(shù)與LLT分解相當(dāng)，且不需要開(kāi)方運(yùn)算。

計(jì)算行列式時(shí)，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

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

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

【例】用改進(jìn)平方根法解線性方程組.

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

解：可知系數(shù)矩陣對(duì)稱正定，設(shè)有

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■

由改進(jìn)平方根法有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

矩陣的三角分解是矩陣分解中最基礎(chǔ)的一種，應(yīng)用領(lǐng)域十分廣泛，它是線性代數(shù)的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡(jiǎn)化某些復(fù)雜方程組的計(jì)算過(guò)程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規(guī)模稀疏或病態(tài)矩陣，但利用矩陣的三角分解就可以解決這些問(wèn)題，因此，矩陣三角分解應(yīng)用廣泛，我們應(yīng)該進(jìn)一步研究。

參考文獻(xiàn)：

［1］沈忱.矩陣的三角分解及其應(yīng)用研究［J］.長(zhǎng)江大學(xué)學(xué)報(bào)，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應(yīng)用［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)，2011，32（01）:122-154.

編輯 郭曉云

endprint

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

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

由矩陣乘法，當(dāng)i≥j時(shí)aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對(duì)于i=1，2，…，n有l(wèi)ij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復(fù)計(jì)算，做如下變換A=LDLT=TLT

其中T=LD，即有

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

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

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

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

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

按照這種方式進(jìn)行分解，乘法運(yùn)算次數(shù)與LLT分解相當(dāng)，且不需要開(kāi)方運(yùn)算。

計(jì)算行列式時(shí)，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

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

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

【例】用改進(jìn)平方根法解線性方程組.

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

解：可知系數(shù)矩陣對(duì)稱正定，設(shè)有

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■

由改進(jìn)平方根法有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

矩陣的三角分解是矩陣分解中最基礎(chǔ)的一種，應(yīng)用領(lǐng)域十分廣泛，它是線性代數(shù)的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡(jiǎn)化某些復(fù)雜方程組的計(jì)算過(guò)程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規(guī)模稀疏或病態(tài)矩陣，但利用矩陣的三角分解就可以解決這些問(wèn)題，因此，矩陣三角分解應(yīng)用廣泛，我們應(yīng)該進(jìn)一步研究。

參考文獻(xiàn)：

［1］沈忱.矩陣的三角分解及其應(yīng)用研究［J］.長(zhǎng)江大學(xué)學(xué)報(bào)，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應(yīng)用［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)，2011，32（01）:122-154.

編輯 郭曉云

endprint

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

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

由矩陣乘法，當(dāng)i≥j時(shí)aij=■likdkljk=■likdkljk+lijdj，ljj=1

于是，對(duì)于i=1，2，…，n有l(wèi)ij=（aij-■likdkljk）／dj，j=1，2，…，i-1di=aii-■dklik2（*）

為了避免重復(fù)計(jì)算，做如下變換A=LDLT=TLT

其中T=LD，即有

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

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

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

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

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

按照這種方式進(jìn)行分解，乘法運(yùn)算次數(shù)與LLT分解相當(dāng)，且不需要開(kāi)方運(yùn)算。

計(jì)算行列式時(shí)，由A=LDLT，有

A=LDLT=LDLT=D=d1d2…dn

求解線性方程組Ax=b

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

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

【例】用改進(jìn)平方根法解線性方程組.

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

解：可知系數(shù)矩陣對(duì)稱正定，設(shè)有

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■

由改進(jìn)平方根法有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

矩陣的三角分解是矩陣分解中最基礎(chǔ)的一種，應(yīng)用領(lǐng)域十分廣泛，它是線性代數(shù)的基本分解方法之一，也是求解線性方程組的方法之一，利用矩陣的三角分解求線性方程組的解，可以簡(jiǎn)化某些復(fù)雜方程組的計(jì)算過(guò)程，這是其他求解方程組的方法所不能比擬的。在矩陣求解算法中，直接法或迭代法都不能有效地解決大規(guī)模稀疏或病態(tài)矩陣，但利用矩陣的三角分解就可以解決這些問(wèn)題，因此，矩陣三角分解應(yīng)用廣泛，我們應(yīng)該進(jìn)一步研究。

參考文獻(xiàn)：

［1］沈忱.矩陣的三角分解及其應(yīng)用研究［J］.長(zhǎng)江大學(xué)學(xué)報(bào)，2010，37（03）:55-84.

［2］王群英.矩陣分解方法的應(yīng)用［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)，2011，32（01）:122-154.

編輯 郭曉云

endprint