Лаборатория 12
Цел на работата: Изследване на числени методи от първи ред за неограничена минимизация на функции на няколко променливи - метод на най-стръмно спускане, метод на спрегнати градиенти; сравнителен анализ на методи от различен ред.
12.1.Теоретично резюме
Алгоритмите за намиране на екстремума на функциите на няколко променливи чрез числени методи се състоят в конструирането на последователност от векториX(k)>,отговарящи на условието:f(X(0)) > f(X(1)) >…> f(X(n)). Елементите на последователносттаX(k)>се изчисляват по формулата
КъдетоP(k)е посоката на снижаване; ak—Дължина на стъпката в тази посока. Всяка начална точкаX(0)може да бъде избрана, но трябва да се използва цялата налична информация за поведението на функциятаF(X), така чеX(0)да не е твърде далеч от минималната точка. След това трябва да изберете посоката, по която искате да поставите следващата точка, и размера на стъпката в тази посока. На практика се използват само методи с конвергенция. Те позволяват краен брой стъпки за получаване на минимална точка или интервал на неопределеност, съдържащ минимална точка и имащ дължина, по-малка от дадено числоE.
Градиентни методи.Както знаете, градиентът на функцията в даден моментX(k)е насочен към най-бързото локално нарастване на функцията. Следователно трябва да слезете в посока, обратна на наклона. Векторът, противоположен на градиента, се наричаАнтиградиент. Избирайки антиградиент като посока на спускане, се стига до итерацияпроцес на формата
В координатна форма този процес се записва по следния начин:
.
Всички методи на спускане, при които векторътP(k)е същият като антиградиента, се наричат Градиентни методи. Те се различават един от друг само по начина, по който се избира стъпката. В методи спостоянна стъпкасе избира някакъв постоянен размер на стъпката за всички итерации. Достатъчно малка стъпка ще гарантира, че функцията намалява, но това може да доведе до необходимостта от извършване на неприемливо голям брой итерации за достигане на минималната точка. От друга страна, твърде голяма стъпка може да причини неочаквано нарастване на функцията или да доведе до колебания около минималната точка. Поради липсата на необходимата информация за избор на размера на стъпката, рядко се използват методи с постоянна стъпка. По-икономични от гледна точка на броя итерации и по-надеждни са градиентните методи спроменлива стъпка, сред които най-често срещаните са методът на най-стръмно спускане и методът на разделяне на стъпките.
Метод на най-бавното спускане. Тук при всяка итерация размерът на стъпката се избира от условието на минимума на функцията в посоката на движение:
, (12.3)
Тоест на всяка стъпка се решава едномерен проблем за минимизиране. Геометричната интерпретация на този метод е доста проста.
Алгоритъмът за най-стръмно спускане е както следва:
1) в точкатаX(0)стойностите на градиентаF(X(0))и стъпката се изчисляват чрез решаване на задачата за едномерна минимизация (12.3);
2) спускането се извършва в посока на антиградиента с избраната стъпка, докато стойността на функциятаF(X)намалее;
3) ако при някояM-та стъпкаF(X(M))>gt; f(X(M-1)), след това в точкатаX(M-1)новградиентF¢(X(M-1))и стъпка и отидете на стъпка 2.
АкоF(X)е непрекъснато диференцируема функция, ограничена отдолу и за някаква начална точкаX(0)множествотоX: f(X) 2013-06-06