数值分析:解线性方程组的直接法-2完整版_第1页
数值分析:解线性方程组的直接法-2完整版_第2页
数值分析:解线性方程组的直接法-2完整版_第3页
数值分析:解线性方程组的直接法-2完整版_第4页
数值分析:解线性方程组的直接法-2完整版_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

§2三角分解法/*MatrixFactorization*/

高斯消元法的矩阵形式/*MatrixFormofG.E.*/:Step1:记L1=,则Stepn

1:其中

Lk=§2MatrixFactorization–MatrixFormofG.E.记为L单位下三角阵/*unitarylower-triangularmatrix*/记

U=A

LU

分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.Couldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.§2MatrixFactorization–MatrixFormofG.E.定理

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

均不为0,则A

LU

分解唯一(其中L

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

,推出Upper-triangularLower-triangularWithdiagonalentries1

注:L

为一般下三角阵而U

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

分解,即

,则即是A的Crout分解。§2MatrixFactorization–Doolittle

道立特分解法/*DoolittleFactorization*/:

——LU

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

U的计算公式。思路§2MatrixFactorization–Doolittle固定i:对j=i,i+1,…,n

有lii=1a将i

,j对换,对j=i,i+1,…,n有b

Algorithm:DoolittleFactorizationStep1:u1j=a1j;lj1=aj1/u11;(j=1,…,n)Step2:computeandfori=2,…,n1;Step3:ab一般采用列主元法增强稳定性。但注意也必须做相应的行交换。§2MatrixFactorization–Choleski

平方根法/*Choleski’sMethod*/:

——对称

/*symmetric*/

正定

/*positivedefinite*/

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

n

称为对称阵,如果aij=aji

。定义一个矩阵A

称为正定阵,如果对任意非零向量都成立。

回顾:对称正定阵的几个重要性质

A1

亦对称正定,且aii>0

若不然,则存在非零解,即存在非零解。

对任意,存在,使得,即。

其中第i

A

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

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

,其中。

A

的特征值/*eigenvalue*/

i

>0

设对应特征值

的非零特征向量为,则。

A

的全部顺序主子式

det(Ak

)>0因为§2MatrixFactorization–Choleski将对称

正定阵

A

做LU

分解U=uij=u11uij/uii111u22unn记为

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

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

i

有。即L

的元素不会增大,误差可控,不需选主元。§2MatrixFactorization–CholeskiAlgorithm:Choleski’sMethodTofactorthesymmetricpositivedefiniten

nmatrixAintoLLT,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

分解,可省开方时间。HW:p.104#5,#9,#15§2MatrixFactorization–TridiagonalSystem

追赶法解三对角方程组

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

i=0

则算法中断,故并非任何三对角阵都可以用此方法分解。§2MatrixFactorization–TridiagonalSystem定理

若A

为对角占优

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

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

ItmeansthatthediagonalentriesofthematrixareveryLARGE.Well,howlargeisLARGE?

Theysatisfythefollowinginequality:注:

如果A是严格对角占优阵,则不要求三对角线上的所有元素非零。

根据不等式可知:分解过程中,矩阵元素不会过分增大,算法保证稳定。

运算量为O(6n)。§2MatrixFactorization–TridiagonalSystemLab06.CroutReductionforTridiagonalLinearSystems ApplyCroutReductiontosolveagivenn×ntridiagonallinearsystemInput Thereareseveralsetsofinputs.Foreachset: The1stlinecontainsaninteger100

n

0whichisthesizeofamatrix.n=

1signalstheendoffile. The2ndlinecontainsn

1realnumbers. The3rdlinecontainsnrealnumbers. The4thlinecontainsn

1realnumbers. The5thlinecontainsnrealnumbers.Thenumbersareseparatedbyspaces.§2MatrixFactorization–TridiagonalSystemOutputEachentryofthesolutionistobeprintedasintheCfprintf:fprintf(outfile,"%16.8e\n",x);Ifthemethodfailstogiveasolution,printthemessage“The

Crout

method

failed.\n”./*here

representsaspace*/Theoutputsoftwotestcasesmustbeseperatedbyablankline.SampleInput

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论