Бінарна алгебраїчна операція
Химия

Методи спуску — завантажити безкоштовно


Методи спуску - завантажити безкоштовно

Завантажити реферат: Методи спуску

Загальна схема.

Всі методи спуску розв’язання задачі безумовної мінімізації розрізняються або вибором напряму спуску, або способом руху вздовж спуску. Це дозволяє написати загальну схему методів спуску.
Вирішується завдання мінімізації функції j(x) по всьому просторі En. Методи спуску перебувають у наступній процедурі побудови послідовності {xk}. Як початкове наближення вибирається будь-яка точка x0IEn. Послідовні наближення x1, x2, … будуються за такою схемою:

  • у точці xk вибирають напрямок спуску — Sk;
  • знаходять (k+1) наближення за формулою xk+1=xk-pkSk.

Напрямок Sk вибирають таким чином, щоб забезпечити нерівність j(xk+1)Число pk визначає відстань від точки xk до точки x+1. Це число називається довжиною кроку чи просто кроком. Основне завдання при виборі величини bk — забезпечити виконання нерівності j(xk+1)спосіб подвоєння кроку.
Вибирають bk = bk-1. Якщо при цьому j(xk+1)

Метод градієнтного спуску.

Одним з найпоширеніших методів мінімізації, пов’язаних з обчисленням градієнта, є метод спуску за напрямом антиградієнта функції, що мінімізується. На користь такого вибору напряму спуску можна навести такі міркування. Оскільки антиградієнт, тобто j'(xk) у точці xk показує напрямок якнайшвидшого зменшення функції, то природним є зміститися з точки xk у цьому напрямі.
Метод спуску, у якому Sk=j'(xk), називається методом градієнтного спуску.
Величина bk в методі градієнтного спуску зазвичай обчислюється шляхом застосування одного з методів одновимірної мінімізації функції y(b)=j(xk-bj'(xk)), що не виключає застосування інших способів відшукання bk.
Якщо як bk вибирають точку одновимірного мінімуму функції y(b)=j(xk-bSk) релаксаційний процес називається методом якнайшвидшого спуску: xk+1=xk-bkj'(xk), bk=arg min {y(b)=j (xk-bSk) | b?0}.

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

Одним з найпростіших способів визначення напрямку спуску є вибір як Sk одного з координатних векторів ±e1, ±e2, …, ±en, внаслідок чого у xk на кожній ітерації змінюється лише один із компонентів.
Існують численні варіанти покоординатного спуску. Але в будь-якому з цих методів вибирають як -Sk або два напрямки, +ej, -ej, якому відповідає нерівність
[j’(xk), Sk] >0.
У разі якщо
Методи спуску - завантажити безкоштовно=0, вважають xk+1=xk і переходять до наступної ітерації.
Опишемо перший цикл методу, що складається із n ітерацій. У довільній точці x0 вибирають S0=±e і визначає величину b0 способом подвоєння так, щоб було j(x1)=j(x0-b0S0)

Практичне завдання

Насправді нам потрібно було знайти мінімум функції z(x)=x2+y2-xy-3y c точністю e, використовуючи описані вище методи.

Знаходження мінімуму моєї функції за допомогою методу покоординатного спуску.

Для знаходження мінімуму моєї функції за допомогою методу покоординатного спуску я використав програму, наведену нижче. Вхідними параметрами цієї програми є координати початкової точки (я взяв х=10, y=10), початковий крок х і y (я взяв Dх=0.5 і Dy=0.5), а так само точність (e=10-5; велику точність брати немає сенсу, оскільки під час виконання програми накопичується помилка і спотворює дані такий точності). Отже, взявши як початкові умови ці значення я отримав координати точки мінімуму:
х = 1,00000977
y= 1,99999931
z=-3,00000142
Для отримання результату програмою було виконано 24 ітерації.

Знаходження мінімуму за допомогою методу градієнтного спуску.

Програма, використана мною для виконання цього завдання, представлена ​​нижче.
Оскільки вхідні параметри цієї програми збігаються з вхідними параметрами задачі №1, то я взяв їх такі ж, що і для першого завдання, щоб порівнявши отримані результати та кількість ітерацій, необхідних для пошуку мінімуму, я зміг зробити якісь висновки про переваги і недоліки обох завдань із практики.
Отже, взявши ті самі початкові умови, я отримав наступні результати:
x = 1,00000234
y= 2,00000119
z=-3,00000094
Кількість ітерацій, яке знадобилося для знаходження точки мінімуму дорівнює 20. Видно, що кількість ітерацій, що знадобилося першій програмі більше, ніж кількість ітерацій, необхідних другій програмі. Це випливає з того, що антиградієнт показує напрямок якнайшвидшого зменшення функції.
Нижче наведено графік збіжності вищеописаного процесу для моєї функції та моїх початкових умов.
Також необхідно додати кілька важливих моментів. По-перше, з того, що кількість ітерацій, що знадобилося для знаходження мінімуму в першому завданні більше, ніж у другому не випливає той факт, що друга програма працює швидше, ніж перша, оскільки для другого завдання необхідно обчислювати не тільки значення функції в якій- або точці, а й її похідної у цій точці, яка може бути більш громіздка, ніж сама функція. Нарешті, другий метод поганий ще й тому, що для довільної функції похідну обчислити неможливо; доведеться спочатку апроксимувати її, а потім шукати мінімум (за рахунок апроксимації значно зростає час та похибка вимірювань).

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *