数据结构- 案例2

在高斯消去法中，我们试图将原N元线性方程组消减为三角形（又称上三角形）。在三角矩阵中，对角线以下的矩阵元素的系数均为0。对高斯消去法而言，最有用的是各行经标准化处理后对角线元素均为1的三角矩阵。图815为标准化后三角矩阵形式的原方程，对角线上的系数（彩色）和向量Y的各分量数值已不再是原来的数值。与图815对应的3个方程为X1X2X34X2X31X34这个方程组得求解相当简单解最后一个方程求的X3即X3等于1，将其代入上面的方程中求得X2（X2等于2，再把这两个值代入第一个方程中求得X1即X1等于1。这一过程称为回代。高斯消去法的算法如下。1高斯消去法算法1将原方程组变换为标准矩阵；2用回代法求解XI10321X4图815标准三角矩阵形式的原方程2增广矩阵在继续学习有关内容前，我们必须确定采用何种数据结构表示有N个未知数的N元线性方程组。表示这类方程组的一种广泛采用的方法是增广矩阵。这种特殊的表示方法可以使矩阵的三角化和回代法的编程更简洁。图816给出了有N个未知数的N元线性方程组的增广矩阵形式。增广矩阵可以用一个二维数组AUG表示。需要注意的是，增广矩阵有N行N1列，增广矩阵的最后一列（以彩色标出）是常数向量Y（如，AUG14为Y1）,增广矩阵的其余各列为系数矩阵A（如AUG11为A1,1）我们见不到有未知数的向量，当线性方程组用增广矩阵表示时，未知数是隐含的。我们的目标是把增广矩阵中的系数标准化，三角化也就是将矩阵化简到土817的形式AUG1,1,AUG2,2和,AUG3,3为1，AUG2,1，AUG3,2和AUG3,2为0。图817中的其他值以彩色显示，且记为AIJ，和YI,单撇号用以强调这些数值与原方程中的值不懂同而已。3,2,31,21,Y2194（A）一般形B示例图817三角形化后的标准增广矩阵增广矩阵的标准化与三角形化现在我们把注意力集转到三角形化和标准化处理上来，也就是把原方程组转换为标准化的上三角形矩阵形式的新方程组。如果我们仅对增广矩阵AUG进行如下操作1AUG的任一行乘以一个非零的数。2将AUG任一行的若干倍加到另一行上。3将任意两行交换。若方程组有惟一解，我们就可以用上述3种操作把方程组变换为所需要的形式（若方程组没有惟一解，我们的算法也能够识别出来）。我们从AUG1,1开始沿对角线依次下移，对增广矩阵的三角化。当我们对某个对角线元素进行处理时，我们称该元素为主元素。当AUGP,P为主元素时，我们要完成两个目标对主元素所在行标准化，使得主元素的值为1。令主元素以下的各列系数均为0即元素AUGP1,P,AUGP2,P,AUGN,P的值为0。第一个目的可以通过将主元素所在行乘以一个适当的常数（即1/AUGP,P）实现，这是操作1的应用。第二个目的可以对主元素以下的各行操作2实现。为了进可能小三角形化过程中计算的舍入误差，建议总是尽量把最大的系数（绝对值）放在主元素的位置。当你处理第P个主元素是，应当检查一下自主元素以下的各列元素，找出绝对值最大的系数，并将其所在行与主元素所在行交换。方程组得解不会因此改变，因为行交换是3种允许操作之一（操作3）。将当前行与包含最大主元素的行交换称为主元素定位。如果最大主元素的值为零怎么办这种情况只有在主元素以下的所有值均为零时才会出现。如果自主元素以下找不到一个非零值，则已知方程组没有惟一解。上述讨论的各种操作在下面的算法中进行了概括。局部变量OK表示方程组是否有惟一解。局部变量INTP/当前行/INTOK/标识方程组是否有惟一解得标志/3高斯函数的算法1先假设方程组有惟一解。2P初始化为首行的下标。3当可能有唯一解且PMAXXMAXFABSAUGJPMAX_ROWJ/若找到非零主元素，进行交换/IFXMAX0PIV_FOUNDPFALSEELSEPIV_FOUNDPTRUEIFMAX_ROWP/行交换/FORKPKNIKXTEMPAUGPKAUGPKAUGMAX_ROWKAUGMAX_ROWKXTEMP图819函数PIVOT6回代我们现在来推导增广矩阵AUG的回代程序。我们需要一个矩阵X表示未知向量。例题中方程组的标准化，三角化的增广矩阵形式如图817（B）所示，我们将其重新列在下面，右侧是其在数组AUG中对应的存储位置（如AUG03的内容为4）1043212010AUGAUG回代中所有的部分矩阵以彩色标出。对上述对角线应用回代原理，我们看由最后一行看到X2AUG231然后，由行1可知X1AUG13AUG12X21112最后，我们由0行知X0AUG03AUG01X1AUG02X2412114（3）1由上观察，我们得出下面的回代算法。用于变换后的增广矩阵的回代算法（下标自零开始）1令未知数向量的最后一个元素为增广矩阵的最后一个元素。2令I依次为I,N2,1,0,计算XIAUGIN1NIJJXAUG这一算法有图820的函数BACK_SUB实现。图821是对一个线性方程测试函数GAUSS和BACK_SUB的主函数。程序中声明的增广矩阵初始化图816的矩阵；试运行显示出解向量X/通过回代计算由增广矩阵AUG表示的线性方程组得解向量设增广矩阵的系数部分已经三角形化，且对角线元素全部为1/VIODBACK_SUBDOUBLEAUGN1NFORIN2I0；I）SUM0FORJI1JNJSUMAUGIJXJXIAUGIJNSUM图820函数BACK_SUB/用高斯消去法和回代法解线性方程组/DEFINEN3/系数矩阵的大小；增广矩阵为N行N1列/INTMAINVIODDOUBLEAUGNN110,10,40,/增广矩阵/20，30，10，90，10，10，10，20，XN/解向量/INTSOLEXISTS/指示是否有解得标志/调用GAUSS对系数矩阵AUG标准化，三角化/GAUSSAUG,/若有解，找到并显示/IFSOL_EXISTSBACK