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

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

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

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

其中

上述消元過程除第一個方程不變以外,

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

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

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

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

個乘法。

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

?Nouniquesolutionexists.定理6

若A的所有順序主子式

/*determinantofleadingprincipalsubmatrices*/

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

非奇異，即A1

存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。高斯主元素消去法例1.用Gauss消去法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）解:本方程組的精度較高的解為用Gauss消去法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算)9999回代后得到與精確解相比,該結(jié)果相當(dāng)糟糕究其原因,在求行乘數(shù)時用了很小的數(shù)0.0001作除數(shù)主元如果在求解時將1,2行交換,即0.9999回代后得到這是一個相當(dāng)不錯的結(jié)果每一步消去過程相當(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*/：

——對稱

/*symmetric*/

正定

/*positivedefinite*/

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

稱為對稱陣，如果aij=aji

。定義一個矩陣A

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

A1

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

其中第i

位

A

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

亦對稱正定對稱性顯然。對任意有

,其中。

A

的特征值/*eigenvalue*/i

>0

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

A

的全部順序主子式

det(Ak

)>0因?yàn)橐虼薉iagonal:對角為非奇異下三角陣為非奇異上三角陣----------(2)--------(3)因此所以綜合以上分析,則有-------------(4)-------------(5)定理11.(Cholesky分解)且該分解式唯一這種關(guān)于對稱正定矩陣的分解稱為Cholesky分解-------------(6)-------------(7)-------------(8)對稱正定線性方程組的解法線性方程組-------------(10)-------------(11)則線性方程組(10)可化為兩個三角形方程組-------------(12)-------------(13)------(14)------(15)對稱正定方程組的平方根法例1.用平方根法解對稱正定方程組解:即所以原方程組的解為思考本例中出現(xiàn)了大量的根式運(yùn)算原因?yàn)榭紤]改變分解方式請求解例1.平方根法的數(shù)值穩(wěn)定性用平方根法求解對稱正定方程組時不需選取主元由可知因此平方根法是數(shù)值穩(wěn)定的事實(shí)上,對稱正定方程組也可以用順序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)锳對稱，所以只需存半個A，即其中運(yùn)算量為O(n3/6)，比普通LU分解少一半，但有n次開方。用A=LDLT

分解，可省開方時間。追趕法解三對角方程組

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

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

若A

為對角占優(yōu)

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

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

ItmeansthatthediagonalentriesofthematrixareveryLARGE.Well,howlargeisLARGE?

Theysatisfythefollowinginequality:注：

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

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

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

的特征根39206>>1

測試病態(tài)程度：給一個擾動，其相對誤差為此時精確解為2.0102>200%例：Hilbert陣cond(H2)