解線性方程組的直接方法

解線性方程組的直接方法第一頁，共五十八頁，編輯于2023年，星期五第2章解線性方程組的直接法本章討論n元線性方程組（2.1）的直接解法。方程組(2.1)的矩陣形式為

Ax=b其中第二頁，共五十八頁，編輯于2023年，星期五若矩陣A非奇異,即det(A)≠0,則方程組(2.1)有唯一解。所謂直接解法是指，若不考慮計算過程中的舍入誤差，經(jīng)過有限次算術(shù)運算就能求出線性方程組的精確解的方法。但由于實際計算中舍入誤差的存在，用直接解法一般也只能求出方程組的近似解。Cramer法則是一種不實用的直接法，下面介紹幾種實用的直接法?！?Gauss消去法

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

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

+(n-1)2-1

+…+22-1

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

第九頁，共五十八頁，編輯于2023年，星期五

§1.2主元Gauss消去法

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

解用順序Gauss消去法,消元得回代得解:x2=1.00,x1=0.00若將方程組改寫成:例1解線性方程組第十頁，共五十八頁，編輯于2023年，星期五用順序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))的第一列元素中,取然后進(jìn)行第一步消元得增廣矩陣B(2)=(A(2),b(2)).再在矩陣B(2)=(A(2),b(2))的第二列元素中,取第十一頁，共五十八頁，編輯于2023年，星期五然后進(jìn)行第二步消元得增廣矩陣B(3)=(A(3),b(3)).按此方法繼續(xù)進(jìn)行下去,經(jīng)過n-1步選主元和消元運算,得到增廣矩陣B(n)=(A(n),b(n)).則方程組A(n)x=b(n)是與原方程組等價的上三角形方程組,可進(jìn)行回代求解.易證,只要|A|0,列主元Gauss消去法就可順利進(jìn)行.

采用十進(jìn)制四位浮點計算,分別用順序Gauss消去法和列主元Gauss消去法求解線性方程組:例2第十二頁，共五十八頁，編輯于2023年，星期五方程組具有四位有效數(shù)字的精確解為x1*=17.46,x2*=-45.76,x3*=5.546

解1.用順序Gauss消去法求解,消元過程為回代得:x3=5.546,x2=-87.24,x1=52.03第十三頁，共五十八頁，編輯于2023年，星期五

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

§2.1Gauss消去法的矩陣表示對矩陣若令記第十六頁，共五十八頁，編輯于2023年，星期五則有

A(2)=記令若則有第十七頁，共五十八頁，編輯于2023年，星期五

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

A(n)=其中第十八頁，共五十八頁，編輯于2023年，星期五也就是:

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

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

=…=Ln-1Ln-2…L2L1A(1)第十九頁，共五十八頁，編輯于2023年，星期五所以有:

A=A(1)=L1-1L2-1…Ln-1-1A(n)=LU而且有其中L=L1-1L2-1…Ln-1-1,U=A(n).L稱為單位下三角矩陣;U是上三角矩陣.第二十頁，共五十八頁，編輯于2023年，星期五

令

Ux=y

得式A=LU稱為矩陣A的三角分解.

§2.2Doolittle分解法

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

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

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

定理2.1第二十一頁，共五十八頁，編輯于2023年，星期五下面介紹矩陣三角分解的Doolittle分解方法,則得對k=2,3,…,n,計算設(shè)akj=lk1u1j+lk2u2j+…+lkk-1uk-1j+ukjaik=li1u1k+li2u2k+…+likukk第二十二頁，共五十八頁，編輯于2023年，星期五第二十三頁，共五十八頁，編輯于2023年，星期五對k=2,3,…,n,計算第二十四頁，共五十八頁，編輯于2023年，星期五由可得這就是求解方程組Ax=b的Doolittle三角分解方法。第二十五頁，共五十八頁，編輯于2023年，星期五

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

解因為所以例3第二十六頁，共五十八頁，編輯于2023年，星期五先解,得再解,得解線性方程組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

第二十七頁，共五十八頁，編輯于2023年，星期五由所以

第二十八頁，共五十八頁，編輯于2023年，星期五為了提高數(shù)值穩(wěn)定性,可考慮列主元三角分解法,設(shè)已完成A=LU的k-1步分解計算,矩陣分解成設(shè)令rkri

相當(dāng)于取為第k步分解的主元素.但要注意方程組的常數(shù)項也要相應(yīng)變換.第二十九頁，共五十八頁，編輯于2023年，星期五例如,用列主元三角分解解例3中方程組.則有第三十頁，共五十八頁，編輯于2023年，星期五設(shè)A為對稱正定矩陣,則有唯一分解A=LU,且ukk>0.則有A=LDM又因為(LDM)T=MTDLT=LDM所以M=LT

