Metoda Newtona - Polski Serwis Naukowy

Ten artykuł dotyczy wyznaczania przybliżonej wartości pierwiastka funkcji. Zapoznaj się również z: 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

Zadanie

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

Solver - to funkcja w kalkulatorach naukowych lub programach komputerowych, umożliwiająca po uprzednim wprowadzeniu równania, wyznaczenie wartości dowolnej zmiennej szukanej, gdy są dane wartości pozostałych zmiennych; bądź też wyznaczenie wartości zmiennej, przy której całe wyrażenie jest równe zeru. W niektórych przypadkach, gdy nie istnieje wzór odwrotny (nie ma możliwości przekształcenia równania), kalkulator lub program komputerowy z solverem jest jedyną drogą obliczenia szukanej wartości. Bardziej zaawansowane solvery wykorzystywane są w problemach optymalizacyjnych.
MathWorld - encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).

$\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

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

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

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

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

Odcięta (łac. abscissa) - pierwsza współrzędna w kartezjańskim układzie współrzędnych (zwanym też prostokątnym układem współrzędnych). Oznaczana jest przeważnie symbolem x, a jej oś symbolem OX.
Zbieżność, przez wiele iteracji, oznacza proces zmierzania do określonej wartości, w czasie; lub zmierzania do określonego punktu, lub wspólnego punktu widzenia, opinii lub sytuacji.

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

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

Przestrzeń unormowana – przestrzeń liniowa, dla elementów której określone jest pojęcie normy będące bezpośrednim uogólnieniem pojęcia długości wektora w przestrzeni euklidesowej. Przestrzenie unormowane pojawiają się w naturalny sposób w analizie matematycznej oraz innych działach matematyki takich jak, na przykład, rachunek prawdopodobieństwa czy równania różniczkowe. Szczególnie istotne z punktu widzenia szeroko pojętych zastosowań są przestrzenie Banacha, tzn. przestrzenie unormowane mające pewną dodatkową własność, związaną z ich strukturą metryczną. Historycznie to własnie pewne konkretne przestrzenie Banacha, które jako pierwsze pojawiły się w kręgu zainteresowań matematyków pierwszej połowy XX w., stały się podwaliną powstania abstrakcyjnej (aksjomatycznej) teorii przestrzeni unormowanych. Teoria przestrzeni unormowanych, a szczególnie teoria przestrzeni Banacha jest jedną z głównych gałęzi analizy funkcjonalnej.
Różniczka – w rachunku różniczkowym tradycyjna nazwa nieskończenie małej zmiany danej zmiennej. Przykładowo, jeśli zmienna oznaczana jest literą x, to zmiana jej wartości często oznaczana jest Δx lub, gdy zmiana powinna być mała, δx. Różniczka reprezentuje podobną zmianę, lecz nieskończenie małą. Choć nie jest to precyzyjnie sformułowane matematycznie pojęcie, to jest ono niezmiernie użyteczne intuicyjnie; istnieje przy tym wiele sposobów formalizacji tego pojęcia.

$|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 stopu

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 ( $\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ść

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.

Macierz Jacobiego – macierz zbudowana z pochodnych cząstkowych (pierwszego rzędu) funkcji, której składowymi są funkcje rzeczywiste. Nazwa pojęcia pochodzi od nazwiska niemieckiego matematyka Carla Gustawa Jacobiego, który je wprowadził (niezależnie pojęcie to badał Michaił Ostrogradski).
Zbiór otwarty – podstawowe pojęcie topologii. W przestrzeni metrycznej (a w szczególności w przestrzeni euklidesowej) jest to zbiór, który wraz z każdym swoim punktem zawiera również pewną kulę o środku w tym punkcie, tzn. taki, w którym dla każdego punktu zbioru istnieje otoczenie w całości zawarte w tym zbiorze.

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.

Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
Iloczyn skalarny – operator na przestrzeni liniowej przypisujący dwóm argumentom z tej przestrzeni rzeczywistą wartość skalarną. Czasami spotyka się również nazwę iloczyn wewnętrzny, jednak odnosi się ono zwykle do ogólniejszych iloczynów skalarnych w przestrzeniach unitarnych.

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

Równanie – forma zdaniowa postaci t1 = t2, gdzie t1,t2 są termami i przynajmniej jeden z nich zawiera pewną zmienną. Równanie jest więc formułą atomową z co najmniej jedną zmienną wolną. Term po lewej stronie znaku równości nazywa się lewą stroną równania, a term po prawej – prawą stroną równania. Szczególnym przypadkiem równania jest forma, w której jeden z termów jest stałą np. 0, czyli gdy jest postaci t1 = 0.
Miejsce zerowe – w matematyce argument funkcji, dla którego przyjmuje ona wartość zerową. Czasem miejsce zerowe nazywa się w skrócie zerem funkcji bądź jej pierwiastkiem.

Przykład

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$

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)