Metoda Neldera-Meada

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 A. Naldera i Rogera Meada (1965)[1].

Opis metody[edytuj]

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

  1. John A. Nalder, Roger Mead. A Simplex Method for Function Minimization. „The Computer Journal”. 7 (4), s. 308-313, 1965. DOI: 10.1093/comjnl/7.4.308 (ang.). 

Linki zewnętrzne[edytuj]