數(shù)值分析講稿

§4.

消去法的變形二、平方根法工程實際計算中，線性方程組的系數(shù)矩陣常常具有對稱正定性，即其各階順序主子式及全部特征值均大于零。矩陣的這一特性使它的三角分解也有更簡單的形式，從而導出一些特殊的解法，如平方根法與改進的平方根法。定理：設A是對稱正定矩陣，則存在唯一的非奇異下三角陣L,使得A

LLT且L的對角元素皆為正.定理證明（1）111111

121u1nu12uuu22u22uu

u

u

u

11n

11

U

unn

unn

證：因A對稱正定，其各階順序主子式均大于零，故有A

LU

其中L為單位下三角矩陣，U為上三角陣。令D

diag(u

,

,u

),

P

D1U

,則P為單位上三角陣。11

nn

DP

n1,n

un1,n1

A

PT

DP故

A

LU

LDP

AT

PT

DLT由LU分解的唯一性

PT

L定理證明（2）uiiu11

D1

0,

Di

/

Di1

0(i

2,

3, ,

n)由于A是對稱正定的,其順序主子式均大于零。故T令

D

diag

(

u11

,

,

unn

)

D

D

D則A

PT

DP

PT

DT

DP

(DP)T

DP

LLT其中L

(DP)T

為非奇異下三角陣,且對角元素皆為正數(shù)。唯一性：假定存在非奇異下三角陣G

L,其對角元素皆為正數(shù)，且使得

A

LLT

GGT

于是有LT

(GT

)1

L1LLT

(GT

)1

L1GGT

(GT

)1

L1G因LT

(GT

)1為上三角陣，L1G為下三角陣，故由上式得LT

(GT

)1

L1G

I即G

L,與假設

。平方根(Cholesky分解法）法2)2jj

jjjkl2122lllll0

llj

1k

10

0

l11ln1

l11l

0

21

22

0

n2

l

0

n1

n

2nn

nn

0

(i

1,

2,(

j

1,

2,

,

n),

(aij由A

LLT其中l(wèi)ii,n).由矩陣乘法及l(fā)

jk

0(當j

k時),1得0(i

j

1,

,

n);j

1k

1l

(a

lij

likljk

)

/

l

jj這里規(guī)定

0。計算順序是按列進行，即k

1l11

li1

(i

2,3,

,n)

l22

li

2

(i

3,

,n)

。i1k

i1(i

1,

2, ,

n).(i

n,

n

1,

,1).yi

(bi

lik

yk

)

/

liik

1nxi

(

yi

lki

xk

)

/

lii當矩陣A完成平方根分解后，求解Ax

b，即求解兩個三角形方程組(1)Ly

b,

求y;

（2）LT

x

y，求x.由于A的對稱性，平方根法的乘除運算量為n3/6數(shù)量級，約是Gauss消去法的一半。上機計算時，所需單元也少，只要A的下三角部分和右端項b，計算中L存放在A的單元，y,x

在b的單元.但這種方法在求L時需作n次開方運算，這樣又增加了計算量，為了避免開方，可使用改進的平方根方法.改進平方根法21dll

1lA

LDLT

21

d1

l1

d

n

ln1

n1

n

21

l21

1n

2

1

其中l(wèi)jj

1,

l

jk

0

(

j

k

),由比較法得2i

iiik

kiiiiik

ikjil

d

;t

l

;,

n).i1k

1i1k

1i1k

1d

a

l

ji

(a

ji

)

/

d

(

j

i

1,

,

n).d

a

l

(a

)

/

d

