サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

求根アルゴリズム 挟み撃ち法 / イリノイ法 / アンダーソン・ビョーク法 [2/3]

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である イリノイ法とアンダーソンビューク法を紹介します。

挟み撃ち法(False position method)

二分法のように根が存在するであろう探索区間を保ちながら, 次の探索点としては直線補間を用いるのが挟み撃ち法です。 割線法と異なるのは探索区間の2端点から直線補間を行う点となります。

input: function f
input: point a, b such that f(a)f(b) < 0 and |f(b)| < |f(a)|
constant: e 許容誤差

while |f(b)| > e
    s = (a*f(b)-b*f(a))/(f(b)-f(a))
    if f(a)f(s) > 0:
        a = s 
    else:
        b = s 
    if |f(a)| < |f(b)|: # bが最適な値にする
        a, b = b, a
return b

ある探索区間  [a, b] について,  f(a) \neq 0 f(b) \neq 0 の符号が異なるならば,  a b を補間した直線と  y=0 との交点は開区間  (a, b) 上に存在します。 すなわち一回のループごとに必ず探索区間は小さくことがわかります。

利点: 収束の堅固さ
欠点: 収束が遅い場合がある

これは  f(x) = 2x^3 - 4x^2 + 3x,  a = -1, b = 1, e = 0.01 として探索を始めた結果です。これを見ると反復回数が進むにつれて、探索点の更新の歩みが遅くなっていますね。 原因としては左端点(  x=-1 )が探索中全く動かないことから探索区間が縮まらず, 各ループにおける線形補間の精度が悪いことが考えられます。

それに対する改善策を提案したのが次で紹介するイリノイ法です。

イリノイ法(Illinois method)

探索区間の両端により線形補間を行うのではなく, 片方を仮想的な点に置き換えて線形補間を行うというのがイリノイ法のアイデアです。探索区間の端点を  a, b とすると, このとき, 次の探索点を  s = \cfrac{af(b)-bf(a)}{f(b)-f(a)} ではなく,  s = \cfrac{af(b)-b\frac{f(a)}{2}}{f(b)-\frac{f(a)}{2}} もしくは,  \cfrac{a\frac{f(b)}{2}-bf(a)}{\frac{f(b)}{2}-f(a)} を採用します。すなわち, 片方の端点の  y 座標を半減させて線分補間を行います。

上の図では,  a y 座標を半減させることで, 探索点  s (図中, 灰色丸点)が a の方に近づき, 探索区間 a s に置き換わりやすくなっている様子を示したものです。探索区間の両端を更新させやすくするために, 前のループで更新されなかった方の端点の  y 座標を半減させるということを行います。

input: function f
input: point a, b such that f(a)f(b) < 0 and |f(b)| < |f(a)|
constant: e 許容誤差

fa = f(a)
fb = f(b)
while |fb| > e
    s = (a*fb-b*fa)/(fb-fa)
    fs = f(s)
    if fa*fs > 0:
        a = s; fa = fs
        fb = fb / 2 # 更新されなかった方の端点のy座標を半減
    else:
        b = s; fb = fs
        fa = fa / 2 # 更新されなかった方の端点のy座標を半減
    if |fa| < |fb|: # bが最適な値にする
        a, b = b, a
        fa, fb = fb, fa
return b

これは,  f(x) = 2x^3 - 4x^2 + 3x,  a = -1, b = 1, e = 0.01 として探索を始めた結果です。割線法が17回のループで探索を終了したのに対し, イリノイ法では9回のループで探索を終えることができています。



アンダーソン・ビョーク法(Anderson & Björk's method)

さらにイリノイ法に工夫を加えたのが, このアンダーソン・ビューク法です。イリノイ法では, 更新されなかった端点の  y 座標を常に半減させていたが, この手法では新しい探索点の具合からどれだけ減らすかを決定します。具体的な決め方は以下の通りです。

探索区間の端点  a, b について, 新しい探索点  s を得たとします。 端点  a s に更新するならば, 次の探索点計算において  fb fb \leftarrow m * fb と更新します。 このとき,  m \cfrac{f(s)}{f(a)} \lt 1 であれば  m = 1 - \cfrac{f(s)}{f(a)}, そうでなければ,  \cfrac{1}{2} とします。

input: function f
input: point a, b such that f(a)f(b) < 0 and |f(b)| < |f(a)|
constant: e 許容誤差

fa = ori_fa = f(a)
fb = ori_fb = f(b)
while |fb| > e
    s = (a*fb-b*fa)/(fb-fa)
    fs = f(s)
    if fa*fs > 0:
        m = 1 - fs / ori_fa if fs / ori_fa < 1 else 1 / 2
        a = s; fa = original_fa = fs
        fb = m*fb  # 更新されなかった方の端点のy座標をm倍減少
    else:
        m = 1 - fs / ori_fb if fs / ori_fb < 1 else 1 / 2
        b = s; fb = original_fb = fs
        fa = m*fa # 更新されなかった方の端点のy座標をm倍減少
    if |fa| < |fb|: # bが最適な値にする
        a, b = b, a
        fa, fb = fb, fa
        ori_fa, ori_fb = ori_fb, ori_fa
return b

これは,  f(x) = 2x^3 - 4x^2 + 3x,  a = -1, b = 1, e = 0.01として探索を始めた結果です。 割線法が17回, イリノイ法では9回のループで探索を終えているのに対し, このアンダーソン・ビョーク法では6回で探索を終えることができました。

元文献を読んでから正確な情報を掲載しますが, ひとまず, この  m の決め方に関する考察を述べます。 各ループにおいて線形補間による端点の更新が小さければ, もう片方の端点の減少率を上げるという式になっていますが, これは更新されなかった方の端点の更新を促していると言えます。 両端が大きく更新されていくのが理想的な探索ですが, あるループで小さい更新が起こると, もし関数が連続的であれば次のループでも同じ側でまた小さい更新が起きやすくなります。 そういう意味で, この戦略は効果的であると言えるでしょう。



参考:
[1] https://en.wikipedia.org/wiki/False_position_method


まえ

つづき