Metoda Newtona

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:

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

Plik:Metoda newtona.png

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:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „http://localhost:6011/pl.wikipedia.org/v1/”:): {\displaystyle 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}|\leq {\frac {f(x_{n})}{m}}$ dla wszystkich $n$

$|{\overline {x}}-x_{n}|\leq {\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.

Przykład

Za pomocą metody Newtona można obliczyć dowolnie dokładnie ${\sqrt {a}},a\in {\mathbb {R}}^{+}$:

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

Funkcja f(x):

$f(x)=x^{2}-a$

$f\,'(x)=2x$

$x_{n+1}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}$

$x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)$

Niech a=2 i $x_{0}=1,5$.

Wtedy:

$x_{1}=0,5(1,5+1,(3))=1,416666(...)$

Niech a=2 i $x_{0}=1,4$.

Wtedy:

$x_{1}=0,5(1,4+1,42857(...))=1,414285(...)$

Zobacz też

Inne metody rozwiązywania równań nieliniowych:

• metoda bisekcji
• metoda siecznych
• algorytm Illinois

Linki zewnętrzne

• Metoda Newtona (ang.) w encyklopedii MathWorld