Obliczanie pierwiastka kwadratowego

Realizacja algorytmu w programie – metoda Newtona‑Raphsona

Algorytm „liczenia w słupku” należy do metod dokładnych, których implementacja jest czasochłonna i wymaga zaangażowania dużej ilości pamięci obliczeniowej komputera. W sytuacji gdy nie zależy nam na precyzyjnym wyniku, optymalną decyzją jest wybór metody przybliżonejmetoda przybliżonametody przybliżonej. Jedną z nich jest metoda Newtona‑Raphsona.

Przeanalizujmy przedstawioną specyfikację oraz pseudokod, a następnie zapoznajmy się z opisem całego algorytmu.

Specyfikacja problemu:

Dane:

• a – liczba podpierwiastkowa; pole kwadratu, którego długość boku jest poszukiwanym pierwiastkiem; nieujemna liczba rzeczywista

• epsilon – bezwzględna wartość różnicy pomiędzy bokami prostokąta o polu powierzchni a, po której osiągnięciu przerywamy dalsze wyznaczanie pierwiastka i zwracamy ostatni otrzymany wynik; określa dokładność obliczeń; nieujemna liczba rzeczywista

Wynik:

• b – wynik pierwiastkowania liczby a dla określonej wartości zmiennej epsilon; liczba rzeczywista

a ← wprowadź liczbę
epsilon ← wprowadź liczbę
b ← a / 2
c ← a / b

dopóki |b - c| > epsilon wykonuj:
	b ← (b + c) / 2
	c ← a / b
    
zwróć b

Podstawowym założeniem omawianej metody jest fakt, że wynik pierwiastkowania danej liczby będzie taki sam jak długość boku kwadratu o polu równym pierwiastkowanej liczbie.

R1DESC1BJQTBO

Ilustracja przedstawia kwadrat. W polu kwadratu - na środku - wpisano małe a. Przy dolnym i prawym boku pierwiastek z małe a.

Zatem jeżeli chcemy obliczyć pierwiastek z a, znajdujemy bok kwadratu o polu równym a.

Poszukiwania rozpoczynamy od prostokąta o bokach długości b i c.

R17DZCXQURD2Q

Ilustracja kwadrat o dwóch dłuższych bokach. W polu kwadratu wpisani małe a. Dolny bok oznaczono jako małe c. Prawy bok jako małe b.

Wartości te są równe:

W każdym kolejnym kroku wyznaczamy bok b ze średniej arytmetycznej długości boków b i c z poprzedniego kroku.

Długość boku c uzyskujemy, dzieląc pole przez długość boku b.

Etap ten powtarzamy, aż wartość bezwzględna różnicy pomiędzy obydwoma bokami osiągnie określoną przez nas precyzję. Wtedy końcowym wynikiem pierwiastkowania będzie wartość b. Pamiętajmy jednocześnie, że im mniejsza jest wartość precyzji, tym dokładniejszy będzie końcowy rezultat.

Osiągnięcie konkretnej precyzji jest tylko jednym z dostępnych wariantów warunku zakończenia algorytmu. Dalsze wyznaczanie wartości pierwiastka b może być przerwane np. po wykonaniu zadanej maksymalnej liczby iteracji. Należy podkreślić, że te warunki niekoniecznie będą spełnione jednocześnie. Najprawdopodobniej program skończy się wówczas po wykonaniu maksymalnej liczby iteracji albo po osiągnięciu konkretnej precyzji. Pisząc program, możemy zatem zdecydować się z góry na zaimplementowanie tylko jednego z tych wariantów.

W sekcji „Symulacja interaktywna” dowiesz się, jak zrealizować omawiany algorytm za pomocą arkusza kalkulacyjnego.

Słownik