数值线性代数课程设计 线性方程组的直接解法
数理学院 09405011班 0940501120 沈骁 摘要：如何利用电子计算机来快速、有效的求解线性方程组的问题是数值线性代数的核心问题。本文将主要介绍解线性方程组的基本的直接法——高斯消去法，平方根法，并用实例来验证此方法的有效性。
关键字：高斯消去法，顺序消去法，选主元消去法，平方根法，消元过程，回代过程,主元数和乘数
引言：因为各种各样的科学与工程问题往往最终都要归结为一个线性方程组的求解问题。本文在比较着几个方法的基础上，通过一道实例来得到最方便最有效的方法。
基本原理：工程计算和科学研究中的许多问题，最终归结为线性代数方程组的求解。求解的方法也有很多，如高斯消去法（顺序消去法，选主元消去法），平方根法。高斯消去法是目前求解中小规模线性方程组最常用的方法；平方根法是求解对称正定线性方程组最常用的方法之一。为了更快速、更方便的求解线性方程组，下面我们比较一下这几种方法哪种更好。
一、高斯（Causs）消去法就是逐步消去变元的
系数，将原方程组Ax?b化为系数矩阵为三角形的等价方程组Ux?d，然后求解系数矩阵为三角形的方程组而得出原方程组解的方法。把逐步消元去变元的系数，将方程组化为以系数矩阵为三角形的等价方程组的过程称为小院过程；把求系数矩阵为三角形的方程组解的过程称为回代过程。最初求解方程组的高斯消去法也称为顺序消去法，它由消元过程和回代过程组成。 顺序消去法 1． 消元过程
考虑一般方程组，为了推导过程方便，记系数矩阵A的元素a(0)ij为aij，右端向量b的元素bi记为a(0)i,n?1，于是方程组
??a11x1?a12x2??a1nxn?b1??a21x1?a22x2??a2nxn?b2 （1.1）成为
???an1x1?an2x2??annxn?bn??a?0??0?11x1?a12x2??a?0?0?1nxn?a?1n?1??0?00?a?0?21x1?a22x2??a????2nxn?a2n?1假设
???a?0?1x1?a?0?nn2x2??a?0??a?0?nnxnnn?1a(0)11?0，将第1个方程乘以(?a(0)i1a(0))加到第i个
11方程(2?i?n),得到第1个导出方程组?a(0)(0)(0)(0)?11x1?a12x2?a1nxn?a1n?1??a(1)x(1)(1)222?a2nxn?a2n?1其中：???a(1)(1)(1)n2x2?annxn?ann?1a(0)a(0)(1)i1ij?aij?(0)a(0)a1j，
2?i?n，2?j?n?1。11a(0)由于因子i1a(0)不止一次地用到，常
11记为l(1)i,1。再假设a22?0，由第1个导出方程组
的第2个方程乘以(?a(1)i2a(1))加到第i个方程
22(3?i?n)，得到第2个导出方程组
?a?0??0??a?0?0?0?11x1?a12x213x3??a?1nx??n?a1n?1???a1??a?1??a?1??1?22x223x3?2nxn?a2n?1??2??2???aa2?33x3??3nxn?a3n?1类似???a?2??2??2?n3x3??annxn?ann?1地记：l?a(1)i2i2a(1)，则第2个导出方程组的元素
22(1)a(0)?a(1)(i2)a(1)(1)(1)ijij?aa(1)2j?aij?li2a2j，
3?i?n，223?j?n?1。重复上述过程n?1次，得到
n?1个导出方程组
?a?0??a?0??0?0?0?11x112x2?a13x3??a???1nxn?a1n?1??1??1??a?a?1?x?1?22x223x3??a2nn?a2n?1??a?2??2??2?33x3??a3nxn?a3n?1???a?n?1?nnxn?a?n?1?nn?1（1.2）其中第k个导出方程组的元素的递推关
系是la(k?1)ik(k)(k?1)(k?1)ik?a(k?1)，aij?aij?likakj kk（1.3）
(1?k?n?1,k?1?i?n,k?1?j?n?1)。由
于上述消元过程只是将原方程组的系数矩阵和右端进行初等变换，因此，第n?1个导出方程组与原方程组等价，即通过消元过程将方程组（1.1）化成了等价的上三角方程组（1.2）。由第k个导出方程组的计算公式（1.3），容易得到消元过程所需要的乘法和加法次数为
n?1Sn?k)(n?k?1)?n11??((n2?1)
k?13除法次数为Sn?1)12??n?1(n?k)?n(k?12 2.回代过程
回代过程就是求等价三角形方程组（1.2）的解。只要a(k?1)kk?0(k?1,2,,n)，就可以最
后一个方程得到xn的值，再从第n?1个方程得xn?1的值。在一般情形，可求得xi的回代递推公
式
?(n?1)?xann?1n??(n?1),?ann??(x(i?1)n(i?1)i??aijxj)???x?j?i?1iai?1,i?n?1,n?2,,1.ii（1.4） 由公式（1.4）可知，回代过程需要n次除法，其乘法和加法的次数同为
1?2??(n?1)?12n(n?1)。所以回代过程需S1121?2n(n?1)次加法，S22?2n(n?1)次
乘、除法。
3.顺序消去法的运算次数与计算步骤
由消元过程和回代过程的运算次数可知，顺序消
去法的加法次数为
S11?S11?S21?6n(2n?3n?5)，乘除法次数为S122?S11?S12?S22?3(n?3n?1)。消元过
程在编程上机运算时，需采用三重循环，即对于k?1,2,,n?1,i?k?1,k?2,,n,计算
l?a(k?1)ikkka(k?1)；对于j?k?1,k?2,,n?1计算
kka(k)a(k?1)(k?1)ij?ij?likakj。回代过程只需要二重循环，即计算xa(n?1)nn?1n?a(n?1)，对于nni?n?1,n?2,,1,s?0;对于
j?i?1,i?2,,n,计算S?S?a(i?1)ijxj,(xai?1)in?1?Si?a(i?1).ii
4.主元数和乘数
由顺序消去法的推导过程可知，无论是消元过程还是回代过程的都不需要对未知元作真正的运算，Ax?b 的系数矩阵的元素和
而仅需要对方程组
右端作运算。因此，在实际运算中，总是将方程组的系数矩阵和右端合在一起，记成增广矩阵(A,b)。
由消元过程（1.3）可以看到，元素a(k?1)kk为“主
元素“，另外，在消元过程中不止一次用到数
lik，这个数称为消元过程的乘数。 二．平方根法
平方根法又叫Cholesky分解法，是求解对称线性方程组最常用的方法之一。对于一般方阵，为了消除LU分解的局限性和误差的过分积累，而采用了选主元的方法。但对于对称正定矩阵而言，选主元却是完全不必要的。 设A?Rn?n是对称正定的，即A满足AT?A而
且xTAx>0对一切的非零向量x?Rn成立.此时,由定理容易推出 Cholesky分解定理：若
A?Rn?n对称正定，则存在一个对角元均为正数
的下三角阵L?Rn?n,求得A?LLT.上式中的L称作A的Cholesky因子。
若线性方程组的系数矩阵是对称正定的，则我们自然可按如下的步骤求其解：（1）求A的Cholesky分解：A?LLT;(2)求解Ly?b得y；（3）求解LTx?y得x。
实验：1.用高斯（Causs）消去法求解下面的84阶方程组
??61??861??x1????861????7?x15???2???x????15?3????????????。 ?861??861?????x82??x???15??83??86????x84??15????14??解：n?10 A?identity(n)
i?1n Ai,i?6 i?1n?1 Ai,i?1?1
i?2n Ai,i?1?8
b1?7 i?2n?1 bi?15 bn?14
M?lu(A)
P?submatrix(M,1,n,1,n)L?submatrix(M,1,n,n?1,2n) U?submatrix(M,1,n,2?n?1,3?n)y?lsolve(L,P?b) x?lsolve(U,y)
?A??147??25.92??
??3710???UI?Gauss2(A) (UI?100?1)??210??? ?32.3811???47?UI??1?0?2.1?12?2?
??0017.571???147?U?Gauss(A,b) U???0?2.1?12???
?0017.571??M?GaussLU(A) L?M1 U?M2
?00?47?L??1?210??? U??1?0?2.1?12??32.3811????
??0017.571???000?A?LU???000??
??000??2.用你编写的程序求解对称求解对称正定方程组Ax?b，其中b随机的选取，系数矩阵为100
??101??1101??1101??阶?????。 ?1101??1101????110??i?1nAi,i?10解: n?5 i?1n?1 Ai,i?1?1 bi?rnd(1)
i?2nAi,i?1?1L?cholesky(A)
y?lsolve(L,b)x?lsolve(LT,y)
改进的平方根方法：
??3.1620.316000?03.1460.3180?LT??0??003.1460.3180??
?0003.1460.318????00003.146??Di,i?(LT)i,ii?1n L?L?D?1
D?D?D??00000?00?T?000M1M2M1?A???00000??
?00000????00000??
结论：通过用两种方法对题目的求解，我们得到
高斯消去法适合用于中小规模线性方程的求解，它一般用于系数矩阵稠密而又没有任何特殊结构的线性方程组，由它改进后得到的选主元消去法是目前计算机上常用的有效方法；而对于一般方阵，为了消除LU分解的局限性和误差的过分积累，而采用了选主元的方法。但对于对称正定矩阵而言，选主元却是完全不必要的。通过上面两道题目的解答让我们对求解线性方程组的求法也有了具体的深刻的了解，更好的认识到了高斯（Causs）消元法和平方根法所适合的范围，也
知道了这两种方法各有各的优点。因此在我们做题时应该综合考虑各种因素来确定我们所要用的方法。这样才能使题目得到最方便、最有效的解答。 参考文献：
徐树方 高立 张平文 《数值线性代数》北京大学出版社 11页至10页
朱方生 李大美 李素贞《计算方法》武汉大学出版社 44页至86页
徐世良 《数值分析与算法》机械工业出版社 36页至44页