Loading AI tools
Z Wikipedii, wolnej encyklopedii
Metoda najszybszego spadku – algorytm numeryczny mający na celu znalezienie minimum zadanej funkcji celu.
Ten artykuł od 2023-06 wymaga zweryfikowania podanych informacji. |
Metoda najszybszego spadku jest modyfikacją metody gradientu prostego.
Metoda najszybszego spadku jest iteracyjnym algorytmem wyszukiwania minimum zadanej funkcji celu
gdzie
Założenia dla metody są następujące:
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ć:
Metodami minimalizacji jednowymiarowej mogą być metoda złotego podziału, metoda dychotomii, metoda punktu środkowego, czy metoda Newtona.
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 ):
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ń.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.