Gauss-Seidel迭代矩阵求法的思考

Gauss-Seidel迭代矩阵求法的思考在迭代法收敛性的判别中，我们有充分条件：若迭代矩阵B的某种范数1qB，则迭代法,1,0,)()1(kdBxxkk对任意的初始向量)0(x都收敛于方程组bAx的精确解*x。从这个条件中我们可以看出，想要知道迭代法是否收敛，就要知道迭代矩阵（当然如果系数矩阵是正定的或严格对角占优的，那就不用知道其迭代矩阵，因为这时它的Jacobi迭代和Gauss-Seidel迭代一定收敛），Jacobi迭代矩阵为ADIULDBJ11)(，Gauss-Seidel迭代矩阵，ULDBG1)(这两个矩阵中都涉及到了矩阵的逆。从上高等代数时学到矩阵的逆开始，就一直惧怕有关矩阵逆的题目，因为求矩阵A的逆*11AAA,这就必须求出A的行列式A与A的伴随矩阵*A,对于求矩阵A的行列式，就是一个繁琐的过程，计算量大且易出错，而这儿还不仅如此，这儿还要求出矩阵A的伴随矩阵*A。如果矩阵nnnnnnaaaaaaaaaA212222111211，则nnnnnnAAAAAAAAAA212221212111*，而其中的nnjnjnnnijijiinijijiinjjaaaaaaaaaaaaaaaaA1,1,1,11,11,11,1,11,11,11,111,11,111ij，因此求*A的计算量比求A的行列式的计算量还要大的多，所以1A很难求。因此数学家便开始寻找求1A的相对容易的方法，其中有一种初等变换的方法，即对EA进行初等行变换，当把A变成E时，E便变成了1A，此方法要简单的多，但在变换过程中要消耗大量空间。在用迭代法解线性方程组的方法中，都涉及到了一个矩阵的逆，而且其涉及到的还不仅仅是一个矩阵的逆那么简单，其涉及到的是用一个矩阵的逆去乘另一个矩阵，如果一步一步算，想要算出矩阵的逆，再算两个矩阵相乘，没有一步是简单的，两步计算过程都很繁琐，极易出错。仔细观察后，我发现正是因为矩阵的逆与另一矩阵相乘，从而在整体上出现了相对简单的计算，其过程是略去矩阵逆的计算，从而简化计算。对于n介线性方程组nnnnnnnnbxaxaxabxaxaxa221111212111，即bAx，其系数矩阵nnijaA非奇异且niaii,,3,2,10，对,2,1,0k，则可建立①Jacobi迭代格式:1).(1),(1),(1)(11,)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax我们知道Jacobi迭代矩阵为2)(11ADIULDBJ,其中nnaaaD2211，00001,21323121nnnnaaaaaaL，30000,122311312nnnnaaaaaaU。由式⑵可看出，计算JB，首先需求出1D,然后再作矩阵乘法。当然这儿由于D的特殊性，1D很好求，1D=nnnnaaaaaa11122111-2211，000-0-B3213333332333122222231121111111311121JnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaADI如果我们抛开式⑵，直接看⑴，就会发现，其实JB可以直接写出来，无需计算，由⑴可得000-0B321333333233312222223112111111131112Jnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaa，其直接从线性方程组中得来，显然快于一步步的计算，而且第二中算法不仅简单还不容易出错，提高了求迭代矩阵的效率。当然，第一种算法的1D可以直接写出很好求，从而效率也没提高多少，但对于Gauss-Seidel迭代，就不然了。②Gauss-Seidel迭代格式：4).(1),(1),(1)1(11,)1(22)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax我们知道Gauss-Seidel迭代矩阵5)(1ULDBG,其中矩阵D,L,U与上述⑶中一样。但此处1)LD（就不是太好求了，即使它是个下三角矩阵。然而求出1)LD（后，还要进行矩阵的乘法，因为ULDBG1)(即：0000)(,12231131213213332312221111nnnnnnnnnGaaaaaaaaaaaaaaaaULDB计算有点繁琐，然而，我产生一种想法，其是否也可与Jacobi迭代矩阵那样,直接写出来了？通过一番计算，再加上实例的体会，我找出了一种相对简洁的关系。把⑷式写成421)(1)1(11,)1(22)1(11)1(2)(2)(323)1(121)1(2221)(1)(313)(21211)1(1nbxaxaxaxabxaxaxaxabxaxaxaaxnknnnknknknnnknnkkkknnkkk把1）代入2）并整理得（由于我们的目的是得到矩阵，所以在此就不考虑nbbb,,,21了）)(211121)(323111321)(2111221)1(222)()()(knnnkkkxaaaaxaaaaxaaaxa2’）令1111111313111212,,,aabaabaabnn，则1）变为)(1)(313)(212)1(1knnkkkxbxbxbx①。此时2’）式变为)(222121)(322231321)(2221221)1(2]/)[(]/)[(]/)[(knnnkkkxaabaxaabaxabax2^)。令2221212222313212322122122,,,-aababaababababnnn，则2^)式变为)(2)(323)(222)1(2knnkkkxbxbxbx②。把①、②式代入3）式整理得)(3232131)(43424321431)(323321331)(222321231)1(333)()()()(knnnnkkkkxababaxababaxbabaxbabaxa3’）令333232131333342432143134332332133133332232123132,,,,aabababaabababababababababnnnn则3’）式变为)(3)(434)(333)(232)1(3knnkkkkxbxbxbxbx③……如此一直在前一步的基础上求后一步矩阵中的元素的值，一直进行下去，则n-1)式变为)(,1)(13,1)(12,1)1(1knnnknnknnknxbxbxbx则第n个式子变为)(,11,,22,,11,)(33,11,232,131,)(22,11,222,121,)1()()()-(KnnnnnnnnnKnnnnnKnnnnnknnnxbababaxbababaxbababaxa即)(,)(44,)(33,)(22,)1(knnnknknknknxbxbxbxbx从而得到Gauss-Seidel迭代矩阵nnnnnnnnnnnnnnnnGbbbaabaaabaababbbbbbbabbbbbbB3222212122231321221221113122222111n111222221120-0000a-aa-00003213332321313323321331332232123122322113120000nnnnnnnnbbbaababaababaabababbbbbbnnininiininiiiniiiiiiiiiiiiiiiiiiiniibbbaababaaababaabababbb,1,,,,,11,,11,,1,1,11,1,11,,,11,,11,,11,1,10---00nnnnnnnnnnnnnnnnnnnnnnnababaababaabababbbbbbbbb,,11,11,,3,11,131,,2,11,121,333232232211312---0000（*）接下来我用书上一个例子来展现上述方法求迭代矩阵的优越性：例设方程组为,722025,19103,928321321321xxxxxxxxx试分别写出Jacobi迭代和Gauss-Seidel迭代格式以及相应的迭代矩阵。解：原方程的Jacobi迭代格式和Gauss-Seidel迭代格式分别为),7225(201),193(101),92(81)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx⑴和),7225(201),193(101),92(81)1(2)1(1)1(3)1(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx⑵由⑴可直接得Jacobi迭代矩阵为01.0411.003.041810JB而相应的Gauss-Seidel迭代矩阵可由（*）式得：045.00275.00175.00375.0025.0125.0020175.0225.0520)]0375.0(2)125.0(50175.00375.0025.0125.000101413108130418103332bbBG与书上用公式算所得结果相同，但这种计算显然很简洁。对于3阶以上的迭代矩阵的计算，我的方法将会节约大量时间，而且还不容易出错。以上我们讨论的是方阵，但从（*）式可以看出，我们也可以求出不是方阵的GB，这便给人一种想法，是否不是方阵时也可用迭代法求其解，但有一点是肯定的，当方程个数少于未知数个数时，线性方程组有无穷多解，因此这个问题有可能是否定的，即无法用迭代法求系数矩阵不是方阵的解，此