第二章解線性方程組的直接方法

第二章解線性方程組的直接方法第1頁，課件共52頁，創(chuàng)作于2023年2月若矩陣A非奇異,即det(A)≠0,則方程組(2.1)有唯一解。所謂直接解法是指，若不考慮計算過程中的舍入誤差，經(jīng)過有限次算術(shù)運算就能求出線性方程組的精確解的方法。但由于實際計算中舍入誤差的存在，用直接解法一般也只能求出方程組的近似解。Cramer法則是一種不實用的直接法，下面介紹幾種實用的直接法。§1Gauss消去法

Gauss消元法是一種規(guī)則化的加減消元法，其基本思想是通過逐次消元計算，把一般線性方程組的求解轉(zhuǎn)化為等價的上三角形方程組的求解。

§1.1順序Gauss消去法為了清楚起見,先看一個簡單的例子.考慮線性方程組第2頁，課件共52頁，創(chuàng)作于2023年2月消去后兩個方程中的x1得再消去最后一個方程的x2得消元結(jié)束,經(jīng)過回代得解:第3頁，課件共52頁，創(chuàng)作于2023年2月上述求解的消元過程可用矩陣表示為:(A,b)=這是Gauss消去法的計算形式,新的增廣矩陣對應(yīng)的線性方程組就是上三角形方程組,可進行回代求解?，F(xiàn)在介紹求解線性方程組（2.1)的順序Gauss消去法:記則,線性方程組(2.1)的增廣矩陣為第4頁，課件共52頁，創(chuàng)作于2023年2月第一步.設(shè),依次用乘矩陣的第1行加到第i行,得到矩陣:第5頁，課件共52頁，創(chuàng)作于2023年2月其中第二步.設(shè),依次用乘矩陣的第2行加到第i行,得到矩陣:其中第6頁，課件共52頁，創(chuàng)作于2023年2月如此繼續(xù)消元下去,第n-1步結(jié)束后得到矩陣:這就完成了消元過程。對應(yīng)的方程組變成：對此方程組進行回代，就可求出方程組的解。第7頁，課件共52頁，創(chuàng)作于2023年2月順序Gauss消去法求解n元線性方程組的乘除運算量是：n2-1

+(n-1)2-1

+…+22-1

+1+2+…+nn=20時,順序Gauss消去法只需3060次乘除法運算.順序Gauss消去法通常也簡稱為Gauss消去法.順序Gauss消去法中的稱為主元素.主元素都不為零矩陣A的各階順序主子式都不為零.

第8頁，課件共52頁，創(chuàng)作于2023年2月

§1.2主元Gauss消去法

(用十進制四位浮點計算):(用Cramer法則可得精確解x1*=1.00010,x2*=0.99990)

解用順序Gauss消去法,消元得回代得解:x2=1.00,x1=0.00若將方程組改寫成:例1解線性方程組第9頁，課件共52頁，創(chuàng)作于2023年2月用順序Gauss消去法,消元得回代得解:x2=1.00,x1=1.00為了提高計算的數(shù)值穩(wěn)定性,在消元過程中采用選擇主元的方法.常采用的是列主元消去法和全主元消去法.給定線性方程組Ax=b,記A(1)=A,b(1)=b,列主元Gauss消去法的具體過程如下:首先在增廣矩陣B(1)=(A(1),b(1))的第一列元素中,取然后進行第一步消元得增廣矩陣B(2)=(A(2),b(2)).再在矩陣B(2)=(A(2),b(2))的第二列元素中,取第10頁，課件共52頁，創(chuàng)作于2023年2月然后進行第二步消元得增廣矩陣B(3)=(A(3),b(3)).按此方法繼續(xù)進行下去,經(jīng)過n-1步選主元和消元運算,得到增廣矩陣B(n)=(A(n),b(n)).則方程組A(n)x=b(n)是與原方程組等價的上三角形方程組,可進行回代求解.易證,只要|A|0,列主元Gauss消去法就可順利進行.

采用十進制四位浮點計算,分別用順序Gauss消去法和列主元Gauss消去法求解線性方程組:例2第11頁，課件共52頁，創(chuàng)作于2023年2月方程組具有四位有效數(shù)字的精確解為x1*=17.46,x2*=-45.76,x3*=5.546

