计算方法-第2章 矩阵变换与计算

第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**

**