interprism's blog

インタープリズム株式会社の開発者ブログです。

クラーメルの公式を使って連立方程式を解く(失敗編)

この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の15日目 の記事です。

こんにちはabeです。 今回のお話は、「クラーメルの公式がやばい」という一言に集約されます。

まずクラーメルの公式とは何か

クラーメルの公式とは、一言で言えば連立方程式の解をシンプルに表す式で、 係数行列を、 定数項をとした場合、 ベクトルで表される解の第成分をとすると、

となります。これが、クラーメルの公式です、なお、は、「の第列をで置き換えたもの」、という意味です。

前回登場した連立方程式:

も

とすることで解けて、

となります。

何がどうやばいのか

何年も前にこの公式を教科書で見た時には、「連立方程式の解が一行で書けてる！超便利！」と思いました(解の存在と性質だけ確かめる時には実際に便利です。)。

github.com

で今頃になってjavaで実装してみたのですが、これが超やばい！前回紹介したガウスの消去法なら2/1000秒程度の時間で解けた問題を解くのに2秒弱かかりました。

主な原因はまあ、今まで説明を完全に省略していたの計算で、ここでも詳細は省略しますが、まず「未知変数と同じ数だけ用意した数字の全ての並べかえの数」だけ処理を回し、そのループの一つ一つの中で、「未知変数の数と同じ数の掛け算」を行う必要があります。ここからはjavaのコードでお見せしましょう。

   public double getDeterminant(){
        double determinant = 0;
        for(Permutation permutation:this.allPermutations){
            determinant += permutation.getSigunature()*this.getElementProductBy(permutation);
        }
        return determinant;
    }

    private double getElementProductBy(Permutation permutation){
        double product = 1;
        for(int row = 0; row < this.size(); row++){
            product *=elements[row][permutation.getValue(row)];
        }
        return product;
    }

例えば先ほどのを求める方程式では、未知の変数がこの3つですので、「未知変数と同じ数だけ用意した数字の全ての並べかえの数」は6つになります。それは、ここでいう、this.allPermutationsが[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]なる配列となって反映されます(詳細は上のgitHubのコミット)。そして、double型の二重配列であるelementsに関して、elements[row][permutation[row]]をrow=0,1,2 に関して掛け算する・・・という流れになります。

変数3つであればあまり問題にならないのですが、9個まで増えると大変で、permutationは362 880通りになります。これにより、ガウスの消去法の1000倍もの時間がかかる機能が出来上がってしまいました。

インタープリズムのページ

PAGE TOP