Мінімізація функції багатьох змінних Наближені чисельні методи Метод Монте-Карло

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Мінімізація функції багатьох змінних. Наближені чисельні методи. Метод Монте-Карло

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)

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Реферат
36.8кб. | скачати


Схожі роботи:
Метод Монте Карло
Метод Монте-Карло
Метод Монте-Карло і його застосування
Метод Монте Карло та його застосування
Мінімум функції багатьох змінних
Функції багатьох змінних Означення границя та неперервність похідні диференціали
Пошук максимуму однієї функції багатьох змінних методом покоординатного спуску і з допомогою методу
Функція багатьох змінних
Обчислення інтегралів методом Монте Карло
© Усі права захищені
написати до нас