并行计算实验指导(6)免费版.doc

并行计算实验指导(6)免费版.doc支持免费共享7线性方程组的直接解法在求解线性方程组(SystemofLinearEquations)的算法中,有两类最基本的算法,一类是直接法,即以消去为基础的解法。如果不考虑误差的影响,从理论上讲,它可以在固定步数内求得方程组的准确解。另一•类是迭代解法,它是一个逐步求得近似解的过程,这种方法便于编制解题程序,但存在若迭代是否收敛及收敛速度快慢的问题。在迭代过程中,山于极限过程一般不可能进行到底,因此只能得到满足一•定精度要求的近似解。本章我们主要介绍几种直接法,迭代法将在下一章讨论。(GaussianElimination)□它分为消元与代两个过程,消元过程将方程组化为一个等价的三角方程组,而网代过程则是解这个三角方程组。=b,其中A为r阶非奇异阵,其各阶主子行列式不为零,x,b为〃维向量。将向量b看成是A的最后一列,此时A就成了-•个〃X(〃+1)的方程组的增广矩阵(AugmentedMatrix),消去过程实质上是对增广矩阵A进行线性变换,使之三角化。高斯消去法按灯1,2,…,〃的顺序,逐次以第k行作为主行进行消去变换,以消去第k列的主元素以下的元素ak+ik,ak+2k,…,。消去过程分为两步,首先计算:akj=akjlakk,j=k+l,…,nbkfcikk这一步称为归一化(Normalization)。它的作用是将主对角线上的元素变成1,同寸第妇亍上的所有元素与常数向量中的饥都要除以四n山于人的各阶主子式非零,可以保证在消去过程中所有主元素〃城皆为非零。然后计算:dijWj-ciikdkj,i,j=k+l,bi=bj-aikbk,i=k+\,…,〃这一步称为消元,它的作用是将主对角线妃以下的元素消成0,其它元素与向量B中的元素也应作相应的变换。在回代过程中,按下式依次解出・・*直接解出,即x„=bn/atl„;进行回代求耳=伤-文"/,】=〃一1,・吐2,1j=i+l在归-化的过程中,要用,秘作除数,当I砍」很小时,会损失精度,并旦可能会导致商太大而使计算产生溢出。如果系数A虽为非奇异,但不能满足各阶主子式全不为零的条件,就会出现主元素山为零的情况,导致消去过程无法继续进行。为了避免这种情形,在每次归一•化之前,可增加一个选主元(Pivot)的过程,将绝对值较大的元素交换到主对角线的位置上。根据选取主元的范围不同,选主元的方法主要有列主元与全主元两种。列主元(ColumnPivot)方法的基本思想是当变换到第k步时,从第k列的。口以下(包括。城)的各元素中选出绝对值最大者。然后通过行交换将它交换到。妣的位置上。但列主元不能保证所选的。奴是同一•行中的绝对值最大者,因此采用了列主元虽然变换过程不会中断,但计算还是不稳定的。全主元方法的基本思想是当变换到第*步时,从右下角(n-k+l)阶子阵中选取绝对值最大的元索,然后通过行变换和列变换将它交换到。妹的位置上。对系数矩阵做行交换不影响计算结果,但列交换会导致最后结果中未知数的次序混乱。即在交换第,列与第j列后,最后结果中为•与为的次序也被交换了。因此在使用全主元的高斯消去法时,必须在选主元的过程中记住所进行的一切列变换,以便在最后结果中恢复。全主元的高斯消去卅行算法如下,其中的我们用邳J]来表示::系数矩阵A”X”,常数向M们】x1输出:解向量工心1Begin(1)fori=1tondoshift[i]=iendforfor/r=ltondoJ=0fori=ktondoforj=ktondoif(|a\ij]|>d)thend=\a\ij]\/js=j,l=iendifendforendforif(js+k)thenforz=ltondo交换a[i,k]^a[ijs]endfor交换shift[k]Wshift\js\endifif(/*k)thenfoi7=Zrtoiido交换那,J]和a[IJ]endfor交换姒]和如]endifforj=k+1tondoa[kj]=a[kj]/a[k9k]endforb[k]=b[k]/a[k^。代幻=1foW+1tondofor/=Z:+ltondoa[ij]=a[ij]-a[i9k]*a[kj]endfor(u)b[i]=b[i]-a[i,k]^[k]o[云]=0endforendforfori=ndownto1do/*采用全主元高斯消去法的回代过程*/for/=z+1to7?do/巾]=a[zj]*x[z]endforendforfork=1tondofori=1tondoif(shift[i]=k)then输出幻的值x[i]endifendforendforE