Metoda Newtona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ujednoznacznienie Ten artykuł dotyczy wyznaczania przybliżonej wartości pierwiastka funkcji. Zobacz też: metoda Newtona (optymalizacja).

Metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych) – iteracyjny algorytm wyznaczania przybliżonej wartości pierwiastka funkcji.

Rozwiązywanie równania nieliniowego[edytuj | edytuj kod]

Zadanie[edytuj | edytuj kod]

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

\mathbb{R} \supset [a,b] \ni x \mapsto f(x) \in \mathbb{R}

w przedziale [a,b]. A zatem znalezienie takiego x^{\ast} \in [a,b], które spełnia następujące równanie:

f(x^{\ast})=0

Opis metody[edytuj | edytuj kod]

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

W metodzie Newtona przyjmuje się następujące założenia dla funkcji f:

  1. W przedziale [a,b] znajduje się dokładnie jeden pierwiastek.
  2. Funkcja ma różne znaki na krańcach przedziału, tj. f\left(a\right) \cdot f\left(b\right) < 0.
  3. Pierwsza i druga pochodna funkcji mają stały znak w tym przedziale.

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

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt x2 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:

x_{k+1} = x_k - \frac{f(x_k)}{f^\prime(x_k)}

Szacowanie błędu[edytuj | edytuj kod]

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

|x^{\ast} - x_k| \leqslant \frac{f(x_k)}{m}

lub

|x^{\ast} - x_k| \leqslant \frac{M}{2m}(x^{\ast} - x_{k-1})^2

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

m=\min_{x \in [a,b]} |f'(x)|

oraz

M=\max_{x \in [a,b]} |f''(x)|

Warunek zakończenia obliczeń[edytuj | edytuj kod]

W metodzie Newtona wykonuje się iteracyjne obliczenia, aż do momentu gdy ich wyniki będą satysfakcjonujące. W praktyce stosowanych jest kilka kryteriów warunków zakończenia obliczeń dla algorytmu (\epsilon to przyjęta dokładność obliczeń):

1. wartość funkcji w wyznaczonym punkcie jest bliska 0:
\left| f(x_k) \right| \leqslant \epsilon
2. odległość pomiędzy kolejnymi przybliżeniami jest dość mała:
\left| x_{k+1} - x_k \right| \leqslant \epsilon
3. szacowany błąd jest dostatecznie mały:
\frac{M}{2m}(x_k - x_{k-1})^2 \leqslant \epsilon
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 \frac{M}{2m}. 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ą ilością 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 \sqrt{a} dla każdej liczby a \in \Bbb R^+:

\sqrt{a}=x \iff a=x^2 \iff x^2-a=0

Funkcja f(x) ma postać:

f(x) = x^2 -a
f\, '(x) = 2x

Rekurencyjny wzór wynosi:

x_{k+1} = x_k - \frac{x_k^2 -a}{2x_k}
x_{k+1} =\frac{1}{2}\left(x_k+\frac{a}{x_k}\right)

Dla danych a=2 i x_0=1,5 algorytm przebiega następująco:

x_{0} = 1,5
x_{1} = \frac{1}{2} (1,5 + \frac{2}{1,5}) \approx 1,416666
x_{2} = \frac{1}{2} (1,416666 + \frac{2}{1,416666}) \approx 1,414214

Rozwiązywanie układu równań nieliniowych[edytuj | edytuj kod]

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

Metodę Newtona można zgeneralizować do przypadku wielowymiarowego i użyć jej do obliczania układów równań nieliniowych.

Zadanie[edytuj | edytuj kod]

Niech U będzie otwartym podzbiorem przestrzeni \mathbb{R}^n oraz F\colon U \to \mathbb{R}^n będzie funkcją różniczkowalną.

Zadaniem uogólnionej metody Newtona jest znalezienie takiej wartości x*, dla której:

F (\mathbf{x^{\ast}}) = \mathbf{0}.

Opis metody[edytuj | edytuj kod]

Algorytm podobnie, jak dla przypadku jednowymiarowego, polega na wyborze punktu startowego \mathbf{x_0} (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:

\mathbf{x_{k+1}} = \mathbf{x_{k}} - \left( F^\prime (\mathbf{x_{k}}) \right)^{-1} F (\mathbf{x_{k}})

gdzie F^\prime jest pochodną (Frécheta) – jest to de facto macierz wielkości \displaystyle n \times n.

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

F^\prime (\mathbf{x_k}) \mathbf{d} = -F (\mathbf{x_k})

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

\mathbf{x_{k+1}} = \mathbf{x_k} + \mathbf{d}

Warunek zakończenia obliczeń[edytuj | edytuj kod]

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

  1. wartość funkcji dostatecznie bliska wektorowi zerowemu:
    \| F (\mathbf{x_{k}}) \| \leqslant \epsilon
  2. dostatecznie mała odległośc pomiędzy kolejnymi punktami w iteracji:
    \| \mathbf{x_{k+1}} - \mathbf{x_{k}} \| \leqslant \epsilon
  3. kryterium mieszane (punkty 1 oraz 2 jednocześnie)

Zbieżność[edytuj | edytuj kod]

Jeśli funkcja F:

to dla punktu startowego \mathbf{x^0} 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):
\mathbf{G}(\mathbf{x}) = \langle F (\mathbf{x}), F (\mathbf{x}) \rangle \in \mathbb{R}
gdzie \langle \cdot, \cdot \rangle oznacza iloczyn skalarny dwóch wektorów.
  • Dla równania nieliniowego – znalezienie pierwiastka odpowiedniej pochodnej f lub przeprowadzenie minimalizacji funkcji \left(f(x)\right)^2

Zobacz też[edytuj | edytuj kod]

Inne metody rozwiązywania równań nieliniowych:

Bibliografia[edytuj | edytuj kod]

  • Fortuna Z., Macukow B., Wąsowski J., Metody Numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.

Linki zewnętrzne[edytuj | edytuj kod]