數(shù)值分析第三章解線性方程組的直接方法演示文稿

數(shù)值分析第三章解線性方程組的直接方法演示文稿目前一頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)優(yōu)選數(shù)值分析第三章解線性方程組的直接方法Ppt目前二頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)求解高斯消元法：思路首先將A化為上三角陣/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=目前三頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)消元記Step1：設(shè)，計(jì)算因子將增廣矩陣/*augmentedmatrix*/第i行mi1

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

1目前四頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)回代Whatif?Nouniquesolutionexists.Whatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.Whatifwecan’tfindsuchk

?Nouniquesolutionexists.定理

若A的所有順序主子式

/*determinantofleadingprincipalsubmatrices*/

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

非奇異，即A1

存在，則可通過(guò)逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。§1GaussianElimination–TheMethod目前五頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)目前六頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)選主元消去法例：?jiǎn)尉冉夥匠探M/*精確解為和*/8個(gè)8個(gè)用GaussianElimination計(jì)算：8個(gè)小主元/*Smallpivotelement*/

可能導(dǎo)致計(jì)算失敗。目前七頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)

全主元消去法/*CompletePivoting*/每一步選絕對(duì)值最大的元素為主元素，保證。Stepk:①選取②Ifik

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

列;③消元注：列交換改變了xi

的順序，須記錄交換次序，解完后再換回來(lái)。列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去換列的步驟，每次僅選一列中最大的元。目前八頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)例：注：列主元法沒(méi)有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在數(shù)學(xué)上嚴(yán)格等價(jià)。標(biāo)度化列主元消去法/*ScaledPartialPivoting*/對(duì)每一行計(jì)算。為省時(shí)間，si

只在初始時(shí)計(jì)算一次。以后每一步考慮子列中最大的aik

為主元。注：穩(wěn)定性介于列主元法和全主元法之間?！?GaussianElimination–PivotingStrategies目前九頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2三角分解法/*MatrixFactorization*/高斯消元法的矩陣形式/*MatrixFormofG.E.*/：Step1:記L1=，則Stepn

1:其中

Lk=目前十頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–MatrixFormofG.E.記為L(zhǎng)單位下三角陣/*unitarylower-triangularmatrix*/記

U=A

的

LU

分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.Couldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.目前十一頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–MatrixFormofG.E.定理

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

均不為0，則A

的

LU

分解唯一（其中L

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

，推出Upper-triangularLower-triangularWithdiagonalentries1注：L

為一般下三角陣而U

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

分解，即

，則即是A的Crout分解。目前十二頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–Doolittle道立特分解法/*DoolittleFactorization*/：

——

LU

分解的緊湊格式/*compactform*/反復(fù)計(jì)算,很浪費(fèi)哦……通過(guò)比較法直接導(dǎo)出L和

U的計(jì)算公式。思路目前十三頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–Choleski平方根法/*Choleski’sMethod*/：

——對(duì)稱(chēng)

/*symmetric*/

正定

/*positivedefinite*/

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

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

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

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

A1

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

其中第i

位

A

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

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

,其中。

A

的特征值/*eigenvalue*/i

>0

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

A

的全部順序主子式

det(Ak

)>0因?yàn)槟壳笆捻?yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–Choleski將對(duì)稱(chēng)

正定陣

A

做LU

分解U=uij=u11uij/uii111u22unn記為

A對(duì)稱(chēng)即記D1/2=Whyisuii>0?Sincedet(Ak)>0則仍是下三角陣定理

設(shè)矩陣A對(duì)稱(chēng)正定，則存在非奇異下三角陣使得。若限定L對(duì)角元為正，則分解唯一。注：對(duì)于對(duì)稱(chēng)正定陣A，從可知對(duì)任意ki

有。即L

的元素不會(huì)增大，誤差可控，不需選主元。目前十五頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–CholeskiAlgorithm: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ì)稱(chēng)，所以只需存半個(gè)A，即其中運(yùn)算量為O(n3/6)，比普通LU分解少一半，但有n次開(kāi)方。用A=LDLT

分解，可省開(kāi)方時(shí)間(p.50-51)。HW:p.54#2,#5,#6目前十六頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–TridiagonalSystem追趕法解三對(duì)角方程組

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

則算法中斷，故并非任何三對(duì)角陣都可以用此方法分解。目前十七頁(yè)\總數(shù)三十三頁(yè)\編于二十一點(diǎn)§2MatrixFactorization–TridiagonalSystem定理

若A

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

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

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

ItmeansthatthediagonalentriesofthematrixareveryLARGE.Well,howlargeisLARGE?