数值计算-线性方程组求解[1]

 

首先，先介绍一下相关数学知识

一、线性组合

线性组合（英语：Linearly combination）是一个线性代数中的概念，代表一些抽象的向量各自乘上一个标量后再相加。

为一向量空间（附于体）的子集合。

如果存在有限多个向量属于，和对应的标量属于，使得，则称是的线性组合。

规定：向量是空集合的线性组合。

二、奇异与非奇异

1、首先，看这个矩阵是不是方阵（即行数和列数相等的矩阵。若行数和列数不相等，那就谈不上奇异矩阵和非奇异矩阵）。 然后，我们把满足|A|≠0的方阵A称为非奇异的,否则就称为奇异的，对应的行列式等于0的矩阵为奇异矩阵。

2、方阵的行列式|A|是否等于0，若等于0，称矩阵A为奇异矩阵；若不等于0，称矩阵A为非奇异矩阵。 同时，由|A|≠0可知矩阵A可逆，这样可以得出另外一个重要结论:可逆矩阵就是非奇异矩阵，非奇异矩阵也是可逆矩阵。

　如果A为奇异矩阵，则AX=0有无穷解，AX=b有无穷解或者无解。如果A为非奇异矩阵，则AX=0有且只有唯一零解，AX=b有唯一解。　 　

3)行列式为0比较易懂的理解方式就是以下2种：

(A)方程组中有一个或几个方程是其他方程的线性组合，或者所有方程中某些变量是其他变量的同一线性组合，这样称为奇异，否则为非奇异，行列式为0即：存在线性相关的列或行 。

(B)矩阵A的行列式等于0的充要条件是A的秩小于n，一个矩阵A的列秩是A的线性无关的纵列的极大数目。类似地，行秩是A的线性无关的横行的极大数目。矩阵的列秩和行秩总是相等的，因此它们可以简单地称作矩阵A的秩。通常表示为r(A)，rk(A)或rank A。m × n矩阵的秩最大为m和n中的较小者，表示为 min(m,n)。

什么是线性无关呢？

在线性代数里，向量空间的一组元素如果其中没有向量可表示成有限个其他向量的线性组合称为线性无关，反之称为线性相关,回到前面的概念，也就是说A的秩小于n，肯定A中存在线性相关的向量，即就是(A)项所列

 

三、高斯消元法

可用来找出下列方程组的解或其解的限制：

　　2x + y - z = 8 (L1)

　　-3x - y + 2z = -11 (L2)

　　-2x + y + 2z = -3 (L3)

　　这个算法的原理是：

　　首先，要将L1 以下的等式中的x 消除，然后再将L2 以下的等式中的y 消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。

　　在刚才的例子中，我们将3/2 L1和L2相加，就可以将L2 中的x 消除了。然后再将L1 和L3相加，就可以将L3 中的x 消除。

　　我们可以这样写：

　　L2 + 3/2 L1→ L2

　　L3 + L1 → L3

　　结果就是：

　　2x + y - z = 8

　　1/2 y + 1/2 z = 1

　　2y + z = 5

　　现在将 − 4L2 和L3 相加，就可将L3 中的y 消除：

　　L3 + -4 L2 → L3

　　其结果是：

　　2x + y - z = 8

　　1/2y + 1/2z = 1

　　-z = 1

　　这样就完成了整个算法的初步，一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。

　　第二步，就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是：

　　z = -1

　　然后就可以将z 代入L2 中，立即就可得出第二个答案：

　　y = 3

　　之后，将z 和y 代入L1 之中，最后一个答案就出来了：

　　x = 2

　　就是这样，这个方程组就被高斯消元法解决了。

　　这种算法可以用来解决所有线性方程组。即使一个方程组不能被化为一个三角形的格式，高斯消元法仍可找出它的解。例如在第一步化简后，L2 及L3 中没有出现任何y ，没有三角形的格式，照着高斯消元法而产生的格式仍是一个行梯阵式。这情况之下，这个方程组会有超过一个解，当中会有至少一个变量作为答案。每当变量被锁定，就会出现一个解。

　　通常人或电脑在应用高斯消元法的时候，不会直接写出方程组的等式来消去未知数，反而会使用矩阵来计算。以下就是使用矩阵来计算的例子：

