Доповідь: Градієнтний метод з подрібненням кроку і метод найшвидшого спуску

Формат: doc

Дата створення: 13.04.2006

Розмір: 10.71 KB

Семінарська робота

Метод найшвидшого метод із дробленням кроку і метод найшвидшого спуску

виконав

Студент групи МОС-22

Кравченко Олександр

Метод найшвидшого метод із дробленням кроку.

У цьому варіанті градиентного методу величина кроку α n на кожній ітерації вибирається з умови виконання нерівності

f (x n +1) = f (x n   n f  (x n))  f (x n)   n || f  (x n) || 2,

де   (0, 1) - деяка заздалегідь обрана константа. Умова гарантує (якщо, звичайно, такі  n вдасться знайти), що получающаяся послідовність буде релаксационной. Процедуру знаходження такого  n зазвичай оформляють так.

Вибирається число   (0, 1) і деякий початковий крок 0. Тепер для кожного n вважають  n = 0 і роблять крок градиентного методу. Якщо з таким  n умова виконується, то переходять до наступного n. Якщо ж умова не виконується, то множать  n на  ( "дроблять крок") і повторюють цю процедуру до тих пір поки рівність

f  (x n) =



1 0

f  [x * + s (x n  x *)] (x n  x *) ds

не виконуватиметься. В умовах теореми про умовну збіжність градієнтного методу з постійним кроком ця процедура для кожного n за кінцеве число кроків приводить до потрібного  n.

Можна показати, що в умовах теореми (про лінійної збіжності градієнтного методу з постійним щагом) градієнтний метод із дробленням кроку лінійно сходиться. Описаний алгоритм позбавляє нас від проблеми вибору  на кожному кроці, замінюючи її на проблему вибору параметрів ,  і 0, до яких градієнтний метод менш чутливий. При цьому, зрозуміло, обсяг обчислень зростає (у зв'язку з необхідністю процедури дроблення кроку), втім, не дуже сильно, оскільки в більшості завдань основні обчислювальні витрати лягають на обчислення градієнта.

Метод найшвидшого спуску.

Цей варіант градиентного методу грунтується на виборі кроку з наступного міркування. З точки x n будемо рухатися в напрямку антіградіента до тих пір поки не досягнемо мінімуму функції f на цьому напрямку, т. Е. На промені L = {x  R m: x = x n   f  (x n);   0}:

 n = argmin [0, ) f (x n   f  (x n)).

Мал. 1

Іншими словами,  n вибирається так, щоб наступна ітерація була точкою мінімуму функції f на промені L (див. Рис.1). Такий варіант градиентного методу називається методом найшвидшого спуску. Зауважимо, що в цьому методі напрямки сусідніх кроків ортогональні. Справді, оскільки функція :   f (x n   f  (x n)) досягає мінімуму при  =  n, точка  n є стаціонарною точкою функції :

0 =  ( n) =

d

d 

f (x n   f  (x n))

 

 =  n

=

= (F  (x n   n f  (x n)),  f  (x n)) =  (f  (x n +1), f  (x n)).

Метод найшвидшого спуску вимагає рішення на кожному кроці завдання одномірної оптимізації. Практика показує, що цей метод часто вимагає меншого числа операцій, ніж градієнтний метод з постійним кроком.

У загальній ситуації, проте, теоретична швидкість збіжності методу найшвидшого спуску не вище швидкості збіжності градієнтного методу з постійним (оптимальним) кроком.

Подібні документи:

Доповідь: Методи дослідження в цитології 6. Визначення тривалості деяких стадій клітинного циклу методом радиоавтографии. Цитологія - наука про клітину. З-посеред інших біологічних наук вона виділилася майже 100 років тому. Вперше узагальнені відомості про будову клітин були зібрані в книгу Ж.-Б. Карнуа «Біологія клітини», що вийшла в 1884 році.

Курсова: Гамма - каротаж. Фізичні основи методу Геофізик - це суб'єкт, здатний з бадьорою силою духу вивертати нескінченні ряди незбагненних формул, виведених з мікроскопічною точністю, виходячи з невизначених припущень, заснованих на спірних даних, отриманих з непереконливих експериментів, виконаних з неконтрольованої апаратурою особами підозрілою надійності і сумнівних розумових здібностей.

Курсова: Судова система РФ та шляхи її реформування У даній роботі розглядається структура судової системи Російської Федерації, а так само проблема судового реформування країни і роль судової реформи в державному устрої на сучасному етапі.

Екзаменаційна: Культура Давньої Русі в 10-13 століттях. Значення прийняття християнства Для початку необхідно визначити що таке культура. Культура (від лат. Cultura) - зведення, виховання, шанування. Слово «культура» належить, напевно до числа найбільш часто зустрічаються. Воно існує практично у всіх мовах і вживається в самих різних ситуаціях. Спори серед вчених навколо поняття культура ведуться вже ні одне століття.

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

реферат Вакцинопрофілактика У боротьбі з інфекційними захворюваннями все більшого значення набувають методи специфічної профілактики. Захист від інфекції за допомогою імунізації відома вже багато сотень років. Так, з давніх часів китайці з цією метою втягували в ніс висушені і подрібнені скоринки віспяних хворих.

Реферат Термічна обробка металів. композиційні матеріали 1. Теорія і технологія термічної обробки. Види термічної обробки. Відпал, нормалізація, гарт, старіння, поліпшення. 1. Теорія і технологія термічної обробки. Види термічної обробки. Відпал, нормалізація, гарт, старіння, поліпшення.