行列を分解して上下三角行列が欲しい

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

与えられた行列を分解して上三角行列と下三角行列を求める手法についてまとめたページです.英語では分解をDecompositionまたはFactorizationと言い, LU分解(LU decomposition), LU分解の特別な場合のコレスキー分解(Cholesky decomposition)と言います.
ー 条件 ー
  • 正方行列AはLUP分解可能.さらに全ての主小行列式が非ゼロで逆行列がある場合LU分解可能
  • 正定値対称行列はLU分解可能
  • 正定値対称行列はコレスキー分解可能
ー 効果 ー
  • 線形な連立方程式の解が容易に求まる
  • LU分解を行えると逆行列が求められる
ーポイントー
  • 他にLDU分解などもある
  • 上又は下三角行列の対角線上の要素を1に固定した場合、求まる行列は一意に定る

解  説

与えられた行列を分解して上三角行列と下三角行列を求めたいときの手法についてまとめる. 有名な手法としてLU分解(及びLUP分解. LU分解の特殊な形)がある. LU分解が可能な行列は限られていて容易な判断としては以下があげられる. LU分解またはLUP分解可能な行列 ・正方行列AはLUP分解可能. ・正方行列Aがさらに逆行列を持ち全ての主小行列式が非ゼロで逆行列がある場合,LU分解可能. ・正定値対称行列ならLU分解可能. またLU分解の特殊な形であるコレスキー分解は以下の条件で可能か判断できる コレスキー分解可能な行列 ・正定値対称行列
行列を分解して上下三角行列が欲しい導入
上記には書かなかったが、LU分解可能であることの必要十分条件に関して記述されている論文のリンクを右に記しておく.

1.LU分解

上記の条件を守ったLU分解は以下の連立方程式を容易なものから解いていくことで実現することができる. Lの対角要素を全て1と仮定している.
LU分解の方法
$$A=LU$$ $$\begin{eqnarray} \left( \begin{array}{cccc} a_{ 11 } & a_{ 12 } & \ldots & a_{ 1n } \\ a_{ 21 } & a_{ 22 } & \ldots & a_{ 2n } \\ \vdots & \vdots & \ddots & \vdots \\ a_{ m1 } & a_{ m2 } & \ldots & a_{ mn } \end{array} \right)=\left( \begin{array}{cccc} 1 & 0 & \ldots & 0 \\ l_{ 21 } & 1 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{ m1 } & l_{ m2 } & \ldots & 1 \end{array} \right)\left( \begin{array}{cccc} u_{ 11 } & u_{ 12 } & \ldots & u_{ 1n } \\ 0 & u_{ 22 } & \ldots & u_{ 2n } \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & u_{ mn } \end{array} \right) \end{eqnarray} $$
A=LUのLU分解の様子.
$$a_{11} = u_{11}$$ $$a_{12} = u_{12}$$ $$\dots$$ $$a_{mn}=u_{1n}l_{m1}+\dots+u_{mn}$$
得られる連立方程式. これを解くことでLU分解可能
LU分解及びLUP分解はガウスの消去法と等価な計算.
LU分解について

2.LUP分解

正方行列で対角要素が0になった場合には、LU分解ができなくなってしまいます.そこで転置行列Pを求めることで正方行列ならいつでも分解できるようにします.
LUP分解について
$$PA=LU $$
P:転置行列 A:与えられた行列
置換行列Pの求め方ですが、プログラムで解くときには直接求めることはしません. 左から列に注目していき、各列で最大の値が上にくるように行を交換することでPAを求めます. もちろんその結果からPを求めることは可能です.
置換行列Pの求め方
$$\begin{eqnarray} A=\left( \begin{array}{rrr} 4 & 11 & 6 \\ 5 & 2 & 3 \\ 3 & 1 & 9 \end{array} \right) \end{eqnarray} $$ $$\begin{eqnarray} A'=PA=\left( \begin{array}{rrr} 5 & 2 & 3 \\ 4 & 11 & 6 \\ 3 & 1 & 9 \end{array} \right) \end{eqnarray} $$ $$\begin{eqnarray} P=\left( \begin{array}{rrr} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right) \end{eqnarray} $$
左のようなAの場合について考えます. Aの1列目(4,5,3)をみると2行目の5が最大です.1列目と2列目を入れ替えます.次に、注目した1列目と交換した列は無視すると残りは3列目しかないので、これで完了です. A'が行を入れ替えて作られた行列です.

3.コレスキー分解

これスキー分解では以下のように分解できることを想定しており、 LU分解に置けるUをL^tに置き換えたにすぎません. なので平方根等を用いること以外、通常通り計算することができます.
コレスキー分解
$$A=LL^{ \mathrm{ T } }$$
コレスキー分解の式
$$L_{j,j}=\sqrt{A_{j,j}-\sum_{k=1}^{l-1}L_{j,k}^2}$$ $$L_{i,j}=\frac{1}{L_{j,j}}\sqrt{A_{i,j}-\sum_{k=1}^{l-1}L_{i,k}L_{j,k}}$$
コレスキー分解を解くアルゴリズム. Cholesky–Banachiewicz とCholesky–Crout アルゴリズムと呼ぶ.
この章を学んで新たに学べる
Comments

Reasons
>>隠す