Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy obliczyć wyznacznik macierzy kwadratowej A n × n za pomocą rozwinięcia Laplace'a. |
Wyznacznik (ang. determinant – oznaczany det) jest liczbą, która została skojarzona z daną macierzą kwadratową A. Rozwinięcie Laplace'a pozwala w sposób rekurencyjny policzyć wyznacznik dowolnej macierzy kwadratowej. Wzór jest następujący:
A | : | macierz kwadratowa o rozmiarze n, której wyznacznik liczymy |
i | : | ustalony wiersz macierzy A, wg którego dokonujemy rozwinięcia Laplace'a |
j | : | kolejne numery kolumn w macierzy A |
ai, j | : | element macierzy A leżący w i-tym wierszu i j-tej kolumnie |
Mi, j | : | minor elementu ai, j – jest to wyznacznik macierzy powstałej z macierzy A po usunięciu z niej i-tego wiersza i j-tej kolumny |
Powyższy wzór jest rekurencyjny, ponieważ występuje w nim Minor, który sam jest wyznacznikiem, a zatem obliczamy go za pomocą tego samego wzoru. Dla przykładu obliczmy wyznacznik macierzy:
Jako wiersz rozwinięcia wybierzemy pierwszy wiersz zawierający elementy 1, 2 i 3. Dla każdego z tych elementów musimy wyznaczyć minory:
Obliczamy wyznaczniki M. Rozwijamy je wg pierwszego wiersza. Minory macierzy o rozmiarze 2 są macierzami jednoelementowymi. Wyznacznik macierzy jednoelementowej jest równy temu elementowi:
M 1, 1 = (-1)1+1
× 5 × 2 + (-1)1+2
× 4 × 7 M1, 1 = (-1)2 × 10 + (-1)3 × 28 M1, 1 = 10 - 28 M1, 1 = -18 M1, 2 = (-1)1+1 × 6 × 2 + (-1) 1+2 × 4 × 3 M1, 2 = (-1)2 × 12 + (-1)3 × 12 M1, 2 = 12 - 12 M1, 2 = 0 M1, 3 = (-1)1+1 × 6 × 7 + (-1) 1+2 × 5 × 3 M1, 3 = (-1)2 × 42 + (-1)3 × 15 M1, 3 = 42 - 15 M1, 3 = 27 |
Mając policzone wartości minorów, możemy przystąpić do wyznaczenia wyznacznika macierzy A:
det A = (-1)1+1 × 1 ×
M1, 1
+ (-1)1+2 × 2 × M1, 2 + (-1) 1+3 × 3 ×
M1, 3 det A = (-1)2 × M 1, 1 + (-1)3 × 2M1, 2 + (-1)4 × 3M 1, 3 det A = M1, 1 - 2M 1, 2 + 3M1, 3 det A = -18 - 0 + 81 det A = 63 |
Możemy już przystąpić do wstępnego określenia algorytmu.
Wyznacznik macierzy An×n obliczamy następująco:
Jeśli n = 1, to wyznacznik macierzy jest równy wartości elementu tej macierzy, czyli:
det A1×1 = det [a1] = a1
Dla n > 1 wybieramy dowolny wiersz lub kolumnę (najlepiej taki, w którym jest najwięcej zer). Następnie każdy wyraz tego wiersza lub kolumny przemnażamy przez wyznacznik macierzy, która powstaje przez usunięcie wiersza i kolumny z mnożonym wyrazem (wyznacznik ten obliczamy rekurencyjnie tą samą metodą). Jeśli suma numeru wiersza i kolumny mnożonego wyrazu jest nieparzysta, to otrzymany iloczyn mnożymy dodatkowo przez -1. Wyliczone iloczyny sumujemy otrzymując wartość wyznacznika.
Klasa złożoności obliczeniowej podanej metody jest równa O (n!).
Dokonajmy prostej analizy. Wyznacznik wyliczamy mnożąc kolejne wyrazy wiersza
(lub kolumny) przez wartości wyznaczników niższego poziomu i sumując
otrzymane iloczyny (dochodzi jeszcze ewentualna zmiana znaku).
Zatem dla wyznacznika n-tego poziomu musimy wyliczyć n
wyznaczników poziomu
(n-1). Czyli:
ilość mnożeń = n × ilość mnożeń dla wyznacznika poziomu n - 1
ilość dodawań = n × ilość dodawań dla wyznacznika
poziomu n - 1 = (n - 1) dodawań iloczynów
W poniższej tabeli wyliczyliśmy ilości mnożeń i dodawań dla kilku kolejnych
wartości n.
Złożoność obliczeniowa operacji wyliczania wyznacznika macierzy |
||
---|---|---|
n | Ilość dodawań | ilość mnożeń |
1 | d1 = 0 | m1 = 0 |
2 | d2 = 1 = 2d1 + 1 | m2 = 2 |
3 | d3 = 5 = 3d2 + 2 | m3 = 6 = 3m2 |
4 | d4 = 23 = 4d3 + 3 | m4 = 24 = 4m3 |
5 | d5 = 119 = 5d4 + 4 | m5 = 120 = 5m4 |
Widać wyraźnie, iż od wartości n = 2 ilość mnożeń jest równa n!, a ilość dodawań jest równa n! - 1. Prowadzi to do bardzo szybkiego wzrostu czasu wykonania algorytmu.
Pozostaje drobna kwestia techniczna. W algorytmie obliczamy wyznaczniki macierzy, które powstają przez usunięcie z macierzy głównej wiersza i kolumny z elementem mnożącym. Aby uniknąć kopiowania elementów, do algorytmu wyliczającego wyznacznik będziemy przekazywali wektor numerów kolumn, w którym umieścimy kolejne numery kolumn zawarte w tej podmacierzy oraz numer pierwszego wiersza. Na przykład w poniższej macierzy chcemy wyliczyć wyznacznik wg elementu a1, 3:
1 | 2 | 3 | 4 | podmacierz
|
wektor kolumn
numer wiersza = 2 |
||||||||||||||||||||||||||||||||||
1 | a1, 1 | a1, 2 | a1, 3 | a1, 4 | |||||||||||||||||||||||||||||||||||
2 | a 2, 1 | a 2, 2 | a2, 3 | a 2, 4 | |||||||||||||||||||||||||||||||||||
3 | a 3, 1 | a 3, 2 | a3, 3 | a 3, 4 | |||||||||||||||||||||||||||||||||||
4 | a 4, 1 | a 4, 2 | a4, 3 | a 4, 4 |
Dane te jednoznacznie określą podmacierz, której wyznacznik należy wyliczyć. Zwróć uwagę, iż wektor kolumn zawiera tyle elementów, ile wynosi stopień wyznacznika. Numer wiersza zawsze będzie numerem o 1 większym od wiersza zawierającego mnożony przez wyznacznik element. Do elementów podmacierzy będziemy się odwoływać zawsze poprzez wektor kolumn.
n | : | określa stopień wyznacznika do obliczenia. n ∈ N |
w | : | określa numer wiersza, w którym rozpoczyna się podmacierz. w ∈ N |
WK | : | wektor kolumn. Zawiera numery kolumn z macierzy głównej, które zawiera podmacierz. WK zawiera tyle numerów kolumn, ile wynosi stopień wyznacznika. Elementy ∈ N i są numerowane od 0. |
A | : | macierz, której wyznacznik liczymy. Wiersze i kolumny są numerowane od zera. A ∈ R |
Wynik działania funkcji det (n, w, WK, A) jest wartością wyznacznika
i, j, k | : | zmienne pomocnicze dla pętli i, j, k ∈ N |
m | : | mnożnik iloczynu wyrazu macierzy przez wyznacznik podmacierzy. Przyjmuje na przemian wartości 1 oraz (-1), m ∈ C. |
KK | : | wektor kolumn umożliwiający rekurencyjne przekazywanie numerów kolumn podmacierzy, dla których liczone są wyznaczniki. Elementami wektora kolumn są liczby całkowite. Elementy ∈ C i są numerowane od zera. Wektor KK ma o jeden element mniej niż wektor WK otrzymany na wejściu. |
s | : | zlicza sumę iloczynów wyrazów wiersza przez wyznaczniki niższych stopni. s ∈ R |
Funkcja rekurencyjna det (n, w, WK, A): | ||
n | : | stopień podmacierzy – przekazywane przez wartość |
w | : | bieżący wiersz macierzy głównej, w którym rozpoczyna się podmacierz – przekazywane przez wartość |
WK | : | wektor kolumn o n elementach – przekazanie przez referencję |
A | : | macierz podstawowa – przekazanie przez referencję |
K01: | Jeśli n = 1, to zakończ z wynikiem A [w][WK [0]] |
sprawdzamy zakończenie rekurencji – zwracamy wynik funkcji |
K02: | Utwórz wektor KK o n-1 elementach | tworzymy tablicę dynamiczną |
K03: | s ← 0 | przygotowujemy się do sumowania iloczynów wyrazów przez minory |
K04: | m ← 1 | mnożnik (-1)i+j |
K05: | Dla i = 0, 1, …,
n - 1: wykonuj kroki K06…K12 |
rozpoczynamy pętlę obliczającą rekurencyjnie rozwinięcie Laplace'a |
K06: | k ← 0 | przygotowujemy wektor kolumn dla wywołania rekurencyjnego |
K07: | Dla j
= 0, 1, …, n - 2: wykonuj kroki K08…K10 |
|
K08: | Jeśli k = i, to k ← k + 1 |
pomijamy kolumnę z bieżącym wyrazem |
K09: | KK [j] ← WK [k] | przepisujemy kolumny z WK do KK pomijając bieżącą |
K10: | k ← k + 1 | |
K11: | s ← s + m × A [w][WK [i] ] × det (n - 1, w + 1, KK, A) | wywołanie rekurencyjne |
K12: | m ← (- m) | następny mnożnik (-1)i+j |
K13: | Usuń wektor KK | tablica dynamiczna przestaje być potrzebna, zwalniamy pamięć |
K12: | Zakończ z wynikiem s | wynik funkcji |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program wczytuje dane definiujące macierz A i oblicza jej wyznacznik. Pierwszą daną powinien być stopień n macierzy A, n > 0 – nie jest ograniczony, lecz nie powinien być zbyt duży (do 10) z uwagi na klasę złożoności O (n!). Następne n2 liczb określają kolejne elementy macierzy, wczytywane wierszami. |
Dane przykładowe (przekopiuj do schowka i
wklej do okna konsoli):
3 1 2 3 6 5 4 3 7 2 |
Pascal// Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a // Data : 8.02.2011 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; // deklaracje typów dynamicznych type NInt = array of integer; // typ wektora kolumn NReal = array of double; // typ wierszy MReal = array of NReal; // typ typ tablicy dynamicznej // Rekurencyjna funkcja obliczająca rozwinięcie Laplace'a //------------------------------------------------------- function det (n, w : integer; var WK : NInt; var A : MReal) : double; var i, j, k, m : integer; s : double; KK : NInt; begin if n = 1 then // sprawdzamy warunek zakończenia rekurencji det := A [w][WK [0]] // macierz 1 x 1, wyznacznik równy elementowi else begin SetLength (KK, n - 1); // tworzymy dynamiczny wektor kolumn s := 0; // zerujemy wartość rozwinięcia m := 1; // początkowy mnożnik for i := 0 to n - 1 do // pętla obliczająca rozwinięcie begin k := 0; // tworzymy wektor kolumn dla rekurencji for j := 0 to n - 2 do // ma on o 1 kolumnę mniej niż WK begin if k = i then inc (k); // pomijamy bieżącą kolumnę KK [j] := WK [k]; // pozostałe kolumny przenosimy do KK inc (k); end; s := s + m * A [w][WK [i]] * det (n - 1, w + 1, KK, A); m := -m; // kolejny mnożnik end; SetLength (KK, 0); // usuwamy zbędną już tablicę dynamiczną det := s; // ustalamy wartość funkcji end; end; //*** PROGRAM GŁÓWNY *** //---------------------- var n, i, j : integer; // stopień macierzy WK : NInt; // wektor kolumn A : MReal; // macierz begin read (n); // odczytujemy stopień macierzy SetLength (A, n); // tworzymy macierz wskaźników for i := 0 to n - 1 do begin SetLength (A [i], n); // tworzymy wiersz for j := 0 to n - 1 do // czytamy wiersz macierzy read (A [i][j]); end; SetLength (WK, n); // tworzymy wiersz kolumn for i := 0 to n - 1 do // wypełniamy go numerami kolumn WK [i] := i; writeln; writeln(det (n, 0, WK, A):0:4); // obliczamy i wyświetlamy wyznacznik SetLength (WK, 0); // usuwamy tablice dynamiczne for i := 0 to n - 1 do SetLength (A [i], 0); SetLength (A, 0); end. |
// Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a // Data : 8.02.2011 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> #include <iomanip> using namespace std; // Rekurencyjna funkcja obliczająca rozwinięcie Laplace'a //------------------------------------------------------- double det (int n, int w, int * WK, double ** A) { int i, j, k, m, * KK; double s; if(n == 1) // sprawdzamy warunek zakończenia rekurencji return A [w][WK [0]]; // macierz 1 x 1, wyznacznik równy elementowi else { KK = new int [n - 1]; // tworzymy dynamiczny wektor kolumn s = 0; // zerujemy wartość rozwinięcia m = 1; // początkowy mnożnik for(i = 0; i < n; i++) // pętla obliczająca rozwinięcie { k = 0; // tworzymy wektor kolumn dla rekurencji for(j = 0; j < n - 1; j++) // ma on o 1 kolumnę mniej niż WK { if(k == i) k++; // pomijamy bieżącą kolumnę KK [j] = WK [k++]; // pozostałe kolumny przenosimy do KK } s += m * A [w][WK [i]] * det (n - 1, w + 1, KK, A); m = -m; // kolejny mnożnik } delete [] KK; // usuwamy zbędną już tablicę dynamiczną return s; // ustalamy wartość funkcji } } //*** PROGRAM GŁÓWNY *** //---------------------- int main() { int n, i, j; // stopień macierzy int * WK; // wektor kolumn double ** A; // macierz cout << fixed << setprecision (4); cin >> n; // odczytujemy stopień macierzy A = new double * [n]; // tworzymy macierz wskaźników for(i = 0; i < n; i++) { A [i] = new double [n]; // tworzymy wiersz for(j = 0; j < n; j++) cin >> A [i][j]; // czytamy wiersz macierzy } WK = new int [n]; // tworzymy wiersz kolumn for(i = 0; i < n; i++) // wypełniamy go numerami kolumn WK [i] = i; cout << endl; cout << det (n, 0, WK, A) << endl; // obliczamy i wyświetlamy wyznacznik delete [] WK; // usuwamy tablice dynamiczne for(i = 0; i < n; i++) delete [] A [i]; delete [] A; } |
Basic' Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a ' Data : 8.02.2011 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- ' Rekurencyjna funkcja obliczająca rozwinięcie Laplace'a '------------------------------------------------------- Function det (n As Integer, w As Integer, WK As Integer Ptr, A As Double Ptr Ptr) As Double Dim As Integer i, j, k, m Dim As Double s Dim KK As Integer Ptr If n = 1 Then ' sprawdzamy warunek zakończenia rekurencji return A [w][WK [0]] ' macierz 1 x 1, wyznacznik równy elementowi Else KK = New Integer [n - 1] s = 0 ' zerujemy wartość rozwinięcia m = 1 ' początkowy mnożnik For i = 0 To n - 1 ' pętla obliczająca rozwinięcie k = 0 ' tworzymy wektor kolumn dla rekurencji For j = 0 To n - 2 ' ma on o 1 kolumnę mniej niż WK If k = i Then k += 1 ' pomijamy bieżącą kolumnę KK [j] = WK [k] ' pozostałe kolumny przenosimy do KK k += 1 Next s += m * A [w][WK [i]] * det (n - 1, w + 1, KK, A) m = -m ' kolejny mnożnik Next det = s ' ustalamy wartość funkcji Delete [] KK End If End Function Dim As Integer n, i, j ' stopień macierzy Open Cons For Input As #1 Input #1, n ' odczytujemy stopień macierzy Dim A As Double Ptr Ptr ' tworzymy macierz dynamiczną A = New Double Ptr [n] For i = 0 To n - 1 A [i] = New Double [n] For j = 0 To n - 1 ' czytamy wiersz macierzy Input #1, A [i][j] Next Next Close #1 Dim WK As Integer Ptr ' tworzymy wiersz kolumn WK = New Integer [n] For i = 0 To n - 1 ' wypełniamy go numerami kolumn WK [i] = i Next Print det (n, 0, WK, A) ' obliczamy i wyświetlamy wyznacznik For i = 0 To n - 1 ' usuwamy tablice dynamiczne Delete [] A [i] Next Delete [] A Delete [] WK End |
Wynik: |
3 1 2 3 6 5 4 3 7 2 63.0000 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.