Минимизация функции многих переменных Приближённые численные методы Метод Монте-Карло (стр. 2 из 2)

(20)

Пример 6: Найти минимум функции

Решение: возьмём начальную точку

. Из (14) имеем:

(21)

(22)

Составляем итерационную формулу (16):

(23)

Имеем:

(24)

(25)

(26)

Ясно, что если h выбрать так, чтобы

, т.е.

, то итерация (26) сходится и

(27)

Иначе говоря:

(28)

Пример 7: Найти точку минимума функции

Решение: возьмём начальное приближение

, ясно, что

. Поэтому, из (16) получаем итерационную формулу:

(29)

Понятно, что

(30)

поэтому:

(31)

(32)

Далее, если

, получаем, что

, т.е.:

(33)

Пример 8: Найти точки минимума функции

Решение: выбираем начальную точку (1,1). Составляем итерационную формулу:

(34)

Распишем подробнее:

(35)

(36)

Если перейти к пределу в (36), при

(37)

то получим точку минимума (1,-2).

(38)

3. Метод Монте-Карло.

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

В методе Монте-Карло зададим функцию

. Выбираем область поиска решения задачи:

(39)

а) Производим случайные броски, т.е. выбираем значения

, для каждой переменной

по формуле:

, где

(40)

б) Сравниваем значения функции:

(41)

если это неравенство выполняется, то

(42)

если (41) не выполняется, то

(43)

в) Процесс случайных бросков продолжается до достижения заданной точности

; число случайных бросков m удовлетворяет условию:

(44)

Где

(45)

(46)