(

j

i

1,ljk

dklik對于i

1,

2,

,

n,上式雖避免了開方運算，但增加了相乘因子，引進變量

對于i

1,

2,

,

n,

有i1tik

lik

dkji

tikljk

ik

1,

2,1.i

i

ik

kni

i

i

ki

ki1k

1k

i1i

2,

,

n;xn

yn

/

dn

;i

n

1,

y

b

l

y

,

x

y

/

d

l

x

,對稱正定矩陣A按LDLT

分解和按LLT分解計算量差不多，但LDLT

分解不需要開方計算。求解Ly

b,

DLT

x

y計算公式

y1

b1;三、追趕法2222

2iiai

bi

ci

b1

c1

d1b

c

x1

a

x

d

x

d

an1

bn1

cn1

xn1

adn1

d

b

x

n

n

n

n

在數(shù)值計算中，如三次樣條插值或用差分方法解常微分方程邊值問題，常常會遇到求解以下形式的方程組簡記Ax

d.此系數(shù)矩陣的非零元素集中分布在主對角線及其相鄰兩次對角線上，稱為三對角矩陣。方程組稱為三對角方程組。22i

i

in

nc1u

ccln

un

b1

c1

0

b

a

c

,

b

a

0l

21A

LU

l3

1n1

u1

1

aici

0(i

2,3,

,n

1)對角占優(yōu)定理：設三對角方程組系數(shù)矩陣滿足下列條件：則它可分解為

1其中ci

(i

1,

2, ,

n

1)為已給出的，且分解是唯一的定理證明（1）ii

i

i1i i1

i

ii

i

i1i i1

ia

l

u

(i

2,

3,

,

m)b

c

l

uu1

b1

l

a

/

u(i

2,

3,

,

m)u

b

c

l將上式右端按乘

則展開,并與A進行比較,得b1

u1如果ui

0

(i

1，2,,m)，則由上式可得定理證明（2）1

1(k

)nu

can1

bn1

cn1

a

bA

n

ck

1ak

/

uk

1

(k

2,

3,按Gause消去法步驟易得，經(jīng)k

1次消元后，三對角方程的系數(shù)矩陣變?yōu)槠渲衭k

bk,n)。kka

bcan

bnck

1b

cn1

n1n1

uk

ck

ak

1

bk

1

ck

1Ob1

c1O

O0

uk

1akO

OO定理證明（3）21

1

1

1u

b

bb

c1a2

b1b2

c1a2

b1b2

c1a2

b1c2u2

b2

c由于A滿足定理所給條件，顯然有

u1

b1

0.又因為

b1

c1

,

b2

a2

c2

,

于是b1b2

b1a2

b1c2

c1a2

b1c2故u2

0且矩陣A

仍滿足定理條件。依此類推可得出(2)ui

0(i

1,2,L

,n)。因此由上面公式唯一確定了L和U。1

1n

n

b

c

0

ci

bi

ai

b

a

0aici

0(i

2,

3,,

n

1)從而有uk

bk

ck

1ak

/

uk

1

(k

2,

3, ,

n)追趕法的計算公式,

m);,

n);i

i1k

k

k

k

1k

k

k

1

ku1

b1

iu

b

c

l

i

i i1

i

y1

d1

y

d

l

