线性代数方程组数值解法及MATLAB实现综述廖淑芳20122090 数计学院12计算机科学与技术1班（职教本科）一、分析课题随着科学技术的发展，提出了大量复杂的数值计算问题，在建立电子计算机成为数值计算的主要工具以后，它以数字计算机求解数学问题的理论和方法为研究对象。

其数值计算中线性代数方程的求解问题就广泛应用于各种工程技术方面。

因此在各种数据处理中，线性代数方程组的求解是最常见的问题之一。

关于线性代数方程组的数值解法一般分为两大类：直接法和迭代法。

直接法就是经过有限步算术运算，可求的线性方程组精确解的方法（若计算过程没有舍入误差），但实际犹如舍入误差的存在和影响，这种方法也只能求得近似解，这类方法是解低阶稠密矩阵方程组级某些大型稀疏矩阵方程组的有效方法。

直接法包括高斯消元法，矩阵三角分解法、追赶法、平方根法。

迭代法就是利用某种极限过程去逐步逼近线性方程组精确解的方法。

迭代法具有需要计算机的存储单元少，程序设计简单，原始系数矩阵在计算过程始终不变等优点，但存在收敛性级收敛速度问题。

迭代法是解大型稀疏矩阵方程组（尤其是微分方程离散后得到的大型方程组）的重要方法。

迭代法包括Jacobi法SOR法、SSOR法等多种方法。

二、研究课题-线性代数方程组数值解法一、直接法1、Gauss消元法通过一系列的加减消元运算，也就是代数中的加减消去法，以使A对角线以下的元素化为零，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。

1.1消元过程1. 高斯消元法(加减消元)：首先将A 化为上三角阵，再回代求解。

