計算方法-第2章%20矩陣變換與計算

DUT

□AL--------'e…____TE_C_HNDlg

第2章矩陣變換和計算

2.1矩陣的三角分解及其應(yīng)用

2.2特殊矩陣的特征系統(tǒng)

2.4矩陣的奇異值分解

修PUT上遂覆吐鎏

dAUANllMVfa*ITYOflECHNDLUCY

2.1矩陣的三角分解及其應(yīng)用

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

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

2.1.3對稱矩陣的Cholesky分解<>

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

2.1.5條件數(shù)與方程組的性態(tài)?

2.1.6矩陣的0?分解?

□AL.___'i??一?一TECHNDlg

Gauss消去法

2.1.1與

矩陣的LU分解

Dtl

□Al…一小、?二一^--TE-CHNDIDGY

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

的一個實例。

(0)

'2]+2+3=41

(0)

4i+32+33+4=112

<8i+7(0)

2+93+54=293

(0)

、61+7/2+9J.+814=304

第一步，消去「）、：）和「）中的1，即用

-；x「+T_”；。）+￡和|_為并+￡得

VL）\2JV2；

21+2+3=4；。）

（1）

2T+3T+4—-J32

32+5劣+54=13『

42+63+84=184（1）

□AL._____'i??一?一TECHNDlg

第二步，消去3⑴和4⑴中的2,即用

,X、/A\

--義『+3⑴和得

2+2+3=4；。)

2+3+4=3￡

<2+2-4(2)

“3十24—鰭3

23+44=184⑵

第三步，消去廣）中的即用-萬，3⑵+4⑴

得

「2-2+3=4-

⑴

2+3+4=32

<

⑵

23+24=43

(3)

24=24

□AL.____________'.e:1:?■1?.一TECHNDlg

,2]+2+3=4n2產(chǎn)叫42=4

2+/4=3)>2豐居M2=3

23+24=4=>Z^ffi42=4

<24=2=>24=2=1

上述為回代求解過程，得解。=(1,1,1,1)O

Gauss消去法的實質(zhì)是首先通過一系列的

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

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

組Ux=c的解。

缸DJJT￡<

