Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2022 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
Metoda Newtona ( ang. Newton's method ) polega na kolejnych przybliżeniach pierwiastka funkcji przez wyznaczanie przecięć stycznej do wykresu funkcji z osią OX. Z tego powodu, podobnie jak w metodzie siecznych, warunki początkowe są następujące:
Na osi OX wybieramy pewien przedział [a,b] o następujących własnościach:
Dodatkowo w przedziale [a,b] pierwsza pochodna funkcji jest różna od zera. Warunek ten gwarantuje nam, iż w tym przedziale funkcja nie posiada minimum/maksimum lokalnego, a co za tym idzie jej styczna nie będzie równoległa do osi OX, ponieważ algorytm bazuje na znajdowaniu punktów przecięcia stycznych z osią OX.
Wyjdźmy od wzoru na punkty przecięcia siecznych z osią OX, który wyprowadziliśmy w metodzie siecznych:
Przekształćmy ten wzór następująco:
We wzorze otrzymaliśmy odwrotność ilorazu różnicowego funkcji f(). Policzmy granicę tego ułamka, gdy xn - 2 zmierza do xn - 1:
W granicy otrzymamy odwrotność pierwszej pochodnej funkcji w punkcie poprzednio wyznaczonym. Otrzymujemy zatem wzór na kolejne przybliżenie pierwiastka funkcji:
Wzór ten nosi nazwę wzoru Newtona. Jest on bardzo prosty, jednakże wymaga znajomości pierwszej pochodnej funkcji.
Gdy punkt xn - 2 zbliża się do punktu xn - 1, to sieczna staje się styczną do wykresu funkcji w punkcie xn - 1. W metodzie Newtona potrzebujemy tylko jednego punktu startowego w przedziale [a,b]. Zasada działania tej metody jest następująca:
W przedziale [a,b] spełniającym warunki początkowe wybieramy dowolny punkt startowy x0:
Za pomocą wzoru Newtona wyznaczamy punkt przecięcia stycznej w punkcie (x0,f(x0)) z osią OX:
Sprawdzamy teraz, czy wartość funkcji w wyliczonym punkcie x1 jest dostatecznie bliska zeru. Jeśli tak, to kończymy. Jeśli nie, to całą procedurę powtarzamy dla x1, wyznaczając kolejny punkt x2:
Sprawdzamy, czy funkcja w punkcie x2 jest dostatecznie bliska zeru. Jeśli tak, to kończymy. Jeśli nie, wyliczamy następne punkty x3, x4, ... , xn, aż warunek będzie spełniony lub zostanie przekroczony limit aproksymacji.
Kolejne punkty x i leżą coraz bliżej pierwiastka funkcji. Metoda Newtona jest zwykle szybko zbieżna. Odległości pomiędzy kolejnymi dwoma punktami x i - 1 i x i maleje. Gdy spadnie poniżej dokładności wyznaczania pierwiastka, obliczenia można przerwać. Wynika z tego, iż w metodzie Newtona obliczenia kończymy w trzech przypadkach:
Wadą metody Newtona jest konieczność wyliczania pierwszej pochodnej w każdym obiegu aproksymacji pierwiastka.
εx | – | dokładność przybliżenia pierwiastka |
εy | – | dokładność przybliżenia do zera |
x0 | – | początkowe przybliżenia pierwiastka |
f | – | funkcja, której pierwiastek będzie obliczany |
f ' | – | pochodna funkcji |
n | – | maksymalna liczba aproksymacji |
x0 | – | przybliżony pierwiastek funkcji |
x1 | – | poprzednia wartość x0 |
f0 | – | wartość funkcji w punkcie x0 |
f1 | – | wartość pierwszej pochodnej w punkcie x0 |
K01: | n ← n - 1 | Zmniejszamy licznik obiegów |
K02: | Jeśli n = 0, to zakończ z błędem |
Sprawdzamy trzeci warunek zakończenia |
K03: | f0 ← f ( x0 ) | Obliczamy wartość funkcji w punkcie x0 |
K04: | Jeśli | f0 | < εy, to zakończ |
Sprawdzamy pierwszy warunek zakończenia |
K05: | f1 ← f '( x0) | Obliczamy wartość pierwszej pochodnej |
K06: | x1 ← x0 | Zapamiętujemy x0 |
K07: | ![]() |
Wyznaczamy kolejne przybliżenie pierwiastka |
K08: | Jeśli | x1 - x0
| < εx, to zakończ |
Sprawdzamy drugi warunek zakończenia |
K09: | Idź do kroku K01 | Kontynuujemy obliczenia |
Poniższy program jest przykładową realizacją algorytmu Newtona. Program oblicza pierwiastek funkcji:
Wzór jej pochodnej jest następujący ( nie wyprowadzamy tego wzoru, metody obliczania pochodnych powinieneś poznać na matematyce. Dobrą alternatywą jest opanowanie MathCAD'a ):
Wykres tej funkcji w przedziale [-3,1] jest następujący:
Z wykresu wynika, iż pierwiastek znajduje się w przedziale [-1,1 , -1]. Jako przybliżenia początkowe wybieramy x0 = -1.
Przykładowy program w języku C++
// Pierwiastek funkcji - metoda Newtona // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //------------------------------------------ #include <iostream> #include <cmath> #include <iomanip> using namespace std; // Tutaj definiujemy funkcję, której pierwiastek jest wyliczany //------------------------------------------------------------- double f(double x) { return sin(x*x-x+1/3.0)+0.5*x; } // Tutaj definiujemy pochodną funkcji //----------------------------------- double df(double x) { return cos(x*x-x+1/3.0)*(2*x-1)+0.5; } // Tutaj definiujemy parametry początkowe double epsx = 1e-14; // Dokładność wyznaczania pierwiastka double epsy = 1e-14; // Dokładność wyznaczania zera double x0 = -1; // Punkt startowy int n = 64; // Maksymalna liczba obiegów // Program główny //--------------- int main() { // Zmienne double f0,f1,x1; bool result = false; setlocale(LC_ALL,""); cout << setprecision(15) << fixed; cout << "Obliczanie przybliżonego pierwiastka funkcji metodą Newtona" << endl << "-----------------------------------------------------------" << endl << endl; while(--n) { // Obliczamy wartość funkcji w punkcie x0 f0 = f(x0); // Sprawdzamy, czy funkcja jest dostatecznie bliska zeru if(fabs(f0) < epsy) { result = true; break; } // Obliczamy wartość pierwszej pochodnej funkcji f1 = df(x0); // Zapamiętujemy bieżące przybliżenie x1 = x0; // Obliczamy kolejne przybliżenie x0 -= f0/f1; // Sprawdzamy, czy odległość pomiędzy dwoma ostatnimi przybliżeniami // jest mniejsza od założonej dokładności if(fabs(x1 - x0) < epsx) { result = true; break; } // Kontynuujemy obliczenia } if(!result) cout << "Zakończono z błędem!" << endl << endl; cout << "Pierwiastek x0 = " << setw(18) << x0 << endl << "Wartość funkcji f(x0) = " << setw(18) << f0 << endl << "Dokładność dla x epsx = " << setw(18) << epsx << endl << "Dokładność dla y epsy = " << setw(18) << epsy << endl << "Liczba obiegów n = " << 64 - n; cout << endl << endl; return 0; } |
Wynik |
Obliczanie przybliżonego pierwiastka
funkcji metodą Newtona ----------------------------------------------------------- Pierwiastek x0 = -1.077713513691340 Wartość funkcji f(x0) = -0.000000000000001 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów n = 5 |
Porównaj otrzymany wynik z czterema poprzednimi metodami:
Obliczanie przybliżonego pierwiastka funkcji metodą
bisekcji ------------------------------------------------------------ Pierwiastek x0 = -1.077713513691339 Wartość funkcji f(x0) = 0.000000000000002 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów i = 44 |
Obliczanie przybliżonego pierwiastka funkcji metodą
regula falsi ---------------------------------------------------------------- Pierwiastek x0 = -1.077713513691339 Wartość funkcji f(x0) = 0.000000000000001 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów = 9 |
Obliczanie przybliżonego pierwiastka funkcji metodą
siecznych ------------------------------------------------------------- Pierwiastek xn = -1.077713513691340 Wartość funkcji f(xn) = 0.000000000000000 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów = 5 |
Obliczanie przybliżonego pierwiastka funkcji metodą
Mullera ----------------------------------------------------------- Pierwiastek x3 = -1.077713513691340 Wartość funkcji f(x3) = 0.000000000000000 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów n = 4 |
Z powyższego porównania wynika, że metoda Newtona przegrywa z metodą Mullera. Jednak dokładna analiza numeryczna pokazuje, że w przypadku ogólnym metoda Newtona jest najszybsza z opisanych wcześniej metod. Jej podstawową wadą jest konieczność obliczania wartości pierwszej pochodnej funkcji w każdym obiegu aproksymacyjnym.
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2022 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.