第2章矩陣變換和計算

2.1矩陣的三角分解及其應用

2.2特殊矩陣的特征系統

2.4矩陣的奇異值分解

I，*

□AllTEaHNOLOGY

2.1矩陣的三角分解及其應用

2.1.1Gauss消去法與矩陣的LU分解。

2.1.2Gauss列主元消去法與帶列主元的LU分解

2.1.3對稱矩陣的Cholesky分解<>

2.1.4三對角矩陣的三角分解▲

2.1.5條件數與方程組的性態?

2.1.6矩陣的2A分解■

DUT嗎"三"〃?零

一

□ALI■支，心二m1d6—,.，TECHMJLWY

Gauss消去法

2.1.1與

矩陣的LU分解

例1消去法求解線性方程組Ax=b

的一個實例。

r(o)

2x}+x2+x3=4'1

r(0)

4%+3X2+3X3+x4=11'2

r(0)

8X]+7X2+9X3+5X4=29'3

r(0)

6xx+7々+9X3+8x4=30'4

第一步，消去今⑼、4°）和q⑼中的用，即用

一不乂八⑼+耳。）、--"：。）+々⑼和J?]x^）+Q（。）得

r（0）

'2x1+x2+x3=4'1

（D

r

x2+x3+x4=32

</⑴

3X2+5X3+5X4=13’3

r（l）

4X2+6X3+8X4=18’4

第二步，消去心⑴和中的I2,即用

(1)(1)

_；X々⑴+-3⑴和-7xr2+r4得

VVk17

'2xr+x2+x3=46(°)

x2+x3+x4=3gD

2X3+2X4=4弓⑵

2/+4%=18產

第三步，消去42）中的/，即用1萬卜個+娟）

得

2%+x2+x3=41⑼

x2+%3+%4=3gi)

2X3+2X4=4勺⑵

2X4=2匕⑶

=>2/12=4

'2x}+%2+￡=4

x2+x3+x4=3—>x2+B-H12=3

2X3+2%4=4=>4

2X4=2=>2X4=^-=1

上述為回代求解過程，得解。x=（L1,1,1）。

Gauss消去法的實質是首先通過一系列的

初等行變換將增廣矩陣(出力)化成上三角增廣

矩陣(Ulc),然后通過回代求與力x=〃三角方程

組Ux=c的解。

我們來觀察Gauss消去法求Ax=b的解,

增廣矩陣(AIb)化成上三角矩陣。Ic)的過程,

如何通過矩陣的變換來實現的。首先，注意

‘2110、（4）

433111

A=b-

879529

