レイリー商の概要
グラフ理論や線形代数でしばしば現れるレイリー商について簡単にまとめる。
レイリー商 $R$ は $R:\mathbb{R}^n \setminus \lbrace 0 \rbrace \rightarrow \mathbb{R}$ は対称行列$\mathbf{A}$とノルムが0ではない$n$次元ベクトル$\mathbf{x}$を用いて以下のように定義される。
$$ R(\mathbf{x}) = \frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} $$
本記事では、レイリー商の性質について説明する。またPythonでの実装例も示す。以下のgithubにもソースコードを置いているので必要ならば参考にしてほしい。
ソースコード
github
- jupyter notebook形式のファイルはこちら
google colaboratory
- google colaboratory で実行する場合はこちら
実行環境
OSはmacOSで、LinuxやUnixのコマンドとはオプションが異なりますので注意。
!sw_vers
ProductName: macOS
ProductVersion: 13.5.1
BuildVersion: 22G90
!python -V
Python 3.9.17
基本的なライブラリをインポートし watermark を利用してそのバージョンを確認してする。 ついでに乱数のseedの設定を行う。
import random
import numpy as np
seed = 123
random_state = 123
random.seed(seed)
np.random.seed(seed)
from watermark import watermark
print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))
Python implementation: CPython
Python version : 3.9.17
IPython version : 8.17.2
numpy: 1.25.2
Watermark: 2.4.3
レイリー商の性質
対称行列$\mathbf{A}$は実数の固有値を持つ。その固有値を$\lambda_i$、固有ベクトルを$\mathbf{v}_i$とする。このとき、レイリー商は以下のように表される。
$$ R\left(\mathbf{x}\right)=\frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} = \frac{\left(\sum_{i=1}^{n} \alpha_i \mathbf{v}_i\right)^T \mathbf{A} \left(\sum_{j=1}^{n} \alpha_j \mathbf{v}_j\right)}{\left(\sum_{k=1}^{n} \alpha_k \mathbf{v}_k\right)^T \left(\sum_{l=1}^{n} \alpha_l \mathbf{v}_l\right)} = \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j \mathbf{v}_i^T \mathbf{A} \mathbf{v}_j}{\sum_{k=1}^{n} \sum_{l=1}^{n} \alpha_k \alpha_l \mathbf{v}_k^T \mathbf{v}_l} $$
対称行列の場合、固有ベクトルは直交するため、$ \mathbf{v}_i^T \mathbf{v}_j = 0 $ （$ i \neq j $ の場合）であり、$ \mathbf{v}_i^T \mathbf{v}_i = 1 $ を満たす。
したがって、
$$ R\left(\mathbf{x}\right)=\frac{\sum_{i=1}^{n} \alpha_i^2 \lambda_i}{\sum_{k=1}^{n} \alpha_k^2} $$
これが行列 $ \mathbf{A} $ の固有値 $ \lambda_i $ の重み付き平均であることがわかる。そして、$ \mathbf{x} $ を、たとえば、最大固有値に対応する固有ベクトルとすれば、$ R\left(\mathbf{x}\right) $ の最大値は最大固有値となる。一方、最小固有値に対応する固有ベクトルを選べば、最小固有値が得られる。
ラグランジュの未定乗数法を利用した解法
wikipeadia を参考にラグランジュの未定乗数法を利用したレイリー商の最大値や最小値の証明をメモっておく。
まず、上記と同様に、行列 $ \mathbf{A} $ のレイリー商を $ R(\mathbf{x}) $ とする。
$$ R(\mathbf{x}) = \frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} $$
また、$ \lambda $ を行列 $ \mathbf{A} $ の固有値とし、$ \mathbf{v} $ をそれに対応する固有ベクトルとすると以下が成立する。
$$ \mathbf{A} \mathbf{v} = \lambda \mathbf{v} $$
ラグランジュの未定乗数法では、目的関数 $ f(\mathbf{x}) $ を最大化または最小化する際に、制約条件 $ g(\mathbf{x}) = 0 $ の下で最適解を見つける。未定乗数法では、ラグランジュ関数 $ L(\mathbf{x}, \lambda) $ を導入するのが一般的な表記である。
$$ L(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) $$
ここで、$ \lambda $ はラグランジュの乗数である。 レイリー商の場合、目的関数 $ f(\mathbf{x}) $ は $ \mathbf{x}^T \mathbf{A} \mathbf{x} $ であり、制約条件 $ g(\mathbf{x}) $ は $ \mathbf{x}^T \mathbf{x} - 1 = 0 $ となる。$\mathbf{x}$に対してそのノルムが1である条件をｆ制約条件として設定することで、$\mathbf{x}$が単位ベクトルであることを保証する。
ラグランジュ関数を次のように設定する。
$$ L(\mathbf{x}, \lambda) = \mathbf{x}^T \mathbf{A} \mathbf{x} - \lambda (\mathbf{x}^T \mathbf{x} - 1) $$
このラグランジュ関数を最大化する $ \mathbf{x} $ を見つけるために、勾配がゼロとなる条件を考える。
$$ \nabla_{\mathbf{x}} L(\mathbf{x}, \lambda) = 0 $$
これを解くと、以下のようになる。
$$ 2 \mathbf{A} \mathbf{x} - 2 \lambda \mathbf{x} = 0 $$
$$ \mathbf{A} \mathbf{x} = \lambda \mathbf{x} $$
これは、行列 $ \mathbf{A} $ の固有値 $ \lambda $ と対応する固有ベクトル $ \mathbf{x} $ の関係を表しており、レイリー商の最大値は $ \mathbf{A} $ の最大固有値に等しくなることがわかる。
Pythonによる実装例
簡単ではあるが、以下にPythonによる実装例を示す。
import numpy as np
# ランダムな対称行列Aとベクトルxを生成
A = np.random.rand(3, 3)
A = (A + A.T) / 2
# 適当なベクトルを用意する
x = np.random.rand(3)
# レイリー商
R = np.dot(x.T, np.dot(A, x)) / np.dot(x.T, x)
print("レイリー商:", R.round(2))
レイリー商: 1.47
結論
本記事では、レイリー商の性質について説明した。
また、ラグランジュの未定乗数法を利用したレイリー商の最大値や最小値の証明を示した。
最後に簡単ではあるが、Pythonによる実装例を示した。