黄金分割法はなぜ効率が良いのか。また、どうすればより改善されるか。

0.参考文献

[1]https://ja.wikipedia.org/wiki/黄金分割探索

1.黄金分割法とは[1]

f(x)は単峰関数であり、極値を調べることを考えます。

数x_1~x_3に対して値f(x_1)~f(x_3)が与えられているとします。このとき、次に調べるべき点x_4は、

となるように定めることで効率よく探索することができます。

2.理由付け[1]

x_1, x_2, x_3の作る比率と、x_1, x_2, x_4の作る比率が等しいと、効率が良いだろうという理由からです。これをもとに計算すれば、x^2=x+1の式が現れ、結果的に黄金比が現れます。

3.より明確な理由付け

2章で説明したものは、少々厳密ではないように感じます。そこで、以下の定理を用いて捉え直します。

定理:「隣り合う3つのフィボナッチ数を3辺の長さとする三角形は球面を作る。その半径Rは3つのフィボナッチ数のうち最小と最大のレンジにπ/(2*x), x:中間のフィボナッチ数をかけたものに含まれる。このレンジは収束値をもち、単位体積(R^3)に対する球面の体積は収束する。」

こうして、球面として関数を捉え直します。この球面に対して座標xが存在し、各座標xに対応する関数f(x)が存在すると捉えます。

すなわち、今まで考えていたx-f(x)平面は、立体的な球体として考えます。

ここで、2次元平面において任意の2地点を結ぶ最短距離は線分です。これを、平面上で、「隣り合う3つのフィボナッチ数を3辺の長さとする三角形」であると捉え直します。

そうすれば、球面にした場合、ほとんど"収束した(体積を持つ)"球において、この三角形は0でない面積を持ちます。

この面積について、各座標xに対応する関数f(x)により評価することができるだろうと予想できます。g(S,f(x))=0なる関数を考えることができるだろうということです。

ここで、今考えていた隣り合う3つのフィボナッチ数において、それより合計が大きい隣り合う3つのフィボナッチ数のうち、最小のもの(要するに、今考えていたもののうち、中間、最大、最大の一つ上)の組み合わせを考えます。

同様に、面積についてg(S',f(x)')=0なる関係を与え、特にS≒S'であるときを考えます。

これは同時にf(x)≒f(x)'を考えていることに対応するだろうと予想できます。

ポイントは、このようなS≒S'を満たす点を探すことが、今回のf(x)の極値を求めることと同値である点です。そして、そのようなS≒S'は、結局フィボナッチ数列を考えることに対応し、結局、黄金比が現れるのでした。

この極値のデータは次元が低くなっても(すなわち曲率を∞にしても)、保存されます。

以上から、黄金比を用いることで、効率よく極値を探索することができるのだろうと予想します。

4.改善

この式では、単に黄金比を用いて(近似的に)比率を与えました。しかし、以上の推論からより精度の高い比率を与えることができると予想します。x_2-x_1、x_3-x_2の2つにおいて、2つの比率(あるいは単にそれぞれの数)に近い、隣り合うフィボナッチ数2つを選択します。これをa_n、a_(n+1)としますと、次のようにφ'を新たに与えられます。