Function nekolib::algo::extremum_float

pub fn extremum_float(
    range: RangeInclusive<f64>,
    eps: f64,
    f: impl FnMut(f64) -> f64
) -> (f64, f64)

三分探索で極値を探す。

関数 $f$ の $[x_l, x_r]$ における極大値を $x^\ast$ として、 $|x-x^\ast| \le \varepsilon$ なる $x$ を求め、$(x, f(x))$ を返す。

Requirements

$f$ は凸である。

Notes

黄金比を用いて分割する実装のため、関数値を使い回すことができる。

Complexity

f の呼び出しを $\log_{\varphi}(\frac{x_r-x_l}{\varepsilon}) + 1$ 回行う。

Suggestions

f64 に限らずジェネリックにするべき？ 関数の返り値も T: PartialOrd にする？

Examples

$f(x) = x^x$ の最小値を求める。

$x = 1/e$ のとき、最小値 $e^{-1/e}$ をとる。 cf. Wolfram|Alpha

use nekolib::algo::extremum_float;

let p = 3.0_f64;
let f = |x: f64| -x.powf(x);

let xl = 0.0;
let xr = 140.0;
let eps = 1.0e-8;
let (x, y) = extremum_float(xl..=xr, eps, f);
let y = -y;

let e = std::f64::consts::E;
assert!(((1.0 / e) - x).abs() < eps);
assert!((e.powf(-1.0 / e) - y).abs() < eps);