連立1次方程式の解法
信号処理で連立1次方程式Ax=b を解かなければならないことがある(→補足-適応フィルタ)が、変数の個数や係数の性質によって適切な解法が違うらしく、どういう違いがあるか疑問に思ったのが本章を書いたきっかけである。といってもこの分野はとても広そうなので、大規模でない連立1次方程式を有限回(n3)の計算で解く方法にしぼって、実装には立ち入らずにアルゴリズムを概観することにする。
なお本章は、Numerical Linear Algebra (Trefethen and Bau)によっている。
◇
解法の方針は、行列Aを、次のような「Ax=b が簡単に解ける行列」に分解することである。
(1) 対角行列D
Dx=b はスカラーの除算で解ける。
(2) 列ベクトルが正規直交(ノルム1かつ互いに直交)している行列Q,P
列ベクトルがノルム1かつ互いに直交している(Q†Q=I)から、Qx=b はQのエルミート共役をかけるだけ(x=Q†b)で解ける。
(3)下三角行列L、上三角行列R
Lx=b は上から順に代入していけば解ける。(前進消去という)
Rx=b は下から順に代入していけば解ける。(後退代入という)
◇◇
有名な分解をあげると次表のものがある。違いをざっくり言うと、
LU分解、Cholesky分解 ＜ QR分解 ＜ SingularValue分解
の順に計算量が多くなるが数値計算の安定性はよくなるらしい。
|
分解 |
図 |
説明 |
|
LU分解 |
|
Aが正方行列でフルランク(つまりA-1が存在する)ならば分解可。 (正確に言うと計算途中でAの対角要素がゼロに ならないように行の置換が必要になることがある) LまたはRの対角要素を1に決めると分解は一意に決まる。 LとRの対角要素を1にしてDを分けたものをLDU分解という。 |
|
Cholesky分解 |
|
Aが正定値のエルミート行列ならば分解可。 Rの対角要素を正に決めると分解は一意に決まる。 Rの対角要素を1にしてDを分けたものを 修正Cholesky分解という。 (LU分解と同じだが、AがエルミートなのでLはR†になり 計算量が半分で済む。また正定値なので行の置換は不要) |
|
QR分解 |
|
任意のAに対して分解可。Aは正方行列でなくてもよい。 Aがフルランクのとき、Rの対角要素を正に決めると 分解は一意に決まる。 |
|
SingularValue 分解 |
|
任意のAに対して分解可。Aは正方行列でなくてもよい。 Dの対角要素(特異値)は一意に決まる。 さらにAが正方行列で特異値がすべて異なるとき、 分解は一意にきまる。 ただし、この分解は有限回の計算では出来ず、 収束するまで反復計算するしかない。 |
