线性代数方程组数值解法及MATLAB实现综述

线性代数方程组数值解法及MATLAB实现综述廖淑芳20122090数计学院12计算机科学与技术1班（职教本科）一、分析课题随着科学技术的发展，提出了大量复杂的数值计算问题，在建立电子计算机成为数值计算的主要工具以后，它以数字计算机求解数学问题的理论和方法为研究对象。其数值计算中线性代数方程的求解问题就广泛应用于各种工程技术方面。因此在各种数据处理中，线性代数方程组的求解是最常见的问题之一。关于线性代数方程组的数值解法一般分为两大类：直接法和迭代法。直接法就是经过有限步算术运算，可求的线性方程组精确解的方法（若计算过程没有舍入误差），但实际犹如舍入误差的存在和影响，这种方法也只能求得近似解，这类方法是解低阶稠密矩阵方程组级某些大型稀疏矩阵方程组的有效方法。直接法包括高斯消元法，矩阵三角分解法、追赶法、平方根法。迭代法就是利用某种极限过程去逐步逼近线性方程组精确解的方法。迭代法具有需要计算机的存储单元少，程序设计简单，原始系数矩阵在计算过程始终不变等优点，但存在收敛性级收敛速度问题。迭代法是解大型稀疏矩阵方程组（尤其是微分方程离散后得到的大型方程组）的重要方法。迭代法包括Jacobi法SOR法、SSOR法等多种方法。二、研究课题-线性代数方程组数值解法一、直接法1、Gauss消元法通过一系列的加减消元运算，也就是代数中的加减消去法，以使A对角线以下的元素化为零，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。1.1消元过程1.高斯消元法(加减消元)：首先将A化为上三角阵，再回代求解。11121121222212nnnnnnnaaabaaabaaab(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()000000nnnnnnnnaaaabaaabaabab步骤如下：第一步：1111,2,,iaiina第行第行11121121222212nnnnnnnaaabaaabaaab111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab第二步：(2)2(2)222,3,,iaiina第行第行111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab11121311(2)(2)(2)(2)222322(3)(3)(3)3333(3)(3)(3)300000nnnnnnnaaaabaaabaabaab类似的做下去，我们有：第k步：()()k,1,,kikkkkaiikna第行第行。n－1步以后，我们可以得到变换后的矩阵为：11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()000000nnnnnnnnaaaabaaabaabab注意到，计算过程中()kkka处在被除的位置，因此整个计算过程要保证它不为0。所以，Gauss消元法的可行条件为：()0kkka。就是要求A的所有顺序主子式均不为0，即1111det0,1,,iiiiaainaa因此，有些有解的问题，不能用Gauss消元求解。另外，如果某个()kkka很小的话，会引入大的误差。例用Gauss消去法解方程组：（1）1234123341518311151111631112xxxx（1）对增广矩阵进行初等变换1221331443()21()121()41233415371512334150522218311155321911116044343111277700444EEEEEEEEE2332443445()677()()61112334123341515373705051515222222112911290000111136367357910000003633EEEEEEEEE得等价方程组12342343441233415371552221129113691033xxxxxxxxxx回代得40x，33x，22x，11x。第一步：将(1)/3使x1的系数化为1,再将(2)、(3)式中x1的系数都化为零，即由(2)-2×(1)(1)得)1(321)1(......23132xxx)1(32)2(......03432xx由(3)-4×(1)(1)得第二步：将(2)(1)除以2/3，使x2系数化为1，得再将(3)(1)式中x2系数化为零，由(3)(1)-(-14/3)*(2)(2)，得第三步：将(3)(2)除以18/3，使x3系数化为1，得经消元后，得到如下三角代数方程组：1.2回代过程由(3)(3)得x3=1,将x3代入(2)(2)得x2=-2,将x2、x3代入(1)(1)得x2=1,所以，本题解为[x]=[1,2,-1]T1.3高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为第一步，消元（1）令aij(1)=aij,（i,j=1,2,3,…,n）bi(1)=bi,（i=1,2,3,…,n）（2）对k=1到n-1，若akk(k)≠0，进行lik=aik(k)/akk(k),（i=k+1,k+2,…,n）aij(k+1)=aij(k)-lik*akj(k),（i,j=k+1,k+2,…,n）bi(k+1)=bi(k)-lik*bk(k),（i=k+1,k+2,…,n）第二步，回代若ann(n)≠0xn=bn(n)/ann(n)xi=(bi(i)–sgm(aij(i)*xj)/-aii(i),（i=n-1,n-2,…,1）,(j=)1(32)3(......6310314xx)2(32)2(......02xx)2(3)3(......6318x)3(3)3(......1xi+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,…,nai1=li1u11,i=1,2,…,n推出u1j=a1j,j=1,2,…,nli1=ai1/u11,i=1,2,…,n这样就定出了U的第一行元素和L的第一列元素。设已定出了U的前k-1行和L的前k-1列，现在确定U的第k行和L的第k列。由矩阵乘法：当rk时，lkr=0,且lkk=1，因为nrrjkrkjula1nrrjkrkjkjulua1所以，同理可推出计算L的第k列的公式：因此得到如下算法——杜利特（Doolittle）算法:(1)将矩阵分解为A=LU,对k=1,2,…,n；j=k,k+1,…n；i=k,k+1,…n；公式1(2)解Ly=b(3)解Ux=y对大规模稀疏问题，如果能够通过调整方程及未知量的顺序使得方程组的系数矩阵成带状结构，则对系数矩阵使用通常的LU分解，可以保障单位下三角矩阵L及上三角矩阵U仍为带状结构.3、直接三角分解法Gauss消去法还有许多变形，有些变形是为了利用特殊技巧减少误差，把Gauss消去法改写为更紧凑的形式，还有一些变形时根据某类矩阵的特性作一些修正和简化，这些方法可统称为直接三角分解法。矩阵的三角分解设A的顺序主子式0(1,2,,)kkn，则可建立线性方程组Axb的Gauss消去法与矩阵分解的关系，即矩阵A的LU分解。这个问题前面已经讲的比较详nrrjkrkjkjnkkjulau1,...,1,nrkkrjkrikiknkkiuulal1,...,1,/)(11,...,2,1:2krrkrkknkylby公式nkrkkrkrkknnkuxuyx11,...,1,/)(3：公式1/)(u11kkkknrrjkyikjknryjkikjkiluulalula细了，此处不再赘述。Doolittle分解法首先假设A的顺序主子式k都不为零，则A可作Doolittle分解，即ALU，其中L是单位下三角阵，有1iil，ij时0ijl；U是上三角阵，ij时0iju。仔细写出为111211112121222212221212111nnnnnnnnnnnnaaauuuaaaluuALUaaallu（2.11）在前面逐步推导L和U的元素公式都要借助于有关的()kija来表示。现在强调指出，只要从给定的A通过比较（2.11）式的两边就可能逐步地把L和U构造出来，而不必利用Gauss消去法的中间结果，这种方法称为Gauss消去法的紧凑格式。根据矩阵的乘法规则，比较（2.11）式的两边可得min(,)1ijijikkjkalu，,1,2,,ijn（2.12）先算出U的第1行，在（2.12）令1i，由111l，10(1)jljn可得11jjua，1,2,,jn接着在（2.12）中令1j，由1111iialu，从而算出L的第1列1111111//iiilauaa，2,,in若U的第1至1k行和L的第1至1k列已经算出，则由（2.12）可计算出U的第k行元素11kkjkjkrrjrualu，,1,,jkkn（2.13）接着再计算出L的第k列元素11kikirrkrikkkalulu，1,,jkn（2.14）解方程组Axb就化为求解LUxb，分两步求解。第一步解Lyb，其中L为下三角阵，只要用逐次向前代入的方法；第二步解Uxy，其中U为上三角阵，用逐次向后代入方法即可解除x。例用Doolittle方法求解：123462116241011141510135xxxx解：第1步算出L和U：111311165119161037L，62111021333379101019174U第2步解Lyb得：231916,3,,574Ty第3步解Uxy得：(1,1,1,1)Tx二、迭代法迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根。对方程组：Axb做等价变换：xGxg如：令AMN，则11()AxbMNxbMxbNxxMNxMb则，我们可以构造序列(1)()kkxGxg若()*kxx***xGxgAxb则，我们可以构造序列(1)()kkxGxg若()*kxx***xGxgAxb同时：(1)()()**(*)kkkxxGxGxGxx