- •Российская Федерация
- •Введение
- •Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка Метод последовательного перебора
- •Поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка
- •Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка и метода последовательного перебора
- •Сравнительное исследование эффективности методов
- •Заключение
- •Список литературы
- •Приложение
Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка Метод последовательного перебора
Обозначим через класс функций, удовлетворяющих условию Липшица на отрезке, с одной и той же для всех функций этого класса константой. Для функции будем рассматривать задачу минимизации первого типа, когда ищется величина .
На классе можно предложить простой и эффективный последовательный метод перебора, когда выбор точкипри каждомпроизводится с учетом вычислений значения функции в предыдущих точках и задачу: как выбрать число и метод, чтобы
(1)
удается решить за меньшее количество вычислений значений функции. Положим
(2)
где ,, ,а число определяется условием.
Теорема 1.
Метод последовательного перебора (2) решает задачу (1) на классе .
Описание метода
Пусть функция удовлетворяет условию Липшица на с известной константой . Тогда, согласно следствия из теоремы 4.5, будет существовать минимуми хотя бы одна из точек минимумафункции на. Будем искать приближения для минимумаи какой-нибудь точки минимумафункциина() с погрешностями, не превышающими заданного положительного числа.
Для решения поставленной задачи разобьем на отрезков ,,;. Вычислим значения функции () в очках разбиения и найдем. Далее сравним полученное значениес величиной, чтобы не выйти за границы отрезка, на котором ищется минимум функции. Если выполняется условие, то переходим к следующему шагу поиска минимума функции. Как только это условие перестанет выполняться, возьмем в качестве последней проверяемой точки.После этого выберем в качестве приближений для точного значения точки минимума и точного значения минимума функциизначенияи, где значениевыбирается соответствующим номеру шага, на котором найдено приближенное минимальное значение точки минимума[2].
Заметим, что метод (1) выгодно отличается простотой реализации и не требует большой машинной памяти. Недостатком метода (1), как и метода ломаных, является необходимость априорного знания константы из условия Липшица.
Метод последовательного перебора, аналогичный методу (2), можно предложить и для некоторых других классов функций. Остановимся на классе функций, дважды .дифференцируемых на отрезке, у которых , где- некоторая фиксированная константа. Обозначим этот класс функций через. Заметим, что если, то, и следовательно, монотонно убывает на . Это значит, что тогда функция достигает своей нижней грани при или . Таким образом, задача минимизации функций из класса в случае решается просто. Поэтому имеет смысл рассматривать класс при .
Тогда для решения задачи минимизации первого типа на классе функций можно предложить следующий метод последовательного перебора
(2)
где, ,, а число определяется условием [2].
Теорема2.2.
Применяя метод (2.2), задачу минимизации первого типа для любой функции можно решить с заданной точностью , т. е.
. (2.4)
В худшем случае (например, если ) может оказаться, что, , и тогда метод (2.3) переходит в метод равномерного перебора с шагом . Если же при некоторых (например, для ), то методом (3) удается получить неравенство (4), вообще говоря, при меньшем, чем методом равномерного перебора. Недостатком метода (3) является требование знания константы.