高斯-约当 (Gauss-Jordan) 消元法 [学习笔记]

朴素高斯消元

program ttdd8;var matrix:array[1..100,1..101] of double;temp:array[1..101] of double;x:array[1..100] of double;i,j,k,n:integer;m:double;beginreadln(n);{一共有n个式子}for i:=1 to n dobeginfor j:=1 to n+1 doread(matrix[i,j]);{依次读入每个式子x1,x2…的系数及常数项}readln;end;for i:=1 to n-1 do{需要消元n-1次}beginfor j:=i to n do{寻找主元，即当前要消去元素系数最大的一个式子}if matrix[j,i]>matrix[i,i] thenbegintemp:=matrix[i];matrix[i]:=matrix[j];matrix[j]:=temp;end;for j:=i+1 to n dobeginm:=matrix[j,i]/matrix[i,i];matrix[j,i]:=0;for k:=i+1 to n+1 domatrix[j,k]:=matrix[i,k]*m-matrix[j,k];end;end;x[n]:=matrix[n,n+1]/matrix[n,n];{回代过程}for i:=n-1 downto 1 dobeginm:=0;for j:=i+1 to n dom:=m+matrix[i,j]*x[j];x[i]:=(matrix[i,n+1]-m)/matrix[i,i];end;for i:=1 to n dowriteln(x[i]:0:2);end.

转自zkw的blog‍

高斯消元法是求解线性方程组的常用方法，高斯约当消元法大家可能不是很熟悉。下面先介绍线性方程组和矩阵的一些基本概念与高斯消元法，然后着重介绍高斯约当消元法相对于高斯消元法的优势：程序简单（不需要回代），应用广泛（例如求矩阵的逆），易于判断处理特殊情况（有无穷多解的情况）。

这是一个线性方程组：

把方程组中的系数矩阵和结果向量并置，得到下面的增广矩阵：

高斯消元法的基本方法是使用加减消元，依次选定每一个未知数，利用增广矩阵的其中一行消去尚未利用的其他行中出现的，最终利用回代过程求得方程组的解。为了减小误差，每次都应选择的系数绝对值最大的一行。

高斯消元法实现时有一些不易处理的问题：

1.回代过程：虽然公式并不复杂，可是编程时代入消元和加减消元并用，对于初学者（比如我）依然是一个不小的障碍。

2.自由变量：如果消元过程中存在自由变量，必须立刻赋值，否则无法继续。这样求出的是一组特解，难以求出其他变量与自由变量的函数关系。

3.交换两行：处理时需要反复交换原矩阵的两行，给调试工作带来困难。

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