- •Киров 2006
- •Рецензент: к.Т.Н., доцент каф. Эвм Матвеева л.И.
- •1 Оформление лабораторной работы
- •1.1 Цель работы
- •1.2 Формирование отчета
- •2 Общие принципы методов поиска безусловного экстремума
- •3 Методы нулевого порядка
- •3.1 Метод конфигураций (метод Хука - Дживса)
- •3.2 Метод деформируемого многогранника
- •3.3 Метод вращающихся координат (метод Розенброка)
- •3.4 Метод сопряженных направлений (метод Пауэлла)
- •4 Методы первого порядка
- •4.1 Метод градиентного спуска с постоянным шагом
- •4.2 Метод наискорейшего градиентного спуска (Метод Коши)
- •4.3 Метод Гаусса - Зейделя
- •4.4 Метод сопряженных градиентов (Флетчера – Ривса)
- •5 Методы второго порядка
- •5.1 Метод Ньютона
- •5.2 Метод Ньютона - Рафсона
- •5.3 Метод Марквардта
- •6 Пример отчета по лабораторной работе
- •7 Блок вариантов заданий
- •8 Библиографический список
3.3 Метод вращающихся координат (метод Розенброка)
Суть метода Розенброка [Rosenbrock H.H.] состоит в следующем. Задается начальная точка. Из нее осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль линейно независимых и ортогональных направлений. В случае удачного шага в исследуемом направлении его значение на следующей итерации увеличивается с помощью коэффициента растяжения, а в случае неудачи уменьшается за счет умножения на коэффициент сжатия (при этом направление поиска изменяется на противоположное). Поиск в системе текущих направлений проводится до тех пор, пока все возможности уменьшения функции не будут исчерпаны. Если по каждому направлению поиска имеет место неудача, строится новое множество линейно независимых и ортогональных направлений и циклический поиск по отдельным направлениям продолжается. Новые направления поворачиваются по отношению к предыдущим так, что они оказываются вытянутыми вдоль оврага (рис. 3.7).
Рисунок 3.7
Алгоритм:
Шаг 1. Задать начальную точку число для остановки алгоритма, коэффициенты растяжения и сжатия , в качестве начальных линейно независимых и ортогональных направлений выбрать координатные направления:
начальную длину шага вдоль каждого из направлений поиска ; - максимальное число неудачных серий шагов по всем направлениям на одной итерации. Положить для всех .
Шаг 2. Сделать шаг по -тому направлению:
если , шаг считается удачным. В этом случае следует положить , и перейти к шагу 3;
если , шаг считается удачным. В этом случае следует положить , и перейти к шагу 3;
Шаг 3. Проверить выполнение условий:
если , то положить и перейти к шагу 2 (сделать шаги по оставшимся направлениям);
если , проверить успешность поиска по текущим ортогональным направлениям:
Если , то есть хотя бы один спуск по направлению на шаге 2 был успешным, положить и перейти к шагу 2;
Если , то есть каждый из текущих шагов был неудачным, оценить успешность поиска на текущей итерации:
-- если , то есть на -той итерации хотя бы один шаг удачный, перейти к шагу 4;
-- если , то есть не было ни одного удачного шага на -той итерации, процесс поиска приостановить. Если число последовательно неудачных серий шагов по всем направлениям на текущей итерации не превышает , проверить условие окончания, а иначе перейти к шагу 4. Проверяются величины , использованные во время последней серии шагов. Если для всех , то
найдено приближенное решение задачи: . Если хотя бы для одного , то положить и перейти к шагу 2.
Шаг 4. Положить и проверить условие окончания
если , то поиск завершить: ;
если , вычислить длины шагов по каждому направлению поиска на -той итерации из соотношения . Далее построить новый набор линейно независимых и взаимно ортогональных направлений поиска с помощью процедуры Грама-Шмидта:
.
После нахождения новых направлений следует положить: для всех , , и перейти к шагу 2.
Замечание: Розенброк рекомендовал следующие коэффициенты растяжения и сжатия: , .
Пример: Методом вращающихся координат (методом Розенброка) найти локальный минимум функции
Решение:
1. Зададим начальную точку , , , . Пусть .
20. Т.к. , шаг неудачен: .
30. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.
21. Т.к. то шаг неудачен: .
31. Имеем i = 2 = n, , выполнена одна неудачная серия шагов: i = 1 < N = 3. На этой серии поэтому положим и перейдем к шагу 2.
22. Т.к. , шаг удачен: .
32. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
24. Т.к. , шаг удачен: .
34. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
25. Т.к. то шаг удачен:
.
35. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
26. Т.к. , шаг удачен: .
36. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
27. Т.к. то шаг удачен:
.
37. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
28. Т.к. , шаг неудачен: .
38. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
29. Т.к. то шаг неудачен:
.
39. Имеем i = 2 = n, . Т.к. выполняется условие , переходим к шагу 4.
40. Положим .
Т.к. , то вычислим из соотношения . Отсюда .
Построим новый набор направлений поиска:
Положим и перейдем к шагу 2.
210.Т.к. , шаг удачен: .
310. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
211. Т.к. то шаг удачен:
.
311. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
212. Т.к. , шаг неудачен: .
312. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
213. Т.к. то шаг удачен:
.
313. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
214. Т.к. , шаг неудачен: .
314. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
215. Т.к. то шаг неудачен:
.
315. Имеем i = 2 = n, . Т.к. выполняется условие , переходим к шагу 4.
41. Положим .
Т.к. , то вычислим из соотношения . Отсюда .
Построим новый набор направлений поиска:
Положим и перейдем к шагу 2.
216. Т.к. , шаг неудачен: .
316. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
217. Т.к. то шаг неудачен:
.
317. Имеем i = 2 = n, , выполнена одна неудачная серия шагов: i = 1 < N = 3. На этой серии поэтому положим и перейдем к шагу 2.
218.Т.к. , шаг удачен: .
318. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
219. Т.к. то шаг удачен:
.
319. Имеем i = 2 = n, . Положим и перейдем к шагу 2.
220. Т.к. , шаг неудачен: .
320. Имеем i = 1 < 2 = n, поэтому i = i + 1 = 2 и переходим к шагу 2.
221. Т.к. то шаг неудачен:
.
321. Имеем i = 2 = n, . Т.к. выполняется условие , переходим к шагу 4.
42. Положим .
Т.к. , то процесс поиска завершается: