Metoda Newtona

Z Wikipedii

Metoda Newtona (metoda stycznych) - algorytm wyznaczania przybliżonej wartości pierwiastka funkcji $y = f (x)$ jednej zmiennej w zadanym przedziale $[a, b]$ . Założenia metody są następujące:

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

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

W pierwszym kroku metody wybierany jest ten kraniec przedziału, dla którego znak funkcji i drugiej pochodnej są równe, a następnie z tego punktu (albo $(a, f (a))$ albo $(b, f (b))$ ) wyprowadzana jest styczna. Odcięta punktu przecięcia stycznej z osią OX jest pierwszym przybliżeniem rozwiązania (ozn. $x 1$ ).

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt $(x 1, f (x 1))$ jest wybierany jako koniec przedziału i wszystkie czynności są powtarzane. Proces jest kontynuowany, aż zostanie uzyskane wystarczająco dobre przybliżenie pierwiastka (wartość funkcji w wyznaczonym punkcie).

Kolejne przybliżenia są dane rekurencyjnym wzorem:

$x_n=\left\{ \begin{matrix} n=0 &: x_0 \in \Bbb R -> dane\\ n>0 &: x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \end{matrix} \right.$

Błąd $n$ -tego przybliżenia jest dany wzorami ( $\overline{x}$ to dokładna wartość pierwiastka):

$|\overline{x} - x_n| \le \frac{f(x_n)}{m}$ dla wszystkich

n

$|\overline{x} - x_n| \le \frac{M}{2m}(\overline{x} - x_{n-1})^2$ dla

n > 0,

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

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

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

Wadą metody Newtona jest konieczność wyznaczania wartości funkcji pochodnej, co w zastosowaniach komputerowych jest kłopotliwe gdy nie jest znana analityczna postać funkcji.