11121121222212n n n n nnn a a a b a a a b a a a b ⎛⎫⎪ ⎪ ⎪⎪⎝⎭(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()00000n n nn n nnn a a a a b a a a b a a b a b ⎛⎫ ⎪⎪ ⎪ ⎪ ⎪⎪⎝⎭步骤如下：第一步：1111,2,,i a i i n a -⨯+=第行第行11121121222212n n n n nnn a a a b a a a b a a a b ⎛⎫⎪ ⎪ ⎪⎪⎝⎭111211(2)(2)(2)2222(2)(2)(2)200nnn nnn a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭第二步：(2)2(2)222,3,,i a i i n a -⨯+=第行第行 111211(2)(2)(2)2222(2)(2)(2)200n nn nnn a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭11121311(2)(2)(2)(2)222322(3)(3)(3)3333(3)(3)(3)300000nn nn nnn a a a a b a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎪⎝⎭类似的做下去，我们有：第k 步：()()k ,1,,k ikk kka i i k n a -⨯+=+第行第行。

n －1步以后，我们可以得到变换后的矩阵为：11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()00000n n nn n nnn a a a a b a a a b a a b a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭注意到，计算过程中()k kk a 处在被除的位置，因此整个计算过程要保证它不为0。

所以，Gauss 消元法的可行条件为：()0k kka ≠。

就是要求A 的所有顺序主子式均不为0，即1111det 0,1,,i i ii a a i n a a ⎛⎫ ⎪≠= ⎪ ⎪⎝⎭因此，有些有解的问题，不能用Gauss 消元求解。

另外，如果某个()k kk a 很小的话，会引入大的误差。

例 用Gauss 消去法解方程组：（1）1234123341518311151111631112x x x x -⎛⎫⎛⎫⎛⎫⎪ ⎪ ⎪---- ⎪ ⎪ ⎪= ⎪ ⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭ （1）对增广矩阵进行初等变换1221331443()21()121()41233415371512334150522218311155321911116044343111277700444E E E E E E E E E +→-+→-+→-⎛⎫⎪⎛-⎫ ⎪- ⎪ ⎪---- ⎪ ⎪−−−−−−→ ⎪ ⎪ ⎪ ⎪⎪-⎝⎭ ⎪-- ⎪⎝⎭2332443445()677()()6111233412334151537370505151522222211291129000111136367357910000003633E E E E E E E E E +→+→-+→--⎛⎫⎛⎫⎪⎪ ⎪ ⎪-- ⎪ ⎪ ⎪ ⎪−−−−−→−−−−−−→ ⎪ ⎪⎪⎪ ⎪⎪⎪ ⎪⎝⎭⎝⎭得等价方程组12342343441233415371552221129113691033x x x x x x x x x x -++=⎧⎪⎪-++=⎪⎪⎨+=⎪⎪⎪=⎪⎩回代得40x =，33x =，22x =，11x =。

第一步：将(1)/3使x 1的系数化为1,再将(2)、(3)式中x 1的系数都化为零，即由(2)-2×(1)(1)得由(3)-4×(1)(1)得第二步：将(2)(1)除以2/3，使x 2系数化为1，得再将(3)(1)式中x 2系数化为零，由(3)(1)-(-14/3)*(2)(2)，得第三步：将(3)(2)除以18/3，使x 3系数化为1，得经消元后，得到如下三角代数方程组：)1(321)1( (23)132=++x x x )1(32)2( (034)32=+x x )1(32)3( (63)10314-=--x x )2(32)2(......02=+x x )2(3)3( (63)18-=x )3(3)3(......1-=x1.2回代过程由(3)(3)得 x 3=1,将x 3代入(2)(2)得x 2=-2,将x 2 、x 3代入(1)(1)得x 2=1,所以，本题解为[x]=[1,2,-1]T1.3高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为 第一步，消元（1） 令a ij (1) = a ij , （i,j=1,2,3,…,n ）b i (1) =b i , （i=1,2,3,…,n ） （2） 对k=1到n-1，若a kk (k)≠0，进行l ik = a ik (k)/ a kk (k), （i=k+1,k+2,…,n ） a ij (k+1) = a ij (k) - l ik * a kj (k), （i,j= k+1,k+2,…,n ） b i (k+1) = b i (k) - l ik * b k (k), （i= k+1,k+2,…,n ）第二步，回代若a nn (n) ≠ 0x n = b n (n) / a nn (n)x i = (b i (i) – sgm(a ij (i) * x j )/- a ii (i) ,（i = n-1,n-2,…,1）,( j = i+1,i+2,…,n )2 、LU 分解法求解线性代数方程组除了高斯消元法外，还常用LU 分解法（三角形分解法）。

LU 分解法的优点是当方程组左端系数矩阵不变，仅仅是方程组右端列向量改变，即外加激励信号变化时，能够方便地求解方程组。

矩阵的三角分解法可分为直接三角分解法,列主元三角分解法,平方根法,三对角方程组的追赶法。

下面讨论直接三角分解法。

设n阶线性方程组Ax=b 。

假设能将方程组左端系数矩阵A，分解成两个三角阵的乘积，即A=LU ，式中，L为主对角线以上的元素均为零的下三角矩阵, 且主对角线元素均为1的上三角矩阵；U为主对角线以下的元素均为零所以有，LUx=b令Ux=y，则Ly=b由A=LU,由矩阵的乘法公式：a1j = u1j, j=1,2,…,na i1 = li1u11, i=1,2,…,n推出u1j = a1j, j=1,2,…,nl i1 = ai1/u11, i=1,2,…,n这样就定出了U的第一行元素和L的第一列元素。

设已定出了U的前k-1行和L的前k-1列，现在确定U的第k行和L的第k列。

由矩阵乘法：. -当r>k 时，l kr =0, 且l kk =1，因为所以，同理可推出计算L 的第k 列的公式：因此得到如下算法——杜利特（Doolittle ）算法:(1) 将矩阵分解为A=LU,对k=1,2,…,n ；j=k,k+1,…n ； i=k,k+1,…n ；公式1(2) 解L y =b(3) 解U x =y对大规模稀疏问题，如果能够通过调整方程及未知量的顺序使得方程组的系数矩阵成带状结构，则对系数矩阵使用通常的LU 分解，可以保障单位下三角矩阵L 及上三角矩阵U 仍为带状结构.∑==nr rjkr kj u l a 1∑=+=-=n r rjkr kj kj nk k j u l a u 1,...,1,∑=+=nr rjkr kj kj u l u a 1∑=+=-=nr kkrj kr ik ik nk k i u u l a l 1,...,1,/)(∑-==-=11,...,2,1:2k r rkr k k nk y l b y 公式∑+=-=-=nk r kkrkr k k n n k u x uy x 11,...,1,/)(3：公式⎪⎪⎪⎩⎪⎪⎪⎨⎧=-=-=∑∑==1/)(u 11kk kknr rj ky ik jk nr yjki kj ki l u u l a l u l a3、直接三角分解法Gauss 消去法还有许多变形，有些变形是为了利用特殊技巧减少误差，把Gauss 消去法改写为更紧凑的形式，还有一些变形时根据某类矩阵的特性作一些修正和简化，这些方法可统称为直接三角分解法。

矩阵的三角分解设A 的顺序主子式0(1,2,,)k k n ∆≠=，则可建立线性方程组Ax b =的Gauss消去法与矩阵分解的关系，即矩阵A 的LU 分解。

这个问题前面已经讲的比较详细了，此处不再赘述。

Doolittle 分解法首先假设A 的顺序主子式k ∆都不为零，则A 可作Doolittle 分解，即A LU =，其中L 是单位下三角阵，有1ii l =，i j <时0ij l =；U 是上三角阵，i j >时0ij u =。

仔细写出为111211112121222212221212111n n n n n n nn n n nn a a a u u u a a a l u u A LU a a a l l u ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪=== ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭（2.11） 在前面逐步推导L 和U 的元素公式都要借助于有关的()k ij a 来表示。