ガウス消元快速入門

ガウス消元快速入門
一、基本説明
アルゴリズム/スキルを学ぶには、まずそれが何をしているのかを知る必要があります.では、ガウス消元は何をしているのでしょうか.
ガウス消元は主に線形方程式群を解くために用いられ,行列のランク,行列の逆を解くこともできる.ACMでは強力な数学兵器です
その時間複雑度はn^3であり,主に方程式群の個数,未知数の個数に関係している.
では、線形方程式のグループとは何ですか.簡単に言えば、複数の未知数があり、各未知数の回数は1回であり、このように複数の未知数からなる方程式群は線形方程式群である.
二、アルゴリズムプロセス
実はガウス消元の過程は方程式のグループを手で解く過程で、小さい時どのように方程式のグループを解くかを思い出します:消元を加減して、未知数を消して、もし複数の未知数があれば、ずっと消して、kx=b(kとbは定数で、xは未知数)のような式を得るまで、未知数xを解くことができて、それから私達は世代を帰って、順番に各未知数の値を解いて、方程式のグループを解いた.言い換えれば、2つのステップに分けられます.加算消元2.未知の数値を求める
ガウス消元はこのような過程である.以下、小さな例で具体的に説明する
0.方程式のグループを解く
三元一次方程式のグループがあります.
⎧⎩⎨2x+y+z=16x+2y+z=−1−2x+2y+z=7①②③ { 2 x + y + z = 1 ① 6 x + 2 y + z = − 1 ② − 2 x + 2 y + z = 7 ③
1.消去x
①×(−3)+② ① × (−3)＋②0 x−y−2 z＝−4 0 x−y−2 z＝−4を得る
①+③①+③0 x+3 y+2 z=8 0 x+3 y+2 z=8を得る
それによって
⎧⎩⎨2x+y+z=10x−y−2z=−40x+3y+2z=8①②③ { 2 x + y + z = 1 ① 0 x − y − 2 z = − 4 ② 0 x + 3 y + 2 z = 8 ③
2.消去y
②×3+③ ② × 3＋③0 x＋0 y−4 z＝−4 x＋0 y−4 z＝−4を得る
さらに得る
⎧⎩⎨2x+y+z=10x−y−2z=−40x+0y−4z=−4①②③ { 2 x + y + z = 1 ① 0 x − y − 2 z = − 4 ② 0 x + 0 y − 4 z = − 4 ③
これで,我々はすでに解いた.
z=1 z = 1
次のステップでは、世代交代プロセスを行います.
3.回代解y
z=1 z=1を②②に持ち込み、求める
y=2 y = 2
さらに得る
⎧⎩⎨2x+y+z=1y=2z=1①②③ { 2 x + y + z = 1 ① y = 2 ② z = 1 ③
4.反復解x
Z=1,y=2 z=1,y=2を①①に持ち込んで求める
x=−1 x = − 1
最終的に
⎧⎩⎨x=−1y=2z=1①②③ { x = − 1 ① y = 2 ② z = 1 ③
これで,方程式群全体が解いた.
三、再解アルゴリズム
方程式群については,その係数はマトリクス(配列)に具体的に存在し,次に実際のマトリクスにおける表現を与える(よく知っていればスキップして見なくてもよい~)
0.方程式のグループを解く
⎡⎣⎢⎢⎢x26−2y122z111val1−17⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 6 2 1 − 1 − 2 2 1 7 ]
1.消去x
⎡⎣⎢⎢⎢x200y1−13z1−22val1−48⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 0 − 1 − 2 − 4 0 3 2 8 ]
2.消去y
⎡⎣⎢⎢⎢x200y1−10z1−2−4val1−4−4⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 0 − 1 − 2 − 4 0 0 − 4 − 4 ]
3.回代解y
帰代の際,各変数を記録した結果は別の配列に保存されるため,保存行列の配列値は変化せず,この行列は主に消元過程を行う.
⎡⎣⎢⎢⎢x200y1−10z1−2−4val1−4−4⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 0 − 1 − 2 − 4 0 0 − 4 − 4 ]
四、再解アルゴリズム
こんなにたくさん言ったのに,実はまだ言っていないことがある.上記の消元法により,実は我々が望んでいるのは上三角陣である(最後のvalを省いた)
⎡⎣⎢2001−101−2−4⎤⎦⎥ [ 2 1 1 0 − 1 − 2 0 0 − 4 ]
Q 1:係数は必ずしも整数ではないでしょう.A 1:このとき配列は浮動小数点数を使います!整数ではありません!
Q 2:いつ解けないの?A 2:消元が完了し、1行の係数が0であることが分かったが、定数項は0ではなく、もちろん解がない.例:
⎡⎣⎢⎢⎢x200y1−10z1−20val1−45⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 0 − 1 − 2 − 4 0 0 0 5 ]
Q 3:いつごろ解けるんですか?A 3:消元が終わって、何行も係数が0で、定数項も0であることを発見して、このように多解しました!いくつかの行為はすべて0で、いくつかの自由要素があって、いわゆる自由要素、これらの変数の値は勝手に取ることができて、無数の情況が与えられた方程式のグループを満たすことができて、例えば:
⎡⎣⎢⎢⎢x200y100z100val100⎤⎦⎥⎥⎥ [ x y z v a l 2 1 1 1 0 0 0 0 0 0 0 0 ]
このx,y,zは無数のグループ解ではないかと言いました.
Q 4:それはいつ解くのが唯一ですか!A 4:排除法をして、2と3を満たさないのは、解釈の唯一ではないでしょうか.つまり、私たちの係数行列は三角行列にすることができます.
五、コード実現
くどくど言って、きっとアルゴリズムの流れはすでに熟知して、コードはどのように実現しますか?より多くのタイプのガウス消元テンプレート
(以下kuangbin大牛のテンプレートを参照)

 #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int MAXN=50;
    int a[MAXN][MAXN];//    
    int x[MAXN];//  
    bool free_x[MAXN];//           
    int gcd(int a,int b){
        if(b == 0) return a; else return gcd(b,a%b);
    }
    inline int lcm(int a,int b){
        return a/gcd(a,b)*b;//       
    }
    //          (Gauss-Jordan elimination).(-2       ，     ，
    //-1    ，0     ，  0     ，          )
    // equ   ，var   。       equ,   0 equ-1,   var+1,   0 var.
    int Gauss(int equ,int var){
        int i,j,k;
        int max_r;//            .
        int col;//      
        int ta,tb;
        int LCM;
        int temp;
        int free_x_num;
        int free_index;

        for(int i=0;i<=var;i++){
            x[i]=0;
            free_x[i]=true;
        }

        //      .
        col=0; //       
        for(k = 0;k < equ && col < var;k++,col++){//         .
        //    col             k   .(          )
            max_r=k;
            for(i=k+1;iif(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
            }
            if(max_r!=k){//   k   .
                for(j=k;j1;j++) swap(a[k][j],a[max_r][j]);
            }
            if(a[k][col]==0){//    col  k     0 ，          .
                k--;
                continue;
            }
            for(i=k+1;i//        .
                if(a[i][col]!=0){
                    LCM = lcm(abs(a[i][col]),abs(a[k][col]));
                    ta = LCM/abs(a[i][col]);
                    tb = LCM/abs(a[k][col]);
                    if(a[i][col]*a[k][col]<0)tb=-tb;//        
                    for(j=col;j1;j++){
                        a[i][j] = a[i][j]*ta-a[k][j]*tb;
                    }
                }
            }
        }
        // 1.      :          (0, 0, ..., a)    (a != 0).
        for (i = k; i < equ; i++){ //        ，            ，               ，      .
            if (a[i][col] != 0) return -1;
        }
        // 2.       :  var * (var + 1)       (0, 0, ..., 0)    ，              .
        //                .
        if (k < var){
            return var - k; //      var - k .
        }
        // 3.       :  var * (var + 1)              .
        //    Xn-1, Xn-2 ... X0.
        for (i = var - 1; i >= 0; i--){
            temp = a[i][var];
            for (j = i + 1; j < var; j++){
                if (a[i][j] != 0) temp -= a[i][j] * x[j];
            }
            if (temp % a[i][i] != 0) return -2; //        ，     .
            x[i] = temp / a[i][i];
        }
        return 0;
    }
    int main(void){
    //    freopen("in.txt", "r", stdin);
    //    freopen("out.txt","w",stdout);
        int i, j;
        int equ,var;
        while (scanf("%d %d", &equ, &var) != EOF){
            memset(a, 0, sizeof(a));
            for (i = 0; i < equ; i++){
                for (j = 0; j < var + 1; j++){
                    scanf("%d", &a[i][j]);
                }
            }
            int free_num = Gauss(equ,var);
            if (free_num == -1) printf("  !
");
            else if (free_num == -2) printf("     ，    !
");
            else if (free_num > 0){
                printf("    !        %d
", free_num);
                for (i = 0; i < var; i++){
                    if (free_x[i]) printf("x%d      
", i + 1);
                    else printf("x%d: %d
", i + 1, x[i]);
                }
            }else{
                for (i = 0; i < var; i++){
                    printf("x%d: %d
", i + 1, x[i]);
                }
            }
            printf("
");
        }
        return 0;
    }