フィボナッチ探索法

フィボナッチ探索法：Fibonacci search technique †

黄金分割法と同様に、一変数関数f(x)の最小（最大）値を求める方法であり、繰り返し計算ルールで探索区間を縮小しながら最適点を効率よく（関数計算をより少なく）求めるために考案された方法である。

• 単峰性の連続関数で、対象の一変数関数が微分可能であれば、 微分係数f'(x)を用いてニュートン法を適用する方法があり、こちらが収束が速い。ニュートン法は繰り返しによる区間縮小法ではない。

The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.

アルゴリズム †

Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If the array size is not a Fibonacci number, let Fm be the smallest number in F that is greater than n.

The array of Fibonacci numbers is defined where Fk+2 = Fk+1 + Fk, when k ≥ 0, F1 = 1, and F0 = 0.

To test whether an item is in the list of ordered numbers, follow these steps:

1.Set k = m. 
2.If k = 0, stop. There is no match; the item is not in the array. 
3.Compare the item against element in Fk-1. 
4.If the item matches, stop. 
5.If the item is less than entry Fk-1, discard the elements from positions Fk-1 + 1 to n. 
  Set k = k - 1 and return to step 2. 
6.If the item is greater than entry Fk-1, discard the elements from positions 1 to Fk-1. 
  Renumber the remaining elements from 1 to Fk-2, set k = k - 2, and return to step 2.

前提 †

関数の極大点をある精度で推定する方法 与えられた区間[a,b]内で連続関数f (x)が定義されており強い単峰性を持つものとする。すなわち 最適点をx*とすれば、区間[a,x*)ではf'>0、最適点でf'(x*)=0、区間(x*,b)ではf'<0　である。（かならずしも１階微分可能性を仮定する必要はない)

n 個の点xi での関数 f( xi） の値の大小関係を知るだけでX*の近傍の最大値x~を求めることを考える。

考え方：命題 †

区間[a,b]内の区間[s,t]にx*が存在することがわかっているとき、s<u<v<tに対し次のことが成立する。

1) f(u)>f(v) --->x* は区間[ s, v]の中
2) f(u)=f(v) --->x* は区間[ u, v]の中
3) f(u)<f(v) --->x* は区間[ u, t]の中

この事実から、f(u)とf(v)の大小関係を知ることができれば、最大値を与えるx*を含む区間の幅を、max[v-s,t-u]以下に限定することができる。

探索法 †

まず区間[a,b]内にu,v(s<u<v<t)を以下のようにとる。

区間の巾をFkとするとき　フィボナッチ数の比で内分するようにu.vを決める
点uの決め方　u-s ：t-s　= Fk-2　：Fk
点vの決め方　v-s ：t-s  =　Fk-1　：Fk
ただし　Fkは、下記のフィボナッチ数
F0=0 F1=1 Fn+2 =Fn+1  + Fn

このとき、f (u), f(v)の大小関係を知ることができれば、最適点は区間[s,v]か[u,t]のいずれかに属するか判定でき、区間巾はフィボナッチ数の比に応じて縮小できる。

上記のことを繰り返していく。 区間の幅は、Fk ,Fk-1 ,...., F2と短くなって、単位長さとなる.

このようにして最大値を与えるXの値域が縮小され、x*の近傍値を求められる。

• 最初の幅Fkの区間[a,b]のときに、２つのフィボナッチ分割点の関数値を知る必要があるが、次からは、幅の区間[s,t]のフィボナッチ分割点のひとつは前の回に調べた点なので､新たに関数値を知る必要なのは１点だけでよい。

• 区間幅が縮小してF2 = 2の時には、その中点がのフィボナッチ分割点であり、中点と2 つの境界点 s,t の関数値が分かれば中点をはさんで右の区間か左左の区間のどちらにx*が存在するか特定できる。
• 区間巾が必要な制度がでれば、停止させ、これを最適の近似値とする。
• 最初に2点で関数値を探り、その後は1点なので、関数値の探索数は、初めにFkから始めた場合は合計k-1回だけ関数を探索すればよいことになる。