第五章 線性代數(shù)方程組的直接解法1

本文格式為Word版，下載可任意編輯——第五章線性代數(shù)方程組的直接解法1

(石大)數(shù)值計算第五章課件

第五章線性代數(shù)方程組的直接解法/*DirectMethodforSolvingLinearAlgebraicSystems*/

求解Ax=b,A∈RCramer法則:法則:法則

nn

det(A)≠0

Dixi=D

i=1,2,L,n

所需乘除法的運(yùn)算量大約為(n+1)!+)!+n)!+

n=20時，每秒億次運(yùn)算速度的計算機(jī)要算多萬年！多萬年！時每秒1億次運(yùn)算速度的計算機(jī)要算30多萬年直接法在沒有舍入誤差的狀況下，在沒有舍入誤差的狀況下，經(jīng)過有限次舍入誤差的狀況下確切解的方法運(yùn)算可以得到方程組的確切解的方法。運(yùn)算可以得到方程組的確切解的方法。

(石大)數(shù)值計算第五章課件

1線性代數(shù)的基礎(chǔ)知識向量范數(shù)(一、向量范數(shù)(/*VectorNorm*/))

Def1設(shè)

的一個映射，→R的一個映射，若對x∈Rnn可以推廣到C與之對應(yīng)，存在唯一實(shí)數(shù)x與之對應(yīng)，且滿足非負(fù)性：非負(fù)性：x≥0,x∈Rn且x=0x=0

是R

n

齊次性：齊次性：λx

=λx,x∈R,λ∈Rn

三角不等性：三角不等性：x+則稱n

y≤x+y,x,y∈R范數(shù)。x的范數(shù)。非負(fù)實(shí)值函數(shù)

n

x為Rn中向量

R稱為賦范線性空間稱為賦范賦范線性空間

(石大)數(shù)值計算第五章課件

常用的幾種向量范數(shù)：常用的幾種向量范數(shù)：設(shè)x向量范數(shù)1-范數(shù)：范數(shù)：2-范數(shù)：范數(shù)：

x1=∑xix2=(∑x)i=12ii=1n12

n

=(x1,x2,L,xn)

T

=(x,x)

-范數(shù)：∞范數(shù)：x∞=maxxi1≤i≤n上述3種向量范數(shù)統(tǒng)稱為范數(shù)(或者Holder范數(shù))范數(shù))上述種向量范數(shù)統(tǒng)稱為P-范數(shù)(或者種向量范數(shù)統(tǒng)稱為范數(shù)

x

p

=(∑xi)pi=1

n

1

p

1≤p∞

(石大)數(shù)值計算第五章課件

設(shè)x

=(x1,x2,L,xn)≠0T

pn

(∑xi)pi=1

n

1

p

=maxxi(∑1≤i≤ni=1

ximaxxi1≤i≤n

1

)

p

=maxxi1≤i≤n

Q由夾逼定理

1≤≤np

lim=1p→∞→∞

x

∞

=maxxi1≤i≤n

(石大)數(shù)值計算第五章課件

兩個重要不等式閔可夫斯基(閔可夫斯基(Minkowski)不等式：)不等式：

《矩陣?yán)碚摷捌鋺?yīng)用》及其應(yīng)用》蔣正新)(蔣正新)

(∑xi+yi)pi=12

n

1

p

≤(∑xi)pi=1

n

1

p

+(∑yi)pi=1n

n

1

p

柯西-許瓦滋(Cauchy-Schwartz)不等式：柯西-許瓦滋()不等式：

(x,y)≤(x,x)(y,y)x,y∈R或者

xiyi≤(∑xi)2(∑yi)∑21i=1i=1i=1

n

n

n

21

2

(石大)數(shù)值計算第五章課件

Cauchy-Schwartz不等式的證明不等式的證明

令u=y2

(x,y)x22

x(x,y)x2

(u,x)=022

u2=(u,u)=(u,y=(y,y)2

x)=(u,y)222

(x,y)x22

2

=y22

(x,y)x

≥0

(x,y)≤x

22

y2=(x,x)(y,y)

(石大)數(shù)值計算第五章課件

階實(shí)對稱正定矩陣，例1:設(shè)A∈Rnn是n階實(shí)對稱正定矩陣，則階實(shí)對稱正定矩陣

x

A

=(xAx)T

1

2

x∈R

n

=LxT

中的一種向量范數(shù)。是Rn中的一種向量范數(shù)。證明：只需驗(yàn)證范數(shù)的3

個條件成馬上可。證明：只需驗(yàn)證范數(shù)的個條件成馬上可。個條件成馬上可1T非負(fù)性：非負(fù)性：x≠0x=(xAx)2A

2

0A

齊次性：齊次性：λx

A

=(λx)A(λx)T

1

2

=λx

下三角陣三角不等性：存在非奇異下三角三角不等性：存在非奇異下三角陣L

A=LLT

T

x

A

=(xLLx)TT

1

2

=((Lx)(Lx))TT

1

2

x+y

A

=L(x+y)2≤Lx2+LyTTT

2

(石大)數(shù)值計算第五章課件

例2:證明

f=(∫f(x)dx)2a

b

1

2

f(x)∈C[a,b]

上的一種范數(shù)。是線性空間C[a,b]上的一種范數(shù)。證明：只需驗(yàn)證范數(shù)的3個條件成馬上可。證明：只需驗(yàn)證范數(shù)的個條件成馬上可。個條件成馬上可非負(fù)性：非負(fù)性：f(x)≠0齊次性：齊次性：λba

fb212a1

2

f=(∫f(x)dx)0222

f=(∫λf(x)dx)

=λf

三角不等性：閔可夫斯基(三角不等性：閔可夫斯基(Minkowski)不等式：)不等式：

