数值分析第三章解线性方程组的直接方法演示文稿

数值分析第三章解线性方程组的直接方法演示文稿现在是1页\一共有33页\编辑于星期三优选数值分析第三章解线性方程组的直接方法Ppt现在是2页\一共有33页\编辑于星期三求解高斯消元法：思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=现在是3页\一共有33页\编辑于星期三消元记Step1：设，计算因子将增广矩阵/*augmentedmatrix*/第i行mi1

第1行，得到其中Stepk：设，计算因子且计算共进行？步n

1现在是4页\一共有33页\编辑于星期三回代Whatif?Nouniquesolutionexists.Whatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.Whatifwecan’tfindsuchk

?Nouniquesolutionexists.定理

若A的所有顺序主子式

/*determinantofleadingprincipalsubmatrices*/

均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注：事实上，只要A

非奇异，即A1

存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。§1GaussianElimination–TheMethod现在是5页\一共有33页\编辑于星期三现在是6页\一共有33页\编辑于星期三选主元消去法例：单精度解方程组/*精确解为和*/8个8个用GaussianElimination计算：8个小主元/*Smallpivotelement*/

可能导致计算失败。现在是7页\一共有33页\编辑于星期三

全主元消去法/*CompletePivoting*/每一步选绝对值最大的元素为主元素，保证。Stepk:①选取②Ifik

k

then交换第k行与第ik

行;Ifjk

k

then交换第k列与第jk

列;③消元注：列交换改变了xi

的顺序，须记录交换次序，解完后再换回来。列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去换列的步骤，每次仅选一列中最大的元。现在是8页\一共有33页\编辑于星期三例：注：列主元法没有全主元法稳定。例：注意：这两个方程组在数学上严格等价。标度化列主元消去法/*ScaledPartialPivoting*/对每一行计算。为省时间，si

只在初始时计算一次。以后每一步考虑子列中最大的aik

为主元。注：稳定性介于列主元法和全主元法之间。§1GaussianElimination–PivotingStrategies现在是9页\一共有33页\编辑于星期三§2三角分解法/*MatrixFactorization*/高斯消元法的矩阵形式/*MatrixFormofG.E.*/：Step1:记L1=，则Stepn

1:其中

Lk=现在是10页\一共有33页\编辑于星期三§2MatrixFactorization–MatrixFormofG.E.记为L单位下三角阵/*unitarylower-triangularmatrix*/记

U=A

的

LU

分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.Couldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.现在是11页\一共有33页\编辑于星期三§2MatrixFactorization–MatrixFormofG.E.定理

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

均不为0，则A

的

LU

分解唯一（其中L

为单位下三角阵）。证明：由§1中定理可知，LU分解存在。下面证明唯一性。若不唯一，则可设A=L1U1=L2U2

，推出Upper-triangularLower-triangularWithdiagonalentries1注：L

为一般下三角阵而U

为单位上三角阵的分解称为Crout分解。实际上只要考虑A*的LU

分解，即

，则即是A的Crout分解。现在是12页\一共有33页\编辑于星期三§2MatrixFactorization–Doolittle道立特分解法/*DoolittleFactorization*/：

——

LU

分解的紧凑格式/*compactform*/反复计算,很浪费哦……通过比较法直接导出L和

U的计算公式。思路现在是13页\一共有33页\编辑于星期三§2MatrixFactorization–Choleski平方根法/*Choleski’sMethod*/：

——对称

/*symmetric*/

正定

/*positivedefinite*/

矩阵的分解法定义一个矩阵A=(aij)nn

称为对称阵，如果aij=aji

。定义一个矩阵A

称为正定阵，如果对任意非零向量都成立。回顾：对称正定阵的几个重要性质

A1

亦对称正定，且aii>0若不然，则存在非零解，即存在非零解。对任意,存在,使得,即。

其中第i

位

A

的顺序主子阵/*leadingprincipalsubmatrices*/Ak

亦对称正定对称性显然。对任意有

,其中。

A

的特征值/*eigenvalue*/i

>0

设对应特征值的非零特征向量为，则。

A

的全部顺序主子式

det(Ak

)>0因为现在是14页\一共有33页\编辑于星期三§2MatrixFactorization–Choleski将对称

正定阵

A

做LU

分解U=uij=u11uij/uii111u22unn记为

A对称即记D1/2=Whyisuii>0?Sincedet(Ak)>0则仍是下三角阵定理

设矩阵A对称正定，则存在非奇异下三角阵使得。若限定L对角元为正，则分解唯一。注：对于对称正定阵A，从可知对任意ki

有。即L

的元素不会增大，误差可控，不需选主元。现在是15页\一共有33页\编辑于星期三§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.因为A对称，所以只需存半个A，即其中运算量为O(n3/6)，比普通LU分解少一半，但有n次开方。用A=LDLT

分解，可省开方时间(p.50-51)。HW:p.54#2,#5,#6现在是16页\一共有33页\编辑于星期三§2MatrixFactorization–TridiagonalSystem追赶法解三对角方程组

/*CroutReductionforTridiagonalLinearSystem*/Step1:对A作Crout分解直接比较等式两边的元素，可得到计算公式（p.52）。Step2:追——即解：Step3:赶——即解：与G.E.类似，一旦i=0

则算法中断，故并非任何三对角阵都可以用此方法分解。现在是17页\一共有33页\编辑于星期三§2MatrixFactorization–TridiagonalSystem定理

若A

为对角占优

/*diagonallydominant*/的三对角阵，且满足，则追赶法可解以A

为系数矩阵的方程组。Hey,whatdoesdiagonallydominantmean???

ItmeansthatthediagonalentriesofthematrixareveryLARGE.Well,howlargeisLARGE?