=LDLT則有§2.3平方根法第三十一頁，共五十八頁，編輯于2023年，星期五分解A=GGT稱為對稱正定矩陣的Cholesky分解.

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

______平方根法.第三十二頁，共五十八頁，編輯于2023年，星期五解三角方程Gy=b,GTx=y可得

解例4解線性方程組第三十三頁，共五十八頁，編輯于2023年，星期五平方根法是求對稱正定系數(shù)線性方程組的三角分解法,對稱正定矩陣的Cholesky分解的計算量和存貯量均約為一般矩陣的LU分解的一半.且Cholesky分解具有數(shù)值穩(wěn)定性.第三十四頁，共五十八頁，編輯于2023年，星期五追趕法是求三對角線性方程組的三角分解法.即方程

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

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

§3.1向量的范數(shù)

定義2.1

設(shè)‖‖是向量空間Rn上的實值函數(shù),且滿足條件:

(1)非負(fù)性:對任何向量xRn,‖x‖0,且‖x‖=0當(dāng)且僅當(dāng)x=0

(2)齊次性:對任何向量xRn和實數(shù),

‖x‖=||‖x‖

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

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

第三十九頁，共五十八頁，編輯于2023年，星期五記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第四十頁，共五十八頁，編輯于2023年，星期五常用的三種向量范數(shù)滿足如下等價關(guān)系

‖x‖‖x‖1

n‖x‖,xRn

定義2.2

設(shè)向量序列k=1,2,…,向量如果則稱向量序列{x(k)}收斂于向量x*,記作易見,第四十一頁，共五十八頁，編輯于2023年，星期五§3.2矩陣的范數(shù)

定義2.3

設(shè)‖‖是以n階方陣為變量的實值函數(shù),且滿足條件:

(1)非負(fù)性:

‖A‖0,且‖A‖=0當(dāng)且僅當(dāng)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ù).第四十二頁，共五十八頁，編輯于2023年，星期五

矩陣的-范數(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)第四十三頁，共五十八頁，編輯于2023年，星期五設(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ù),則第四十四頁，共五十八頁，編輯于2023年，星期五矩陣的范數(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)+第四十五頁，共五十八頁，編輯于2023年，星期五任何兩種矩陣范數(shù)也具有等價性m‖A‖‖A‖

M‖A‖,ARnn矩陣序列的收斂性也定義為§4線性方程組固有性態(tài)與誤差分析§4.1線性方程組的固有性態(tài)考慮線性方程組其精確解為x*=(-9800b1+9900b2,9900b1-10000b2)T第四十六頁，共五十八頁，編輯于2023年，星期五若把線性方程組變?yōu)榻鉃閤=(-9800b1+9900b2-19700

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

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

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

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

Ax=b所以

‖x‖=‖A-1b‖‖A-1‖‖b‖又由于

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

‖x‖‖b‖‖A‖‖A-1‖‖b‖‖x‖即第四十八頁，共五十八頁，編輯于2023年，星期五再設(shè)b是精確的,A有誤差A(yù),此時記解為x+x,則(A+A)(x+x)=b則有

Ax+A(x+x)=0所以x=-A-1A(x+x)于是

‖x‖‖A-1‖‖A‖‖x+x‖也就是記Cond(A)=‖A‖‖A-1‖,稱為方程組Ax=b或矩陣A的條件數(shù).第四十九頁，共五十八頁，編輯于2023年，星期五經(jīng)常使用的條件數(shù)有Condp(A)=‖A‖p‖A-1‖pp=1，2，。當(dāng)A為對稱矩陣時，有Cond2(A)=|1|/|n|其中1，n分別是A的按絕對值最大和最小的特征值。例如，對前面方程組的系數(shù)矩陣A有Cond1(A)=Cond(A)=39601，Cond2(A)39206由于計算條件數(shù)運算量較大,實際計算中若遇到下述情況之一,方程組就有可能是病態(tài)的:第五十頁，共五十八頁，編輯于2023年，星期五(1)矩陣元素間數(shù)量級差很大,且無一定規(guī)律;(2)矩陣的行列式值相對來說很小;(3)列主元消去法求解過程中出現(xiàn)量級很小的主元素;(4)數(shù)值求解過程中,計算解x的剩余向量r=b-Ax已經(jīng)很小,但x仍不符合要求.§4.2預(yù)條件和迭代改善1.線性方程組的預(yù)條件處理對病態(tài)方程組Ax=b,考慮線性方程組其中第五十一頁，共五十八頁，編輯于