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

數(shù)值計(jì)算方法第五章解線性方程組的直接方法DirectMethodforSolvingLinearSystems第5章解線性方程組的直接方法高斯消去法矩陣三角分解向量和矩陣的范數(shù)誤差分析其中簡(jiǎn)記作求解解線性方程組的兩類方法：

迭代法：從解的某個(gè)近似值出發(fā)，通過(guò)構(gòu)造一個(gè)無(wú)窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）

直接法:經(jīng)過(guò)有限次運(yùn)算后可求得方程組精確解的方法(不計(jì)舍入誤差!)高斯消元法：思路首先將A化為上三角陣/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=一、Gauss消去法計(jì)算過(guò)程相當(dāng)于第i個(gè)方程-第一個(gè)方程×數(shù)→新的第i方程—同解！第一方程不動(dòng)！

其中

上述消元過(guò)程除第一個(gè)方程不變以外,

第2—第n個(gè)方程全消去了變量1，而系數(shù)

和常數(shù)項(xiàng)全得到新值：系數(shù)矩陣與常數(shù)項(xiàng)：消元記Step1：設(shè)，計(jì)算因子將增廣矩陣/*augmentedmatrix*/第i行mi1

第1行，得到其中Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行？步n

1回代過(guò)程算法消去第一列的n-1個(gè)系數(shù)要計(jì)算n*(n-1）

個(gè)乘法。

Gauss消去法乘法計(jì)算量需要修改前述算法，研究原矩陣A在什么條件下才能保證高斯消去的進(jìn)行。Whatif?Nouniquesolutionexists.Whatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.Whatifwecan’tfindsuchk

?Nouniquesolutionexists.定理6

若A的所有順序主子式

/*determinantofleadingprincipalsubmatrices*/

均不為0，則高斯消元無(wú)需換行即可進(jìn)行到底，得到唯一解。注：事實(shí)上，只要A

非奇異，即A1

存在，則可通過(guò)逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。高斯主元素消去法例1.用Gauss消去法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）解:本方程組的精度較高的解為用Gauss消去法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算)9999回代后得到與精確解相比,該結(jié)果相當(dāng)糟糕究其原因,在求行乘數(shù)時(shí)用了很小的數(shù)0.0001作除數(shù)主元如果在求解時(shí)將1,2行交換,即0.9999回代后得到這是一個(gè)相當(dāng)不錯(cuò)的結(jié)果每一步消去過(guò)程相當(dāng)于左乘初等變換矩陣LkGauss消去法的矩陣表示i+1行i+1行LU形式Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.Couldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.定理

若A的所有順序主子式/*determinantofleadingprincipalsubmatrices*/

均不為0，則A

的

LU

分解唯一（其中L

為單位下三角陣）。證明：由§1中定理可知，LU分解存在。下面證明唯一性。若不唯一，則可設(shè)A=L1U1=L2U2

，推出Upper-triangularLower-triangularWithdiagonalentries1注：L

為一般下三角陣而U

為單位上三角陣的分解稱為Crout分解。實(shí)際上只要考慮A*的LU

分解，即

，則即是A的Crout分解。直接計(jì)算A的LU分解(例)一般計(jì)算公式

計(jì)算量與Gauss消去法同.LU分解求解線性方程組平方根法/*Choleski’sMethod*/：

——對(duì)稱

/*symmetric*/

正定

/*positivedefinite*/

矩陣的分解法定義一個(gè)矩陣A=(aij)nn

稱為對(duì)稱陣，如果aij=aji

。定義一個(gè)矩陣A

稱為正定陣，如果對(duì)任意非零向量都成立?；仡櫍簩?duì)稱正定陣的幾個(gè)重要性質(zhì)

A1

亦對(duì)稱正定，且aii>0若不然，則存在非零解，即存在非零解。對(duì)任意,存在,使得,即。

其中第i

位

A

的順序主子陣/*leadingprincipalsubmatrices*/Ak

亦對(duì)稱正定對(duì)稱性顯然。對(duì)任意有

,其中。

A

的特征值/*eigenvalue*/i

>0

設(shè)對(duì)應(yīng)特征值的非零特征向量為，則。

