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

Ch3解线性方程组的直接方法求解bxA高斯消元法：思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=消元记,)()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回代)()(/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–TheMethod0(1,2,,1)定理（矩阵的分解）设为阶矩阵，如果的顺序主子式，则可分解为一个下三角矩阵和一个上三角矩阵的乘积，且这种分解是唯一的.iLUAnADinALU选主元消去法例：单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用GaussianElimination计算：911212110/aam999212210101010...0.011ma8个92121012mb9991010011100,112xx小主元/*Smallpivotelement*/可能导致计算失败。全主元消去法/*CompletePivoting*/每一步选绝对值最大的元素为主元素，保证。1||ikmStepk:①选取;0||max||,ijnjikjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去换列的步骤，每次仅选一列中最大的元。0||max||,iknikkiaak例：211111091,112xx11021111102119注：列主元法没有全主元法稳定。0,112xx例：211101019999991010010101注意：这两个方程组在数学上严格等价。标度化列主元消去法/*ScaledPartialPivoting*/对每一行计算。为省时间，si只在初始时计算一次。以后每一步考虑子列中最大的aik为主元。||max1ijnjiasnkkkaa...iiksa注：稳定性介于列主元法和全主元法之间。§1GaussianElimination–PivotingStrategies高斯-若当消去法/*Gauss-JordanMethod*/与GaussianElimination的主要区别：每步不计算mik，而是先将当前主元akk(k)变为1;把akk(k)所在列的上、下元素全消为0;bAxIbxA1Hey!Isn’titbetterthanGaussianElimination?Whatmakesyousayso?Obviouslywenolongerneedthebackwardsubstitution!You’dbetterwaittillwegothroughthenextsectiontodrawyourconclusion…§1GaussianElimination–Gauss-JordanMethod运算量/*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§1GaussianElimination–AmountofComputationCompletePivoting:比GaussianElimination多出比较，保证稳定，但费时。33nOPartialPivoting:比GaussianElimination只多出比较，略省时，但不保证稳定。32nOScaledPartialPivoting:比GaussianElimination多出除法和比较，比列主元法稳定。但若逐次计算si(k)，则比全主元法还慢。)(2nO32nOGauss-JordanMethod:运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。23nO1||AIIA123*0.0012.0003.0001.0001.0003.7124.6232.0002.0001.0725.6433.000(0.4904,0.05104,0.3675)10.0012.0003.0001.000|1.0003.7TxxxxAb例1：阶方程组四位有效数字精确解为解：（）高斯消去法213132100020001.997124.6232.0002.0001.0725.6433.0000.0012.0003.0001.0000.0012.0003.0001.000020043005100202004300510020400160062003005.0002.000(0.400mmmx,0.09989,0.4000)T21310.50000.000522.0001.0725.6433.000|1.0003.7124.6232.0000.0012.0003.0001.0002.0001.0725.6433.00003.1761.8010.50002.0013.0031.002mmAb（）交换行，避免绝对值小的主元作除数。（列主元素法）320.63002.0001.0725.6433.00003.1761.8010.500001.8680.687(0.4900,0.05112,0.3678)mTx1123G-J245.356123100356001|245010245010356001123100nAAAI例2：用法求的逆矩阵解：15/32001/302/31012/301/31101/31101/205/22013/203/21001/211/20100132010331|.001210nIA§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§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§2MatrixFactorization–MatrixFormofG.E.定理若A的所有顺序主子