曲がった迷路その20 - はさみうち法

暑くて目が覚めた。外は選挙カーや右翼の街宣車やなぜだか知らんが花火のドンが鳴ったり、ベランダの前のお寺の墓場では殺虫剤でもまいているのかポンプの音がぼぼぼぼ、とか言ってうるさい。
休ませてくれよう。

迷路生成は先が見えてきてペースが上がってる。今回は1次元最適化の簡単な方。

はさみうち法

はさみうち法と言うのは、最小値が含まれていることがわかっている区間[a,b]を、半分に割って狭めていく方法である。

二つに割ったとき、どちらに最小値が含まれているかを知るために微係数を使う。

図-26のように、区間[a,b]が最小値を含んでいるなら、aでの微係数とbでの微係数の符号は逆のはずである。図では赤い矢印で微係数を描いた。

その間の2等分点をcとする。最小値はcでの微係数と逆符号の区間（図では[c,b]）に含まれ、そうでない区間には含まれないはずである。この含まれる方の区間に対して再び2等分点をとって同じことを繰り返すと、1回ごとに区間の長さを半分にでき、許す誤差をεとすると

となるまで繰り返せばよい。

今回の場合、誤差ではなく区間の長さで決めた方が良い。その場合には最初の区間の長さだけで繰り返しの回数が決まる。繰り返しの回数をn、許す区間の長さをδとすると

つまり

回繰り返せばよい。

ちょっとおおげさ。今回の場合ポテンシャルのグラディエントから微係数の値は求まるけど、区間が小さくなると内挿による数値的な不安定性のために最小値を取り逃す可能性がある。また、解析的な微分でなく、数値的に微係数を求めている場合も、その精度や、停止条件には要注意である。