Ch 解线性方程组的直接方法

Ch5解线性方程组的直接方法荣垮促剂坎要觉谣嘿跃饼捂茄廊舱丰越瞻响辟番诊誓朱刺蔬媳密演底肤吼Ch解线性方程组的直接方法Ch解线性方程组的直接方法求解bxA高斯消元法：思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=装伐帚核萍歹冰捕期假杂渔屑蒋颂澜要严扶衅赋聪沧囚酋敝青账皇灌开溪Ch解线性方程组的直接方法Ch解线性方程组的直接方法消元记,)()1()1(nnijaAA)1()1(1)1(...nbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaamii将增广矩阵/*augmentedmatrix*/第i行mi1第1行，得到)1(1)1(1)1(12)1(11...baaan)2(A)2(b)...,,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij其中Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行？步n1)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa禹冰持鞭霄裤僚朔淌情琉滩杜哥十艾俐确泡稀颐梧环磅牺著摹剩瞅香炯宗Ch解线性方程组的直接方法Ch解线性方程组的直接方法回代)()(/nnnnnnabx0)(nnnaWhatif?Nouniquesolutionexists.)1...,,1()(1)()(niaxabxiiinijjiijiii0)(iiiaWhatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.0)(ikiaWhatifwecan’tfindsuchk?Nouniquesolutionexists.定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为0，则高斯消元无需换行即可进行到底，得到唯一解。iiiiiaaaaA...............)det(1111注：事实上，只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。§1GaussianElimination–TheMethod庸皇嗡苔手驭长喻揪总珐乔截颠舀首楷息肿唇祸机蹿枝竹饯唤蚂黍床激分Ch解线性方程组的直接方法Ch解线性方程组的直接方法0(1,2,,1)定理（矩阵的分解）设为阶矩阵，如果的顺序主子式，则可分解为一个下三角矩阵和一个上三角矩阵的乘积，且这种分解是唯一的.iLUAnADinALU岳竖贵株丰亢休间嫂恕挖花漱鲸蛮赘蹄遍铡些诱掩粘祝婆糯讲呀藏桓聂脊Ch解线性方程组的直接方法Ch解线性方程组的直接方法选主元消去法例：单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用GaussianElimination计算：911212110/aam999212210101010...0.011ma8个92121012mb9991010011100,112xx小主元/*Smallpivotelement*/可能导致计算失败。爽篇扔陷毁挡线端翱抹筷找渔搪陶掐棺皂婶愧撒斟草呐琉钩痉阴筏格猩珍Ch解线性方程组的直接方法Ch解线性方程组的直接方法全主元消去法/*CompletePivoting*/每一步选绝对值最大的元素为主元素，保证。1||ikmStepk:①选取;0||max||,ijnjikjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去换列的步骤，每次仅选一列中最大的元。0||max||,iknikkiaak杯粘土蝎孕挛页路咐择寄伞挞荣手凡执跳丝嫂杯获文炳驱晌魔擂鸣缅偷晾Ch解线性方程组的直接方法Ch解线性方程组的直接方法例：211111091,112xx11021111102119注：列主元法没有全主元法稳定。0,112xx例：211101019999991010010101注意：这两个方程组在数学上严格等价。标度化列主元消去法/*ScaledPartialPivoting*/对每一行计算。为省时间，si只在初始时计算一次。以后每一步考虑子列中最大的aik为主元。||max1ijnjiasnkkkaa...iiksa注：稳定性介于列主元法和全主元法之间。§1GaussianElimination–PivotingStrategies己妮靡捧祟巡酬估舟搬浙缩啸羚仰卷塌畔移摩伶厢沟其摊潍风蕾勤咽畴搽Ch解线性方程组的直接方法Ch解线性方程组的直接方法高斯-若当消去法/*Gauss-JordanMethod*/与GaussianElimination的主要区别：每步不计算mik，而是先将当前主元akk(k)变为1;把akk(k)所在列的上、下元素全消为0;bAxIbxA1Hey!Isn’titbetterthanGaussianElimination?Whatmakesyousayso?Obviouslywenolongerneedthebackwardsubstitution!You’dbetterwaittillwegothroughthenextsectiontodrawyourconclusion…§1GaussianElimination–Gauss-JordanMethod垄铆瑰轮贷钩轧守娩贬倒腮霹愿僻洲漱付倘谬顺椎拇速指彰文蚀空羌讯挨Ch解线性方程组的直接方法Ch解线性方程组的直接方法运算量/*AmountofComputation*/§1GaussianElimination–AmountofComputation由于计算机中乘除/*multiplications/divisions*/运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。GaussianElimination:Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行n1步)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii(nk)次(nk)2次(nk)次(nk)(nk+2)次nnnknknnk6523)2)((2311消元乘除次数：1次(ni+1)次22)1(1211nninni回代乘除次数：GaussianElimination的总乘除次数为，运算量为级。nnn3132333n白镊仙咬攻苞号览航唤簇约舰询殉端氟锅髓幸矿点库闸蹈币浙郧说畦蠕工Ch解线性方程组的直接方法Ch解线性方程组的直接方法§1GaussianElimination–AmountofComputationCompletePivoting:比GaussianElimination多出比较，保证稳定，但费时。33nOPartialPivoting:比GaussianElimination只多出比较，略省时，但不保证稳定。32nOScaledPartialPivoting:比GaussianElimination多出除法和比较，比列主元法稳定。但若逐次计算si(k)，则比全主元法还慢。)(2nO32nOGauss-JordanMethod:运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。23nO1||AIIAHW:p.42#1p.43#6釉谓断上描愿虏暂岔柏盾奶鳖和伐赞色扬哲逸纫北线治鉴穗剔腋苯豪贡忌Ch解线性方程组的直接方法Ch解线性方程组的直接方法§2三角分解法/*MatrixFactorization*/高斯消元法的矩阵形式/*MatrixFormofG.E.*/：Step1:)0(/111111aaamii记L1=1...11121nmm，则][)1()1(1bAL)1(1)1(1)1(11...baan)2(A)2(bStepn1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121..................nnnnnnnnnbbbaaaaaabALLL其中Lk=1...11,,1knkkmm夜攘鲸淌置宗攘四议豆粳筑鹤雄疽郎纲家槽吹父牙蚀舍甚绿唉插价酬憨成Ch解线性方程组的直接方法Ch解线性方程组的直接方法§2MatrixFactorization–MatrixFormofG.E.1kL1...11,,1knkkmm111211...nLLL111jim,记为L单位下三角阵/*unitarylower-triangularmatrix*/记U=)()2(2)2(22)1(1)1(12)1(11............nnnnnaaaaaaLUAA的LU分解/*LUfactorization*/Heyhasn’tGEgivenmeenoughheadache?WhydoIhavetoknowitsmatrixform??!WhenyouhavetosolvethesystemfordifferentwithafixedA.bCouldyoubemorespecific,please?FactorizeAfirst,thenforeveryyouonlyhavetosolvetwosimpletriangularsystemsand.bbyLyxU衷窿隘几声鲍悔激宅疤铲腊咆干爬窄肚楷限释堑效胞骡沪耶弛尽岛律阵叹Ch解线性方程组的直接方法Ch解线性方程组的直接方法§2MatrixFactorization–MatrixFormofG.E.定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为0，则A的LU分解唯一（其中L为单位下三角阵）。证明：由§1中定理可知，LU分解存在。下面证明唯一性。若不唯一，则可设A=L1U1=L2U2，推出121UU211122211LLUULLUpper-triangularLower-tr