Прямі методи безумовної мінімізації функцій

курсовая работа

3.3 Метод правильного симплексу

Правильним симплексом в просторі En називається множина з n + 1 рівновіддалених одна від одної точок (вершин симплексу). Відрізок, що зєднує дві вершини, називається ребром симплексу.

У просторі E2 правильним симплексом є сукупність вершин рівностороннього трикутника, в E3 - правильного тетраедра.

Якщо х0 - одна з вершин правильного симплексу в En то координати інших n вершин х1,. ., хn можна знайти, наприклад, за формулами:

(6),

де d1 , d2 , a - довжина ребра, j=1, 2, …, n (тут j - це номер виміру простору En). Вершину х0 симплексу, побудованого за формулами (6), будемо називати бaзовою. В алгоритмі симплексного методу використовується наступна важлива властивість правильного симплексу. За відомим симплексом можна побудувати новий симплекс відображенням якої-небудь вершини, наприклад, хk симметрично щодо центру ваги хc інших вершин симплексу. Нова і стара хk вершини повязані співвідношенням:

, де xc.

В результаті отримується новий правильний симплекс з тим же ребром і вершинами =2xc - хk, хi, i= 0, ..., n, i k. Таким чином, відбувається переміщення симплексу в просторі Еn. На рисунку 9 представлена ??ілюстрація цієї властивості симплексу в просторі Е2.

Рисунок 9 - Побудова нового симплексу в E2 відображенням точки х: a - початковий симплекс х0, х1, х2; б - новий симплекс х0, х1, ; центр відображення - точкa xc = (х0+ х1) /2 .

Пошук точки мінімуму функції f(x) за допомогою правильних симплексів проводять у наступний спосіб. На кожній ітерації порівнюються значення f(х) у вершинах симплексу. Потім проводять описану вище процедуру відображення для тієї вершини, в якій f(х) приймає найбільше значення. Якщо у відображеній вершині виходить менше значення функції, то переходять до нового симплексу. В протилежному випадку скорочують довжину ребра симплексу, наприклад, удвічі і будують новий симплекс з цим ребром. В якості базової вибирають ту вершину х0 старого симплексу, в якій функція приймає мінімальне значення. Пошук точки мінімуму f(x) закінчують, коли або ребро симплексу, або різниця між значеннями функції в вершинах симплексу стають досить малими. Опишемо один з варіантів алгоритму цього методу для випадку функції двох змінних.

Крок 0. Вибрати параметр точності , базову точку х0 = , ребро .

Крок 1. Побудувати початковий симплекс за формулами:

Крок 2. Обчислити значення f(х) в вершинах симплексу х0, ..., x2. Упорядкувати вершини симплексу х0,..., х2 так, щоб f (х0) f (х1) f (х2).

Крок 3. Знайти середнє значення функції:

.

Перевірити умову з урахуванням того, що:

Якщо ця умова виконується, то обчислення припинити, вважаючи х* х0, f * f(x0). В протилежному випадку перейти до кроку 4.

Крок 4. Знайти

і виконати відображення вершини х2. Так як точка xc має координати , то відображена вершина матиме координати:

.

Якщо f() < f(x2), то покласти х2 = (тобто побудувати новий симплекс з вершинами х0, х1, ) і перейти до кроку 2, інакше - перейти до кроку 5.

Крок 5. Перейти до нового правильного симплексу з удвічі меншим ребром, вважаючи базовою вершиною х0. Тобто покласти а=а / 2 і перейти до кроку 1.

Геометрична ілюстрація роботи алгоритму в просторі показана на рисунку 10, де точки х0, х1, х2 - вершини початкового симплексу, а пунктиром вказані процедури відображення.

Рисунок 10 - Пошук точки мінімуму функції за допомогою правильних симплексів в просторі

Делись добром ;)