Лабораторная работа: Лабораторная работа 1. Методы минимизации функций одной переменной.

Постановка задачи: Требуется найти безусловный минимум функции одной переменной , т.е. такую точку , что . Значение точки минимума требуется вычислить приближенно с заданной точностью .

Предполагается, что для функции известно, что точка минимума , , причем на заданном интервале функция является унимодальной.

Пусть на предварительно выбранном интервале неопределенности целевая функция является выпуклой дифференцируемой функцией. Тогда необходимым и достаточным условием глобального минимума является равенство нулю первой производной функции:

Задания

1. Написать в среде MATLAB функции, реализующие метод паребора, метод поразрядного поиска, метод дихотомии, метод золотого сечения, метод парабол, метод средней точки, метод хорд и метод Ньютона.

2. Выбрать для выполнения лабораторной работы тестовую функцию, номер которой соответствует номеру Вашего компьютера. Например, для компьютера №3 это будет функция 3), для компьютера №13 – функция 4): 13-9=4; для компьютера №23 это будет функция 5): 23-9 2=5.

1)

2)

3)

4)

5)

6)

7)

8)

9)

3. Для выбранной функции (построить ее график!) и для каждого рассмотренного выше метода изучить зависимость скорости работы (числа вычислений функции или производной ) от заданного значения точности . Провести сравнение методов друг с другом. Объяснить полученные результаты.

4. С помощью метода Ньютона, используя аналитические производные и их численные аппроксимации решить задачу минимизации функции

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

Решить ту же задачу с теми же начальными приближениями с помощью модификаций метода Ньютона (метода Марквардта и метода Ньютона-Рафсона). Объяснить полученные результаты.

5. Составить программу нахождения глобального минимума многомодальных функций методом перебора и методом ломаных. Проверить ее работоспособность на примере следующих функций (построить их графики!):

Сделать выводы о сравнительных достоинствах и недостатках метода перебора и метода ломаных.

6. Сдать лабораторную работу преподавателю, ответив предварительно контрольные вопросы.

Вопросы и задания для самоконтроля

1. Пусть − дифференцируемая унимодальная на отрезке функция, причем . Оценить точность при определении минимального значения методом перебора в результате вычислений .

2. Может ли оценка для точности определения методом перебора нарушаться для функций, не являющихся унимодальными? Ответ пояснить рисунком.

3. Какие прямые методы называются методами пассивного поиска? Последовательного поиска?

4. Повысится ли эффективность метода поразрядного поиска, если шаг поиска последовательно уменьшать не в четыре, а в какое-либо другое число раз?

5. В чем состоит идея метода исключения отрезков?

6. Может ли применение методов исключения отрезков привести к неверному определению , если функция не унимодальна? Ответ пояснить рисунком.

7. Зависит ли точность определения которую гарантируют методы дихотомии и золотого сечения в результате вычислений , от конкретной функции ?

8. Требуется найти точку минимума унимодальной функции на отрезке длины 1 с точностью . Имеется возможность измерить не более 10 значений . Какой из прямых методов минимизации можно использовать для этого?

9. Доказать, что погрешность определения точки минимума функции методом перебора не превосходит величины .

10. Доказать, что в методе дихотомии число итераций, необходимое для определения точки минимума с точностью , определяется формулой .

11. Доказать, что число итераций, необходимое для достижения заданной точности на отрезке в методе золотого сечения определяется формулой .

12. Сравнить необходимые количества вычисленных значений и функции при поиске ее точки минимума на отрезке длины 1 с точностью 10^-5 методом деления отрезка пополам и методом перебора.

13. Зависит ли точность определения которая получается методом парабол в результате вычислений функции , от конкретной функции ?

14. Указать класс функций, для точного определения точек минимума которых достаточно одной итерации метода парабол.

15. В окрестности точки минимума график близок к симметричному относительно вертикальной оси, проходящей через точку , а график заметно асимметричен. Для какой из этих функций следует ожидать более высокой скорости сходимости, применяя метод парабол?

16. Пусть − выпуклая дифференцируемая функция и . Можно ли указать погрешности определения точки минимума и минимального значения по формулам , ? Ответ пояснить рисунком.

17. Является ли условие достаточным для того, чтобы число было точкой минимума унимодальной, но не выпуклой функции ? Ответ сопроводить примером.

18. Указать класс функций, для которых точное определение точки минимума гарантировано в результате всего одной итерации метода Ньютона.

19. Сформулировать достаточные условия сходимости метода Ньютона.

20. Сформулировать достаточные условия монотонной сходимости метода Ньютона. Всегда ли в этом случае скорость сходимости будет квадратичной?

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

22. Минимизировать функцию с помощью методов Ньютона и золотого сечения. Сравнить скорость сходимости методов.

23. Сформулировать оценку погрешности определения минимума многомодальной функции методом перебора.

24. Увеличение используемого значения константы Липшица при реализации метода ломаных приводит к замедлению сходимости метода. Объяснить этот факт с помощью геометрической иллюстрации.

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