Практика 4: Метод Хукка-Дживса

Для начала необходимо задать стартовую точку $\overline{x}_{1}$ = ($x_1$; $x_2$), начальный шаг ($h$ иногда $p$), точность ($T$), параметр для шага по образцу ($\lambda$ иногда $a$ ). Суть алгоритма заключается в последовательном использовании двух шагов (поисков): иссследующего шага и шага по образцу. Подробнее об этом в теории.

Пример решения задачи

Дано:

Функция - $f(x) = x^2+y^2$

Начальная (базовая) точка - [$x_1$; $x_2$] = [2; 3]

Шаг - $p = 1$

Точность - $T = 0,5$

1. Исследуюший шаг. Исследуем соседние с начальной точкой точки:

[$x_1 + p$; $x_2$] = [3, 3] $f(x) = 3^2 + 3^2 = 18$

[$x_1 - p$; $x_2$] = [1, 3] $f(x) = 1^2 + 3^2 = 10$

Выбираем наименьшее - это 10. Значит $x_1$ = 1. Далее проверяем соседей по $x_2$.

[$x_1$; $x_2 + p$] = [1, 4] $f(x) = 17$

[$x_1$; $x_2 + p$] = [1, 2] $f(x) = 5$

Наименьшее 5. Теперь [1, 2] - новая базовая точка.

2. Шаг по образцу.

Используем формулу : ${\displaystyle {\overline {x}}_{3}={\overline {x}}_{1}+\lambda ({\overline {x}}_{2}-{\overline {x}}_{1})}$, где $\lambda$ (обычно) = 2.

$x_3$ = $[2, 3] + 2 ([1, 2] - [2, 3]) = [0, 1]$ $f(x_3) = 1$

Далее действия повторяются.

Затем снова исследуем окрестность точки (исследующий шаг). На этот раз $x_3$ = [0, 1]:

     [0+p, 1] = [1, 1] f(x) = 2

     [0-p, 1] = [-1, 1] f(x) = 2

так как тут равные значения, рассмотрим окрестности дальше

     [0, 1+p] = [0, 2] f(x) = 4

     [0, 1-p] = [0, 0] f(x) = 0

Наименьшее значение 0. Точка [0, 0] становится новой базовой точкой.

Шаг по образцу

     x_3 = [1, 2] + 2 ([0, 0] - [1, 2]) = [-1, -2]

     f(x) = 5 

(Самое время подсчитать сколько раз ты считал значение функции, потому что в данном примере это 10ый подсчет и уже можно остановиться!)

Исследующий шаг

     [-1+p, -2] = [0, -2]  f(x) = 4

     [-1-p, -2] = [-2, -2]  f(x) = 8

     [0, -2+p] = [0, -1]  f(x) = 1

     [0, -2-p] = [0, -3] f(x) = 9

Не удалось найти точку лучшую, чем базовая ([0, 0]). Уменьшаем шаг на 2 ($p = p/2$).

Исследуем

     [0+p, 0] = [0,5, 0] f(x) = 0,25

     [0-p, 0] = [-0,5, 0] f(x) = 0,25

     [0, 0+p] = [0, 0,5] f(x) = 0,25

     [0, 0-p] = [0, -0,5] f(x) = 0,25

Нет лучшего решения, чем точка [0, 0], поэтому это ответ