トップ > 数理計画用語集 > Bunch-Parlett 分解

数理計画用語集

Bunch-Parlett 分解

読み:ばんちぱれっとぶんかい
関連コレスキー分解LU 分解主双対内点法

一般の実対称行列equationに対し以下の性質を満たす行列equation が存在する.

equation

ここでequation

equation : equation equation

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

equation:equation

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

equation:equation

の形の行列(2×2の行列equation がいくつか対角に並んだあとに行列equationの固有値が続く形).

このように行列equationを他の行列の積に分解する手法のことをBunch-Parlett 分解と呼ぶ.

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

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

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

変数  equation

最小化 equation

制約式 equation

上記の非線形計画法に対するアルゴリズムとして主双対内点法がある.主双対内点法では,変数equation の他に変数equationequationを導入する.この3つの変数を解に収束するように更新していく.その際に各変数を動かす方向equationequationequationを定めるために,次の連立一次方程式を解く必要がある.

equation

ここでequationは以下の通り.

equation,equation

equation, equation

equation, equation

equation , equation

一般にequation は正定値ではないという問題がある.そのためBunch-Parlett 分解が用いられる.正定値でない行列の例としてequation が有名である.直交行列による分解の存在と混合しやすいので注意が必要.