Metoda Newtona – algorytm iteracyjny mający na celu znalezienie minimum lokalnego funkcji jednej zmiennej lub wielu zmiennych rzeczywistych o wartościach w zbiorze liczb rzeczywistych. Zasadniczym elementem algorytmu jest obliczanie gradientu i hesjanu funkcji, charakteryzujących lokalne własności wykresu funkcji: kierunek jej maksymalnego wznoszenia się oraz krzywiznę wykresu funkcji. Obliczeń dokonuje się w kolejnych punktach i przemieszcza się w stopniowo w kierunku minimum.

To, które minimum lokalne zostanie znalezione, zależy od przyjętego punktu startowego; jedynie w przypadku, gdy funkcja jest ściśle wypukła, posiada pojedyncze minimum. Metodę można stosować do funkcji dwukrotnie różniczkowalnych, gdyż obliczanie gradientu i hesjanu wymaga obliczania pierwszej i drugiej pochodnych funkcji.

Problem znajdowania minimum funkcji występuje jako podstawowe zagadnienie problemów optymalizacji. Wtedy funkcją, dla której szuka się minimum, jest tzw. funkcją straty / funkcją kosztu. Metodą Newtona nazywana jest również metoda rozwiązywania równań nieliniowych (por. Metoda Newtona), jednak pomimo takiej samej nazwy dotyczy ona innego rodzaju zadań numerycznych.

Funkcja jednej zmiennej Metoda Newtona zastosowana do znalezienia minimum funkcji jednej zmiennej o wartościach w zbiorze liczb rzeczywistych

wymaga, by funkcja była podwójnie różniczkowalna w badanej dziedzinie.

Wzór rekurencyjny dla metody ma prostą postać

gdzie oraz to pierwsza i druga pochodne funkcji obliczone w aktualnym punkcie procesu iteracyjnego. Punkt początkowy wybiera się dowolnie, choć im bliżej minimum, tym krócej będzie trwać proces poszukiwania.

Jeżeli przy tym jest ściśle wypukła w badanej dziedzinie, to algorytm znajduje minimum globalne. Gdy zaś nie spełnia tego warunku, to istnieje wiele minimów - wtedy funkcja ma wiele minimów lokalnych i algorytm znajduje jedno z nich, co zależy od wybory punktu startowego .

Funkcje wielu zmiennych Metoda Newtona zastosowana do znalezienia minimum funkcji wielu zmiennych rzeczywistych o wartościach w zbiorze liczb rzeczywistych , wymaga, by funkcja była podwójnie różniczkowalna w badanej dziedzinie, tj. (funkcja jest ciągła i podwójnie różniczkowalna).

Jeżeli przy tym jest ściśle wypukła w badanej dziedzinie, to algorytm znajduje minimum globalne. Gdy zaś nie spełnia tego warunku, to istnieje wiele minimów - wtedy funkcja ma wiele minimów lokalnych i algorytm znajduje jedno z nich, co zależy od wybory punktu startowego .

Opis algorytmu thumb|Porównanie metody Newtona (linia czerwona) z metodą gradientu (linia zielona) dla funkcji dwóch zmiennych. Metoda Newtona jest szybciej zbieżna do minimum, gdyż używa informacji o krzywiźnie wykresu funkcji w celu zoptymalizowania ścieżki poszukiwań. Metoda gradientu używa jedynie informacji o lokalnym spadku wykresu funkcji. 1. Wybierz punkt startowy .

2. Oblicz kierunek poszukiwań .

Z rozwinięcia Taylora wynika, że wartość funkcji w punkcie niewiele odległym od punktu wyraża wzór: ,

gdzie:

- wektor małego przemieszczenia, - gradient funkcji w punkcie , - macierz Hessego w punkcie , - reszta o wielkości rzędu kwadratu długości wektora , T oznacza transpozycję wektora lub macierzy

Funkcję w punkcie można więc przybliżyć do wyrazów 2-go rzędu funkcją , taką że

Kierunek dobierz tak, by zminimalizować funkcję , tj.

co prowadzi do wzoru (dowód - por. np. Fortuna, Macukow, str. 149)

gdzie -1 oznacza operację liczenia macierzy odwrotnej.

3. Oblicz kolejny punkt

4. Sprawdź, czy obliczony punkt spełnia warunek stopu - jeśli nie, to przyjmij k:= k + 1 i wróć od punktu (2); jeśli tak, to zatrzymaj obliczenia.

Algorytm można krótko opisać następująco: Wybierz punkt startowy . Oblicz . Przyjmij nowe przybliżenie . Sprawdź kryterium stopu, jeśli nie jest spełnione, to przyjmij k := k+ 1 i przejdź ponownie do punktu 2; jeśli jest spełnione, to STOP.

Modyfikacja Newtona-Raphsona Modyfikacja metody optymalizacyjnej Newtona, nazwana metodą Newtona-Raphsona, polega na obliczaniu w kolejnych krokach przesunięć do punktów, w którym funkcja ma najmniejsze wartości w kierunkach, wskazywanych przez metodę; dzięki temu zwiększona zostaje szybkość zbieżności do minimum.

W metodzie tej najpierw wybiera się punkt startowy, analogicznie jak w pierwszej metodzie. Dla tego punktu obliczany jest kierunek poszukiwań oraz obliczana jest na jego podstawie minimalizacja kierunkowa, tzn. obliczana jest taka wartość , że .

Kolejny krok obliczany jest ze wzoru

Algorytm można opisać następująco: Wybierz punkt startowy . Oblicz wektor . Znajdź taką liczbę , że wartość funkcji obliczona w punkcie leżącym na kierunku jest możliwie najmniejsza; innymi słowy: dokonaj minimalizacji wartości funkcji względem . Przyjmij jako nowe przybliżenie szukanej wartości. Sprawdź kryterium stopu: jeśli nie jest spełnione, to podstawa k:= k + 2 i przejdź ponownie do punktu 2; jeśli jest spełnione, to STOP.

Uwaga:

Znalezienie wartości , dla której funkcja przyjmuje wartość minimalną w danym kierunku, można dokonać za pomocą dowolnej metody optymalizacji numerycznej jednowymiarowej, np. metodą punktu środkowego, metodą złotego podziału.

Implementacja Przy implementacji metody Newtona, przy określaniu kierunku poszukiwań , zamiast obliczania macierzy odwrotnej do hesjanu można skorzystać z metod numerycznych rozwiązywania układów równań liniowych

w celu obliczenia wartości wektora .

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

Zbieżność Metoda Newtona jest metodą o zbieżności kwadratowej. Oznacza to, że przy spełnieniu założeń metody, odległości pomiędzy kolejnymi przybliżeniami a minimum funkcji maleją kwadratowo .

Metoda Newtona dla funkcji kwadratowych znajduje minimum już w pierwszym kroku – wynika to z faktu, że w metodzie Newtona funkcja f jest lokalnie aproksymowana właśnie funkcją kwadratową.

Zobacz też metoda gradientu prostego metoda najszybszego spadku metoda złotego podziału metoda Levenberga-Marquardta optymalizacja (matematyka)

Bibliografia Fortuna Z., Macukow B., Wąsowski J.: Metody numeryczne, Wydawnictwa Naukowo-Techniczne, 2006, str. 149-152. Szmelter J., Metody komputerowe w mechanice, Państwowe Wydawnictwo Naukowe, Warszawa 1980, str. 133-135. Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

Linki zewnętrzne Wideo wykład na MIT o metodzie Newtona

Kategoria:Metody numeryczne Kategoria:Metody optymalizacji Kategoria:Isaac Newton