Рефетека.ру / Математика

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

1. Минимизация функции многих переменных. Аналитические методы.


Теорема Вейерштрасса: пусть Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло- множество функций непрерывных на замкнутом ограниченном множестве Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Если Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло, тогда Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло достигает своих наибольшего и наименьшего значений.

Определение: точки максимума и минимума называются точками экстремума функции. Теорема Ферма: (необходимое условие существования экстремума). Пусть функция Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло- определена в окрестности точки Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Если Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло- является точкой экстремума функции Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло, и в этой точке существуют частные производные, тогда


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


Обобщение: если Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло- точка экстремума, то в этой точке либо выполняется формула (1), либо производная не определена. Определение: точки, в которых выполняется условие (1), называются точками экстремума функции Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Сейчас изложим достаточные условия существования экстремумов функции многих переменных. Для этого вспомним некоторые сведения из теории квадратичных форм.

Определение: квадратичная форма


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

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


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

Пример:


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

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

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


Определение: квадратичную форму, которая принимает как положительные, так и отрицательные значения называют неопределённой формой.

Пример:


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


Теперь, мы уже можем сформулировать достаточные условия существования экстремумов для функции многих переменных.

Теорема: пусть Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-КарлоМинимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло, и пусть Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло является критической точкой функции Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Если квадратичная форма


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


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

На вопрос: когда квадратичная форма является положительно (или отрицательно) определённой, отвечает критерий Сильвестра:

Для того, чтобы квадратичные формы (2),(3) были положительно-определёнными, необходимо и достаточно, чтобы


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


Для того, чтобы квадратичная форма (2), (3) была отрицательно-определённой, необходимо и достаточно, чтобы


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

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


Как видим, для нахождения точек экстремума нам нужно решать систему, в общем, нелинейных уравнений (1), а для выяснения характера точки экстремума нужно на основе критерия Сильвестра проверять условия (5), (6) и (7) для дифференциальной квадратичной формы (4) в точке экстремума. Проиллюстрируем этот метод на примере 5: Функция двух переменных:


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


Решение: найдём критические точки:

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


откуда получаем критические точки: А(0;0); В(3;2). Исследуем эти точки. Для этого нам нужно выяснить, в каждой из этих точек, к какому виду принадлежит квадратичная форма:


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

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

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

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


В точке A(0;0) имеем:


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


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

Сильвестра не дают ответа на вопрос о наличии экстремума в этой точке.

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

В точке B(3;2) имеем:

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


получаем матрицу квадратичной формы:


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

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


т.е. по критерию Сильвестра B(3;2) является точкой максимума: Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло


2. Метод градиентного спуска.


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

Пусть, нам нужно найти Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Рассмотрим некоторую точку Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-КарлоМинимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло и вычислим в этой точке градиент функции Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло:


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


где Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло - ортонормированный базис в пространстве Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло. Если Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло, то полагаем:

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


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


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


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


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


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

………………………..

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

Здесь m – число итераций. Процесс итерации останавливается, когда достигается требуемая предельная погрешность, т.е. когда выполнены условия остановки итерации:


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

Рефетека ру refoteka@gmail.com