解1.用順序Gauss消去法求解,消元過程為回代得:x3=5.546,x2=100.0,x1=-104.0第12頁，課件共52頁，創(chuàng)作于2023年2月

2.用列主元Gauss消去法求解,消元過程為第13頁，課件共52頁，創(chuàng)作于2023年2月回代得:x3=5.545,x2=-45.77,x1=17.46可見，列主元Gauss消去法是在每一步消元前,在主元所在的一列選取絕對值最大的元素作為主元素.而全主元Gauss消去法是在每一步消元前,在所有元素中選取絕對值最大的元素作為主元素.但由于運算量大增,實際應(yīng)用中并不經(jīng)常使用.第14頁，課件共52頁，創(chuàng)作于2023年2月§2直接三角分解法

§2.1Gauss消去法的矩陣表示對矩陣若令記第15頁，課件共52頁，創(chuàng)作于2023年2月則有

A(2)=記令若則有第16頁，課件共52頁，創(chuàng)作于2023年2月

A(3)=如此進行下去,第n-1步得到:

A(n)=其中第17頁，課件共52頁，創(chuàng)作于2023年2月也就是:

A(n)=Ln-1A(n-1)其中

=Ln-1Ln-2A(n-2)

=…=Ln-1Ln-2…L2L1A(1)第18頁，課件共52頁，創(chuàng)作于2023年2月所以有:

A=A(1)=L1-1L2-1…Ln-1-1A(n)=LU而且有其中L=L1-1L2-1…Ln-1-1,U=A(n).L稱為單位下三角矩陣;U是上三角矩陣.第19頁，課件共52頁，創(chuàng)作于2023年2月式A=LU稱為矩陣A的三角分解.

§2.2Doolittle分解法

設(shè)n階方陣A的各階順序主子式不為零,則存在唯一單位下三角矩陣L和上三角矩陣U使A=LU.

證明只證唯一性,設(shè)有兩種分解

A=LU則有=E所以得于是Ax=bLUx=b

令

Ux=y

得定理2.1第20頁，課件共52頁，創(chuàng)作于2023年2月下面介紹矩陣三角分解的Doolittle分解方法,則得對k=2,3,…,n,計算設(shè)akj=lk1u1j+lk2u2j+…+lkk-1uk-1j+ukjaik=li1u1k+li2u2k+…+likukk第21頁，課件共52頁，創(chuàng)作于2023年2月第22頁，課件共52頁，創(chuàng)作于2023年2月對k=2,3,…,n,計算第23頁，課件共52頁，創(chuàng)作于2023年2月由可得這就是求解方程組Ax=b的Doolittle三角分解方法。第24頁，課件共52頁，創(chuàng)作于2023年2月

利用三角分解方法解線性方程組

解因為所以例3第25頁，課件共52頁，創(chuàng)作于2023年2月先解,得再解,得解線性方程組Ax=b的Doolittle三角分解法的計算量約為1/3n3,與Gauss消去法基本相同.其優(yōu)點在于求一系列同系數(shù)的線性方程組Ax=bk,(k=1,2,…,m)時,可大大節(jié)省運算量.例如,求上例中矩陣A的逆矩陣.可分別取常向量

b1=(1,0,0)T,b2=(0,1,0)T,b3=(0,0,1)T

第26頁，課件共52頁，創(chuàng)作于2023年2月由所以第27頁，課件共52頁，創(chuàng)作于2023年2月為了提高數(shù)值穩(wěn)定性,可考慮列主元三角分解法,設(shè)已完成A=LU的k-1步分解計算,矩陣分解成設(shè)令rkri

相當于取為第k步分解的主元素.但要注意方程組的常數(shù)項也要相應(yīng)變換.第28頁，課件共52頁，創(chuàng)作于2023年2月例如,用列主元三角分解解例3中方程組.則有第29頁，課件共52頁，創(chuàng)作于2023年2月設(shè)A為對稱正定矩陣,則有唯一分解A=LU,且ukk>0.則有A=LDM又因為(LDM)T=MTDLT=LDM所以M=LT

