Bunch-Parlett 分解

Bunch-Parlett 分解#

  • 読み: ばんちぱれっとぶんかい

  • 英名:

一般の実対称行列 \(A\) に対し以下の性質を満たす行列 \(P,L,D\) が存在する.

(3)#\[PAP^\top = LDL^\top\]

ここで \(P,L,D\)

(4)#\[\begin{split}P \colon \begin{pmatrix} \begin{matrix} 1 & & \\ & \ddots & \\ & & 1 \end{matrix} & & \\ & \begin{matrix} 0 & 0 & \cdots & 0 & 1 \\ 0 & 1 & \ddots & & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & & \ddots & 1 & 0 \\ 1 & 0 & \cdots & 0 & 0 \end{matrix} & \\ & & \begin{matrix} 1 & & \\ & \ddots & \\ & & 1 \end{matrix} \end{pmatrix}\end{split}\]

の形の行列の積で表される行列(一般に置換行列と呼ばれる),

(5)#\[\begin{split}L \colon \begin{pmatrix} l_{1,1} & 0 & \cdots & 0 \\ l_{2,1} & \ddots & \ddots & \vdots \\ \vdots & \cdots & \ddots & 0 \\ l_{n,1} & \cdots & l_{n,n-1} & l_{n,n} \end{pmatrix}\end{split}\]

の形の行列(一般に下三角行列と呼ばれる),

(6)#\[\begin{split}D \colon \begin{pmatrix} \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} & & & & & & & & \\ & \ddots & & & & & & & \\ & & \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} & & & & & & \\ & & & d_1 & & & & & \\ & & & & \ddots & & & & \\ & & & & & d_s & & & \\ & & & & & & 0 & & \\ & & & & & & & \ddots & \\ & & & & & & & & 0 \end{pmatrix}\end{split}\]

の形の行列 ($ 2 :raw-latex:`\times 2` $ の行列 \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) がいくつか対角に並んだあとに行列 \(A\) の固有値が続く形).このように行列 \(A\) を他の行列の積に分解する手法のことを Bunch-Parlett 分解と呼ぶ.

このほかによく知られている行列分解の手法としてコレスキー分解がある.しかし一般の実対称行列 \(A\) に対してコレスキー分解が存在するための必要十分条件は「\(A\) の固有値がすべて正でなければならない」である.そのため適応できないケースが存在する.さらに有名な行列分解の手法として LU 分解がある.この分解アルゴリズムも「\(A\) の全ての主座小行列の行列式が 0 でない」という必要十分条件があり適用できない場合がある(有名な反例として \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) が知られている).

上記の条件が満たされない行列に対して Bunch-Parlett 分解が用いられる.教科書によっては分解の手法について紹介していても Bunch-Parlett 分解などのような固有の呼び方をしないことも多いため,行列数値計算に興味のある者以外にはあまり知られていない.

Bunch-Paralett 分解と非線形計画問題#

Bunch-Parlett 分解を必要とする背景として,以下の一般形の非線形計画問題を解くという目的がある.

(7)#\[\begin{split}\begin{array}{ll} \min & f(x) \\ \mathrm{s.t.} & g(x) = 0, \ g(x) \in \mathbb{R}^m \\ & x \in \mathbb{R}^n \\ & x \ge 0 \end{array}\end{split}\]

上記の非線形計画法に対するアルゴリズムとして主双対内点法がある.主双対内点法では,変数 \(x \in \mathbb{R}^n\) の他に変数 \(y \in \mathbb{R}^m\)\(z \in \mathbb{R}^n\) を導入する.この 3 つの変数を解に収束するように更新していく.その際に各変数を動かす方向 \(\Delta x \in \mathbb{R}^n\)\(\Delta y \in \mathbb{R}^m\)\(\Delta z \in \mathbb{R}^n\) を定めるために,次の連立一次方程式を解く必要がある.

(8)#\[\begin{split}\begin{pmatrix} L & A^\top & -I \\ A & 0 & 0 \\ Z & 0 & X \end{pmatrix} \begin{pmatrix} \Delta x \\ \Delta y \\ \Delta z \end{pmatrix} = \begin{pmatrix} M \\ N \\ XZe-\sigma e \end{pmatrix}\end{split}\]

ここで \(L \in \mathbb{R}^{n \times n}\)\(A \in \mathbb{R}^{m \times n}\)\(M \in \mathbb{R}^n\)\(N \in \mathbb{R}^m\)\(Z \in \mathbb{R}^{n \times n}\)\(X \in \mathbb{R}^{n \times n}\)\(e \in \mathbb{R}^n\)\(\sigma \in \mathbb{R}\) は以下の通り.

(9)#\[L_{i,j} = \left(\frac{\partial^2 f}{\partial x_i \partial x_j}(x) + \sum_s{y_s} \cdot \frac{\partial^2 g_s}{\partial x_i \partial x_j}(x) \right), \ A_{i,j} = \left( \frac{\partial g_i}{\partial x_j}(x) \right)\]
(10)#\[M_i = \left(\frac{\partial f}{\partial x_i}(x) + \sum_s{y_s} \cdot \frac{\partial g_s}{\partial x_i}(x) - z_i \right), \ N_i = \left( g_i(x) \right)\]
(11)#\[\begin{split}Z = \begin{pmatrix} z_1 & 0 & \cdots & 0 \\ 0 & z_2 & 0 & \vdots \\ \vdots & 0 & \ddots & 0 \\ 0 & \cdots & 0 & z_n \end{pmatrix}, \ X = \begin{pmatrix} x_1 & 0 & \cdots & 0 \\ 0 & x_2 & 0 & \vdots \\ \vdots & 0 & \ddots & 0 \\ 0 & \cdots & 0 & x_n \end{pmatrix}\end{split}\]
(12)#\[\begin{split}e = \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}, \ \sigma > 0\end{split}\]

一般に \(L\) は正定値ではないという問題がある.そのため Bunch-Parlett 分解が用いられる.正定値でない行列の例として \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) が有名である.直交行列による分解の存在と混合しやすいので注意が必要.

関連