36)
Algorytm :
· Po pierwsze wybieramy arbirtalnie punkt startowy ( oczywiście z dziedziny )
· Następnie w punkcie startowym obliczamy gradient funkcji celu oraz wartość funkcji celu w tym punkcie ( de facto tutaj już sprawdza się kryterium stopu )
· Obieramy kierunek poszykiwań =
· Dokonujemy minimalizacji kierunkowej funkcji minα F( xk – α ∇f(xk))
·
· Sprawdzamy kryterium stopu, jeśli nie jest to kryterium spełnione to ponownie dokonujemy minimalizacji kierunkowej
Kryteria STOP :
Opis :
W metodzie najszybszego spadku dokonujemy poszukiwań minimum funkcji celu rozpoczynając je od dowolnie wybranego punktu należącego do dziedziny funkcji. Poszukiwania odbywają się w kierunku zgodnym z minus gradientem – czyli pierwszą pochodną kierunkową funkcji celu. Jest to metoda iteracyjna dlatego każdy następny krok obliczamy w oparciu o poprzedni. Każdy krok oblicza się ze wzoru
( ). α dobieramy tak, aby funkcja była minimalizowana na kierunku. W tej metodzie obliczamy nstp kroki tak długo aż będziemy dostatecznie blisko celu ( czyli spełniają kryteria STOP ).
* Jedna sprawa, że metoda ta wykorzystuje przybliżenie liniowe
* Metoda najszybszego spadku jest metodą o zbieżności liniowej. Oznacza to, iż przy spełnieniu założeń metody, odległości pomiędzy kolejnymi przybliżeniami, a minimum funkcji maleją liniowo
37)
· Kolejne wektory w tej metodzie są do siebie prostopadłe
· Długości tych wektorów maleją ( normy tych wektorów są o coraz mniejszych wartościach )
· * wektory są na kierunkach gradientu, więc są prostopadłe do warstwic
· * Przy ekstremum nie jest prostopadłe do warstwic tylko styczne do warstwic
38)
Ekstremum jest lokalne jeśli w pewnym otoczeniu otwartym funkcja nie przyjmuje wartości większych/ mniejszych ( w zależności czy jest to minimum czy maksimum lokalne ). Natomiast ekstremum globalne jest to minimalna lub maksymalna wartość funkcji w całej dziedzinie. ( Ekstremum = wartość , nie jest punktem ).
39)
Konwencjonalne metody poszukiwania minimalnej wartości funkcji jaką jest metoda najmniejszego spadku startują z dowolnie obranego punktu początkowego i poszukując w jego pobliżu mniejszej (niż poprzednia) wartości funkcji celu, zmierzają do minimum. Poszukiwanie takie uzależnione jest od obranego punktu startowego i nie zawsze kończy się w minimum globalnym. Ponadto, metoda najmniejszego spadku nie posiada mechanizmów ( np. stochastycznych tak jak w genetycznych czy wyżarzaniu ) , które pozwoliłyby na wyjście z osiągniętego ekstremum i poszukiwaniu innych ekstremów, w których wartość funkcji może być mniejsza niż osiągnięta. Czyli nie jest metodą globalną. * Wyszukuje tylko ekstrema globalne w funkcjach unimodalnych – czyli z jednym ekstremum.
40 )
Nie jest z tych samych powodów.
41)
RYSUNEK załączony
∇ f(x) ο π’( t ) = 0
Jest to iloczyn skalarny gradientu oraz pochodnej parametryzacji ( czyli wektor styczny do warstwicy w punkcie ). Ich iloczyn skalarny jest równy zero czyli x=90o przy cosx. Czyli są ortogonalne.
42)
TW. Rayleigha λmin || x ||2 <= xT Q x < = λmax || x ||2
Założenia – macierz rzeczywista , dodatnio określona oraz symetryczna
Można udowodnić, że gdy I i II pochodna są dodatnie to w tym punkcie rzeczywiście jest minimum funkcji.
∆f(h) = 0
Hf > 0
F(x) = ∇ f(x)h + ½ ht Hf(x) h + o(|| h || 2 ) =
= ½ ht Hf(x) h + o(|| h || 2 ) >= ½ λmin || x ||2 > 0
chomikSGHowy