Найти максимальное значение неизвестной функции в интервале - PullRequest
Новая
       15

Найти максимальное значение неизвестной функции в интервале

0 голосов
/ 27 июня 2019

Учитывая непрерывную, но неизвестную функцию f(x), как я могу найти максимальное значение, которого она достигает за закрытый интервал, вызывая f(x) как можно меньше раз?

Функция неизвестна, поэтому я не могу взять производную явно. Единственный способ проверить значения - вызвать его. f(x) в данном интервале будет иметь только одну критическую точку, но максимальное значение может быть в конечных точках.

Мне не нужна супер высокая точность. Допустим, если метод превышает определенное количество итераций, он остановится и вернет текущее наибольшее значение.

1 Ответ

1 голос
/ 27 июня 2019

Это процесс «разделяй и властвуй».

Конечные точки (a, f (a)) и (b, f (b)) делят ось Y на три области с горизонтальными границами наf (a) и f (b).wlog Я ограничу обсуждение первым квадрантом, предполагая, что f (b)> f (a) 

     |
     |
f(b)-+-------------------------*-----------
     |
     |
     |
     |
f(a)-+-*-----------------------------------
     |
     |
     +-a-------r--------s------b-----

Примите два других значения, 'r' и 's', такие что a < r < s < b.Поскольку существует не более одной точки перегиба, существуют некоторые ограничения на различные возможности для f (r) и f (s), упорядоченных по конечным точкам.

Если оба меньше f (b), томаксимальная точка должна быть справа от s, интервал [s, b].

Если f (r) велико, то так же, как и f (s).
f (r)> f (s)> f (b) означает, что max находится в интервале [a, s]
f (s)> f (r)> f (b) означает, что max находится в интервале [r, b]

Оставшийся случай - это f (a) f (b).Опять же, мы получаем, что максимум должен быть справа от f (r), второй точки в предыдущем случае, интервал [r, b].

После этого определения итерируем оставшийся интервал.Для [a, s] или [r, b] у нас уже есть одна точка в интервале;выберите еще один в большую сторону (если два одинакового размера, выберите любой);для [s, b] нам нужно еще две точки.

Упрощенный способ выбора точек состоит в том, чтобы просто разделить пополам или разделить на три части рассматриваемый интервал.Если вы хотите попробовать что-то более изощренное, используйте свою историю точек, чтобы приблизить функцию (например, подгонка сплайнов) и выберите точки, чтобы быстрее сходиться.

Это вас заводит?

...