[6798,<30,返回

三次消元過程寫成矩陣的形式分別為:

，1、(2110、，2110、

143310111

LXA-—2

—4187950355

「31J(6798,<0468,

、(1110、(2110、

101110111

-3103550022

—41J1°46町(0024,

DU一T

□ALITEOmOLOGY

fl，2110、

10111

L3{L2LXA)—

10022

-11J<0024,

，2110、

0111=u

0022

[0002,

有令人驚奇，而平凡的性質：

(1)4的逆恰好是4本身的每一個對角線以下的元素都取

相反數；即1..

1I

h+l,k1

??

??

??

DUT

一

□ALITEOmOLOGY

事實上，我們定義4=(o???OL「?/J

則心可寫成

Lk=I-Ik。；,

其中,=(0…01。…0)，44=0。而

(f明(/+/.)=/./聞//3

DUT

一

□ALITEOmOLOGY

故4的逆為:<o

10

+

1k+\,k0

1J

n,k°J

(\

1

k+\,k1

n.k

DU一T嗎"三"〃?零

□ALI■支，心二m1d6—,.，TECHMJLWY

則對于例題中的單位下三角陣而言,就有：

riri、ri、

-2111

A二

4=—41-311

1一3—4—1ij

500

、、ri、

21理=1a1

41311

(3ij4ijiij

□ALLTtaHNOLOGY

（2）乘積矩陣上恰好是它們具有的非零對角線以下元素嵌入

到相應位置的單位下三角矩陣。

考慮矩陣乘積SL

=(1+4〃)(1+4+1/+1)

I+1必+4+1線+1

q、

*

*

1

k+l,k1

II二

Lk+2,kLk+2,k+l,

；：1

/71

1bn,k+lJ

DUT

一

□ALITEOmOLOGY

當我們取所有這些矩陣乘積七時，對角線下面的每處都有

同樣方便的性質：

f1

211

上二也1…口=

311321

〃2…I吁1U

\nl

DIJT嗎"三"〃?零

―_?L

□ALI■支，心二血1d6—?.，TECHMJLWY

這樣一來，例題中的計算過程可以表示為

也加4A=4匕狙

令

L=

DUT嗎"三"〃?零

一

□ALI■支，心二血1d6—?.，TECHMJLWY

則由性質(2),可得出L的表達式，即

、r1<1、

211■1

41々=311

(3411J

1

L—=1

1

DU一T

□ALITEOmOLOGY

qfl)

中2111

4131■1

4

(3、iL

，1000、

2100

L=GZH=

4310

1341b

□ALITECHMJLWY

從而有

110、

J81

8392

i649?>

第

照提到矩附啼階初隨分解果存在"階單位下

三角矩陣上和〃階上三角矩陣U,使得

A=LU

則稱其為矩陣力的LU分解，也稱Doolittle分解。

Doolittle方法求解線性方程組：

ZX=5o（LU）X=5

a

LY=B

UX=Y

<

其中z,x,B,y均為矩陣

下面對一般打階方陣A進行LU分解。通過前例

我們可以想到

思路首先將力化為上三角陣,

再回代求解。

DBI■JT

□ALITECHMJLWY

步驟如下:

、

%1

第一步，第1行X+第，行,=2,???，幾

an7

“11a\\aa

“12a.Inb「nAn

⑴

b0嗎a2n娉）

〃21〃22Q02n2

bI0〃n⑴n

yanlan2annn)

運算量:(n-1)X(1+n)

-J*:

第二步:第2行-,,

方r

陽r

QH7

-31

)f1\z1^

\Jbl7

QZ^

2z

>23

z\(2\

04)oQ\l3ZJb7

33

??

??-??

??::?

?

2

olzl\7(2\

］。心a\37P/!

nH

運算量：(n-2)X(1+n-l)=(M-2)M

□ALLTtaHNOLOGY

類似的做下去，我們有:

第左步：第左行x—41r+第，?行，i=k+L..?,〃

VakkJ

運舁里:(〃-Q義(1+n-友+1)=(〃-Q(〃-A+2)

n-1步以后,我們可以得到變換后的矩陣為:

(

aaa

u。12!3\n

0嗎

00<

Q(〃T)n

1°00nne-j

因此，總的運算量為：

n-1

>(n-k)(n-k+2)

攵二1

加上解上述上三角陣的運算量(n+l)n/2,

總共為：

3

n2〃

-----1-n---

33

當〃較大時，它和同階的。

注意到，計算過程中4丁)處在被除的位置，因此整個計算過

程要保證它不為0。所以，Gauss消元法的可行條件為：

(D

akkw0

而這一條件的等價條件是要求力的均不為o,即

an…au

detw0,/=1<?n.

aa

_ilii)

因此，有些有解的問題,不能用Gauss消元求解o

另外，如果某個很小的話，會引入大的誤差。

于是便有了

DUT嗎"三"〃?零

一

□ALI■支，心二血1d6—?.，

Gauss列主元消去法

2.1.2

與

帶列主元的LU分解

1.Gauss列主元消去法

例2在一臺八位十進制的計算機上,用

Gauss消去法解線性方程組

，］一

0823丫

-13.7124.623x22

1.0725.643，%3,

「2a

□ALI

解：在八位十進制的計算機上，經過兩次消元有

-8

f10231、

0.2xlO90.3xlO9O.lxlO9

(AIb)?第三次道元＞0

00.401O90.601O90.201()9

7

(Ulc)

顯然(UIC)有無窮多解.但實際上，det(4)wO,線

性方程組有唯一解。

因此在計算過程中的舍入誤差使解的面目全非了

,這些均是由于小主元作除數所致.

□ALL____iMNSUUL_____TECHMJLWY

Gauss列主元消去法：

為避免小主元作除數、或0作分母，在Gauss消去法

中增加選主元的過程，即在第4步(k=1,2,-1)

消元時，首先在第左列主對角元以下(含主對角元)

元素中挑選絕對值最大的數，并通過初等行交換，

使得該數位于主對角線上，然后再繼續消元。

稱該絕對值最大的數為列主元。

將在消元過程中，每一步都按列選主元的Gauss消去

法稱之為Gauss列主元消去法。

例3用Gauss列主元消去法解例2中的方程組。

(10-8231]

解(/⑶=-13.7124.6232

「21.0725.6433,

r-7-211。0而2-21.05%旃435.643

一纏到逢鼬道冬換.和第邛汐

o6x-RD0..1碑@15啾,16?3吵.5

oc0.1865554L,x100.rri10)J

I0.2到電-8g.3x103

用回代法求(U1c)的解得二(Ulc)

x=(-0.49105820,-0.05088607,0.36725739)r

方程組的精確解為：

x=(-0.491058227,-0.050886075,0.367257384)，

例3用Gauss列主元消去法解例2中的方程組。

(10-8231、

解：(力")=-13.7124.6232

「21.0725.6433)

「二2IfflTO7256S3SI433》、31

0-10.3H7^IDD20.10B.50.5

鼻K3咫兀=(U\c)

yoo一80.201(2oas63?541xQ.0xjl?.^851854)

用回代法求（"。）得數值解為:

x=(-0.49105820,-0.05088607,0.36725739)r

方程組的精確解為：

x=(-0.491058227,-0.050886075,0.367257384)，

□ALL口TECHNOLOGY

2.帶列主元的LU分解

由上述Gauss列主元消去過程可以得到

矩陣的帶有列選主元的LU分解，還是以例1

中的系數矩陣）為例來說明。回憶

1u7

v-L

一iA工-鬟匕

1

1i型J

一1lu233f50=u

I

-1--J11碰

y乂424744《了5初4

口TECHNOLOGY

實際上，上述過程可以表示為

L&P&L°PDL、P\A=U

JJ乙AJLJL

顯然，巴右々似乎并不是一個單位下三角

矩陣.我們將上式改寫為

L3（P3L2P：）（P3P2L】PjP：）（P3P2PJA=U

DUT

一

□ALITEOmOLOGY

由巴的定義知斤=A，即

'oo10、，1000、

0001

0100二尸/

P\

10000010

0OJ

k000b<01

<1000、

0100

0001

1°010J

DU一T

□ALITEOmOLOGY

從而，記(1

1

2

L?=P3L2P3=1

7

3

1

7

(1、

3

1

乙=P3P2“2P3=

1

2

J

1

47

顯然,口和匕分別與4和4結構相同，只是下三

角部分的元素進行相應的對調。從而有

心（乙七心）（心舄4巴|與1）（6巴々）力=U

0

ZZ=&Z；Z；1

32L.{P3P2P^A

令

p=p3P2外L=

則有g010、

0001

P=P3P2PL

0100o

ooo300、

I-

400

12

-

27110

1

^3

4一11

3)

這樣，我們得到另一種形式的矩陣分解:

PA=LU

PALU

一般地,如果力為〃階方陣，進行Gauss列

主元消去過程為：

類似的，可以改寫成：

(Ln工_2工葭)(PNP21)A=U

其中,I=匕1月+14片+i尺1(A=l,2".”-2)

與心的結構相同，只是下三角部分元素經過了

對調。因此，令

L=(LJL『2…必'P=P"1P2Pl

則

PA=LU

定理對任意打階矩陣4均存在置換矩陣

P、單位下三角矩陣七和上三角矩陣U,使得

PA=LU

例用Gauss列主元消去法解如下方程組并給出

以NU分解。

解：1。—6—1-2、

(A\b)=1224

12-211,

1、

4

—2,

,2-211)

第一次消元、nQ37

22

10-6-1-2J

2-211

選列主元，丫2-0>Q_6-1-2

37

03

22>

用回代法求的解得：

5-2H—[5(515丫

%3=77x=------------=--------即

2「【江為

22-6126

F面求相應的R4NU分解

第一次選列主元,交換第1行和第3行，左乘置換矩陣Pi

901、‘0-6-1、，2-21、

010122122

0」21,<0—6—1,

DBI■JT

□ALI

第一次消元,用心左乘(P/),即

(100、-21、(1-21)

3

1012203

~22

1°0b10-6-V1°—6

第二次選列主元,交換第2行和第3行，即左乘置

換矩陣心

r100(2-21、2-21

3

001030—6—1

3

203

<01071°—6-V2>

DUT嗎"三"〃?零

一

□ALI■支，心二血1d6—?.，TECHMJLWY

第二次消元、，用左乘(P2LLPL4),即、

1002-212-21

0100—6-10—6—1=U

131

010300

22)2)

注意:

100

Li=巴上芯=010

1

01

I2)

DUT

一

□ALITEOmOLOGY

則分解應為:

—6—］、

22

-2

1002-21

00°—6—1

11

0100

2八2>

DUT

一

□ALITEOmOLOGY

即有：PA=LU

\(

go1VO-6-111002-21

100122=0100-6—1

11

?i2-2100

。大272>

練習題用列主元Gauss消去法解如下方程組，并利用得到的

上三角矩陣求出det(A)

326、

10-70

解：15-1

，-3264、,10-707、10-707

消元1,61

10-707此@>-32640----o—

1010

6

56,15-15J5:5

0一□一

22J

DBI■JT

□ALI

(A

io-70710-707

55消元55

05＞05

2222

1613131

0600

1010；T5)

從而求得方程組解:二0工2-1

又,’100、，010、g10、

)

P=001100001det(P=1

<01<00b110

則

531

det(PZ)=det(LU戶10x—x——=155,det(N)=155

25

2.1.3對稱矩陣的Cholesky分解

DBI■JT

□ALITECHMJLWY

將對稱正定陣力做LU分解，得到L和U,進一步

“11記為DU

u=

即Z=L（D。），由Z對稱，得L（DU）=UT（DII）

由力的LU分解的唯一性-?L=UT即A=LDE

則L=LD12是下三角矩陣

t己1)1/2=

??小

對稱正定陣的分解為:A=LLT

定理：（ChoIesky分解）

對任意"階對稱正定矩陣A9均存在下三

角矩陣L使A=LU成立，稱其為對稱正定矩

陣力的Cholesky分解.進一步地，如果規定L

的對角元為正數，則上是唯一確定的。

下面研究如何進行對稱正定矩陣的Cholesky

分解。當然，上述的證明過程提供一種計算

Cholesky分解的方法。我們還可以使用下面

將要介紹的直接分解方法。

□ALLTtaHNOLOGY

設

a\\“12aIn(In(InInA

122

a21a22612n21”22

an2ann)InnJ

y^nln2nnJ

利用矩陣乘法規則和利用的下三角結構得到:

%=Zlikljk+lijljj，i=j,j+L…，幾

k=i

□ALLTtaHNOLOGY

用平方根法解線性代數方程組的算法

(1)對矩陣力進行Cholesky分解，即力=上〃,

由矩陣乘法：

對于7=1,2,…,n計算

1

'/T12<j-i)

I..=a：-Yl2

JJJJ一#k9*=，廠E，訪〃力，

V左=17\k=l)

i=/+l,j+2,…，n

計算次序為：

lPr2P1，"22,"32，葉〃2,nno

(2)求解下三角形方程組

(i-i\

/="一2?汝尢""，，=2,3,???坦

Vk=\J

(3)求解上文=丁

居=為〃小玉=y—〃”'

I攵=，+1)

i=〃一1,九一2,???,1

由(J-1后

JJJJ—水

\k=lJ

a

得"力-k=l由此推出▼Ijk-^jj，辛1,2,…,/o

因此在分解過程中上元素的數量級不會增長，

故平方根法通常是數值穩定的,不必選主元。

例用Cholesky方法解線性方程組4rM其中

,4-11、f4]

A=-14.252.75b=6

J2.753.5,s

解：顯然4=4且2=4〉0,。2=16〉0,。3=16>煙此，

為對稱正定矩陣，故存在力=上/7。由分解公式（2?15）和（246）

次計算出L的諸元素：

.=卮="=2,—詈=-0.5,，=>=。.5,

YMl

2

/=J%2-X（）

22J=".25-OS=2,Z31=^^=0.52.75+0.5=1.5,

111

從而得(2、

L=-0.52

、0.51.51?

再利用(2-18)求下三角方程組與『6的解，即得

y-2-3-2,V_%一“IJ_6+1_35

兒2》2q2

為=2二匾J二&二X=7.25—0.5x2—1.5x3.5=1,J=(2,,3.5,1)，

再利用(2-19)求上三角方程組1%可的解，即得

=0.5x(2+0.5-0.5)=1,X=(l,1,l/o

11

2.1.4三對角矩陣的三角分解

設三對角矩陣任g]

“2%。2

A-

b—Ci

<a〃b-

如果矩陣）可以進行LU分解z=/u,其中

(1‘44

l214

,u=

14-i

ijUn>

用追趕法解三對角形方程組的算法

(1)對矩陣力進行LU分解，公式如下:

4=q,z=1,2,-1

—b、

<

=aj%_],i=2,3,…，〃

、%=b「l￡_[,，=2,3,…,〃

計算次序是:

%—j2.“2-A—43―------->%—“

(2)求解下三角形方程組

，=2,3,…,〃

(3)求解幾=>

工小汽/%,%,=(/—c/,+1)/%，

i=〃一1,〃一2,???/

定理設具有三對角形式的矩陣/,滿足條件

(1)間＞同＞。

⑵同＞同〉0

(3)b.＞a.+c.,a.c,0,i=2,3,???〃—l

VL&0c

則方程組4r=/可用追趕法，且解存在唯一。

證由(2-22)和條件(1)知，/=々W圾有°<7l/l-<Ii°

下面用歸納法證明小為。且有0<,<1,，=2,3,…,”1。

假設%產0,0<卜卜隊(2-22)和條件(3),知

%|=。一/￡」>|2|一同之同誹卜同9，=2,3,一、1

Ui-1

故u^0,0<—<1,z=2,3,-??,n-L

/

再應用條件(2),得

"』=|2—乙%|>hH。』鏟>瓦H*l>。。

\Un-\

從而可得det(Z)=det(Z)det(Z7)="J必.乙…it"!LW0,

故方程組4r=/1的解存在唯一。又因為

%|=上一/￡」＞間一同之上?閆明一同尹，=2,3,…,〃

Ui-1

于是有

|可一同＜%＜|修+|%|,且4=弓,明=戶,，=2,3,???,〃

即追趕法計算過程中的中間數有界，不會產生大的變化，從而

說明它通常是數值穩定的。

____iMNSUUL_____TECHMJLWY

定理條件中有。。，如果有某個%=。或

q.=0,則可化成低階方程組求解。

追趕法公式簡單，計算量和存儲量都小。整個求

解過程僅須5〃-4次乘除和3(〃-1)次加減運算，總共

8〃-7次運算。僅需4個一維數組存儲向量c,〃"和f

其中成lh切和“分別存在數組c,〃4和/中。當力對角

占優時，追趕法通常數值穩定。

7

□ALLWLOGY

慚追趕法解線性方程組4r=4其中

,4-10、

A=-14-1b=2

<0-14,9

解利用公式(2-22),4=G=L依次計算出wp/2,w2,/2,w3,/3

諸元素：

b}=u}=4,/2二"二0.25,/=4=4-(-0.25)><(-1)=3.75

u}

%=阻=———=—0.2667,u3=b3—13c2=4—0.2667=3.7331

u23.75

,100、4-10、

L=-0.2510U=03.75-1

、0-0.26671?、003.7333,

再利用(2-23),求下三角線性方程組的解，即得

%=1,為二力-仆％=3+。.25=3.25，

%=力一4-為=2+02667x3.25=2.8667,

7=(1,325,2.8667/o

再利用(2-24)求上三角線性方程組Ur寸的解，即得

退=&=。7679,%;乂一?占=1.071%

U31^2

r

=迎-￡2-0.5179,x=(0.7679,1.0714,0.5179)o

u1

2.1.5條件數與方程組的性態

I，*

□ALLTtaHNOLOGY

考慮線性方程組

(26V?v/ViA’8、

、26.00001人/J18.00001,

它有準確解為：］=(1,1尸。

如果方程組的系數矩陣以及右端項發生微小的

變化，得(26YxA’8、

、25.99999k8.00002y

它有準確解:x=(10,-2)；可以看出，方程組的解變

化非常大。

□ALL____iMNSUUL_____TECHMJLWY

定義如果線性方程組中，N或力的

元素的微小變化，就會引起方程組解的巨大變

化，則稱方程組為“病態”方程組，矩陣4稱

為“病態”矩陣.否則稱方程組為“良態”方

程組，矩陣力稱為“良態”矩陣。

我們需要一種能刻畫矩陣和方程組“病態”

標準的量。

□ALLTtaHNOLOGY

求解時，力和〃的誤差對解式有何影響？

設4精確，b有誤差bb，得到的解為x+即

絕對誤差放大因子

A(.x+x)=b+3b

n8bnIISJUVII/TIIMI仍II

相對誤差放大因子

又IIZ?11=11Axll<IIAII-llxll

115x11<

llxll11/7II

□ALITECHMJLWY

定義設4為非奇異矩陣』?|為矩陣的算子范數,

則稱cond(N)=|同mi為矩陣力的條件數。

常用的條件數為:

cond^Z)=AA~x

00

con。(A)=川JM】

cond(y4)=4ax(44)

9現川L=J小力?)

分別稱為矩陣/的8-條件數、1-條件數和2-條件數。

□ALLTtaHNOLOGY

注意，由/"力=/一14力"力二4一1(力力”)力

det(2Z-1(A4H)A)=det(^-1(2Z-(AA“))/)

=det(^-1)-det(2Z-AAH)?det(Z)

=det(X1—")

貝！J=—4"），|那=心（不力）

2

田］=-4r卬）=兒（，）-才）

=—（（"尸）=力皿（（/4尸）=編（不⑷

故COnd2（/）=A4一1=J/（"""）

22274”?）

矩陣的條件數具有如下的性質：

(1)cond(Z)>1

cond(^)=||A-1|||A||>HA^A]=||/||=1

(2)cond(Z)=cond(^4-1)

cond(ZT)=A-1-(A-1)-1=A-1-||A||=cond(^)

(3)cond(a4)=cond(Z),ow0,aGR

cond((x4)=||cr川.||(crAy11|=|葉Ml?同?^A\

=邱/』=cond(Z)

(4)如果為U(正交)矩陣，則

cond9(Z7)=1

cond2(CM)=cond2(^4Z7)=cond2(^4)

□ALL____iMNSUUL_____TECHMJLWY

cond(Z)越大，解的相對誤差界可能越大,

力對求解線性方程組來說就越可能呈現病態。

但cond(Z)多大力算病態，通常沒有具體的

定量標準；cond(Z)越小，解的相對誤差界越

小，反之，呈現良態。

F面給出兩個與條件數有關的定理

胃階Hilbert矩陣

11、

1

n

[1]11

Hi,j=1,2,…，n

n=(%)”〃2n+\

**

+JT,nxn**

**