=LDLT則有§2.3平方根法第30頁，課件共52頁，創(chuàng)作于2023年2月分解A=GGT稱為對稱正定矩陣的Cholesky分解.

Ax=b轉(zhuǎn)換為Gy=b,GTx=y若記G=(gij),則有:對k=1,2,…,n實際計算時,可采用緊湊格式

______平方根法.第31頁，課件共52頁，創(chuàng)作于2023年2月解三角方程Gy=b,GTx=y可得

解例4解線性方程組第32頁，課件共52頁，創(chuàng)作于2023年2月平方根法是求對稱正定系數(shù)線性方程組的三角分解法,對稱正定矩陣的Cholesky分解的計算量和存貯量均約為一般矩陣的LU分解的一半.且Cholesky分解具有數(shù)值穩(wěn)定性.第33頁，課件共52頁，創(chuàng)作于2023年2月追趕法是求三對角線性方程組的三角分解法.即方程

三對角矩陣A的各階順序主子式都不為零的一個充分條件是:|a1|>|c1|>0;|an|>|dn|>0;|ai||ci|+|di|,cidi0,i=2,3,…,n-1.在此條件下,A=LDM=TM,稱之為矩陣A的Crout分解.對三對角矩陣A進行Crout分解,有§2.4追趕法第34頁，課件共52頁，創(chuàng)作于2023年2月其中解三角方程Ty=b,Mx=y可得稱之為解三對角方程組的追趕法.第35頁，課件共52頁，創(chuàng)作于2023年2月

解例5解線性方程組第36頁，課件共52頁，創(chuàng)作于2023年2月當滿足條件|a1|>|c1|>0;|an|>|dn|>0;|ai||ci|+|di|,cidi0,i=2,3,…,n-1.時,追趕法是數(shù)值穩(wěn)定的,追趕法具有計算程序簡單,存貯量少,計算量小的優(yōu)點.第37頁，課件共52頁，創(chuàng)作于2023年2月§3向量和矩陣的范數(shù)

§3.1向量的范數(shù)

定義2.1設(shè)‖

‖是向量空間Rn上的實值函數(shù),且滿足條件:(1)非負性:對任何向量xRn,‖x‖0,且‖x‖=0當且僅當x=0(2)齊次性:對任何向量xRn和實數(shù),

‖

x‖=|

|‖x‖(3)三角不等式:對任何向量x,yRn

‖x+y‖

‖x‖+‖y‖則稱‖

‖為空間Rn上的范數(shù),‖x‖為向量x的范數(shù).

第38頁，課件共52頁，創(chuàng)作于2023年2月記x=(x1,x2,…,xn)T,常用的向量范數(shù)有:

向量的1-范數(shù):‖x‖1=|x1|+|x2|+…+|xn|

向量的2-范數(shù):‖x‖2=

向量的

-范數(shù):‖x‖

=

例6設(shè)向量x=(2,-4,3,1)T,求向量范數(shù)‖x‖p,p=1,2,

.

解由定義‖x‖1=10,‖x‖2=

,‖x‖

=4.雖然不同范數(shù)的值可能不同，但它們間存在等價關(guān)系.定理2.2(范數(shù)的等價性)對于Rn上的任何兩種范數(shù)‖

‖

和‖

‖

,存在正常數(shù)m,M,使得m‖x‖

‖x‖

M‖x‖

,

xRn第39頁，課件共52頁，創(chuàng)作于2023年2月常用的三種向量范數(shù)滿足如下等價關(guān)系

‖x‖

‖x‖1

n‖x‖

,

xRn定義2.2設(shè)向量序列k=1,2,…,向量如果則稱向量序列{x(k)}收斂于向量x*,記作易見,第40頁，課件共52頁，創(chuàng)作于2023年2月§3.2矩陣的范數(shù)

定義2.3設(shè)‖

‖是以n階方陣為變量的實值函數(shù),且滿足條件:(1)非負性:‖A‖0,且‖A‖=0當且僅當A=0(2)齊次性:‖

A‖=|

|‖A‖,R(3)三角不等式:‖A+B‖

‖A‖+‖B‖(4)三角不等式:‖AB‖

