消去法等解线性方程组(一)

个人资料整理仅限学习使用1/23消去法等解线性方程组一）中文摘要Gauss消去法是目前求解中小规模线性方程组即阶数不要太高，例如不超过1000）常用的方法，它一般用于系数矩阵稠密即矩阵的绝大多数元素都是非零的）而没有任何特殊结构的线性方程组。本文对GAUSS、列主元及完全主元消去法这几种方法进行了比较。求解n阶线性方程组Ax=b的基本思想是在逐步消元的过程中，把方程组的系数矩阵化为上三角矩阵，从而将原方程组约化为容易求解的等价三角方程组，然后进行回代求解。b5E2RGbCAP关键词：Gauss消去法；C++编程ELIMINATIONMETHODFORSOLVINGLINEAREQUATIONS(一p1EanqFDPwENGLISHABSTRACTGausseliminationmethodisthesmallsizeofsolvinglinearequations(i.e.theorderisnottoohigh,forexample,notmorethan1000commonlyusedmethod,itisgenerallyusedforthecoefficientmatrixdense(ie,mostofthematrixelementsarenonzerowithoutanyspecialstructureoflinearequations.Inthispaper,GAUSS,themainelementandcompletelyEliminationPCAthesemethodswerecompared.个人资料整理仅限学习使用2/23SolvingnlinearequationsAx=bisthebasicideaofthegradualeliminationprocess,theequationsofthecoefficientmatrixintouppertriangularmatrix,thusreducedtotheoriginalequationseasytosolvetrigonometricequationsequivalencegroupthenbacksubstitutiontosolve.DXDiTa9E3dKeywords:Gausseliminationmethod。C++ProgrammingRTCrpUDGiT目录消去法等解线性方程组一）1目录3一、问题背景4二、问题提出5三、数学原理与算法分析53.1不选主元Gauss消去法53.1.1不选主元Gauss消去法数学原理53.1.2不选主元Gauss消去法算法步骤63.2列主元Gauss消去法73.2.1列主元Gauss消去法数学原理73.2.1列主元Gauss消去法算法描述83.3完全主元Gauss消去法83.3完全主元Gauss消去法数学原理83.3.1算法描述如下103.4计算结果及敏度分析11四、其他方法13五、参考文献14个人资料整理仅限学习使用3/23六、附录15一、问题背景在古代数学和近代数学数值计算和工程应用中，求解线性方程组都是重要的课题。西方的Gauss消元法在求解未知数多的大型线形方程组则是在20世纪中叶电子计算机问世后才成为现实。这次实验将充分运用各种数值计算方法，及计算机的强大数值计算功能来解决所遇到的问题。5PCzVD7HxA数学上，高斯消元法，是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。其基本思路如下：jLBHrnAILg设有方程组Ax=b，设A是可逆矩阵。将矩阵的初等行变换作用于方程组的增广矩阵bAB，将其中的A变换成一个上三角矩阵，然后求解这个三角形方程组xHAQX74J0X高斯消元法的算法复杂度是O(n3，这就是说，如果系数矩阵的是n×n，那么高斯消元法所需要的计算量大约与n3成比例。LDAYtRyKfE高斯消元法对于一些矩阵来说是稳定的。对于普遍的矩阵来说，高斯消元法在应用上通常也是稳定的，所以本次课程设计采用GAUSS、列主元及完全主元消去法求解线性方程组。Zzz6ZB2Ltk个人资料整理仅限学习使用4/23二、问题提出先用你所熟悉的计算机语言将不选主元、列主元和完全主元Gauss消去法编写成通用的子程序，然后用你编写的程序求解下面的方程组考虑n从70到80）dvzfvkwMI114151515157681681681681681612321nnnxxxxxx对上述方程组还可以采用哪些方法求解？选择其中一些方法编程上机求解上述方程组，说明最适合的是什么方法；将计算结果进行比较分析，谈谈你对这些方法的看法。rqyn14ZNXI个人资料整理仅限学习使用5/23三、数学原理与算法分析3.1不选主元Gauss消去法3.1.1不选主元Gauss消去法数学原理Gauss消去法即是把一个给定的矩阵分解为一个下三角L和一个上三角U的乘积。为此我们找到了一个最简单的下三角矩阵TkkkLIle.其中1,(0,,0,,,)kkknklllEmxvxOtOco即1,,1111kkknkLll1）这种类型的下三角称作Gauss变换。而称向量kl为Gauss向量。对于一个给定的向量1(,,)TnnxxxR，我们有111,(,,,,,)TkkkkkknknkLxxxxxlxxl只要取,1,,iikkxliknx，便有1(,,,0,,0)TkkLxxx。于是将Gauss变换作用于一个矩阵，就将对应的列向量相应项变为0。一般的阶矩阵A,在一定条件下，我们也可以计算n-1个Gauss变换121nLLL使SixE2yXPq5121nnLLLA为上三角矩阵。ALU，这种计算主元分解的方法称做Gauss消去法。LU分解的可行性分析：若nnAR的顺序主子阵L均非奇异，则存在唯一的单位下三角nnLR和上三角阵nnUR使得ALU对于题1中，我们可以通过高等代数的方法计算个人资料整理仅限学习使用6/23出对于*det()A*.det()A0,也即存在唯一性。6ewMyirQFL3.1.2不选主元Gauss消去法算法步骤步骤1，首先将方程组用增广矩阵(1)ijnnBAba表示。步骤2:1）输入数据A和b，置det=1；2）消元过程，对1,2,,1kna、选主元，找,1,,kikkn使得,maxkikikkinaa；b、如果,0kika，则矩阵A奇异，程序结束；否则执行3）。c、如果kik，则交换第k行与第ki行对应元素位置，kkjijaa，,,1jkn。d、消元，对,,ikn，计算/,ikikkklaa对1,,1jkn，计算：.ijijikkjaala2）iiikikbblb3）e、置det=kka*det步骤3：回代过程：1）若0,nna则矩阵奇异，程序结束；否则执行2）。2）,1/;nnnnnxaa对1,,2,1in，计算,11/niinijjiijixaaxa3.2列主元Gauss消去法3.2.1列主元Gauss消去法数学原理每次消去中，选取每列的绝对值最大的元素作为消去对象并作为主元素。然后换行使之变到主元位子上，在进行消元计算。设)()(kkbxA，确定第k列个人资料整理仅限学习使用7/23主元所在位置ki，在交换ki行和k行后，在进行消元。根据矩阵理论，交换ki和k两个方程的位置，列主元素的消去过程相当于对交换后的新矩阵进行消元，即kavU42VRUs)1(,kkikkAAILk4）同时，右端向量)(kb变化为)1(,kkikkbbILk5）3.2.1列主元Gauss消去法算法描述如果在高斯顺序消去法消去过程进行到第i步时，现选取ria)(nri中绝对值最大的元素，设为第j行的元素jia，把矩阵的第i行和第j行互换，这时iia变为jia，然后将第i+1行至第n行中的每一行减去第i行乘以iikiaak代表行号），依次进行消元。y6v3ALoS89Gauss列主元消去法的算法步骤如下：步骤1：将方程组写成以下的增广矩阵的形式：43212423222114131211............nnnnaaaaaaaaaaaa6）步骤2：对k=1，2，3,...,n-1,令nksskpkaamax；交换增广矩阵的第k行与第p行；个人资料整理仅限学习使用8/23步骤3：对j=k+1，k+2，...,n,计算kkjkkmjmjmaaaaam=看，k+1，...，n）kkjkkjjaabbb；步骤4：算法结束。3.3完全主元Gauss消去法3.3完全主元Gauss消去法数学原理设方程组的增广矩阵为nnnnjnninijiiinjnjbaaaabaaaabaaaabaaaaB1111111112121222222111112117）首先在A中选取绝对值最大的元素作为主元素，例如0max1111ijnjnijiaa，然后交换B的第1行与第1i行，经第一次消元计算得22,,bAbA8）重复上述过程，已完成第1k步的选主元素，交换两行及交换两列，消元计算，),(bA约化为nnnnkkknkknnkkbaabaabaabaaabA2222111211,9）其中kA元素仍记作ija，kb元素仍记作1,,2,1nkbi。个人资料整理仅限学习使用9/23第k步选主元素在kA右下角方框内选），即确定ki，kj使0maxijnjknikjiaakk10）交换kkbA,第k行与kj行元素交换kA第k列与kj列元素，将kkjia调到kk,位置，再进行消元计算，最后将原方程化为nnnnnnbbbyyyaaaaaa21212221121111）其中1y，2y，…，ny的次序为未知数1x，2x，…，nx调换后的次序。回代求解得1,2,11niayabyabyiinijiijiinnnn12）3.3.1算法描述如下设bAx。本算法用A的带有行、列交换的Gauss消去法，消元结果冲掉A，乘数ijm冲掉ija，计算解x冲掉常数项b，用k表示对A的消元次数。用一整型数组nIz开始记录未知数1x，2x，…，nx的次序即下标1，2，…，n），最后记录调换后未知数的下标。M2ub6vSTnP步骤1对于i=1,2，…，n，有iiIz；对于1k，2，…，1n，做到步6；步骤2选主元素ijnjknikjiaakkmax；步骤3如果0kkjia，则计算停止这时0detA）；个人资料整理仅限学习使用10/23步骤41）如果kik，则转2），否则换行：nkkjaajikjk,1,，kikbb；2）如果kjk，则转步5，否则换行：),2,1(niakij，)(kjIzkIz；步骤5计算乘数kkikikikaamanki,,1；步骤6消元计算kjikijijamaa),1;,,1(nkjnki；kikiibmbbnki,,1。步骤7回代求解1）nnnnabb；2）对于1,2,,2,1nni，iinijjijiiababb1。步骤8调整未知数的次序1）对于ni,