|
最小2乗法の連立1次方程式A†Ax= A†bにおいて対角要素にゲタをはかせると、係数A、bの誤差に対して解xαの誤差が極端に増幅されるのを防げる(チホノフの正則化)
ここでαは、A、bの誤差δに合わせて
となるように決める。この左辺はα=0から∞まで動くときx0からbまで単調増加するから、与えられたδに対してαが一意に決まる |
連立1次方程式を解いていると、計算の途中で桁落ちして解が不安定になることがある。桁落ちするのはデジタル回路(浮動小数点表示)のせいであり、桁落ちしやすさはアルゴリズムのせいであるが、そもそも係数A、bが解xを不安定にする特徴をもっている場合がある。ざっくり言うと
・行列をかけることは、回転、鏡映、伸縮の組み合わせ。
・このうち長さを変えるのは伸縮つまり対角行列。(球が楕円体に変換されるイメージ)
・この対角要素に極端に大きい/小さいものがあると、その方向の誤差だけ極端に増幅されてしまう。
というわけである。そこで、対角要素にゲタをはかせれば、誤差が極端に増幅されるのを防げる。
以下、誤差がどのように抑えられるのか定量的に見ていく。なお、ここの計算は「逆問題の考え方(上村豊)」によっている。
◇
解きたい連立1次方程式を
とすると、最小2乗法による解は
であった。(この右辺の行列は疑似逆行列と呼ばれA+で表す)
◇◇
Aの特徴を調べるために、対角行列Σとユニタリ行列U,Vに分解する(→補足-特異値分解)
このとき疑似逆行列A+の特異値分解は
すなわち、疑似逆行列A+の特異値はＡの特異値の逆数になっている。
今、定数項bがあるujの方向にεだけ変化すると
解xの変化量はvjの方向に1/σj倍になる。したがって、σjが小さいと誤差が極端に増幅される。
◇◇◇
次に対角要素にゲタαをはかせると
これの疑似逆行列の特異値分解は
対角要素にゲタαをはかせたおかげでσjが小さくても1/σjのように発散せずに済む。(このゲタをはかせる方法はチホノフの正則化と呼ばれている)
◇◇◇◇
ゲタαは小さすぎると効かないし、大きすぎると αx=bとなって方程式の意味がない。目安としてA、bの誤差δに合わせて
となるように決める。ここで、正則化解xαは
(6)の左辺を計算してみると
式(2)、(5)から
を代入すると
結局、
の左辺は、α=0から∞まで動くときx0からbまで単調増加するから、与えられたδに対して必ずαが決まる
◇◇◇◇◇
上記では、解xの誤差のbの誤差に対する増幅率が1/σ倍になることは示したが、実はAの誤差に対する増幅率も上限は同じになることが示せる。そのために、行列のノルムという概念を使う。Aのノルムは、長さ1のベクトルxが動いたときのAxの長さの上限と定義される。
この定義から得られる不等式
を使って、解xの誤差をbの誤差で評価すると
また係数Aの誤差は1次までとって
だから、解xの誤差をAの誤差で評価すると
b、Aの誤差に対する増幅率は、いずれも同じ上限
で抑えられていることが示せた。(このκ(A)は条件数と呼ばれている)
ちなみに、Aを球から楕円体への変換とイメージすれば、Aのノルムは楕円体の最も長い半径、すなわち対角要素(特異値)の最大のものである。
また疑似逆行列A+の特異値はAの特異値の逆数だったから
したがって誤差の増幅率はノルムの代わりにAの特異値で表せて
結局、b、Aの誤差に対する解xの誤差の増幅率は、Aの特異値の最大/最小の比で抑えられる。