機械学習勉強ログ

機械学習に関連した勉強を記録していこうと思います。

線形代数で連立方程式を解く(2) 〜余因子展開を使って解く〜

線形代数を使って、連立方程式を解くの2回目です。 今回は余因子展開を使った逆行列の求め方についての説明回となります。

図解とPythonによるプログラムをつけて数式を解説していきます。

余因子展開による方程式の解法

 A^{-1} = \frac{1}{|A|} \tilde{A}

  •  |A|は、行列式(determinant)で、 \det{A}とも書きます。
  •  \tilde{A} は余因子行列と言います。

これらを求めるためには、小行列余因子の求め方を知る必要があります。

小行列と余因子を求める

余因子の定義

 \tilde{a}_{ij} = (-1)^{i+j} |A_{ij}|

小行列を求める

まずは、小行列ですが  A_{ij} と表されている部分が小行列にあたります。 これは図解で見てもらったほうが早いですが、元の行列 A からi行j列を除いた部分の行列のことです。

つまり、 |A_{ij}| は現状の正方行列より、一回り小さい正方行列の行列式を求めることになります。 例えば、3次の正方行列だったら、2次の正方行列の行列式を求めることになります。

余因子を求める

次に余因子の係数の部分(下記)ですが、

 (-1)^{i+j}

この部分は、符号を決定している部分で行列の縦横のインデックスを足した値が偶数であれば正の符号、奇数であれば負の符号になります。

 \tilde{a}_{ij} = (-1)^{i+j} |A_{ij}|

余因子の式全体としては、n-1次の行列式を求め、行列のインデックスによって符号を付与しているということになります。

行列式( |A|)を求める

余因子を使って行列式は、以下のように表されます。

 |A| = \sum_{k=1}^{n} a_{ik} \tilde{a}_{ik} = \sum_{k=1}^{n} a_{kj} \tilde{a}_{kj}

計算方法についての解説ですが、まずはi, jどの行、列でもいいのですが任意の行か列を選びます。 その行の最初から最後まで、要素と余因子の積を \Sigmaで足し合わせます。

例: 3次正方行列の行列式

余因子展開で違和感があるのは、行列式を求める計算の中に行列式があるためですが、 3次元の行列式を求めるために、余因子展開をかけると2次元の行列式が出てきて、 2次元の行列式を求めるために、1次の行列式、つまり 要素そのものになるまで式の展開が続きます。

この方法であれば、どんなに高次であろうと行列式が求まりますね。😁

行列式(余因子展開)を求めるソースコード(参考)

プログラマには、ソースコードの方がわかりやすいかもしれないので、 自分の書いたコードも合わせて提示しておきます。

# 小行列を求める
def submatrix(m,i,j):
  return np.delete(np.delete(m, i, axis=0), j, axis=1)


# 余因子を求める
def cofactor(m,i,j):
  sign = np.power(-1,i+j) 
  sm = submatrix(m,i,j)
  
  return sign * det(sm)  

# 余因子展開により行列式を求める
def det(m, i=0):
  def term(m,k,i=0):
    return m[i,k] * cofactor(m,i,k)
  
  # スカラーの場合は、値そのものを返す
  if (m.shape == (1,1)):
    return m[0,0]
  
  # 2 x 2以上の正方行列の場合は、余因子展開で求める
  else:  
    return np.sum(
        [ term(m,k,i) for k in range(0, m[:,0].size)]
    )

要は、小行列がスカラーになるまで再帰的に、展開を続けるアルゴリズムになります。

余因子行列( \tilde{A})を求める

余因子行列の方は行列式(余因子展開)に比べれば楽です。 下記は、2次の例ですが余因子( \tilde{a}_{ij})を並べた行列を転置したものが余因子行列になります。


\tilde{A} = \begin{bmatrix}
\tilde{a_{11}} &  \tilde{a_{12}} \\\
\tilde{a_{21}} &  \tilde{a_{22}}
\end{bmatrix}^T

逆行列( A^{-1})を求める

  •  Aの各要素に対する余因子を求めます。
  • そこから、 |A| \tilde{A}を求めます。
  • 下記の公式に当てはめて逆行列を求めます。

 A^{-1} = \frac{1}{|A|} \tilde{A}

方程式の解を求める

 x = A^{-1} \cdot b を計算します。

まとめ

非常に長い手順でしたが、方程式の解を求める手順を紹介しました。 ここに書いてあることを定着させるには、一度は手を動かして解いた方がいいと思います。

今回やったこと

  • 余因子展開を用いた、逆行列の算出方法と方程式の解の算出方法を学んだ。
    • 余因子、小行列、余因子行列、行列式の計算方法について学んだ
    • 余因子展開については、理解を助けるためPythonコードを提示した。

わかったこと

  • 数式の読み方
    • 項や因子ごとに意味を考えると全体が見えてくる。
    • 具体的な値をいくつか当てはめて考えることも有効。そこから、抽象に立ち返っても良い。
  • 数式の意味さえ理解してしまえば、プログラムに変換するのは難しくない。(現状のところは)
  • (何冊か本を買ったのでわかったことだが)数学の解説書で実用に重きをおいている本と、理論の堅牢性や高度な抽象化に重きをおいているものがある。自分の目的にあった本を選択することが大切。

次回やること

余因子展開は行列式を求める手法としてはいいですが、 逆行列を求めるだけなら、もっといい方法をガウスさんが確立してくれています。😁

それをガウスの消去法というのですが、次回はそちらについてPythonコードも含めて解説していきます。