Metoda Newtona

W metodzie Newtona do wyznaczenia kierunku poszukiwań wykorzystuje się gradient funkcji oraz Hessian – macierz drugich pochodnych. Metoda ta jest bardzo szybko zbieżna dla funkcji kwadratowych. Jej wadą jest rozbieżności dla niektórych funkcji i punktów początkowych oraz konieczność liczenia i odwracania Hessianu (co jest dość pracochłonne), dlatego w praktyce często używa się metod Quasi-Newtonowskich.

Oznaczenia:

x₀ – pierwsze przybliżenie rozwiązania (punkt startowy)

x_i – i-te przybliżenie rozwiązania

H – macierz drugich pochodnych (Hessian) –

ε – wymagana dokładność

Algorytm:

1. Ustal , x₀, ε > 0

2. Sprawdź, czy punkt x_i spełnia kryterium stopu - jeślito x_i jest rozwiązaniem

3. Wyznacz kolejne przybliżenie rozwiązania , gdzie

   jest kierunkiem poprawy,

   jest macierzą odwrotną do macierzy drugich pochodnych w punkcie x_i, natomiast to długość kroku minimalizująca jednowymiarową funkcję

4. 

5. Idź do punktu 2.