Metoda Newtona

metoda numeryczna rozwiązywania równań liczbowych oparta na stycznych

Metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych) – algorytm iteracyjny prowadzący do wyznaczenia przybliżonej wartości miejsca zerowego funkcji jednej zmiennej lub wielu zmiennych[1].

Metoda Newtona
ilustracja
Rodzaj

algorytm iteracyjny, wyznaczanie przybliżonej wartości pierwiastka funkcji

Miejsce zerowe funkcji jednej zmiennej edytuj

Zadanie edytuj

Niech będzie dana funkcja ciągła   jednej zmiennej rzeczywistej, określona na przedziale  

 

Zadanie polega na wyznaczeniu miejsca zerowego (pierwiastka) równania

 

tj. na znalezieniu liczby   takiej że  

Opis metody edytuj

 
Ilustracja działania metody Newtona, pokazane zostały 4 pierwsze kroki.

Założenia:

  1. W przedziale   znajduje się dokładnie jeden pierwiastek funkcji  
  2. Funkcja ma różne znaki na krańcach przedziału, tj.  
  3. Pierwsza i druga pochodna funkcji mają stały znak w tym przedziale.

Krok 1: Wybierz dowolną wartość startową   np.   (lub  ); następnie wyznacz równanie stycznej do wykresu funkcji w punkcie   następnie wyznacz odciętą   punktu przecięcia tej stycznej z osią OX – odcięta   jest drugim przybliżeniem szukanego rozwiązania.

Krok 2: Wartość   wybierz jako nową wartość startową i powtórz obliczenia z kroku 1 – otrzymasz nową wartość przybliżoną  

Proces kontynuuj do chwili, gdy będzie spełniony warunek zapewniający uzyskanie wystarczającego przybliżenia, co kończy proces iteracyjny (warunki kończące proces opisano dalej).

Wzór rekurencyjny edytuj

Dowodzi się, że kolejne przybliżenia szukanego miejsca zerowego dane są wzorem rekurencyjnym:

 

Szacowanie błędu edytuj

Błąd  -tego przybliżenia można oszacować poprzez nierówności:

 

lub

 

gdzie   – dokładna wartość pierwiastka, zaś stałe   zadają wzory:

 

oraz

 

Warunek zakończenia obliczeń edytuj

Stosowanych jest kilka kryteriów zakończenia obliczeń (  to przyjęta dokładność obliczeń):

1. wartość funkcji w wyznaczonym punkcie jest bliska 0:
 
2. odległość pomiędzy kolejnymi przybliżeniami jest dość mała:
 
3. szacowany błąd jest dostatecznie mały:
 
4. kryterium mieszane (punkty 1 i 2 jednocześnie)

Zbieżność edytuj

Metoda Newtona-Raphsona jest metodą o zbieżności kwadratowej – rząd zbieżności wynosi 2 (wyjątkiem są zera wielokrotne, dla których zbieżność jest liniowa i wynosi 1), zaś współczynnik zbieżności   Oznacza to, iż przy spełnionych założeniach błąd maleje kwadratowo wraz z ilością iteracji.

Metoda Newtona jest metodą rozwiązywania równań często używaną w solverach, ze względu na jej szybką zbieżność (w algorytmie liczba cyfr znaczących w kolejnych przybliżeniach podwaja się). Wadą jej jest fakt, iż zbieżność nie musi zawsze zachodzić. W wielu przypadkach metoda bywa rozbieżna, kiedy punkt startowy jest zbyt daleko od szukanego pierwiastka równania.

Profesjonalne solvery wykorzystują stabilniejsze, lecz mniej wydajne metody (jak np. metoda bisekcji) do znalezienia obszarów zbieżności w dziedzinie funkcji, a następnie używają metody Newtona-Raphsona do szybkiego i dokładniejszego obliczenia lokalnego pierwiastka równania. Dodatkowo solvery posiadają zabezpieczenia przed nadmierną liczbą wykonywanych iteracji (przekroczenie ustalonej liczby iteracji jest równoznaczne z niepowodzeniem algorytmu w zadanym przedziale).

Przykład edytuj

Za pomocą metody Newtona można obliczyć pierwiastek   dla każdej liczby  

 

Funkcja f(x) ma postać:

 
 

Wzór rekurencyjny ma postać:

 
 

Dla danych   i   algorytm przebiega następująco:

 
 
 
 

Miejsce zerowe funkcji wielu zmiennych edytuj

 
Przykład użycia metody Newtona do rozwiązywania układu równań nieliniowych

Metodę Newtona można uogólnić do przypadku wielowymiarowego, tj. użyć jej do rozwiązywania układów równań wielu zmiennych (liniowych lub nieliniowych).

Zadanie edytuj

Niech U będzie otwartym podzbiorem przestrzeni   oraz   będzie funkcją różniczkowalną.

Zadaniem uogólnionej metody Newtona jest znalezienie punktu   dla którego funkcja zeruje się, tj.

 

gdzie  

Opis metody edytuj

Algorytm, podobnie jak dla przypadku jednowymiarowego, polega na wyborze punktu startowego   (często wybiera się wektor zerowy lub wektor jedynek), a następnie rekurencyjnym przekształcaniu tego wektora aż do momentu, gdy kolejne przybliżenia będą satysfakcjonujące. Wektory przekształcane są zgodnie z równaniem macierzowym:

 

gdzie   jest pochodną (Frécheta) – jest to de facto macierz wielkości  

Przy implementacji metody, zamiast odwracania macierzy   efektywniej jest rozwiązać układ równań (tożsamy z powyższym równaniem):

 

a następnie na podstawie obliczonego d wyznaczyć kolejne przybliżenie:

 

Warunek zakończenia obliczeń edytuj

Kryterium zakończenia obliczeń podobnie jak w metodzie jednowymiarowej może być (w zadanej normie   oraz dokładności  ):

  1. wartość funkcji dostatecznie bliska wektorowi zerowemu:
     
  2. dostatecznie mała odległość pomiędzy kolejnymi punktami w iteracji:
     
  3. kryterium mieszane (punkty 1 oraz 2 jednocześnie)

Zbieżność edytuj

Jeśli funkcja F:

  •   dla pewnego  
  • pochodna   jest odwzorowaniem zwężającym i nieosobliwym,

to dla punktu startowego   będącego dostatecznie blisko x*, wielowymiarowa metoda Newtona jest zbieżna oraz zbieżność ta jest kwadratowa.

Pierwiastki wielokrotne edytuj

Przy rozwiązywaniu równań nieliniowych kłopotliwymi dla metody Newtona mogą być pierwiastki wielokrotne, dla których zbieżność algorytmu staje się liniowa. Dla takich przypadków metoda Newtona może być dużo wolniejsza niż inne metody rozwiązywania równań o zbieżności liniowej.

Aby zaradzić tego typu problemom, w praktyce stosuje się następujące podejścia:

  • Dla układu równań – przeprowadzenie optymalizacji funkcji G (znalezienie minimum zadanej funkcji celu):
 
gdzie   oznacza iloczyn skalarny dwóch wektorów.
  • Dla równania nieliniowego – znalezienie pierwiastka odpowiedniej pochodnej   lub przeprowadzenie minimalizacji funkcji  


Zobacz też edytuj

Metody rozwiązywania równań nieliniowych:

Inne:

Przypisy edytuj

  1.   Piotr Krzyżanowski, Grzegorz Łukaszewicz, Przez wieki z metodą Newtona, pismo „Delta”, wrzesień 2021 [dostęp 2021-09-03].

Bibliografia edytuj

Linki zewnętrzne edytuj