Реферат: Минимизация функции многих переменных Приближённые численные методы Метод Монте-Карло
Название: Минимизация функции многих переменных Приближённые численные методы Метод Монте-Карло Раздел: Рефераты по математике Тип: реферат |
Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло 1. Минимизация функции многих переменных. Аналитические методы. Теорема Вейерштрасса: пусть Определение: точки максимума и минимума называются точками экстремума функции. Теорема Ферма: (необходимое условие существования экстремума). Пусть функция
Обобщение: если Определение: квадратичная форма
называется положительно (отрицательно) определённой, если Пример: 1) 2) 3) Определение: квадратичную форму, которая принимает как положительные, так и отрицательные значения называют неопределённой формой. Пример: 4) Теперь, мы уже можем сформулировать достаточные условия существования экстремумов для функции многих переменных. Теорема: пусть
(т.е. второй дифференциал функции На вопрос: когда квадратичная форма является положительно (или отрицательно) определённой, отвечает критерий Сильвестра: Для того, чтобы квадратичные формы (2),(3) были положительно-определёнными, необходимо и достаточно, чтобы
Для того, чтобы квадратичная форма (2), (3) была отрицательно-определённой, необходимо и достаточно, чтобы
Как видим, для нахождения точек экстремума нам нужно решать систему, в общем, нелинейных уравнений (1), а для выяснения характера точки экстремума нужно на основе критерия Сильвестра проверять условия (5), (6) и (7) для дифференциальной квадратичной формы (4) в точке экстремума. Проиллюстрируем этот метод на примере 5: Функция двух переменных:
Решение: найдём критические точки:
откуда получаем критические точки: А(0;0); В(3;2). Исследуем эти точки. Для этого нам нужно выяснить, в каждой из этих точек, к какому виду принадлежит квадратичная форма:
В точке A(0;0) имеем:
так что Сильвестра не дают ответа на вопрос о наличии экстремума в этой точке. Для решения этого вопроса надо привлечь старшие производные и формы более высокого порядка, для которых соответствующей общей теории пока нет, поэтому нужно обращаться к численным исследованиям. В точке B(3;2) имеем:
получаем матрицу квадратичной формы:
т.е. по критерию Сильвестра B(3;2) является точкой максимума: 2. Метод градиентного спуска. Как мы видели из последнего численного примера, строгий аналитический метод не всегда приводит к цели (случай, когда Пусть, нам нужно найти
где
где
где
………………………..
Здесь m – число итераций. Процесс итерации останавливается, когда достигается требуемая предельная погрешность, т.е. когда выполнены условия остановки итерации:
Пример 6: Найти минимум функции Решение: возьмём начальную точку
Составляем итерационную формулу (16):
Имеем:
Ясно, что если h выбрать так, чтобы Иначе говоря:
Пример 7: Найти точку минимума функции Решение: возьмём начальное приближение
Понятно, что
поэтому:
Далее, если
Пример 8: Найти точки минимума функции Решение: выбираем начальную точку (1,1). Составляем итерационную формулу:
Распишем подробнее:
Если перейти к пределу в (36), при
то получим точку минимума (1,-2).
3. Метод Монте-Карло. Для минимизации функции многих переменных разработано множество численных методов, но большинство из них связано с подсчётом градиента функции, что со своей стороны может дать эффективные алгоритмы вычисления лишь, если удаётся аналитически подсчитать частные производные. Между тем, более универсальным методом минимизации функции многих переменных является метод перебора, при котором произвольным образом разбивается область определения функций на симплексы и в каждом узле симплекса вычисляется значение функции, причём происходит сравнение – перебор значений и на печать выводится точка минимума и значение функции в этой точке. В методе Монте-Карло зададим функцию
а) Производим случайные броски, т.е. выбираем значения
б) Сравниваем значения функции:
если это неравенство выполняется, то
если (41) не выполняется, то
в) Процесс случайных бросков продолжается до достижения заданной точности
Где
|