Jak komputer liczy pierwiastek?

Question

W szkole uczą ,że pierwiastki liczy się.. no właśnie, niewiadomo. Po prostu każdy wie, że pierwiastek z 81 to 9, a ze 100 to 10. Człowiek szuka liczby, która po pomnożeniu przez siebie da równowartość liczby zapisanej w pierwiastku. A jak robi to komputer?

W C++ jest funkcja w bibliotece math.h, sqrt. Wysyłamy do niej liczbe double, a ona zwraca nam jej pierwiastek. Jak ona ten pierwiastek liczy?

Answer 1

Polecam przeczytać  https://pl.wikipedia.org/wiki/Metody_obliczania_pierwiastka_kwadratowego

Answer 2

Można liczyć z Szeregu Taylora

http://www.matematyka.pl/303369.htm

Wzór jest tez wspomniany w Wikipedii 

https://pl.wikipedia.org/wiki/Pierwiastek_kwadratowy

Answer 3

Mnie bardziej ciekawi w jaki sposób liczy pierwiastek dowolnego stopnia z dowolnej liczby... Np. pierwiastek stopnia 2.05 z liczby 1.99.

Jasne, że można tę wartość przybliżyć korzystając z metod wykorzystujących różniczki, ale czy na pewno tę metodę zastosuje procesor?

Hej, przecież to napisali programiści przy współpracy z matematykami!

W teorii: https://pl.wikipedia.org/wiki/Algorytm_obliczania_pierwiastka_n-tego_stopnia jednak nadal potem trafiamy na problemy typu niecałkowite potęgi, które prowadzą nas znowu do niepełnych pierwiastków. Ale jakby to ziterować z odpowiednim limitem, to pewnie coś się uda wyliczyć.

Comments

Ta teoria świetnie sprawdza się w praktyce. Miałem takie fajne rzeczy na przedmiocie, zwanym "metody numeryczne". Sam przytoczyłeś link z rozwiązaniem - my na zajęciach robiliśmy to kalkulatorem, metodą Newtona-Raphsona, z wykorzystaniem macierzy.

Ale jakby to ziterować z odpowiednim limitem, to pewnie coś się uda wyliczyć.

No i tutaj tkwi sedno - należy mieć świadomość, jak dokładny wynik nas interesuje. Jeśli robisz to ręcznie, to widzisz ile miejsc po przecinku masz i które z nich są jeszcze "niestabilne".
Jeśli piszesz algorytm dla komputera, zakładasz sobie pewien mały epsilon i obliczasz błąd względny. Kiedy błąd względny < epsilon, kończysz algorytm.

---

Jak wyliczysz błąd względny, nie mając wartości odniesienia? ;) Na dokładność będzie inny wzór - wynikający ze wzoru obliczającego i zależny od ilości wykonanych iteracji. Prawdopodobnie dokładność wyznaczono doświadczalnie.

My na metodach numerycznych używamy MathCada.

Ew. wartość odniesienia do wyliczenia błędu można wyliczyć poprzez odwrócenie wzoru i porównanie tego z wartością początkową, ale wątpię, żeby to miało zastosowanie, miało sens i w ogóle było miarodajne.

---

Jak wyliczysz błąd względny, nie mając wartości odniesienia?

Przyjmując za wartość rzeczywistą wartość obliczoną w aktualnej (n) iteracji, zaś za wartość przybliżoną wartość iteracji n-1.

wartość odniesienia do wyliczenia błędu można wyliczyć poprzez odwrócenie wzoru i porównanie tego z wartością początkową

Wartość początkowa to zawsze jest bzdura, nie mogę załapać o co Ci tutaj chodzi.

A co do prowadzenia zajęć, to sam prowadzący przyznał, że powinny to być laborki przy oprogramowaniu matematycznym lub ewentualnie jakimś IDE, ale cóż... Wydział oszczędza, ćwiczenia rachunkowe są tańsze.

---

Wartość początkowa przed jakiejkolwiek iteracją. Wartość, którą chcemy policzyć. No ale tak, to ma sens z tym błędem względnym.

Answer 4

http://stackoverflow.com/questions/4541130/definitions-of-sqrt-sin-cos-pow-etc-in-cmath