A

的全部順序主子式

det(Ak

)>0因?yàn)橐虼薉iagonal:對(duì)角為非奇異下三角陣為非奇異上三角陣----------(2)--------(3)因此所以綜合以上分析,則有-------------(4)-------------(5)定理11.(Cholesky分解)且該分解式唯一這種關(guān)于對(duì)稱正定矩陣的分解稱為Cholesky分解-------------(6)-------------(7)-------------(8)對(duì)稱正定線性方程組的解法線性方程組-------------(10)-------------(11)則線性方程組(10)可化為兩個(gè)三角形方程組-------------(12)-------------(13)------(14)------(15)對(duì)稱正定方程組的平方根法例1.用平方根法解對(duì)稱正定方程組解:即所以原方程組的解為思考本例中出現(xiàn)了大量的根式運(yùn)算原因?yàn)榭紤]改變分解方式請(qǐng)求解例1.平方根法的數(shù)值穩(wěn)定性用平方根法求解對(duì)稱正定方程組時(shí)不需選取主元由可知因此平方根法是數(shù)值穩(wěn)定的事實(shí)上,對(duì)稱正定方程組也可以用順序Gauss消去法求解而不必加入選主元步驟Algorithm:Choleski’sMethodTofactorthesymmetricpositivedefinitennmatrixAintoLLT,whereL

islowertriangular.Input:thedimensionn;entriesaijfor1

i,j

nofA.Output:theentrieslijfor1

j

iand1

i

nofL.

Step1Set

;Step2Forj=2,…,n,

set;Step3Fori=2,…,n1,

dosteps4and5

Step4Set

;

Step5

Forj=i+1,…,n,

set

;Step6Set

;Step7Output(lijforj=1,…,iandi=1,…,n

);STOP.因?yàn)锳對(duì)稱，所以只需存半個(gè)A，即其中運(yùn)算量為O(n3/6)，比普通LU分解少一半，但有n次開(kāi)方。用A=LDLT

分解，可省開(kāi)方時(shí)間。追趕法解三對(duì)角方程組

/*CroutReductionforTridiagonalLinearSystem*/Step1:對(duì)A作Crout分解直接比較等式兩邊的元素，可得到計(jì)算公式（p.194）。Step2:追——即解：Step3:趕——即解：與G.E.類似，一旦i=0

則算法中斷，故并非任何三對(duì)角陣都可以用此方法分解。定理

若A

為對(duì)角占優(yōu)

/*diagonallydominant*/的三對(duì)角陣，且滿足，則追趕法可解以A

為系數(shù)矩陣的方程組。Hey,whatdoesdiagonallydominantmean???

ItmeansthatthediagonalentriesofthematrixareveryLARGE.Well,howlargeisLARGE?

Theysatisfythefollowinginequality:注：

如果A是嚴(yán)格對(duì)角占優(yōu)陣，則不要求三對(duì)角線上的所有元素非零。

根據(jù)不等式可知：分解過(guò)程中，矩陣元素不會(huì)過(guò)分增大，算法保證穩(wěn)定。

運(yùn)算量為O(6n)?！?.向量和矩陣的范數(shù)一、向量范數(shù)顯然二、矩陣的范數(shù)矩陣范數(shù)例與前述三種向量范數(shù)相容的三種矩陣范數(shù)：求矩陣A的各種常用范數(shù)解:由于特征方程為容易計(jì)算計(jì)算較復(fù)雜對(duì)矩陣元素的變化比較敏感使用最廣泛性質(zhì)較好矩陣A的譜半徑ReIm(A)定理1.與假設(shè)矛盾定理1.5.6誤差分析右端項(xiàng)b的擾動(dòng)對(duì)解的影響相對(duì)誤差放大因子系數(shù)矩陣A的擾動(dòng)對(duì)解的影響條件數(shù)的定義條件數(shù)的性質(zhì)精確解為例計(jì)算cond(A)2。A1=解：考察A

的特征根39206>>1

測(cè)試病態(tài)程度：給一個(gè)擾動(dòng)，其相對(duì)誤差為此時(shí)精確解為2.0102>200%例：Hilbert陣cond(H2)