Метод с обратным переменным шагом

В методе при произвольно заданном шаге h от левой границы интервала поиска выполняется движение с расчетом значения функции на каждом шаге до тех пор, пока шаги удачные, т.е. функция уменьшается. В случае неудачного шага выполняется движение в обратном направлении с уменьшенным шагом поиска, пока шаги удачные. Если шаг оказывается снова неудачным, его опять уменьшают. Минимум будет достигнут, когда шаг поиска станет меньше предварительно заданной точности по аргументу.

Графическая интерпретация метода с обратным переменным шагом (рис.1.4.11)

Рис.1.4.11. Метод с обратным переменным шагом

Метод поиска с использованием чисел Фибоначчи

 

Последовательность чисел Фибоначчи,

определяемая

реккурентным соотношением:

может быть использована для организации поиска экстремума функции одной переменной.

Абсолютная погрешность, возникающая

при поиске этим методом, не превышает величины:

Fs - s-е число в последовательности чисел Фибоначчи.

Таблица этой последовательности до s = 12 приведена ниже:

S	1	2	3	4	5	6	7	8	9	10	11	12
FS	1	2	3	5	8	13	21	34	55	89	144	233

 

При выполнении s = 21 вычислений

 точность определения экстремума

составляет

т.е. оказывается более высокой, чем в методе золотого сечения.

Порядок поиска экстремума с использованием чисел Фибоначчи (рис.1.4.12)

Рис.1.4.12. Поиск экстремума с использованием чисел Фибоначчи

По заданной точности ∆ поиска

рассчитывается вспомогательное число:

 

Находится число Фибоначчи Fs, такое, что:

 

Определяется минимальный шаг поиска:

Рассчитывается значение R в точке,

определяемой соотношением:

Рассчитывается значение R в точке,

определяемой соотношением:

Если шаг оказался удачным, т.е.:

то рассчитывается значение R в точке,

определяемой соотношением:

Если шаг оказался неудачным, т.е.:

то x3 определяется:

 

Процедура продолжается последовательно до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности.

 

Прямые методы поиска экстремума функции многих переменных, не использующие производные (методы нулевого порядка)

Метод сканирования

Исследуется целевая функция вдоль одного выбранного направления (вдоль одной из координатных осей) с шагом h1. В каждой точке вычисляется и запоминается значение целевой функции. После того как весь диапазон изменения этой переменной исследован и для него найдено минимальное (максимальное) значений целевой функции, изменяется значение другой переменной на величину шага h2 и опять исследуется диапазон первой переменной, в котором снова определяется искомый экстремум, и т.д. После нахождения всех экстремумов находится искомый глобальный экстремум.

Графическое (рис.1.4.13) представление поиска экстремума для случая двух переменных:

Рис.1.4.13. Поиск экстремума для случая двух переменных

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

Если имеются ограничения, то точки, которые не удовлетворяют уравнениям (или неравенствам) ограничений исключаются, и в них не вычисляются значения критерия R. Однако каждую точку требуется проверять относительно ограничения. Если переменных много, то такого рода проверка также требует длительного времени.

Прием проверки ограничений

типа равенств может быть

представлен в виде:

при этом поиск ведется по n-1 переменной, а значение xj рассчитывается из этого соотношения. Разумеется, что xj должно проверяться на допустимый диапазон его изменения.

Если относительная точность поиска равна e по каждой из переменных, то количество вычислений целевой функции,

необходимых для поиска экстремума, составит

n – число переменных

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