📂行列代数

制約付極値定理

定理¹

制約付き極値定理 (Constrained Extremum Theorem):

行列 $A \in M_{n \times n}(\mathbb{R})$ が 対称 だとしよう。さらに $A$ の 固有値 を $\lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}$ とする。すると次が成り立つ。

(a) $\| \mathbf{x} \| = 1$ の制約^constraintの下で、二次形式 $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$ は最大値と最小値を持つ。

(b) 最大値と最小値はそれぞれ $\lambda_{1}$、$\lambda_{n}$ である。

説明

$\mathbf{x}^{\mathsf{T}} \mathbf{x} = \| \mathbf{x} \|^{2}$ なので、式を下のように変えれば $\| \mathbf{x} \| = 1$ の制約を課した場合と同じ結果が得られる。

$$ \dfrac{\mathbf{x}^{\mathsf{T}} A \mathbf{x}}{\mathbf{x}^{\mathsf{T}} \mathbf{x}} $$

この値を レイリー商 と呼ぶ。

証明

$A$ が対称であると仮定したので、主軸定理 により次を満たす 直交行列 $P$ が存在する。

$$ \mathbf{x}^{\mathsf{T}} A \mathbf{x} = \lambda_{1}y_{1}^{2} + \cdots + \lambda_{n}y_{n}^{2}, \quad \mathbf{x} \in \mathbb{R}^{n} $$

このとき $P$ は 直交変数変換 により $\mathbf{x} = P \mathbf{y}$ が成り立つ。$P$ は直交行列なので ノルムを保存する。

$$ \| \mathbf{x} \| = \| \mathbf{y} \| = y_{1}^{2} + \cdots + y_{n}^{2} $$

したがって次の不等式が成り立ち、$\lambda_{1}$ と $\lambda_{n}$ は $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$ の 上界 と 下界 になる。

$$ \begin{align*} \lambda_{n} &= \lambda_{n}(y_{1}^{2} + \cdots + y_{n}^{2}) \\ &\le \lambda_{1}y_{1}^{2} + \cdots + \lambda_{n}y_{n}^{2} = \mathbf{x}^{\mathsf{T}} A \mathbf{x} \\ &\le \lambda_{1}(y_{1}^{2} + \cdots + y_{n}^{2}) \\ &= \lambda_{1} \end{align*} $$

$$ \implies \lambda_{n} \le \mathbf{x}^{\mathsf{T}} A \mathbf{x} \le \lambda_{1} $$

$\mathbf{x}_{1}$ を $\lambda_{1}$ に対応する固有ベクトルとすれば次が成り立つ。

$$ \mathbf{x}_{1}^{\mathsf{T}} A \mathbf{x}_{1} = \lambda_{1} \mathbf{x}_{1}^{\mathsf{T}} \mathbf{x}_{1} = \lambda_{1} $$

同様に、$\mathbf{x}_{n}$ を $\lambda_{n}$ に対応する固有ベクトルとすれば次を得る。

$$ \mathbf{x}_{n}^{\mathsf{T}} A \mathbf{x}_{n} = \lambda_{n} $$

したがって $\lambda_{1}$、$\lambda_{n}$ はそれぞれ $\mathbf{x}^{\mathsf{T}} A \mathbf{x}$ の最大値と最小値である。

■