Przejdź do zawartości

Metoda Newtona

Z Wikipedii, wolnej encyklopedii
Metoda Newtona
ilustracja
Rodzaj

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

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].

Miejsce zerowe funkcji jednej zmiennej

[edytuj | edytuj kod]

Zadanie

[edytuj | edytuj kod]

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 | edytuj kod]
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 | edytuj kod]

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

Szacowanie błędu

[edytuj | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]
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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

Metody rozwiązywania równań nieliniowych:

Inne:

Przypisy

[edytuj | edytuj kod]
  1. publikacja w otwartym dostępie – możesz ją przeczytać Piotr Krzyżanowski, Grzegorz Łukaszewicz, Przez wieki z metodą Newtona, pismo „Delta”, wrzesień 2021 [dostęp 2021-09-03].

Bibliografia

[edytuj | edytuj kod]

Linki zewnętrzne

[edytuj | edytuj kod]