最小2乗法 - その6

MathematicaとRaspberry Piで遊んでるせいで、こっちを忘れてしまいそうになっている。まあ別に忘れても誰も何とも言わないだろうけど、一応続けることにする。

前回は最小2乗法で関数展開するときに、どう言う場合に数値解が不安定になるかというのを具体的な例で見た。単純なベキ展開では条件が悪くなることが多いけど、そういった悪条件の最小2乗法でも、とにかく数値が欲しい、と言う場合がある。そのときは無理矢理にでも数字を作らないといけないけど、逆行列に極端に大きな数字や小さな数字が出てきて、すぐ桁落ちしてしまう。そういうときどうすればいいのか。

6  QR分解

ということで、逆行列を計算せずに解を求めたい。そのとき使われるのがQR分解と言う手法である。これは行列Gを直交行列Qと上三角行列Rの積に分解する。

直交行列と言うのは列ベクトルの長さが全部1で、しかもお互いに直交している行列である。直交行列の条件数は1で、つまりこれは数値的には非常に安定で、これ以上数値的に安定な行列は単位行列ぐらいしかない。

しかも直交行列は転置すると逆行列になる、

という便利な特徴を持っている（証明するまでもなく自明。普通は式-44を満たす行列のことを直交行列の定義とする）。そこで、行列GをQR分解して

とすれば、Rは上三角行列なので、昔懐かしいガウスの消去法の後退代入が使えて解が求まる、ということになる。この場合は逆行列が必要ない。

どうせ上三角行列にするんだったら、ガウスの消去法でいいんじゃないか、これなら逆行列を計算しないので、と思うかもしれない。

ガウスの消去法は実質的にLU分解と同じである。LU分解とは

と分解する。ここでLは下三角行列、Uは上三角行列である。LU分解できれば

というふたつの方程式に分解できる。このふたつはどちらも端の要素から順番に代入していくことで簡単に解くことができて、まず上の式からpを求め、それを使って解aを求めることができる。

このLもUも三角行列なので、ちゃんと数字が埋まれば特異にはならないことが明らかで、しかも計算量が少ないので非常にいいアルゴリズムなんだけど、ひとつだけ問題がある。それは単純なLU分解では数値的安定性を保証できないということである。つまりLU分解によって条件数がどうなるかは分解前にはわからないし、それを制御する方法がない（実はまったくないわけではなく、ピボッティングという行を入れ替える動作をすると改善できる。しかしピボッティングで数値的安定性を完全に制御できるわけではない）。

実は逆にLU分解によって条件数が改善する場合もあり得る。うまく使えば計算量は少なく、作業領域も必要ではないので非常に優れた方法になりえる。特に大きな行列を扱う場合のためにいろいろ研究されている。

それに較べてQR分解はすくなくとも分解によって条件数が悪化しないと言うことが保証できる。ようするに、あまり頭を使わずに、なんでもかんでもバカちょんでやりたいならQR分解が楽、ということである。

6.1  直交行列とベクトルの積

n次元直交行列Qとn次元ベクトルrとの積s

を考える。ここでは証明はやらないけど、直交行列は、その積によって

• 内積の値を保存する

という特徴がある。ちゃんと書くとa、bを任意のベクトル、Rを直交行列とすると

である（証明は式-44から簡単にできる）。このことからまず

• ベクトルの長さを保存する

が自動的に言える。

こうなるような変換にはどんなものがあるか、というのを幾何学的に考えてみると

• 原点を通るある直線のまわりに回転させる
• ある超平面（n−1次元（あるいはそれ以下の次元の）空間内）に対して鏡映する
• 要素の順番を入れ替える

の３通りしかしない。これは一般の行列Gと直交行列Qとの積QGで

• 列ベクトルの相対的な位置関係は変わらない

ということである。相対的な位置関係と言うのは、行列を列ベクトルのたばだと考えて、直交行列をそれにかけても、たばの全体をぐるぐると回転させたり、鏡に映したり、座標軸を入れ替えたりするだけ、ということである。列ベクトル間のそれぞれの内積の値を変えないので、このような幾何学的なイメージはあたりまえである。

そして最小2乗法に出てくる行列の数値的な安定性は、列ベクトルがそれぞれどれだけ独立しているか、ということだった。従って

• 直交行列による積によって行列の条件数は変わらない

ということが直感的にわかる（証明は簡単だけど、条件数の計算をちゃんとやらないといけない）。

ということは行列をQR分解したとき

である。これはLU分解にはない特徴である。最小2乗法にQR分解を使えば、条件数を変えずに後退代入が使える行列になる、ということであって、これがQR分解を使う利点である。

もともと直交行列は固有値問題に有効な手段としての方が応用範囲は広くて、量子力学では直交行列を複素数に拡張したユニタリ行列がいろいろな場面で道具として大活躍する。最小2乗法での利点はそのおすそわけのようなものである。

一言注意しておくと、これまでの議論でわかるように、QR分解によって条件の悪い問題が改善されるということはない。条件の悪い問題は悪いなりにむりやり解くことができる、というだけである。ただなんとなくベキで展開してみました、なんていうのではなくほんとうに数値的な安定性が必要なら、データ上で直交性のいいモデル関数を選んでLU分解で解を得る、ということを考えるべきである。