线性方程组的直接解法

1线性方程组的直接解法

Gauss消去法直接三角分解方法方程组的性态与误差估计2在自然科学与工程技术中，很多问题的解决常常归结为解线性方程组的问题：很多数值计算方法到最后也涉及到线性方程组的求解问题：如电学中的网络问题，机械和建筑结构的设计和计算等。

如求样条插值的M和m的关系式，解曲线拟合的法方程，求矩阵特征值的反幂法等问题。电子计算机线性方程组{稠密和稀疏（按系数矩阵含零元多少分）高阶和低阶（按阶数的高低分）对称正定、对角占优等（按系数矩阵的形状性质分）基本解法{直接法（通过有限步计算得到精确解，适用于低阶、大型带型阵）

迭代法（通过逐次迭代逼近得到近似解，适用于大型稀疏、非带型阵）线性方程组及方法分类4求解线性方程组：对此方程组进行求解有两种方法：采用Cramer法则、消元法。5Cramer(克莱姆)法则

对于20阶的线性方程组,若用Cramer法则求解,其乘、除运算次数为9.7*1020,用一亿次/秒的计算机,要30.8万年！若用高斯消去法进行数值求解，乘、除运算只需约3060次。定理：如果线性方程组则方程组有唯一解：其中Ak是将A的第k列元素依次换成常数项b1,…,bn得到的行列式。的系数行列式非零，即计算量大6Gauss消去法一、高斯顺序消去法思路首先将A化为上三角阵

/*upper-triangularmatrix*/，再回代求解

/*backwardsubstitution*/。=

是一种古老的求解线性方程组的方法,按自然顺序进行消元的方法.7例1

解方程组解step1

消元8Step2

对上三角形方程进行回代求解,得

下面我们来一般性地讨论求解n阶线性方程组的高斯顺序消去法.9消元Step1：设，计算因子将增广矩阵/*augmentedmatrix*/第i行li1

第1行，得到与(1)式等价的方程组10Step2：一般第k次消元(1≤k

≤n-1)

1112Step3：继续上述过程,且设aii（i-1）≠0(i=1,2,…,n-1),直到完成第n-1

次消元,最后得到与A(0)x=b(0)等价的三角形方程组A(n-1)x=b(n-1).将(1)式化为(2)式的过程称为消元过程.forforforGauss消去法的消元过程算法Gauss消去法工作量为14回代定理

若A的所有顺序主子式

/*determinantofleadingprincipalsubmatrices*/

均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注：事实上，只要A

非奇异，即A1

存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。15高斯顺序消去法流程图FTk=k+1FT消元过程回代过程16顺序消去法的缺点为：当主元akk(k

-1)=0时,消元过程不能继续进行；当akk

(k-1)

≠0时,虽然消元过程可以进行,但若

akk

(k-1)

≈0时,时,会出现很小的数作除数的现象,使舍入误差增大,导致解的严重失真.17例2解方程组/*精确解为*/用Gauss消去法计算：二、主元素消去法18

由上例可以看出,为提高算法的数值稳定性,应选取绝对值尽可能大的元素作主元.按列部分选主元的消去法也称列主元消去法。19解：20一些特殊情况,主元就在对角线上,不需选主元.如元素满足如下条件的矩阵

即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角占优矩阵.例如性质：严格对角占优矩阵必定非奇异.

算法:

Gauss列主元消去算法求方程组Ax=b

的解.输入:增广矩阵An(n+1)=（A|b）.输出:

近似解xk=ak,n+1(k=1,2,…,n)

或失败信息.消元过程fork=1,2,…,n-1doStep1-Step4

Step1

寻找行号ik

,使得Step2

如果，则交换第k行和ik行；

否则转Step7

算法:

Gauss列主元消去算法（续）Step3fori=k+1,…,n

计算

Step4forj=k+1,…,n+1

计算

回代过程Step5Step6fori=n-1,…,1

计算

Step7Output(系数矩阵奇异);/*不成功*/STOP.

编程时此处调用回代算法23三、高斯-约当消去法（求矩阵逆）与Gauss消去法的主要区别：

每一步不计算lik

，而是先将当前主元akk(k-1)

变为1;把akk(k-1)

所在列的上、下元素全消为0;这种方法是不是比Gauss消去法更好?Gauss消去法过程中，消去对角线下方和上方的元素，称这种方法为高斯-约当消去法.这种方法不用回代过程了，看上去是要好些？24运算量

/*AmountofComputation*/由于计算机中乘除/*multiplications/divisions*/

运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。

Gauss消去法:Stepk：设，计算因子且计算共进行n

1步(nk)次(nk)2

次(nk)次(nk)(nk+2)

次消元时乘除次数：1次(ni+1)次回代时乘除次数：Gauss消去法的总乘除次数为，运算量为级。25

Gauss-Jordan消去法:

运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。Gauss-Jordan消元法求矩阵的逆

Gauss消元法有许多变形，列主元素法是其中之一，在列主元法的基础上还可对算法进行如下的修改：在消元过程中选主元后，先将主元化为1，然后将主元所在列上，下方各元素均化为0，这样消元的结果使系数矩阵化为了单位阵，无需回代就得到了原方程之解，这种无回代过程的列主元素法称为Gauss-Jordan消元法。

Gauss-Jordan消元法比顺序消去法计算量大一点，实践中使用不多，但用它求逆阵却十分方便。因为消元过程实质上就是对系数矩阵A实行初等变换，将A化为单位阵，相当于对A左乘了一系列的初等变换阵M1，M2，…，Mn-1，Mn，使：紧接下屏Gauss-Jordan消元法求矩阵的逆（续1）这表明同样的一组初等变换在将A化为I的同时，可将I化为A1，即有：

因此，以Gauss-Jordan消元法求A的逆阵，就是要找到Mi(i=1,2,…,n)，以它们逐个左乘(A,I),逐列将A的对角线上的元素化为1，而其余元素化为0，最终将A化为单位阵，则I化为A的逆阵A1。Gauss-Jordan消元法求矩阵的逆（续2）设增广阵为：

这里aij(1)=a1j，上述aij(2)的计算与Gauss消元法基本上相同，仅仅由于m11与Gauss消元法中的乘数l11不相同引起第一行元素a1j(2)与aij(2)计算不相同，假若把增广阵中I的各列视为A的第n+1列，第n+2列，…，那么上述计算公式中的第二个下标可扩充到2n。Gauss-Jordan消元法求矩阵的逆（续3）…Gauss-Jordan消元法求逆阵(续4)Gauss-Jordan消元法求逆阵(续5)Gauss-Jordan消元法求逆阵(续6)1……设经过k–1步后得到：Gauss-Jordan消元法求逆阵(续7)其中：Gauss-Jordan消元法求逆阵(续8)完成n步消元后，A1放在原A的位置。

Gauss-Jordan法求逆阵的具体步骤

按上述紧缩存贮原则，可节省存贮单元，同时还使得整个计算更简单了。可总结求逆步骤如下：上述1，2是求第k列元素，构成Mk（即求主列）

（计算其他元素，但少k列，k行）

用上述Gauss-Jordan法求逆阵，计算量约为n3，是Gauss消元法的3倍，为保证方法稳定性，还可选列主元，若仍按上述紧缩存贮原则，则最后需按行交换的相反次序作列交换才能得到A1。

Gauss-Jordan法求逆阵的具体步骤(续)Gauss-Jordan法求逆阵举例例解：按紧缩存贮方式，逐次计算结果与存