Metoda Newtona-Raphsona – implementacje

Chcąc uzyskać pierwiastek kwadratowy z danej liczby najpewniej skorzystamy z funkcji sqrt() z biblioteki matematycznej i słusznie. Po co się kłopotać, gdy nie jest to konieczne. No, ale co jeśli będziemy pozbawieni możliwości 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.



O wielu innych, równie przydatnych algorytmach, przeczytasz w tej książce

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

Tak zaś prezentuje się algorytm na schemacie blokowym:

metoda newtona-raphsona - schemat blokowy
grupa wsparcia matura z informatyki

Metoda Newtona-Raphsona implementacje

C++

Java

Python

Listę zagadnień, które mogą przydać Ci się na maturze, znajdziesz w tym wpisie.

You Might Also Like
Dodaj komentarz

icon