Читайте также:
|
|
Стратегия метода Марквардта состоит в построении последовательности точек , таких, что
Точки последовательности вычисляются по правилу
где - задается пользователем, Е – единичная матрица,
- последовательность положительных чисел, таких, что матрица
положительно определена. Как правило, число
назначается как минимум на порядок больше, чем самый большой элемент матрицы
, а в ряде стандартных программ полагается
. Если
, то
. В противном случае
. Легко видеть, что алгоритм Марквардта в зависимости от величины
на каждом шаге по своим свойствам либо приближается к алгоритму Ньютона, либо к алгоритму градиентного спуска.
Построение последовательности заканчивается, когда либо
, либо число итераций
, где
- малое положительное число, а М – предельное число итераций.
Алгоритм:
Шаг 1. Задать М – предельное число итераций. Найти градиент
и матрицу Гессе
.
Шаг 2. Положить k = 0, .
Шаг 3. Вычислить .
Шаг 4. Проверить выполнение условия :
а) если неравенство выполнено, то расчет окончен и ;
б) в противном случае перейти к шагу 5.
Шаг 5. Проверить выполнение условия :
а) если неравенство выполнено, то расчет окончен и ;
б) если нет, перейти к шагу 6.
Шаг 6. Вычислить матрицу .
Шаг 7. Вычислить матрицу .
Шаг 8. Вычислить .
Шаг 9. Вычислить .
Шаг 10. Вычислить .
Шаг 11. Проверить выполнение условия :
а) если неравенство выполняется, то перейти к шагу 12;
б) если нет, перейти к шагу 13.
Шаг 12. Положить и перейти к шагу 3.
Шаг 13. Положить и перейти к шагу 7.
Пример:
Найти локальный минимум функции
Решение:
1. Зададим
, M:
,
, M =10.
Найдем градиент функции в произвольной точке и матрицу Гессе
.
2. Положим k = 0, .
30. Вычислим :
.
40. Проверим условие :
.
50. Проверим условие :
.
60. Вычислим :
.
70. Вычислим :
.
80. Вычислим :
.
90. Вычислим .
100. Вычислим .
110. Проверим выполнение условия .
120. Полагаем k = 1, и переходим к шагу 3.
31. Вычислим :
.
41. Проверим условие :
.
51. Проверим условие :
.
61. Вычислим :
.
71. Вычислим :
.
81. Вычислим :
.
91. Вычислим .
101. Вычислим .
111. Проверим выполнение условия .
121. Полагаем k = 2, и переходим к шагу 3.
32. Вычислим :
.
42. Проверим условие :
.
52. Проверим условие :
.
62. Вычислим :
.
72. Вычислим :
.
82. Вычислим :
.
92. Вычислим .
102. Вычислим .
112. Проверим выполнение условия .
122. Полагаем k = 3, и переходим к шагу 3.
33. Вычислим :
.
43. Проверим условие :
.
53. Проверим условие :
.
63. Вычислим :
.
73. Вычислим :
.
83. Вычислим :
.
93. Вычислим .
103. Вычислим .
113. Проверим выполнение условия .
123. Полагаем k = 4, и переходим к шагу 3.
34. Вычислим :
.
44. Проверим условие :
.
54. Проверим условие :
.
64. Вычислим :
.
74. Вычислим :
.
84. Вычислим :
.
94. Вычислим .
104. Вычислим .
114. Проверим выполнение условия .
124. Полагаем k = 5, и переходим к шагу 3.
35. Вычислим :
.
45. Проверим условие :
.
55. Проверим условие :
.
65. Вычислим :
.
75. Вычислим :
.
85. Вычислим :
.
95. Вычислим .
105. Вычислим .
115. Проверим выполнение условия .
125. Полагаем k = 6, и переходим к шагу 3.
36. Вычислим :
.
46. Проверим условие :
.
Расчет окончен. Найдена точка .
Проанализируем полученную точку:
Функция является строго выпуклой, т.к. ее матрица вторых производных
в силу того, что
. Точка
является найденным приближением точки минимума
.
Решение задачи представлено на рисунке 5.4.
Рисунок 5.4.
Дата добавления: 2015-07-20; просмотров: 233 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Метод Ньютона - Рафсона | | | Пример отчета по лабораторной работе |