f+g≤f+g(∫[f(x)+g(x)]dx)≤(∫f(x)dx)+(∫g(x)dx)b212b212b2aaa12

(石大)數(shù)值計算第五章課件

向量范數(shù)的性質(zhì)：向量范數(shù)的性質(zhì)：性質(zhì)1性質(zhì)證明：證明：

x,y∈R

n

xy≤xyxy≥yxn

x=xy+y≤xy+yy=yx+x≤yx+xnn

xy≤xy同理

性質(zhì)2性質(zhì)設(shè)

A∈R,則對R上每一種范數(shù),Tnx=(x1,x2,Lxn)∈RTh5.1Ax都是(x1,x2,Lxn)的n元連續(xù)函數(shù)。元連續(xù)函數(shù)。元連續(xù)函數(shù)

(石大)數(shù)值計算第五章課件

性質(zhì)3性質(zhì)

x

是(x1,x2,Lxn)n元連續(xù)函數(shù)的元連續(xù)函數(shù)

(等價性/*EquivalenceProperty*/))Def2等價性設(shè)

α和

上定義的兩種范數(shù)，假使存在正數(shù)是Rn上定義的兩種范數(shù)，假使存在正數(shù)βα

c1,c2滿足cx1則稱

≤xn

β

≤c2x

α

x∈R

n

α和

上等價的向量范數(shù)。β是R上等價的向量范數(shù)。證明見文獻(xiàn)[3]文獻(xiàn)

性質(zhì)4性質(zhì)性質(zhì)5性質(zhì)

向量范數(shù)的等價性具有傳遞性。向量范數(shù)的等價性具有傳遞性。傳遞性的所有向量范數(shù)是彼此等價彼此等價的Rn的所有向量范數(shù)是彼此等價的。

Th5.2

(石大)數(shù)值計算第五章課件

性質(zhì)6性質(zhì)

x2≤(x11+x21+L+xn1)22T

2

x2≤x1≤nx

x∞≤x2≤nx∞記y=(1,1,L,1)Tz=(x1,x2,L,xn)1x1≤x∞≤x1n2=(x11+x21+L+xn1)證明：證明：僅證設(shè)x

=(x1,x2,L,xn)2n2k=1

T

=(y,z)≤y2

22

z

22

x1=(∑xk)

=nx

22

(石大)數(shù)值計算第五章課件

矩陣范數(shù)(二、矩陣范數(shù)(/*MatrixNorm*/))

Def3設(shè)

是Rnn

→R

nn的一個映射，的一個映射，若對A∈R

存在唯一實(shí)數(shù)非負(fù)性：非負(fù)性：A

與之對應(yīng)，A與之對應(yīng)，且滿足nn

可以推廣到C

nn

≥0,A∈R且A=0A=0nn齊次性：齊次性：λA=λA,A∈R,λ∈R三角不等性：三角不等性：

A+

B≤A+B,A,B∈RA,B∈Rnn

nn

AB≤AB則稱

A

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

Rnn賦范線性空間賦范線性空間

(石大)數(shù)值計算第五章課件

證明：例3:設(shè)A=(aij)nn,證明：

A

F

=(∑∑a)i=1j=12ij2

n

n

Frobenius范數(shù)范數(shù)

1

2

是一種矩陣范數(shù)是一種矩陣范數(shù)。矩陣范數(shù)。

證明：只需驗(yàn)證范數(shù)的4個條件成馬上可。簡稱F-范數(shù)證明：只需驗(yàn)證范數(shù)的個條件成馬上可。簡稱范數(shù)個條件成馬上可上述范數(shù)可以看成是記維向量的2-范數(shù)范數(shù)，n維向量的范數(shù)，故只需驗(yàn)證n2irrj

B=(bij)nn2Fn

ABn

=∑∑

n

≤∑∑(∑air)(∑brj)2i=1j=1r=1r=1

n

i=1j=1r=1nn2

∑a

=(∑∑air)2

n

n

b

(∑∑brj)2

i=1r=1nn

=A

j=1r=12

F

B

2F

(石大)數(shù)值計算第五章課件

AF=(tr(AA))=(tr(AA))TT

12

12

=λ1+λ2+L+λn其中

tr(A)=∑aiii=1

n

λi

是AT

A的特征值

稱之為矩陣A跡的

相容性()Def4相容性(/*Compatibility*/)設(shè)上的范數(shù)，xα是Rn上的范數(shù)，Aβ是Rnn上的范數(shù)假使對x∈Rn,A∈Rnn滿足

Ax

α

≤A

β

x

α

則稱上述矩陣范數(shù)與向量范數(shù)相容。則稱上述矩陣范數(shù)與向量范數(shù)相容。相容

(石大)數(shù)值計算第五章課件

中的任意一種矩陣范數(shù)，設(shè)Aβ是Rnn中的任意一種矩陣范數(shù)，則在RTh5.3中至少存在一種向量范數(shù)xα,使得Aβ和xα是相容的相容的。證明：設(shè)證明：

n

x=(x1,x2,L,xn)∈RT

n

令x

α

x1x2=Mxn

0L00L0MMM0L0

B=β

β

易驗(yàn)證它是一種向量范數(shù)。易驗(yàn)證它是一種向量范數(shù)。

(石大)數(shù)值計算第五章課件

由AB≤AB得A=(aij)nna11a12La1nx1000ax000a22La2n221MMMMMMMMan1an2Lannxn000βa11a12La1nx1000ax000a22La2n221≤MMMMMMMMan1an2Lannβxn000記

β

(石大)數(shù)值計算第五章課件

而AB

β

∑a1jxjj=1n∑a2jxj=j=1Mn∑anjxjj=1n

000000MM