　　2 1 -1 8

　　-3 -1 2 -11

　　-2 1 2 -3

　　跟着以上的方法来运算，这个矩阵可以转变为以下的样子：

　　2 1 -1 8

　　0 1/2 1/2 1

　　0 0 -1 1

　　这矩阵叫做“行梯阵式”。

　线性代数中，矩阵是行阶梯形矩阵（Row-Echelon Form），如果：

• 所有非零行（矩阵的行至少有一个非零元素）在所有全零行的上面。即全零行都在矩阵的底部。
• 非零行的首项系数(leading coefficient)，也称作主元, 即最左边的首个非零元素，严格地比上面行的首项系数更靠右。
• 首项系数所在列，在该首项系数下面的元素都是零 (前两条的推论).

这个3×4矩阵是行阶梯形矩阵：

四、增广距阵

增广矩阵就是在系数矩阵的右边添上一列，这一列是线性方程组的等号右边的值。 如：方程AX=b 系数矩阵为A，它的增广矩阵为(A b)。

　　增广矩阵通常用于判断矩阵的有解的情况，比如说

　　秩（A)<秩（A b) 方程组无解；

　　r（A)=r（A B)=n，方程组有唯一解；

　　r（A)=r（A B)<n，方程组无穷解；

　　r（A)>r（A B)不可能，因为增广矩阵的秩大于等于系数矩阵的秩。

　　对于方程组(1):　

　　a11 x1+a12 x2+a13 x3+…+a1n xn=b1（1）

　　a21 x1+a12 x2+a23 x3+…+a2n xn=b2（2）

　　……………………

　　ai1 x1+ai2 x2+ai3 x3+ … +ain xn=bi（i）

　　……………………

　　am1 x1+am2 x2+am3 x3+…+amn xn=bm（m)

　　系数矩阵为:

　　[ a11 a12 a13 …a1n ]

　　[ a21 a22 a23 …a2n ]

　　[ …………………… ]

　　[ ai1 ai2 ai3 … ain ]

　　[ …………………… ]

　　[am1 am2 am3…amn]

　　增广矩阵为：

　　[ a11 a12 a13 …a1n b1 ]

　　[ a21 a22 a23 …a2n b2 ]

　　[ ……………………… ]

　　[ ai1 ai2 ai3 … ain bi ]

　　[ ……………………… ]

　　[am1 am2 am3…amn bm]

五、高斯－若尔当消元法（英语：Gauss-Jordan Elimination）

，是数学中的一个算法，是高斯消元法的另一个版本。它在线性代数中用来找出线性方程组的解，其方法与高斯消去法相同。唯一相异之处就是这算法产生出来的矩阵是一个简化行梯阵式，而不是高斯消元法中的行梯阵式。相比起高斯消元法，此算法的效率比较低，却可把方程组的解用矩阵一次过表示出来。

可以利用高斯消元算法产生以下的矩阵，便可把所得出的解或其限制简明地表示出来：

　　1 0 0 2

　　0 1 0 3

　　0 0 1 -1

　　最后这矩阵叫做“简化行梯阵式”，亦是高斯－约当消元法指定的步骤。

 
化简后的行阶梯形矩阵(reduced row echelon form), 也称作行规范形矩阵(row canonical form)(也称简化行梯阵式)，如果满足额外的条件:

• 每个首项系数是1，且是其所在列的唯一的非零元素。例如:

注意，这并不意味着化简后的行阶梯形矩阵的左部总是单位阵. 例如，如下的矩阵是化简后的行阶梯形矩阵:

因为第3列并不包含任何行的首项系数.

高斯约当消元法每次消去时把当前等式中 xi的系数化为1 ，同时不仅消去尚未利用的行中出现的xi ，也消去已利用的行中出现的 xi 。这样在消元完成后不需要回代过程，方程组中每一行都是  的形式。同时由于不需要回代过程，方程组中各个未知数的消元顺序不再那么严格，因此我们可以把“选择行主元”变成“选择列主元”，也就是依次选定每一个方程，从中选择系数绝对值最大的  来消元。这样方程可以依次处理，自由变量在消元完成之前不会出现。若出现“无元可消”，只有两种情况： 0=0 和 0=C ，前者直接忽略，后者直接无解。