ЛПР 10. Методы одномерной оптимизации
![]()
|
ЛАБОРАТОРНАЯ РАБОТА №10 По предмету «ЧИСЛЕННЫЕ МЕТОДЫ» ТЕМА: «Методы одномерной оптимизации» ![]() ЛАБОРАТОРНАЯ РАБОТА №10 ТЕМА: «Методы одномерной оптимизации» 10.1 Постановка задачи Целью данной работы является закрепление понятия одномерной оптимизации, изучение методов одномерной оптимизации, а именно, алгоритм Свенна нахождения отрезка, содержащего точку максимума, метод деления отрезка пополам, метод золотого сечения и т.д.. Методы одномерной оптимизации Пусть функция ![]() ![]() ![]() Решением или точкой максимума (минимума) этой задачи назовем такую точку ![]() ![]() ![]() ![]() ![]() Методы одномерной оптимизации условно подразделяются на три группы. К первой группе относятся методы, основанные лишь на вычислении значений самой функции ![]() Вторую группу составляют методы, использующие значения как самой функции, так и ее первой производной (методы первого порядка). И, наконец, к третьей группе относятся методы, использующие значения функции, ее первой и второй производной (методы второго порядка). В дальнейшем будем считать, что максимизируемая функция является унимодальной. Определение. Функция ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Другими словами, унимодальная функция монотонно возрастает слева от точки максимума и монотонно убывает справа от нее. Отметим, что предположение об унимодальности функции в окрестности точки ![]() Поиск отрезка, содержащего точку максимума. Алгоритм Свенна Исходные данные. ![]() ![]() ![]() Шаг 1. Вычислить ![]() ![]() ![]() ![]() Шаг 2. Если ![]() ![]() Шаг 3. Если ![]() ![]() ![]() шагу 4, в противном случае ![]() ![]() ![]() Шаг 4. ![]() ![]() Шаг 5. Если ![]() ![]() Шаг 6. Если ![]() ![]() ![]() ![]() ![]() Заметим, что случай ![]() ![]() Уменьшение длины отрезка, содержащего точку максимума, достигается путем последовательного исключения частей этого отрезка. Величина интервала, исключаемого на каждом шаге, зависит от расположения двух пробных точек внутри отрезка. Поскольку координата точки максимума априори неизвестна, целесообразно размещать пробные точки таким образом, чтобы обеспечивать уменьшение длины отрезка в одном и том же отношении. Дихотомический поиск (метод деления отрезка пополам) Пробные точки у, z на каждом шаге этого метода выбираются следующим образом: ![]() ![]() где ![]() ![]() При малых ![]() Алгоритм Исходные данные. Отрезок ![]() ![]() ![]() ![]() Шаг 1. ![]() ![]() ![]() Шаг 2. Если ![]() ![]() Шаг 3. ![]() ![]() ![]() ![]() Шаг 4. Если ![]() ![]() ![]() ![]() ![]() Шаг 5. ![]() На каждой итерации дихотомического поиска производятся два вычисления значения функции и после ![]() ![]() ![]() Метод золотого сечения Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Легко доказать, что золотое сечение отрезка ![]() ![]() ![]() ![]() ![]() Отсюда ![]() ![]() Нетрудно также проверить, что точка ![]() ![]() ![]() ![]() Исходные данные: ![]() ![]() Шаг 1. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Шаг 2. Если ![]() Шаг 3. ![]() ![]() ![]() ![]() ![]() ![]() Шаг 4. ![]() ![]() ![]() ![]() ![]() ![]() Шаг 5. Если ![]() ![]() Шаг 6. ![]() Как было отмечено выше, на каждой итерации метода золотого сечения производится лишь одно вычисление значения функции. При этом длина полученного в результате одной итерации отрезка составит ![]() ![]() Если сравнить методы дихотомического поиска и золотого сечения, используя в качестве критерия эффективности ![]() ![]() ![]() ![]() ![]() ![]() т.е. метод золотого сечения оказывается более эффективным. Метод средней точки Для отыскания корня уравнения ![]() которому соответствует точка максимума унимодальной и дифференцируемой на заданном отрезке функции ![]() ![]() Если в точке ![]() ![]() то с учетом предположения об унимодальности можно утверждать, что точка максимума не может находиться левее точки ![]() ![]() ![]() ![]() ![]() Алгоритм Исходные данные. Точки ![]() ![]() ![]() ![]() ![]() Шаг 1. ![]() ![]() Шаг 2. Если ![]() ![]() Шаг 3. Если ![]() ![]() ![]() Метод хорд (секущих) При реализации этого метода учитывается не только знак производной, но и ее значение. Метод заключается в решении уравнения ![]() методом хорд и носит поэтому те же название. Предполагаем, как и в предыдущем разделе, что знаки производной унимодальной функции ![]() ![]() ![]() ![]() ![]() Тогда приближение ![]() ![]()
Алгоритм метода хорд тот же, что и алгоритм метода средней точки за исключением того, что координата точки ![]() Метод Ньютона-Рафсона Предполагаем, что унимодальная функция ![]() ![]()
Алгоритм Исходные данные, ![]() ![]() Шаг 1. ![]() Шаг 2. ![]() Шаг 3. Если ![]() ![]() Шаг 4. ![]() Последовательность (14) сходится к стационарной точке лишь при выполнении определенных условий, накладываемых на вид функции и выбор начальной точки (теорема о сходимости метода касательных). |