Algorytm Newtona-Raphsona

Opis działania

Podczas omawiania algorytmy należy przypomnieć sobie zależności w prostokącie. Załóżmy, że figura ma pole P. Zakładając, że mamy jeden bok ma długość a to drugi wyniesie . Szczególnym przypadkiem prostokąta jest kwadrat i wtedy . W celu zbliżania do siebie wartości obu boków należy użyć średniej arytmetycznej.

Algorytm jest wykonywany w pętli. Na początku ustalamy, że bok a = P. W każdym następnym kroku poprawiamy bok a ustalając go na średnią obu boków prostokąta czyli . W ten sposób liczba a podniesiona do kwadratu coraz mniej różni się od wartości pola P. Jednak z powodu ograniczeń przechowywania danych w komputerze i dokładności obliczeń możemy nigdy nie uzyskać, że a² = P. Istnieją dwa sposoby rozwiązania tego problemu i używanie obydwu naraz jest zalecane:

1. możemy wyliczać średnią arytmetyczną n razy, w ten sposób wykonamy maksymalnie n powtórzeń
2. wartość bezwzględna różnicy dwóch kolejnych przekształceń jest nie większa od ustalonej precyzji ε. Pozwoli to na przerwanie obliczeń kiedy okaże się, że każde kolejne przybliżenie nie wnosi znaczącej różnicy do naszych obliczeń

Weźmy przykładowo liczbę P = 160, przyjmijmy, że wykonamy maksymalnie 8 kroków i skończymy obliczać kiedy ε < 0.0001:

Przerywamy obliczanie pierwiastka - podczas rozpoczynania iteracji numer 8 uzyskaliśmy, że różnica między a oraz jest ≤ 0.0001 = ε. Sprawdzamy uzyskany wynik 12.6491: (12.6491)² = 159.9997308 co faktycznie w zaokrągleniu daje 160. W przypadku gdyby ε był inny to liczba wykonanych iteracji mogłaby się zmienić.

Implementacja

Funkcja realizująca algorytm Newtona-Raphsona:

1. double sqrtNewtonRaphson(double p, double e, double i){
2.   double a = p;
3.   while(abs(a - p / a) > e && i--)
4.     a = (a + p / a) / 2;
5.   return a;
6. }

(1.)Funkcja zwraca liczbę rzeczywistą - wyliczony bok a. Jako argumenty przyjmujemy p - liczbę pierwiastkowaną, e - epsilon, dzięki temu możemy ustawiać precyzję wyliczeń oraz i - ile maksymalnie mamy wykonać iteracji. Jest to bardzo ważne, ponieważ samo poleganie na różnicy przybliżeń mogłoby spowodować nieskończoną pętle.

(2.) Przyjmujemy, że nasz bok a=p. Następnie (3.) w pętli sprawdzamy warunek czy różnica przybliżeń nie jest mniejsza/równa e oraz sprawdzamy czy możemy jeszcze wykonać iterację. Zastosowałem tutaj postdekrementacje - podczas sprawdzania aktualna wartość i jest zamieniana na wartość prawda/fałsz. Wszystko co jest różne od 0 to prawda. Po sprawdzeniu wartości zmniejszamy wartość i o 1. (4.) W pętli wyliczamy nową wartość boku. Po zakończeniu pętli while zwracamy wartość a.

Testowanie funkcji

Przykład rozpatrywany na początku artykułu możemy wywołać następująco:

1. int main () {
2.   cout << sqrtNewtonRaphson(160, 0, 8) << endl;
3.   system("pause");
4.   return 0;
5. }

Należy pamiętać, że przy zmniejszeniu ilości iteracji zmniejsza się precyzja wyniku, dlatego warto ustalać precyzje przy użyciu epsilona. Należy jednak pamiętać, aby epsilon nie był bardzo mały, ponieważ zwiększy to ilość iteracji. Z reguły im większa liczba pierwiastkowana tym więcej iteracji należy wywołać.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję main(), która wczyta parametry p - liczbę pierwiastkowaną, e - epsilon przybliżeń oraz i - ile iteracji ma wykonać program. Na ekran powinien zostać wypisany pierwiastek danej liczby. Program powinien wypisać na ekran instrukcje jaki parametr aktualnie wczytuje program - użytkownik niekoniecznie musi wiedzieć jak działa nasz program.

• Kod źródłowy Zadanie 1