y(k

2,

3,x

(

y

c

x

)

/

u(k

n

1,

n

2,

,1).

kA

LU分解公式：

l

a

/

u

(i

2,

3,解Ly

d得：再解Ux

y得:

xn

yn

/

un追趕法的基本思想與Gauss消去法及三角分解法相同,只是由于系數(shù)中出現(xiàn)了大量的零,可使計算公式簡化,減少了計算量。可證,當系數(shù)矩陣為嚴格對角占優(yōu)時,此方法具有良好的數(shù)值穩(wěn)定性?！?.向量和矩陣的范數(shù)一、向量范數(shù)向量范數(shù)定義:設對任意向量x

Rn

,

按一定的規(guī)則有一實數(shù)與之對應,記為

x

,

若

x

滿足1,x

0

,且x0當且僅當

x

0;

(正定)2,x

x,為任意實數(shù)

(齊次)3,x

yxy,

對任意x,y

Rn(三角不等式)則稱

x

為

向量x的范數(shù).向量范數(shù)例2122nix

)i1x

x2

x2

(1

n1nx

x1

xn

xii

11inx

max{

x1

,,

xn

}

max{

xi

}npip1/

px

i

1

x1in

1in1in

1in

max

xi

max

yi

x

y

可驗證上面范數(shù)均滿足范數(shù)定義的條件。以-范數(shù)為例:滿足條件1,2顯然。由于x,

y

Rn為向量，而其分量x

,

y

(i

1,

,

n)i

i為實數(shù)，故有x

y

max

xi

yi

max

xi

yi

例：計算向量x

(1,2,3)T

的各種范數(shù)。解：

x

6,

x

3,

x

14.1

2如果Rn中兩個范數(shù)

和

'

，存在實數(shù)m,M

0，使得對任意n維向量x,都有m

x

x

'

M

x

，則稱這兩個范數(shù)是等價的。對兩個等價范數(shù)而言，同一向量序列有相同的極限。21

2i

1x2xx2nnxn1in1in

2

x2

x2

x

.2

n

max

xi

.

x2

x22

n

2

x

x不難證明，1－范數(shù)，2－范數(shù)和－范數(shù)是等價的。例：

x

max

x

設

x

x

j則

x

x

j

2－范數(shù)和－范數(shù)等價。如不作說明，今后

是指任意一種向量范數(shù)。二、矩陣的范數(shù)定義：對任意n階方陣A，按一定的規(guī)則由一實數(shù)與之對應，記為

A

。若

A

滿足1,

A

0

,

且

A

0當且僅當

A

0;

(正定)2,

A

A

,

為任意實數(shù)

(齊次)3,4，A

B

A

B

,

對任意A,B兩個n階方陣(三角)AB

A

B

（相容性條件）則稱A

為矩陣A的范數(shù)。xxxxxx

1Ax

A

xx

xA

max

Ax

max

Ax定理：設A為n階方陣，

是Rn中的向量范數(shù)，則A

max

Ax

是一種矩陣范數(shù)，稱其為由向量范數(shù)

誘導出的矩陣范數(shù)。證：設A

(aij

)為任意n階方陣，x為任意n維非零向量。因為x

為范數(shù)是1的單位向量，故x

xxx

y

1

x

1max

Ax

max

A

x

max

Ay

max

Axxxxx

1x

1Ax

0

Ax

A

0.

max

Ax

A

.x

11，顯然

A

0.若A

0,則

A

max

Ax

0.反之，若

A

0

2，

A

max

Ax

max

Axx

1

x

13,對任意兩個n階方陣A和B，A

B

max (

A

B)x

max

Ax

Bxx

1

x

1

max(

Ax

Bx

)

max

Ax

max

Bxx

1

x

1

x

1

A

B

.xxx

1A

max

Ax

max

AxAxx4，對任意n維非零向量x,有

A

即

Ax

A

x

.故有

AB

max

(

AB)x

max

A(Bx)x

1

x

1

max

A

Bx

max

A

B

xx

1

x

1

A

B5，對任意n維向量x，都有

Ax

A

x

。這一性質稱為矩陣范數(shù)與向量范數(shù)的相容性。可由三種常用的向量范數(shù)誘導出矩陣范數(shù)。xxA

max

Ax21

12

2Tx

1A

max

Ax

其中

是

A

A,

的最大特征值。又稱為譜范數(shù)。設A

(aij

)為n階方陣。矩陣范數(shù)例與前述三種向量范數(shù)相容的三種矩陣范數(shù)：1

1nx

1

1i1A

max

Ax

max1

jnaij

,

為矩陣的列向量的1－范數(shù)的最大值稱為矩陣的列和范數(shù)。1nj

1A

max

Axx

1

max1inaij

,

為矩陣的行向量的1－范數(shù)的最大值稱為矩陣的行和范數(shù)2

1

2如果將矩陣范數(shù)看作Rn

空間上的向量范數(shù)，則由向量范數(shù)的等價性可得矩陣范數(shù)的等價性。例：A

34

,計算A的各種范數(shù)。

解：

A

6,

A

7,

A

5.46.1

2矩陣的誤差可用矩陣范數(shù)表示：設A*是A的近似矩陣，A

A*

、A

A*

/

A

分別稱為A*的關于范數(shù)

的絕對誤差與相對誤差。矩陣A的譜半徑i1in(i

1,

2,

(

A)

max

i定義：設A

Rnn的特征值為,n)

稱(

Ax

x

x

,

Ax

A

x

x

A

x

A

(

A)

A

)定理：

(

A)

A為A的譜半徑。,

A

為

A

的任意矩陣范數(shù).§5.誤差分析一、矩陣的條件數(shù)x

1.00001x

2

x

0

1

2

2

x1

1.x

1.00001x

2.00001x

1

1

2

2一個實際問題化為數(shù)學問題，初始數(shù)據(jù)往往會有誤差，即有擾動，從而使計算結果產生誤差。例：方程組

x1

x2

2

x1

2

.而方程組

x1

x2

2比較這兩個方程組可以看出，他們只是右端項有微小的差別，最大相對誤差為1

105

,但它們的解卻大不相同，解分量21的相對誤差至少為。2定義：如果矩陣A或常數(shù)項b的微小變化，引起方程組Ax

b解的巨大變化，則稱此方程組為“”方程組，矩陣A稱為“”矩陣（相對于方程組而言）。否則稱方程組為“良態(tài)”方程組，A稱為“良態(tài)”矩陣。矩陣的“

”性質是矩陣本身的特性。為了定量刻劃方程組的“

”程度，下面對方程組Ax

b就系數(shù)矩陣或右端項分別有擾動的兩種情形進行

。右端項b的擾動對解的影響Ax

bA

AAbxb

b

b

xA1A1A1A1A

x

b

x

A1

b

x

A1

b

b設b有擾動

b，相應解x的擾動記為

x,即A(x

x)

b

b由Ax

b，兩邊取范數(shù)又因為

x

A此式表明,當右端項有擾動時,解的相對誤差不超過右端項的相對誤差的

A

倍。系數(shù)矩陣A的擾動對解的影響AAxA

A

x

A

A

x

AA1A1A1A11

x

A1

A(x

x)

A

(

x

x

)1

A1

A1

A

A如果右端項無擾動，系數(shù)矩陣A有擾動

A，相應的解x的擾動仍記為

x,則(

A

A)(x

x)

b

A

x

A(x

x)

0如果

A充分小，使得

A1

x

(1

A1

A

)

A

1,則由上式得A1A1上式表明，當系數(shù)矩陣有擾動時，解的擾動仍與A有關。一般地，A

越大，解的擾動也越大。條件數(shù)的定義max222min.vA-1

(

AT

A)

(

AAT

)A1A1(1)

cond

(

A)

cond

(

A)

A

綜上分析可知,量

A-1 A實際上刻劃了解對原始數(shù)據(jù)變化的靈敏程度,即刻劃了方程組的“

”程度。定義：設A為非奇異陣，稱數(shù)cond

(A)v

A

(v

1,2或v）為矩陣A的條件數(shù)。常用的條件數(shù)，有(2)

A的譜條件數(shù)2,n

1當A為對稱矩陣時，cond

(A)其中1，n為A的絕對值最大和絕對值最小的特征值。Au

u

u

A1u

A1u

1

uA

條件數(shù)的性質A

A1

A

I

1.v

v1、對任何非奇異矩陣A，都有cond

(A)v

1.1由定義

cond

(

A)v

Av2、設A為非奇異矩陣且c

（0

常數(shù)），則cond

(cA)v

cond

(

A)v3、如果A為正交矩陣，則cond

(A)2＝1；

如果A為非奇異矩陣，R為正交矩陣,則cond

(RA)2

cond

(

AR)2

cond

(

A)2

.max22min.

(

AT

A)

(

AT

A)1cond

(

A)2

A

A

1121111n

1

1

3Hn

2

n

1

1

n

1

n2n

1例：Hilbert矩陣計算H3的條件數(shù)。n(1)

H3(

)同

可計算一般陣當0.500

0.3333

0.

5簡記為(H3

H其解為x

xH3

b

x

(0.0895,

0.5120,

0.4910)T

H3

0.18103

0.06%

b

0.182%,

x

0.5120

51.2%.x

1由于x

x

(1.0895,0.4880,1.491)T

,x

(1,1,1)T這表明H3與b相對誤差不超過0.2%，而引起解的相對誤差超過50％.”方程的經(jīng)驗判斷。根”的。計算條件數(shù)需要求矩陣的逆，因而比較據(jù)數(shù)值經(jīng)驗，在下列情況下，方程組常是“（1）在用主元素法時出現(xiàn)小主元；如果A的最大特征值和最小特征值之比（