Metody numeryczne

1. Szybkie podnoszenie do potęgi

Jest to metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi O(logn), gdzie n oznacza wykładnik obliczanej potęgi.

Algorytm szybkiego potęgowania jest konsekwencją tego, że aby obliczyć wartość x^k wystarczy znać x^⌊k/2⌋, a następnie w zależności od wykładnika k.

Przykładowo, aby obliczyć 3¹³ wystarczy znać wartość x=3⁶, następnie policzyć y = x²=3¹² i wynik wynosi y*3. W ten sposób aby przejść od 3⁶ do 3¹³ wystarczy wykonać dwa mnożenia zamiast 7.

Algorytm ten można zapisać w postaci prostej funkcji rekurencyjnej.

Pseudokod:

funkcja potęga(x, n)

jeżeli n = 0

zwróć 1

jeżeli n jest nieparzysta

zwróć x · potęga(x, n - 1)

w przeciwnym przypadku

a = potęga(x, n/2)

zwróć a²

Implementacja w C++ w pliku potega.cpp

1. Stabilny algorytm rozwiązywania równania kwadratowego ax² + bx + c

Klasyczna metoda rozwiązywania równania kwadratowego, nazywana algorytmem „delty” nie zawsze jest stabilna w realizacjach komputerowych. Dzieje się tak, ponieważ liczby rzeczywiste są reprezentowane w komputerze w sposób przybliżony. Przybliżenia te mogą się kumulować, powodując błędy w obliczeniach.

• Algorytmy stabilne to takie algorytmy, w których błędy obliczeń nie kumulują się.

• Algorytmy niestabilne to takie algorytmy, w których błędy obliczeń kumulują się - niewielka zmiana wartości początkowej może doprowadzić do bardzo dużych różnic w wartości końcowej.

Sposób reprezentacji liczby rzeczywistej za pomocą notacji naukowej – liczba zmiennoprzecinkowa

X=M*B^E

X-wartość liczby zmiennoprzecinkowej

M-mantysa, liczba ułamkowa należąca do przedziału <1,B)

B-podstawa systemu liczbowego, 10 dla systemu dziesiętnego

E-wykładnik/cecha, liczba całkowita

Zakres cechy ma wpływ na wielkość liczb w tej reprezentacji. Liczba cyfr przeznaczona na mantysę wpływa na dokładność obliczeń. Jeśli na mantysę przeznaczono k cyfr, to wartość mantysy zostanie zapamiętana jako zaokrąglenie liczby do k cyfr.
Przykładowo, gdy dla mantysy przeznaczymy 4 znaki, liczba 3,14159265359 zostanie zapamiętana jako 3,141.

Niedokładność algorytmu delty powstaje, gdy iloczyn 4ac jest bardzo mały w stosunku do b². Wtedy pierwiastek z delty jest w przybliżeniu równy b. Dodawanie lub odejmowanie liczb bliskich sobie może doprowadzić do utraty dokładności.

$$x1 = \frac{- b - \sqrt{\text{delta}}}{2a}$$

Odejmujemy w tym przypadku dwie liczby bliskie sobie. Zatem w zależności od znaku b w przypadkach $- b - \sqrt{\text{delta}}$ lub $- b + \sqrt{\text{delta}}$ następuje odejmowanie dwóch bliskich sobie liczb.

Stabilny algorytm rozwiązywania równania kwadratowego opiera się na wzorach Viette’a.

x1 + x2 =   − a/b x1 * x2 = c/a

Polega on na posłużeniu się wzorem na iloczyn pierwiastków, do obliczenia tego pierwiastka, którego wartość może być zaburzona błędami zaokrągleń – zależnie od znaku b.

Dla b>0: $x1 = \frac{- b - \sqrt{\text{delta}}}{2a}$; x2 = c/(a * x1).

Dla b<0: $x2 = \frac{- b + \sqrt{\text{delta}}}{2a}$; x1 = c/(a * x2).

Implementacja w C++ w pliku rownanie_kwadratowe.cpp

Bibliografia:

• http://pl.wikipedia.org

• http://www.lowkole.pl

Adam Sawicki kl.3c