‖A‖‖B‖則稱‖A‖為矩陣A的范數(shù).

記A=(aij),常用的矩陣范數(shù)有:

矩陣的1-范數(shù):‖A‖1

,也稱矩陣的列范數(shù).

矩陣的2-范數(shù):‖A‖2

,也稱為譜范數(shù).第41頁，課件共52頁，創(chuàng)作于2023年2月

矩陣的

-范數(shù):‖A‖

,也稱為行范數(shù).

矩陣的F-范數(shù):‖A‖F(xiàn)

例7設(shè)矩陣求矩陣A的范數(shù)‖A‖p,p=1,2,,F.

解

‖A‖1=4,‖A‖

=5,‖A‖F(xiàn)第42頁，課件共52頁，創(chuàng)作于2023年2月設(shè)‖

‖是一種向量范數(shù),則定義稱之為由向量范數(shù)派生的矩陣算子范數(shù).矩陣的算子范數(shù)滿足

‖Ax‖‖A‖‖x‖,xRn把滿足上式的矩陣范數(shù)稱為與向量范數(shù)相容的矩陣范數(shù).對于p=1,2,,矩陣范數(shù)‖A‖p是由向量范數(shù)‖x‖p派生的矩陣算子范數(shù),所以‖A‖p是與‖x‖p相容的矩陣范數(shù).但‖A‖F(xiàn)不是一種算子范數(shù),卻與‖x‖2是相容的.設(shè)‖

‖是一種算子范數(shù),則第43頁，課件共52頁，創(chuàng)作于2023年2月矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系.設(shè)是矩陣A的特征值,x是對應(yīng)的特征向量,則有

Ax=

x利用向量和矩陣范數(shù)的相容性,則得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖設(shè)n階矩陣A的n個特征值為1,2,…,n,則稱為矩陣A的譜半徑.對矩陣的任何一種相容范數(shù)都有(A)‖A‖另外,>0,一種相容范數(shù),使‖A‖(A)+第44頁，課件共52頁，創(chuàng)作于2023年2月任何兩種矩陣范數(shù)也具有等價性m‖A‖

‖A‖

M‖A‖

,

ARnn矩陣序列的收斂性也定義為§4線性方程組固有性態(tài)與誤差分析§4.1線性方程組的固有性態(tài)考慮線性方程組其精確解為x*=(-9800b1+9900b2,9900b1-10000b2)T第45頁，課件共52頁，創(chuàng)作于2023年2月若把線性方程組變?yōu)榻鉃閤=(-9800b1+9900b2-19700

,9900b1-10000b2+19900)T可見x-x*=(-19700

,19900)T解的誤差可能放大到常數(shù)項的誤差的近2萬倍。若把線性方程組變?yōu)閯t線性方程組可能無解.這種由于原始數(shù)據(jù)微小變化而導(dǎo)致解嚴重失真的線性方程組稱為病態(tài)方程組,相應(yīng)的系數(shù)矩陣稱為病態(tài)矩陣.第46頁，課件共52頁，創(chuàng)作于2023年2月設(shè)線性方程組

Ax=b系數(shù)矩陣是精確的,常數(shù)項有誤差b,此時記解為x+x,則

A(x+x)=b+b于是

A

x=b所以

‖

x‖=‖A-1

b‖‖A-1‖‖

b‖又由于

‖b‖=‖Ax‖‖A‖‖x‖因此

‖

x‖‖b‖‖A‖‖A-1‖‖

b‖‖x‖即第47頁，課件共52頁，創(chuàng)作于2023年2月再設(shè)b是精確的,A有誤差A(yù),此時記解為x+x,則(A+A)(x+x)=b則有

A

x+A(x+x)=0所以

x=-A-1

A(x+x)=0于是

‖

x‖

‖A-1‖‖

A‖‖x+x‖也就是記Cond(A)=‖A‖‖A-1‖,稱為方程組Ax=b或矩陣A的條件數(shù).第48頁，課件共52頁，創(chuàng)作于2023年2月經(jīng)常使用的條件數(shù)有Condp(A)=‖A‖p‖A-1‖pp=1，2，。當A為對稱矩陣時，有