资源描述：
《线性方程组的直接解法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1.7线性方程组的直接解法在求解线性方程组(SystemofLinearEquations)的算法中，有两类最基本的算法，一类是直接法，即以消去为基础的解法。如果不考虑误差的影响，从理论上讲，它可以在固定步数内求得方程组的准确解。另一类是迭代解法，它是一个逐步求得近似解的过程，这种方法便于编制解题程序，但存在着迭代是否收敛及收敛速度快慢的问题。在迭代过程中，由于极限过程一般不可能进行到底，因此只能得到满足一定精度要求的近似解。本章我们主要介绍几种直接法，迭代法将在下一章讨论。1.1高斯消去法解线性方程组在直接方法
2、中最主要的是高斯消去法(GaussianElimination)。它分为消元与回代两个过程，消元过程将方程组化为一个等价的三角方程组，而回代过程则是解这个三角方程组。19.1.1高斯消去及其串行算法对于方程组Ax=b，其中A为n阶非奇异阵，其各阶主子行列式不为零，x，b为n维向量。将向量b看成是A的最后一列，此时A就成了一个n×(n+1)的方程组的增广矩阵(AugmentedMatrix)，消去过程实质上是对增广矩阵A进行线性变换，使之三角化。高斯消去法按k=1,2,…,n的顺序，逐次以第k行作为主行进行消去变换
3、，以消去第k列的主元素以下的元素。消去过程分为两步，首先计算：akj=akj/akk,j=k+1,…,nbk=bk/akk这一步称为归一化(Normalization)。它的作用是将主对角线上的元素变成1，同时第行上的所有元素与常数向量中的bk都要除以。由于A的各阶主子式非零，可以保证在消去过程中所有主元素akk皆为非零。然后计算：aij=aij-aikakj,i,j=k+1,…,nbi=bi-aikbk,i=k+1,…,n这一步称为消元，它的作用是将主对角线akk以下的元素消成0，其它元素与向量B中的元素也应作
4、相应的变换。在回代过程中，按下式依次解出xn,xn-1,…,x1：①直接解出xn，即xn=bn/ann；②进行回代求在归−化的过程中，要用akk作除数，当∣akk∣很小时，会损失精度，并且可能会导致商太大而使计算产生溢出。如果系数A虽为非奇异，但不能满足各阶主子式全不为零的条件，就会出现主元素aii为零的情况，导致消去过程无法继续进行。为了避免这种情形，在每次归一化之前，可增加一个选主元(Pivot)的过程，将绝对值较大的元素交换到主对角线的位置上。根据选取主元的范围不同，选主元的方法主要有列主元与全主元两种。列
5、主元(ColumnPivot)方法的基本思想是当变换到第步时，从第列的akk以下（包括akk）的各元素中选出绝对值最大者。然后通过行交换将它交换到akk的位置上。但列主元不能保证所选的akk是同一行中的绝对值最大者，因此采用了列主元虽然变换过程不会中断，但计算还是不稳定的。全主元方法的基本思想是当变换到第步时，从右下角（n-k+1）阶子阵中选取绝对值最大的元素，然后通过行变换和列变换将它交换到akk的位置上。对系数矩阵做行交换不影响计算结果，但列交换会导致最后结果中未知数的次序混乱。即在交换第i列与第j列后，最后
6、结果中xi与xj的次序也被交换了。因此在使用全主元的高斯消去法时，必须在选主元的过程中记住所进行的一切列变换，以便在最后结果中恢复。全主元的高斯消去串行算法如下，其中aij我们用a[i,j]来表示：算法19.1单处理器采用全主元高斯消去法的消去过程算法输入：系数矩阵An×n，常数向量bn×1输出：解向量xn×1Begin(1)fori=1tondoshift[i]=iendfor(2)fork=1tondo(2.1)d=0(2.2)fori=ktondoforj=ktondoif(│a[i,j]│>d)thend
7、=│a[i,j]│，js=j，l=iendifendforendfor(2.3)if(js≠k)then(i)fori=1tondo交换a[i,k]和a[i,js]endfor(ii)交换shift[k]和shift[js]endif(2.4)if(l≠k)then(i)forj=ktondo交换a[k,j]和a[l,j]endfor(ii)交换b[k]和b[l]endif(2.5)forj=k+1tondoa[k,j]=a[k,j]/a[k,k]endfor(2.6)b[k]=b[k]/a[k,k]，a[k,k
8、]=1(2.7)fori=k+1tondo(i)forj=k+1tondoa[i,j]=a[i,j]-a[i,k]*a[k,j]endfor(ii)b[i]=b[i]-a[i,k]*b[k](iii)a[i,k]=0endforendfor(3)fori=ndownto1do/*采用全主元高斯消去法的回代过程*/forj=i+1tondob[i]=a[i,j]*x[i]e
