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

DUT

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

第2章矩阵变换和计算

2.1矩阵的三角分解及其应用

2.2特殊矩阵的特征系统

2.4矩阵的奇异值分解

修PUT上遂覆吐鎏

dAUANllMVfa*ITYOflECHNDLUCY

2.1矩阵的三角分解及其应用

2.1.1Gauss消去法与矩阵的LU分解，

2.1.2Gauss列主元消去法与带列主元的LU分解

2.1.3对称矩阵的Cholesky分解<>

2.1.4三对角矩阵的三角分解▲

2.1.5条件数与方程组的性态•

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产叫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消去法的实质是首先通过一系列的

初等行变换将增广矩阵(力®化成上三角增广

矩阵(Ulc),然后通过回代求与4r=〃三角方程

组Ux=c的解。

缸DJJT£<

[INIANUMVIfBITVElECHNmUGY

我们来观察Gauss消去法求Zx=〃的解,

增广矩阵(AIb)化成上三角矩阵(UIc)的过程,

如何通过矩阵的变换来实现的。首先，注意

[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

有令人惊奇，而平凡的性质:

(1)的逆恰好是本身的每一个对角线以下的元素都取

相反数；即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）乘积矩阵上恰好是它们具有的非零对角线以下元素嵌入

到相应位置的单位下三角矩阵。

考虑矩阵乘积厂吗

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

++1+1

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

（1、

+2,+2,+1

••

♦・

••

,,+1ij

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

当我们取所有这些矩阵乘积七时，对角线下面的每处都有

同样方便的性质：

T

211

j七…马二31321

21J

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

这样一来，例题中的计算过程可以表示为

令

L=

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

则由性质（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

当较大时，它和同阶的。

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,

\八”

解：在八位十进制的计算机上，经过两次消元有

108231、

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

00.4«1090.6«1090.201()9

=(UIc)

显然(Ulc)有无穷多解.但实际上，det(/)wO,线

性方程组有唯一解。

因此在计算过程中的舍入误差使解的面目全非了

,这些均是由于小主元作除数所致.

DUT

d…一一r・rTECHNDlg

Gauss列主元消去法：

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

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

消元时，首先在第列主对角元以下（含主对角元）

元素中挑选绝对值最大的数，并通过初等行交换，

使得该数位于主对角线上，然后再继续消元。

称该绝对值最大的数为列主元。

将在消元过程中，每一步都按列选主元的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兀“i03nwm)2100.5=(U\c)

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

用回代法求（。।。）得数值解为:

x二(-0.49105820,-0.0508860790.36725739)

方程组的精确解为：

X=(-0.491058227,-0.050886075,0.367257384)

1摩）I>vr]«隹修

2.带列主元的LU分解

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

矩阵的带有列选主元的LU分解,还是以例1

中的系数矩阵）为例来说明。回忆

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

显然,区和工分别与七和4结构相同，只是下三

角部分的元素进行相应的对调。从而有

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的结构相同，只是下三角部分元素经过了

对调。因此，令

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

下面求相应的尸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

则分解应为:

、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

练习题用列主元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分解.进一步地，如果规定L

的对角元为正数，则1是唯一确定的。

DUT

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

下面研究如何进行对称正定矩阵的Cholesky

分解。当然，上述的证明过程提供一种计算

Cholesky分解的方法。我们还可以使用下面

将要介绍的直接分解方法。

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

设

11121121i

21222122222

••

・♦

••

I12

)\12A7

利用矩阵乘法规则和利用的下三角结构得到:

-1

=Z+，=,+i,…,

二1

DLI

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

用平方根法解线性代数方程组的算法

(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¥

因此在分解过程中上元素的数量级不会增长，

故平方根法通常是数值稳定的，不必选主元。

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

设三对角矩阵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

定理设具有三对角形式的矩阵a满足条件

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

(2)||>||>0

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

则方程组4v=/可用追赶法，且解存在唯一。

DUT

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

1

证由(2-22)和条件(1)知，i="现有0<-<°

1

下面用归纳法证明为0且有0<—<1,=2,3，…，-lo

假设户0,0<|上•卜以(2-22)和条件(3),知

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

—1

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

再应用条件（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,・・・,

即追赶法计算过程中的中间数有界，不会产生大的变化，从而

说明它通常是数值稳定的。

定理条件中有,如果有某个=。或

=0,则可化成低阶方程组求解。

追赶法公式简单，计算量和存储量都小。整个求

解过程仅须5〃-4次乘除和3(〃-1)次加减运算，总共

8〃-7次运算。仅需4个一维数组存储向量c,〃"和f

其中"",""和M分别存在数组c,dA和/中。当力对角

占优时，追赶法通常数值稳定。

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条件数与方程组的性态

DLI/一包电笠一，4

工，」

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

考虑线性方程组

V

(161’8、

126.00001人27k8.00001y

它有准确解为：=(1,1)。

如果方程组的系数矩阵以及右端项发生微小的

变化，得(267\(8、

(25.99999JIJ、8.00002,

它有准确解:=(10,-2)；可以看出，方程组的解变

化非常大。

DUT

；

□ALd…一一r・rTECHNDlg

定义如果线性方程组中，/或〃的

元素的微小变化，就会引起方程组解的巨大变

化，则称方程组为“病态”方程组，矩阵4称

为“病态”矩阵.否则称方程组为“良态”方

程组，矩阵Z称为“良态”矩阵。

我们需要一种能刻画矩阵和方程组“病态”

标准的量。

OJJT£

□AL…一