Jeśli będziemy chcieli obliczyć iloczyn macierzy rzędu 2 w zwykły
sposób
potrzebujemy do tego 8 mnożeń oraz 4 dodawania:
Algorytm Strassena pozwala na zredukowanie tej liczby.
Do zastosowania tego algorytmu wymagane jest używanie macierzy o
wymiarach będacych potęgami 2. Jeżeli macierze nie mają potęg 2 to
wykonujemy uzupełnienie 0 do najbliższej potęgi 2.
Pytanie jaki mamy zysk w tym algorytmie? Wczesniej potrzebnych było 8
mnożen oraz 4 dodawania. Tutaj potrzebujemy 7 mnożeń i 18 dodawań. Dla
małych macierzy jest to rzeczywiście nieopłacalne jednak jeśli mnożyć
będziemy macierze o większych rozmiarach zysk będzie znaczący.
Złożoność tradycyjnego
algorytmu wynosi: , a dla algorytmu
Strassena tylko .
Wynik ten można uzyskać rozwiązując odpowiednie równanie rekurencyjne:
Przykład 1
Oblicz za pomocą algorytmu Strassena
iloczyn poniższych macierzy.
Zadanie 1
Oblicz metodą Strassena i zwykłą iloczyn macierzy C = A*B
Zadanie 2 (zadanie domowe)
Napisz program, który oblicza iloczyn dwóch macierzy rzędu 2 przy
pomocy algorytmu Strassena.
Zadanie 2* (zadanie domowe dla chętnych)
Napisz program, który wczytuje liczbę n
(wymiar macierzy), dwie macierze oraz
wykonuje mnożenie tych macierzy metodą Strassena.
Algorytm Hornera
Każdy wielomian można zapisać w postaci:
Równie dobrze można go zapisać w postaci równoważnej:
Jeszcze inna, a równoważna postać zapisania tego wielomiany wygląda
następująco:
Gdybyśmy chcieli obliczać wartość wielomianu w dowolnym punkcie,
okazałoby się, że najkorzystniej jest to robić przy pomocy ostatniej z
postaci. Dzięki niej do obliczenia wartości potrzeba wykonania
najmniejszej liczby działań (mnożeń i dodawań). Bezpośrednio z tej
obserwacji wynika algorytm Hornera.
Obliczanie wartości wielomianu w punkcie
Aby obliczyć wartość wielomianu w(x) w punkcie x0,
trzeba wykonać następujące kroki:
Po wykonaniu podanych operacji od kroku n do 0, po ostatnim z nich mamy
daną wartość wielomianu w danym punkcie.
Przykład 2
Zadanie 3
Oblicz przy pomocy algorytmu Hornera wartości danych wielomianów w
punktach:
Dzielenie wielomianów
Algorytm Hornera ma również głębszą interpretację. Łatwo można bowiem
udowodnić, że jest algorytmem dzielenia wielomianu w(x) przez wielomian
(x-x0). Wystarczy porównać wpsółczynniki przy tych samych potęgach z
następujących równośći:
i wynika z tego natychmiast identyczność:
Przykład 3
Patrząc na rozwiązanie Przykładu 2 widać wyraźnie, że:
Zadanie 4
Oblicz przy pomocy algorytmu Hornera wielomiany:
Obliczanie pochodnych wielomianów
Przykład 4
Weźmy dane takie same jak w Przykładzie 2. Wtedy:
Zadanie 5
Oblicz przy pomocy algorytmu Hornera wszystkie pochodne wielomianów w
danym punkcie:
Algorytm Show-Trauba
Zadanie 6
Znajdź wzory algorytmu Show-Trauba dla q=1
Zadanie 7
Znajdź wzory algorytmu Show-Trauba dla q=n+1
Zadanie 8
Znajdź przy pomocy algorytmu Show-Trauba wszystkie pochodne wielomianu
w danym punkcie przy zadanym q:
Zadanie 9 (zadanie domowe)
Napisz program, który oblicza wartość wielomianu w punkcie przy pomocy
algorytmu Hornera.
Zadanie 9* (zadanie domowe)
Napisz program, który oblicza wartości wszystkich pochodnych wielomianu
w punkcie przy pomocy
algorytmu Show-Trauba dla pewnego ustalonego q.
, a dla algorytmu
Strassena tylko 
.
