线性方程组的矩阵求解算法

1、线性方程组的矩阵求解算法 摘要 线性方程组的矩阵求解算法,只需在约当消元法的基础上,再对方程组的增广矩阵的行最简形进行行(列)删除和增加行,交换行等运算即可得到方程组的解,并且这种方法既可求解有唯一解的方程组.因而算法简单,易于实现.关键词 线性方程组;解向量;解法;约当消元法1 矩阵求解算法设有线性方程组,其增广矩阵,算法的步骤如下:第一步:利用约当消元法,把增广矩阵化为行最简形,设行最简形为.若则方程组无解;否则设并执行以下步骤;第二步:删除中的所有零行和每一行第一个非零元素(这个非零元素一定是1)所在的列,得到矩阵并记录每行的第一个非零元所在的列标,放在一维数组中,如第行的第一个非零元在

2、第列,则;第三步:构造矩阵,其中 第四步:对矩阵中的行作交换运算:把中的第行(即从第行开始直到第一行)依次与其下一行交换,使之成为第行,交换运算结果后的矩阵记为,则中的前个维列向量即为方程组的一个基础解系,最后一列向量即为方程组的一个特解;第五步:写出方程组的通解.2 算法证明先证一个特殊情形,增广矩阵的行最简形矩阵的左上角为一阶的单位矩阵,即第行的第一个非零元的列标为,即,所以设为 则 由上述算法可得为 由于,故从得到时,中的行不需交换位置,即那么矩阵的增广矩阵的线性方程组为 令 , , 可以验证是方程组(1)所对应的齐次线性方程组的解,是方程组(1)的特解,又的后个分量构成的向量组,线性无

3、关,把它扩充成维向量组后也线性无关,所以线性无关,又因为,所以方程组(1)的基础解系中有个向量,因此即为方程组(1)的基础解系,特殊情形得证.对于行最简形矩阵为一般情形时,可以通过若干次列交换把它变形为上述特殊情形,但是,列交换将会导致最后结果中对应未知数的次序混乱,即在进行第列与第列的交换后,最后结果中与次序也就被交换了,因此,在这过程中,必须记住所进行的一切列交换,以便在最后结果中恢复,但若使用本矩阵求解算法,则可避免上述麻烦,为了叙述方便,还是只证一种特殊情形.设 即则 , , 现在证明的前个列向量是所对应的方程的基础解系,的最后一列是该方程组的特解,把矩阵的第2列依次与第3列,第4列,

4、第列交换,得到矩阵 设矩阵所对应的方程组的解向量为,所对应的方程组的解向量为,则有 即若是所对应的方程组的解向量,则是矩阵所对应的方程组的解向量,而由上述所证的特殊情形,所对应的方程组的基础解系和一个特解分别为 , , 由此可得矩阵所对应的方程组的基础解系和特解为 , , , , 而,即为的列向量组,这一情形得证若为起它任意情形,只要重复上上述证明过程,即可得到证明.3 举例 例 设有线性方程组求其通解. 解方程组的增广矩阵为 的行最简形矩阵为 划掉中的最后两个零行和每行的第一个非零元所在的第一列,第三列,第四列,得矩阵,并且 构造矩阵 由于,所以应把中第3行依次与其后的行交换,使之成为第4行

5、,然后因为,所以把中第2行依次与其后的行交换,使之成为第3行最后因,故第1行不需与任何行交换,这样变得到矩阵, 所以方程组的通解为 4.算法分析事实上,本算法是约当消元法的推广,因为若时,最简形矩阵的前列为阶单位矩阵,所以由得时,为矩阵,且为的最后一列所构造成的矩阵,由构造时,不断增加行,由得到时,不需交换行,即,因而方程组的解向量为,这也是约当消元法的结果也就是说约当消元法是本算法当时的特殊情形,由于本算法的所有加法和乘法都在把增广矩阵化为行最简形矩阵的着一过程中,所以有以下结论:1) 算法的计算量与约当消元法的计算量相等;2) 算法所需的存贮空间略多于约当消元法所需的存贮空间;3) 在求方

6、程组的通解时,其稳定性与精度和约当消元法的完全一致.另外,由于本算法从输入方程组到输出通解(或唯一解),中间的所有运算都是对矩阵进行的,所以算法简单,容易在计算机上实现,当然,由于本算法包含约当消元法,因而它除了有与约当消元法相同的缺点以外,它还有一个缺点:有时需要移动大量的元素,特别是当未知数的个数与方程的个数都很大时,元素的移动量可能更大.总之,本算法在约当消元法的基础上,不需增加乘法和加法运算,即可得到方程组的通解,因而本算法有一定的适用价值. 参考文献1徐士良 计算机常用算法M 北京: 清华大学出版社,1995.122同济大学 线性代数M 北京: 高等教育出版社, 2002.13邓建中等 计算方法M 西安: 西安交通大学出版社,2001.84刘仲奎