Metoda Neldera-Meada
Metoda Neldera–Meada lub sympleksowa metoda spadku (ang. downhill simplex method) – metoda numeryczna wyznaczania ekstremum (typowo minimum) nieliniowej funkcji wielu zmiennych bez korzystania z pochodnych. Tak więc może być stosowana do funkcji nieróżniczkowalnych.Została opisana po raz pierwszy przez Johna Neldera i Rogera Meada (1965)[1].
Opis metody
Wybieramy trzy parametry (liczby rzeczywiste): oraz
Na przykład mogą to być wartości 1, 1/2 i 1. W każdym kroku metody dany jest układ
punktów z
taki, że wektory
są liniowo niezależne. Powłoka wypukła tych wektorów jest sympleksem n-wymiarowym. Numerację punktów tak wybieramy, aby zachodziły nierówności
Teraz definiujemy trzy punkty:
Zauważmy, że jest środkiem ściany sympleksu, która jest naprzeciw punktu
czyli punktu „najgorszego” (szukamy minimum).Konstrukcja nowego sympleksu zależy od wartości funkcji w zdefiniowanych punktach
Wyróżniamy trzy przypadki
Jeżeli to
a w przeciwnym razie
Teraz nowy punkt to
Jeżeli to
Ponadto definiujemy
Jeżeli
to
a w przeciwnym razie dla
definiujemy
Teraz – w razie potrzeby – dokonujemy przenumerowania nowych punktów tak, aby zachodziło uporządkowanie
co kończy kolejny krok metody.
Podany opis bazuje na oryginalnej pracy Neldera i Meada. Istnieją też modyfikacje tej podstawowej metody – na przykład metoda wzmocnionego spadku Tsenga.
Przypisy
Linki zewnętrzne
- Nelder–Mead (Simplex) Method, Uniwersytet Gdański. paula.univ.gda.pl. [zarchiwizowane z tego adresu (2011-09-04)].