Для того, чтобы найти минимум или максимум унимодальной функции на заданном интервале [a,b] с точностью eps можно воспользоваться методом "золотого сечения": double goldenRatioMin ( double a, double b, const MathFunc1 & func, double eps ); double goldenRatioMax ( double a, double b, const MathFunc1 & func, double eps );Но лучше применять более быстрые методы. Алгоритм fmin я взял из книги "Машинные методы математических вычислений" (Дж.Форсайт, М.Малькольм, К.Моулер) и переписал с небольшими изменениями с FORTRANа на С++. Он представляет собой комбинацию метода "золотого сечения" и параболической интерполяции. Аналогично был сделан алгоритм fmax: double fmin ( double a, double b, const MathFunc1 & func, double eps ); double fmax ( double a, double b, const MathFunc1 & func, double eps );В моих тестах этот алгоритм в среднем делал в 2 раза меньше запросов вычисления значений функции, чем метод "золотого сечения". Для разных функций этот показатель у меня колебался от 10 до 90%. Из этого следует, что лучше применять функции fmin и fmax, а метод "золотого сечения" был оставлен здесь по традиции. Следующая функция находит минимакс на множестве парабол вида x*x + a*x + b: Def<double> getMinMaxParabola1d ( CArrRef<Set2<double> > arr );Описание шаблона классов Def находится здесь. Описание шаблона классов Set2 находится здесь. Описание шаблона классов CArrRef находится здесь. Исходники находятся в файле opti1d.cpp. Наверх |