Algorytmy, C++, Matura z informatyki - nauka i materiały.

Metoda Newtona-Raphsona C++ – implementacja

metoda newtona-raphsona c++

Chcąc uzyskać pierwiastek kwadratowy z danej liczby najpewniej skorzystamy z funkcji sqrt() z biblioteki math.h i słusznie. Po co się kłopotać, gdy nie jest to konieczne. No, ale co jeśli będziemy pozbawieni możliwośći użycia tej funkcji? No tu zaczynają się schody… Trzeba wyznaczyć ten pierwiastek na własną rękę. Na pomoc przychodzi nam metoda Newtona-Raphsona, która jest jednym ze sposobów na wyznaczenie pierwiastka.

Metoda Newtona-Raphsona – teoretycznie

Metodą Newtona-Raphsona nazywamy algorytm iteracyjny, którego zadaniem jest wyznaczenie pierwiastka kwadratowego z liczby rzeczywistej. Wykorzystując jednak ten algorytm musimy wziąć pod uwagę fakt, iż wynik niekoniecznie musi być dokładny. Wpływają na to między innymi ograniczenia typów w kompilatorze.

Działanie metody opiera się na założeniu, że bok kwadratu o polu równym liczbie, dla której wyznaczamy pierwiastek, równa się się właśnie temu pierwiastkowi.

Przykład:

Dla przykładu spróbujemy wyznaczyć pierwiastek z liczby 36. Wiem, że dla człowieka to nie problem. Wystarczy sobie na szybciutko w głowie policzyć, że √36 to 6, ale komputer tego nie wie. Musimy mu pokazać jak do tego wyniku dojść.

Krok 1

Długość pierwszego boku ustawiamy na długość równą połowie liczby 36, czyli 18, a drugi będzie się równał ilorazowi 36 przez nowopowstały bok, czyli przez 18. Drugi bok wyniesie 2. Jeśli długość pierwszego boku podniesiona do potęgi drugiej będzie równa 36 to długość tego boku jest naszym pierwiastkiem. Niestety 18*18 nie równa się 36, więc idziemy dalej.

Krok 2

Pierwszy bok tym razem będzie się równał połowie sumy dwóch poprzednich boków. (18+2)/2=10. Natomiast drugi bok tak samo jak poprzednim razem równy jest ilorazowi liczby 36 przez pierwszy bok, czyli w tym przypadku będzie to 3.6. Druga potęga liczby nie równa się 36, więc idziemy do kolejnego kroku.

Krok 3

Tutaj postępujemy tak samo jak w kroku drugim (będziemy tak robić do skutku). Pierwszy bok to (10+3.6)/2=6.8, natomiast drugi to 36/6.8=5.29412.   6.8*6.8!=36.

Krok 4

Pierwszy bok ->6.04706, drugi bok ->5.95331. Kwadrat pierwszego boku nie równa się 36.

Krok 5

Pierwszy bok ->6.00018, drugi bok ->5.99982. Kwadrat pierwszego boku nie równa się 36.

Krok 6

Pierwszy bok ->6, drugi bok ->6. Kwadrat pierwszego boku równa się 36. Koniec działania algorytmu. Wynikiem jest 6.

 

Metoda Newtona-raphsona c++

W przypadku, gdy pierwiastek z liczby jest niewymierny algorytm będzie pracować, dopóki wynik będzie spełniał założoną dokładność, a mianowicie dopóki wartość bezwzględna różnicy dwóch boków będzie liczbą większą od założonej dokładności.

 

Metoda Newtona-Raphsona – algorytm

Tak wygląda nasz algorytm w postaci pseudokodu:

pobierz liczbę
x<-liczba/2
dopóki |x-liczba/x|> ustalona dokładność wykonuj
     x=(x+liczba/x)/2
     jeżeli x*x równa się liczbie zakończ działanie pętli

zwróć x

Metoda Newtona-Raphsona C++ implementacja

 

Dodaj komentarz