ガウス･ジョルダン法

ガウスの消去法の前進消去を拡張すると正方行列の逆行列を求めることができる．これは，ガウス･ジョルダン法(Gauss-Jordan method)，もしくは，掃出し法(sweeping-out method)と呼ばれる．

まず，の正方行列を考える．ならばは正則行列(regular matrix)である (逆になら特異行列(singular matrix))．の単位行列をとすると，が正則ならば，を満足する行列が1つだけ存在する．このを逆行列と呼びで表される．

さて，ガウスの消去法で対象とした連立1次方程式において，をに，をに置き換えることを考える．そうすると拡大行列は以下のようになる．

であるので，両辺にをかけると

となる．つまり，拡大行列の左側半分が単位行列となるように変換することで，右側半分に逆行列ができる．

このとき，逆行列は，

となる．前進消去を拡張し，これらの処理を行うことで逆行列を求めるのが，ガウス・ジョルダン法である．

ガウス・ジョルダン法の実装†

ガウスの消去法における前進消去では上三角行列にするために，の条件を満たす要素のみ対象として処理していたが，ガウス・ジョルダン法ではすべての要素に対象を広げる．ガウス・ジョルダンでの前身消去の式は以下である．

ガウス・ジョルダン法で逆行列を求めるコード例を以下に示す．


int GaussJordan(vector< vector<double> > &A, int n)
{
        for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            A[i][j+n] = (i == j ? 1.0 : 0.0);
        }
    }
 
        for(int k = 0; k < n; ++k){
        double akk = A[k][k];
                for(int j = 0; j < 2*n; ++j){
            A[k][j] /= akk;
        }
 
                for(int i = 0; i < n; ++i){
            if(i == k) continue;
            double aik = A[i][k];
            for(int j = 0; j < 2*n; ++j){
                A[i][j] -= A[k][j]*aik;
            }
        }
    }
 
    return 1;
}

Menu

ガウス・ジョルダン法の実装†