LU分解とその応用について

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

こんにちはabeです。今回はLU分解を用いた連立方程式の解法とその応用・効力について書いていきます。

   /**
    * 行列をLU分解する。Lを返し、this.coefficientMatrixがUとなる。
    *
    * @return
    */
    public SquareMatrix splitLU(){
        double[][] lowerTriangleMatrix =
                new double[this.values.length][this.values.length];

        //Lを求めるときはいいが、Lの逆行列を求める場合はこのロジックは使えないことに注意
        for(int columnNumber = 0; columnNumber < this.values.length; columnNumber++){
            double[] FrobeniusColumn = this.eliminateOnTheColumn(columnNumber);
            for(int rowCoordinate = 0; rowCoordinate < this.values.length; rowCoordinate++){
                lowerTriangleMatrix[rowCoordinate][columnNumber] = FrobeniusColumn[rowCoordinate];
            }
        }

        return new SquareMatrix(lowerTriangleMatrix);
    }

LU分解で係数行列を分ける

早速ですが次の、右辺だけやたらと字が汚い連立方程式を解いてくれと頼まれた場合を考えてみましょう。

f:id:interprism:20171206202315j:plain

この連立方程式は、(都合よく絶対値の大きな係数が斜めに並んでいるため)行列に書き換えてガウスの消去法で容易に解くことができます。

$\left( \begin{array}{ccc} 1 & 1 & 1 \\ -2 & 3 & 1 \\ 3 & -2 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 6 \\ 1 \\ 9 \end{array} \right)$

行列の左下の方にある数字を0にするために、中段に上段の2倍を足し、下段から上段の3倍を引きます。

$\left( \begin{array}{ccc} 1 & 1 & 1 \\ \it{0} & \it{5} & \it{3} \\ \it{0} & \it{-5} & \it{1} \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 6 \\ \it{13} \\ \it{-9} \end{array} \right)$

次に、下段に中段の値を足します。

$\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 5 & 3 \\ \it{0} & \it{0} & \it{4} \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} 6 \\ 13 \\ \it{4} \end{array} \right)$

このまでくれば $z=1$ がすぐにわかり、さらに $5y+3z=13$ から $y=2$ がわかり、さらにさらに $x+y+z=6$ から $x=3$ となり、方程式が解けました。

あるいはLU分解を用いても同程度の手間で解くことができます。先ほどの式変形を具体的に計算する前に行列で表してみます、

$\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \it{1} & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ \it{2} & 1 & 0 \\ \it{-3} & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 1 & 1 \\ -2 & 3 & 1 \\ 3 & -2 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) \\ = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \it{1} & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ \it{2} & 1 & 0 \\ \it{-3} & 0 & 1 \end{array} \right) \left( \begin{array}{c} 6 \\ 1 \\ 9 \end{array} \right)$

細かい説明は省きますが、今回新しく出てきた行列の $\it{2}$ が、先ほどの「中段に上段の2倍を足し」の部分を表し、 $\it{-3}$ は「下段から上段の3倍を引き」のことで、 $\it{1}$ は、「下段に中段の値を足し」の言い換えとなっています。残りの $1$ は、元の数字を保持するためのパーツです。左辺は普通に計算すれば先ほどと同じであるため、

$\left( \begin{array}{ccc} 1 & 1& 1 \\ 0 & 5 & 3 \\ 0 & 0 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) \\ = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -3 & 0 & 1 \end{array} \right) \left( \begin{array}{c} 6 \\ 1 \\ 9 \end{array} \right)$

ここで、式を二つに分けて、

$\left( \begin{array}{ccc} 1 & 1& 1 \\ 0 & 5 & 3 \\ 0 & 0 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} a \\ b \\ c \end{array} \right) \\ \left( \begin{array}{c} a \\ b \\ c \end{array} \right) = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -3 & 0 & 1 \end{array} \right) \left( \begin{array}{c} 6 \\ 1 \\ 9 \end{array} \right)$

また、ここでは詳しく説明しませんがフロベニウス行列の性質を用いて、

$\left( \begin{array}{ccc} 1 & 1& 1 \\ 0 & 5 & 3 \\ 0 & 0 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} a \\ b \\ c \end{array} \right) \\ \left( \begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{array} \right) \left( \begin{array}{c} a \\ b \\ c \end{array} \right) = \left( \begin{array}{c} 6 \\ 1 \\ 9 \end{array} \right)$

と変形できます。連立方程式が1問から2問に増えて、一見遠回りのようですが、下の式からは $a=6,b=13,c=4$ であることがすぐにわかり、上の式に代入して先ほどと同じ解が出ます。

さて、この解答を見せたに行ったところ、前提が違うから解き直してくれと言われてしまいました。右辺の一番上は6でなく0で、さらに二番目は1じゃなくて7だそうです。読めるかー！

ということで解きなおすことになるのですが、単純な消去法では左辺と右辺の式変形を同時に行わなければならなかったため、右辺の原型が早い段階で分からなくなります。これに対し、LU分解を用いた解法では途中まで右辺が原型を保っているため、そこで数字を入れなおすことでやり直すことができます。

$\left( \begin{array}{ccc} 1 & 1& 1 \\ 0 & 5 & 3 \\ 0 & 0 & 4 \end{array} \right) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} a \\ b \\ c \end{array} \right) \\ \left( \begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{array} \right) \left( \begin{array}{c} a \\ b \\ c \end{array} \right) = \left( \begin{array}{c} 0 \\ 7 \\ 9 \end{array} \right)$

ここから、 $a=0, b=7, c=16$ であることがわかり、 $z=4, y=-1, x=-3$ がいえます。

皆さんも学生時代に散々味わったと思いますが、連立方程式を解く際に苦労するのは係数の消去の部分です。専門家によるとこれには未知変数の数の3乗に比例するコストがかかる(つまり、未知変数が3つの連立方程式を解く手間は未知変数2つのそれの2倍以上である)そうです。これを乗り越えた後の部分の手間は2乗に比例ですので、係数の消去をスキップすることは大きなアドバンテージとなります。

ではそのようなアドバンテージを得る機会はどのようなところにあるのでしょうか。「出題者の字が汚いとき」は冗談として、熱に関する分析にヒントがあるんじゃないかと考えました。