Excelで操る!フィボナッチ探索法による最小値(最大値)の探索

Excelを用いた科学技術計算が第2版になりました　30年10月！

amazon：Excelで操る! ここまでできる科学技術計算第2版

楽天： Excelで操る! ここまでできる科学技術計算 [ 神足　史人 ]

　　図１　例題関数のグラフ

フィボナッチ数

　フィボナッチ数は次式で定義される。

　F_N= F_N-1+F_N-2

　F₀ = F₁=1

　Excelを用いると簡単に計算され、下図となる。

　　　　　　図2　Excelを用いたフィボナッチ数の計算

たった1日で即戦力になるExcelの教科書

入門者のExcel VBA―初めての人にベストな学び方 (ブルーバックス)

Excel VBAのプログラミングのツボとコツがゼッタイにわかる本

すぐに使える！ Excel関数逆引き辞典

最小値を求めるときのフィボナッチ探索法

図２　分割法

　探索回数(N)が決まっている場合、探索範囲をフィボナッチ数(F_N)で分割し、探索する方法が原理的にもっとも有利である。
図2の様に、F_N=F_N-1+F_N-2となるフィボナッチ数の性質を利用し、探索範囲F_NをF_N-1対F_N-2に分割し、分割点の関数値を比較しながら探索範囲を狭めていく。けっきょく、探索範囲をF_N-2/F_Nの比で分割していくことになる。

計算手順を下記に示す。

(1) 探索範囲[F：T]を設定する。

(2) F_N-2/F_Nの比に左側分割点L、右側分割点Rを求める。

(3) 分割点での関数値f(L)、f(R)を求める。

(4) f(L) > f(R)のとき、FをＬに置き換える。そうでないとき、TをＲに置き換える。

(5) (2)～(4)をＮ回繰り返す。

Excelで操る！黄金比/黄金分割法による最小値(最大値)の探索では範囲分割比が一定となる黄金比を採用した。フィボナッチ法はこの範囲分割比が一定の条件をはすしたことななる。Ｎが大きいとき、最初の分割比は黄金比に近づく。

Excelで操る!フィボナッチ探索法

Excelを用いて例題の関数f(x)=x+2/xの最小値を初期探索範囲[1:2]、探索回数(N=１５)の条件で求めてみよう。理論解はx=√2のときf(x)は最小となる。
図3様に、セルに計算を組み込む。