Zadanie[edytuj]

Zadaniem metody jest znalezienie pierwiastka równania zadanej funkcji ciągłej f:

w przedziale [a,b]. A zatem znalezienie takiego
, które spełnia następujące równanie:

Opis metody[edytuj]

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

Metoda Newtona przyjmuje następujące założenia dla funkcji
:

1. W przedziale
   znajduje się dokładnie jeden pierwiastek.

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.

W pierwszym kroku metody wybierany jest punkt startowy
(zazwyczaj jest to wartość
, lub
), z którego następnie wyprowadzana jest styczna w
. Odcięta punktu przecięcia stycznej z osią OX jest pierwszym przybliżeniem rozwiązania (ozn.
).

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt
jest wybierany jako nowy punkt startowy i wszystkie czynności są powtarzane. Proces jest kontynuowany, aż zostanie uzyskane wystarczająco dobre przybliżenie pierwiastka

Kolejne przybliżenia są dane rekurencyjnym wzorem:

Szacowanie błędu[edytuj]

Błąd k-tego przybliżenia można oszacować poprzez nierówności (x* to dokładna wartość pierwiastka):

lub

gdzie stałe wyznacza się ze wzorów:

oraz

Warunek stopu[edytuj]

Metoda Newtona wykonuje iteracyjnie obliczenia, aż do momentu gdy jej wyniki będą satysfakcjonujące. W praktyce stosowanych jest kilka kryteriów warunków stopu dla algorytmu (ε 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 niestety fakt, iż wspomniana zbieżność nie musi zawsze zachodzić. W wielu przypadkach metoda bywa rozbieżna - przeważnie 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ą ilością wykonywanych iteracji (przekroczenie ustalonej liczby iteracji jest równoznaczne z niepowodzeniem algorytmu w zadanym przedziale).

Przykład[edytuj]