img010 (54)

15

oraz równanie A- x = b ma rozwiązanie, to znaczy istnieje wektor x*e R" taki, że A ■ x— b, to wektor x dany jest wzorem

x* =(a^t-a)'-A^T-b .    (2.6)

(2.6)

Wektor x jest w tym przypadku jedynym rozwiązaniem układu równań A - x = b .

Podstawowa z punktu widzenia analizy teoretycznej jest metoda otrzymywania rozwiązania wykorzystująca wzory Cramera. Niech dane będzie równanie (2.1). Dopełnienie algebraiczne A,y ustalonego elementu ag macierzy^ definiuje się wzorem ([2, 16])

(2.7)

Ay = (^-1) ’^+J ' det My,

gdzie My jest minorem macierzy A powstałym przez wykreślenie i-tego wiersza i y-tej kolumny.

Ma miejsce następujące twierdzenie.

Twierdzenie 2.1 (Cramera [2,16])

Równanie (2.1) (układ (2.3) n równań liniowych z n niewiadomymi) ma dokładnie jedno rozwiązanie wtedy i tylko wtedy, gdy macierz współczynników A tego układu równań jest macierzą nieosobliwą. Współrzędne wektora x rozwiązania dane są następującymi wzorami Cramera

n

(2.8)

Metoda Cramera wyznaczania rozwiązania układu równań liniowych (2.1), (2.3) przy użyciu wzorów wyznacznikowych (2.8) jest mało efektywna i przydatna w obliczeniach jedynie dla układów nie więcej niż czterech równań. Metoda ta wymaga bowiem wykonania w przybliżeniu 2 ■ (n + 1)! działań mnożenia związanych z obliczeniem występujących we wzorach (2.8) wyznaczników. Aby ocenić, jak szybko wzrasta nakład obliczeniowy związany z wykorzystaniem metody Cramera, odnotowuje się, że już dla n = 10 (układ 10 równań z dziesięcioma niewiadomymi) 2 • (« + 1)! = 2 - 11! = 79 833 600. Dla porównania, omawiana w tym rozdziale metoda eliminacji Gaussa wymaga wykonania w przybliżeniu rłi3 działań mnożenia i dzielenia dla wyznaczenia współrzędnych wektora rozwiązania układu n równań liniowych z n niewiadomymi, co dla układu n = 10 równań daje w wyniku liczbę 334 działań mnożenia i dzielenia, a więc znacznie mniej niż 2 • (n + 1)! [6, 7, 8, 19].

Całkowita liczba operacji arytmetycznych wymaganych przez algorytm obliczeniowy jest jednym z podstawowych elementów dla oszacowania jego efektywności. Efektywność obliczeniową algorytmu związaną z nakładem obliczeniowym określa się w praktyce na podstawie wymaganej do wykonania liczby działań mnożenia i dzielenia, przy czym dzielenie jest w tych oszacowaniach traktowane jako mnożenie. Czas potrzebny na wykonanie działania dodawania lub odejmowania przez procesor komputera jest znacznie krótszy, niż czas potrzebny do wykonania mnożenia lub dzielenia liczb. Liczba działań dodawania i odejmowania ma istotny wpływ na efektywność algorytmu w przypadku, gdy działania te dominują ilościowo w stosunku do liczby działań mnożenia i dzielenia.