黄金分割法

作成日:2001-12-14
最終更新日:

単峰性をもつ関数 f(x) を最小にする xmin の値を返すアルゴリズムとして、黄金分割法が知られている。 この黄金分割法について述べる。なお、単峰性は「たんぽうせい」と読むと思われる。英語では unimodality である。

単峰性をもつ関数とは、区間 [a, b] で定義された関数で(連続性は仮定しない)、 ある xmin ∈ (a,b) に対し、 a < x < xmin なる区間で減少し、xmin < x < b なる区間で増加する関数である。

以下は、下に凸な関数を例にとって、単峰関数の最小値を求める方法の実装である。

まずは、下限に 0 を、上限 に 2 を、許容誤差に 0.01 を入れる。 そして、関数に x * x - 2 * x + 3 を指定する。 そこで計算ボタンをクリックすると、答えが .9968943799848582 となる。

下限 low 上限 high
許容誤差 tolerance 関数 f
最小値を与える x

なんらかの事情により計算を中断することがある。 このときは「エラーのため計算できません。」という警告を表示し、計算を停止する。 中断の理由は、次のような原因が考えられる。

  1. 単峰ではない
  2. 許容誤差が正ではない
  3. 許容誤差が上限と下限の差より大きい

なお、上限と下限が逆のときは、上限と下限を交換して計算する。

まりんきょ学問所JavaScript 手習い > 黄金分割法


MARUYAMA Satosi