Metoda najszybszego spadku

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda najszybszego spadkualgorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.

Metoda najszybszego spadku jest modyfikacją metody gradientu prostego.

Algorytm[edytuj kod]

Zadanie[edytuj kod]

Metoda najszybszego spadku jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu :

gdzie .

Założenia dla metody są następujące:

Opis[edytuj kod]

Ilustracja działania metody najszybszego spadku dla dwuwymiarowej funkcji celu. W każdym kroku, w zadanym kierunku wyszukiwana jest najmniejsza wartość funkcji celu.

Działanie metody najszybszego spadku jest bardzo podobne do metody gradientu prostego. Na samym początku algorytmu wybierany jest punkt startowy . W punkcie tym obliczany jest antygradient funkcji celu, który będzie stanowił kierunek poszukiwań w procedurze. Następny punkt jest obliczany według wzoru:

jeśli obliczony punkt nie spełni warunku stopu algorytmu, całe postępowanie jest powtarzane.

Różnicą pomiędzy metodą najszybszego spadku a metodą gradientu prostego jest sposób wyszukiwania wartości - dokonywana jest minimalizacja kierunkowa funkcji:

Algorytm ogólnie można zapisać:

  1. Wybierz punkt startowy
  2. Dokonaj minimalizacji kierunkowej funkcji względem .
  3. Sprawdź kryterium stopu, jeśli jest spełniony to STOP. W przeciwnym wypadku powtórz punkt 2.

Metodami minimalizacji jednowymiarowej mogą być metoda złotego podziału, metoda dychotomii, metoda punktu środkowego, czy metoda Newtona.

Kryterium stopu[edytuj kod]

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie najszybszego spadku, można użyć następujących kryteriów stopu (dla zadanej precyzji oraz normy ):

  • (test stacjonarności).

Zbieżność[edytuj kod]

Przykład niefortunnego wyboru punktu startowego w metodzie najszybszego spadku. Przy takim wyborze dla odpowiedniego rodzaju funkcji celu metoda charakteryzuje się wolną zbieżnością.

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:

Metoda najszybszego spadku ma szybszą zbieżność w porównaniu z metodą gradientu prostego. Niemniej oba algorytmy należą do klasy algorytmów o złożoności liniowej.

Wadą metody jest wolna zbieżność przy niezbyt fortunnym wyborze punktu startowego. Dodatkowo metoda może być bardzo wrażliwa na błędy zaokrągleń.

Zobacz też[edytuj kod]

Bibliografia[edytuj kod]

  1. Fortuna Z., Wąsowski J.: Metody Numeryczne. Wydawnictwa Naukowo-Techniczne, 2006. ISBN 83-204-3245-6.
  2. Stachurski A.: Podstawy optymalizacji. Oficyna Wydawnicza PW, 1999. ISBN 83-7207-085-7.

Linki zewnętrzne[edytuj kod]