[INIANUMVIfBITVElECHNmUGY

我們來觀察Gauss消去法求Zx=〃的解,

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

如何通過矩陣的變換來實現(xiàn)的。首先，注意

[2110、（4）

433111

A-b=

879529

1679句130J返回

DLI

□AL--------'e…____TE_C_HNDLg

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

□Al._____'i??一?一

0、

Z3（Z2Z1^4）=

22

24>

，2110、

0111

=u

0022

、0002,

□AL.____________'.e:1:?■1?.一TEC、HNDlg

注意單位下三角矩陣

1

7

有令人驚奇，而平凡的性質(zhì):

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

相反數(shù)；即I1.

獷=1

旬1

9

DLT

□AL.___'i??一?一

事實上，我們定義I=(0???0

+1

則Lk可寫成

其中。=((h..010…0),eI=0。而

++

□AL---「.--?ITECHNDlg

故的逆為:<1fo、

10

廠=++

卜1a0

uI

r、

J

□AL.____________'.e:1:?■1?.一TECHNDlg

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

50。

1、0

心211

141

1J〔11>

DLI

□AL--------'e…____TE_C_HNDlg

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

到相應(yīng)位置的單位下三角矩陣。

考慮矩陣乘積廠嗎

匕七：=（+）（++i+i

++1+1

=+++i+「+1+1―

（1、

+2,+2,+1

??

??

??

,,+1ij

□AL.____________'.e:1:?■1?.一TECHNDlg

當(dāng)我們?nèi)∷羞@些矩陣乘積七時，對角線下面的每處都有

同樣方便的性質(zhì)：

T

211

j七…馬二31321

21J

□AL.____________'.e:1:?■1?.一TECHNDlg

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

令

L=

□AL.____________'.e:1:?■1?.一TECHNDlg

則由性質(zhì)（2）,可得出1的表達式，即

（

、(1

211

4131

1J41J

111

L=Z1Z2Z3=

BUT

□AL.___'i??一?一TECHNDlg

、

fl

2

廳=4311

4

、3711>

X000、

2100

L==

4310

13411>

照提到矩附肺階的隨分解果存在〃階單位下

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

A=LU

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

□AL.____________'.e:1:?■1?.一TECHNDlg

Doolittle方法求解線性方程組:

AX=BO（LU）X=B

LY=B

<

<UX=Y

其中力，x,B,y均為矩陣

DLI/一包電笠一，4

且-‘

□AL…一分小?二一^---TECHNDIDGY

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

我們可以想到

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

再回代求解。

DUT

□ALTECHNDlg

步驟如下：

(\

第一步，第1行X—-+第行,

InJ

???11

11121

(1)(1)

22

2122…2

(1)(1)

7

\12

運算量：(〃一1)X(1+n)

DUT

□Al…一小—一r?rTECHNDlg

第二步:第2行

(121311

1112i⑴(1)⑴⑴

（i）222322

2⑵(2)(2)

03333

（i）

⑵(2)(2)

03

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

□AL--------'e…____TE_C_HNDlg

類似的做下去，我們有:

/(-1)、

第步：第行+弟彳丁，=???

Ax(-D+1,,

k7

運算量：(〃-QX(1+n-九+1)=(〃-左)(〃-A+2)

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

11121311

(1)(1)(1)(1)

02223.22

(2)(2)(2)

0033…33

**??**

**??**

*****

(-1)(-1)

0007

□AL--------'e…____TE_C_HNDlg

因此，總的運算量為：

Z(-)(-+2)

加上解上述上三角陣的運算量U+l)nd、

總共為：

3

-----F2----

33

當(dāng)較大時，它和同階的。

DLI力M黎三力鎘

□AL--------'e…____TE_C_HNDlg

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

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

(7W0

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

、

a1

1j

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

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

于是便有了

□AL.____________'.e:1:?■1?.一TECHNDlg

Gauss列主元消去法

2.1.2

與

帶列主元的LU分解

DUT

□AL--------'e…____TE_C_HNDlg

1.Gauss列主元消去法

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

Gauss消去法解線性方程組

10823丫1、，1、

二

-13.7124.62322

I-21.0725.643I3,

\八”

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

108231、

(力1〃)第三次消元>00.2xlO90.3xl090.1xlO9

00.4?1090.6?1090.201()9

=(UIc)

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

性方程組有唯一解。

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

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

DUT

d…一一r?rTECHNDlg

Gauss列主元消去法：

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

中增加選主元的過程，即在第4步（=1,2,…，-1）

消元時，首先在第列主對角元以下（含主對角元）

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

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

稱該絕對值最大的數(shù)為列主元。

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

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

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

10823P

解(A\b)=-13.7124.6232

-21.0725.6433

(-121No*21.055^435.6433?、

隨；型畦城至軍換一跖0和o第序品.里那x4PD.W3慚.5

o

0.2X-81865xlo

I?！?f^xio3°:1o'

用回代法求（U1c）的解得二（Ulc）

x二(-0.49105820,-0.05088607,0.36725739)

方程組的精確解為：

X=(-0.491058227,-0.050886075,0.367257384)

DUT

□AL--------'e…____TE_C_HNDlg

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

”8231、

解：(41〃)=-13.7124.6232

-21.0725.6433

72560433》13

飛岑g?！癷03nwm)2100.5=(U\c)

yoo80.201(2O.a^6SS541xai><Jl(ft^851854)

用回代法求（。?。）得數(shù)值解為:

x二(-0.49105820,-0.0508860790.36725739)

方程組的精確解為：

X=(-0.491058227,-0.050886075,0.367257384)

1摩）I>vr]?隹修

2.帶列主元的LU分解

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

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

中的系數(shù)矩陣）為例來說明?；貞?/p>

z

/

k

K

=u

DIJT

-----'e…____.—TECHNOLOGY

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

L3P3L2P2LJ1A=U

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

矩陣.我們將上式改寫為

，3（巴46戈巴巴4巴1耳，（巴巴4）/=U

B,I?U■)T

□AL.___'i??一?一TECHNDlg

由P的定義知尸二p,即

<000、000、

000000

p?==pj

000000

0

00J100J

000、

000

p，

000

1000J

BU?T

Jiw■1_w.

□AL.______'i??一?一TECHNDlg

從而，記

2

A=P3L2P3=

7

3

7J

了

工=P3P2^2「3￡

~2

4j

DUT

□AL--------'e…____TE_C_HNDlg

顯然,區(qū)和工分別與七和4結(jié)構(gòu)相同，只是下三

角部分的元素進行相應(yīng)的對調(diào)。從而有

L3S3L2P3、（P3P2L1Plp（乙巴4）N=U

0

4

z3L24（4巴=4￡七

令

111

p=p3PzP1，L=Z；Z2Z3

□AL.____________'.e:1:?■1?.一TECHNDlg

則有f000、

0001

P=P3P2PLA.

001

ooo3000、

-

400

1

-

L=二二后二210

1

-

411

3J

□AL.____________'.e:1:?■1?.一TECHNDlg

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

PA=LU

“371加

ALU

□AL.____________'.e:1:?■1?.一TECHNDlg

一般地，如果/為階方陣，進行Gauss列

主元消去過程為：

L

類似的，可以改寫成：

（L/2…工工）（P1…巴

--------'e…______

其中,L=P+1LP+1-P（左=1,2,..”〃一2）

與L的結(jié)構(gòu)相同，只是下三角部分元素經(jīng)過了

對調(diào)。因此，令

L=(L_J1

2WP=P?P2Pl

則

PA=LU

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

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

PA=LU

DUT

□AL------------------..TECHNOLOGY

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

P4=LU分解。

解：(0—6—1—2、

（川〃）=1224

（2—211?

2-211

選列主元，2—3>0—6-1-2

37

03

22>

—先迎溫

□AL--------'e…____TE_C_HNDlg

用回代法求的解得：

5-2-\—[(55、

=--即X=

322--6126I6122J

下面求相應(yīng)的尸ZNU分解

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

001、0-6-1、，2-21、

010122122

12.21,

0°，—6—1,

第一次消元，用乙左乘(PM),即

r100V2-21A(2-21)

3

3

2

—6

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

換矩陣巴

DLT

□AL.___'i??一?一

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

002-22-2

000-10—6

3

00300

2j2>1)

注意:

100

右=P2LJ2~010

1

01

I2)

□AL.____________'.e:1:?■1?.一TECHNDlg

則分解應(yīng)為:

、zA

/、f

1oOloO21

O

-01o1O0;

1Io1I-1

-o0

一

一2

2/I2/k7

□AL.____________'.e:1:?■1?.一TECHNDlg

即有:PA=LU

((

<00<0—6002-2

1002200—6

0人2-200

1°7I22727

DUT

□AL--------------'e…_______T_E__C__HNDLg

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

上三角矩陣求出det()

，-326V1附

10-7027

5八37

解：15-1

326<10-707、10-707

,，消元1/61

10-707——3264------->0--------O—

1010

5615-156J

15-1>0959

22J

DLI

□AL--------'e…____TE_C_HNDlg

A

10-7o710-7o7

55消元）55

0505

2222

613131

0600

10io>~5

從而求得方程組解:二02~

又,<10r00、(010)

det(P)=1

0000001

(010J(0000J

則

det(PN)=det(￡t/)^10x-x—=155,det(z)=155

25

□AL.____________'.e:1:?■1?.一TECHNDlg

2.1.3對稱矩陣的Cholesky分解

/r工落"

TtCHNDLDGY

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

記為DU

U=

即4=上00),由/對稱，得L(pu}^uT(p￡]

由力的LU分解的唯一性—L=UT即A=LDL

則L=LD1/2是下三角矩陣

t己I)1。=

??丁

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

□ALTECHMlg

定理：（ChoIesky分解）

對任意打階對稱正定矩陣A,均存在下三

角矩陣上使4=3成立，稱其為對稱正定矩

陣N的Cholesky分解.進一步地，如果規(guī)定L

的對角元為正數(shù)，則1是唯一確定的。

DUT

□AL--------'e…____TE_C_HNDlg

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

分解。當(dāng)然，上述的證明過程提供一種計算

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

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

□AL.____________'.e:1:?■1?.一TECHNDlg

設(shè)

11121121i

21222122222

??

??

??

I12

)\12A7

利用矩陣乘法規(guī)則和利用的下三角結(jié)構(gòu)得到:

-1

=Z+，=,+i,…,

二1

DLI

□AL--------'e…____TE_C_HNDLg

用平方根法解線性代數(shù)方程組的算法

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

由矩陣乘法：

對于J=l,2,-?-,n計算

1

（-1、萬（-1

-X2-Z/

9

1=1）\=17

i=j+Lj+2,…，n

計算次序為：

11，21，22,32,2,O

□AL.____________'.e:1:?■1?.一TECHNDlg

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

1=Ju，-S/

(3)求解上勺=『

得-z2,由此推出|H「，^i,2,-jo

=1￥

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

故平方根法通常是數(shù)值穩(wěn)定的，不必選主元。

DLI力M黎三力鎘

□AL----------------'e…________T__E__C__HNDLg

例用Cholesky方法解線性方程組4r=〃，其中

(4-11)(4]

A=-14.252.75b=6

、12.753.5,"5,

解：顯然H=4且i=4〉0,2=16〉0,3=16>(0此,

為對稱正定矩陣，故存在由分解公式（2-15）和（2?16）

次計算出L的諸元素：

生=-0531=3_=0.5,

1111

—2迎&X?

2222-214.25—0.52=2,31=上=0.5(275+0.52)=1.5,

11

22

33-彳-32=73.5-0.5-1.5=1

33.

DLI力M黎三力鎘

□AL----------------'e…________T__E___C_HNDlg

從而得2

L--0.52

0.51.57

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

1_2211

1——2.2―

11r22

_3-31132

。

3-2=7.25—0.5x2-L5x3.5=l,y=(2,,3?5,l)

33

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

2—32?2_3?5-1?5_]

3且二一二1,2=

331222

1212

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

11

□AL.____________'.e:1:?■1?.一TECHNDlg

2.1.4三對角矩陣的三角分解

ODUI、

□AL.___'i??一?一TECHNDlg

設(shè)三對角矩陣i

222

A=

—1

7

如果矩陣）可以進行LU分解ANU,其中

-1—1

77

少通勰立力i

□AL--------'e…____TE_C_HNDlg

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

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

=,=1,2,…，-1

1=1

=/_「=2,3,…，

=-i.=2,3,???,

計算次序是:

1―2—2—3.3>

□AL.____________'.e:1:?■1?.一TECHNDlg

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

—1，=2,3,???,

(3)求解以=7

+1〃

—1,-2<>1

□AL?，一TECZlg

定理設(shè)具有三對角形式的矩陣a滿足條件

(1)|i|〉|i|〉O

(2)||>||>0

(3)||>||+||,。0,=2,3,…-1

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

DUT

□AL------------------..TECHNOLOGY

1

證由(2-22)和條件(1)知，i="現(xiàn)有0<-<°

1

下面用歸納法證明為0且有0<—<1,=2,3，…，-lo

假設(shè)戶0,0<|上?卜以(2-22)和條件(3),知

=—1>—>||~||=2,3,…，-1

—1

故。0,0<—<1,=2,3,…，-lo

再應(yīng)用條件（2）,得

一1>>Oo

—1>

—1

DUT

□AL--------'e…____TE_C_HNDLD6Y

從而可得det(Z)=det(Z)det(Z7)=x2---W0,

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

一>>||-||—二，

=-一J1L>2,3,…

-1

于是有

—<<+,且=，=,=2,3,???,

即追趕法計算過程中的中間數(shù)有界，不會產(chǎn)生大的變化，從而

說明它通常是數(shù)值穩(wěn)定的。

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

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

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

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

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

其中"",""和M分別存在數(shù)組c,dA和/中。當(dāng)力對角

占優(yōu)時，追趕法通常數(shù)值穩(wěn)定。

7

DUT

□ALFNOLOGY

仞I追趕法解線性方程組4r=仇其中

4-10、

A=-14-1b=2

、0-14,

解利用公式(2-22),==1膿次計算出1，2，2，2，3，3

諸元素：

[=]=4,2=二二0.25,2=2_21=4_(-0.25)X(-1)=3?75

1

二-=-0.2667,=_-4-0.2667=3.7331

3——JJJ/

23.75

DUT

□AL------------------..TECHNOLOGY

/100、4-10、

Z=-0.2510U=03.75-1

、0-0.2667L003.7333,

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

.=1,2=?—[=3+0.25=3.25,

J=J-J--N2+0.2667x3.25=2.8667,

7=(1,3.25,2.8667)。

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

3=」=0.7679,2=2—2.3=1.0714,

32

1==0.5179,x=(0.7679,1.0714,0.5179)。

1

□AL.____________'.e:1:?■1?.一TECHNDlg

2.1.5條件數(shù)與方程組的性態(tài)

DLI/一包電笠一，4

工，」

□AL…一分小?二一^-------TECHNDIDGY

考慮線性方程組

V

(161’8、

126.00001人27k8.00001y

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

如果方程組的系數(shù)矩陣以及右端項發(fā)生微小的

變化，得(267\(8、

(25.99999JIJ、8.00002,

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

化非常大。

DUT

；

□ALd…一一r?rTECHNDlg

定義如果線性方程組中，/或〃的

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

化，則稱方程組為“病態(tài)”方程組，矩陣4稱

為“病態(tài)”矩陣.否則稱方程組為“良態(tài)”方

程組，矩陣Z稱為“良態(tài)”矩陣。

我們需要一種能刻畫矩陣和方程組“病態(tài)”

標準的量。

OJJT￡

□AL…一