Strona główna » Algorytmy » Artykuły » Wyznacznik Macierzy
1011
 

Wyznacznik Macierzy

https://mattomatti.com/a0012
· część 1 · część 2 · część 3 · Wyznacznik ·

Definicja

Niech będzie dana macierz kwadratowa A stopnia n.

Wyznacznikiem nazywamy, takie odwzorowanie, które danej macierzy An×n przyporządkowuje dokładnie jedną liczbę rzeczywistą det(A).

Wyliczanie

Dla macierzy A stopnia 1 wyznacznikiem jest jego jedyna wartość. Dla macierzy stopnia 2 i 3 istnieją wzory, ale najwygodniejszym sposobem jest Rozwinięcie Laplace’a, które upraszcza macierz dowolnego stopnia do macierzy dowolnego stopnia.

W uproszczeniu mówi o tym, że wyznacznik można policzyć w sposób rekurencyjny. Rozwijając wyznacznikiem względem wiersza należy dla każdego wiersza należy wykonać to samo. Dla i-tego wiersza: pobrać pierwszy element, pomnożyć go przez -1 podniesione do potęgi będącą sumą współrzędnych pobranego elementu, a następnie pomnożyć przez dopełnienie algebraiczne pobranego elementu. W tym przypadku jest to pomnożenie przez wyznacznik macierzy z wykreśloną pierwszą kolumną i bez i-tego wiersza.

Przykład

Weźmy macierz stopnia 3:

(1)(6·1 - 4·6) + (-5)(2·1 - 3·4) + (3)(2·6 - 3·6) = (-18) + 50 + (-18) = 14

Implementacja

Kod zamieszczony poniżej został oparty o rozwijaną bibliotekę matrix.h, która posiada już odpowiednie funkcje do między innymi wczytywania / usuwania macierzy co powinno ułatwić skupienie się tylko na rozwiązywanym problemie.

Jak pewnie można zauważyć algorytm można zaimplementować przy pomocy dwóch funkcji: jedna z nich będzie służyć do wyliczania wyznacznika, a druga będzie funkcją pomocniczą, która będzie przygotowywać kolejne dopełnienia algebraiczne.

Dopełnienie algebraiczne

Funkcja, która będzie tworzyć dopełnienie będzie przyjmować trzy argumenty: mat - wskaźnik na macierz typu Matrix oraz pozycję elementu w zmiennych remx i remx. Funkcja ta nie sprawdza poprawności wprowadzonych danych.

  1. Matrix* copyPartOfMatrix(Matrix* mat, int remx, int remy) {
  2.   Matrix* matrix = new Matrix();
  3.   matrix->n = mat->n - 1;
  4.   matrix->m = mat->m - 1;
  5.   double** table = new double*[matrix->n];
  6.   for (int i = 0, ipos = 0; i < mat->n; i++) {
  7.     if (i != remy) {
  8.       double* row = new double[matrix->m];
  9.       for (int j = 0, jpos = 0; j < mat->m; j++) {
  10.         if (j != remx) {
  11.           row[jpos] = mat->data[i][j];
  12.           jpos++;
  13.         }
  14.       }
  15.       table[ipos] = row;
  16.       ipos++;
  17.     }
  18.   }
  19.   matrix->data = table;
  20.   return matrix;
  21. }

(2.) Utwórz nową macierz i (3. - 4.) wskaż, że ma o jeden wiersz i kolumnę mniej niż macierz pierwotna. (5.) Zadeklaruj nową tablicę danych. (6.) Rozpocznij przepisywanie wierszy. Potrzebne są tutaj dwa liczniki: i oraz ipos. Pierwszy z nich przechodzi po kolejnych elementach tablicy wiersza pierwotnego, a druga po wierszach nowej macierzy. W ten sposób istnieje możliwość pominięcia przepisywania jednego wybranego wiersza. (7.) Jeśli wybrany wiersz ma nie być przepisywany to go pomiń. Wtedy zwiększony zostanie indeks i, ale nie ipos. (8. - 13.) Analogiczne rozumowanie dla przepisywanych wartości do wiersza.

Wyznaczanie wyznacznika

Funkcja wyznacznik() będzie przyjmować tylko jeden argument mat, którym jest wskaźnik na macierz typu Matrix. (2.) Na początek funkcja upewnia się, że macierz jest kwadratowa i jeśli nie to (3.) zwraca wyjątek.

  1. double wyznacznik(Matrix* mat) {
  2.   if (mat->m != mat->n)
  3.     throw "Macierz nie jest kwadratowa";
  4.   if (mat->m == 1)
  5.     return mat->data[0][0];
  6.   double w = 0;
  7.   for (int i = 0; i < mat->n; i++) {
  8.     Matrix* cmatrix = copyPartOfMatrix(mat, 0, i);
  9.     w += pow(-1, i + 1) * mat->data[i][0] * wyznacznik(cmatrix);
  10.     deleteMatrix(cmatrix);
  11.   }
  12.   return w;
  13. }

Rekurencja wymaga warunku stopu bez, którego rekurencja jest nieskończona. (3.) W tym przypadku jest to sprawdzenie czy macierz jest stopnia 1 i jeśli tak to (4.) zwrócenia wartości jej wyznacznika. Jeśli jednak macierz jest większa to przygotowujemy się do jej dzielenia. (5.) Deklarujemy zmienną, która będzie sumować kolejne wartości z każdej iteracji: (6. - 10.) Dla każdego wiersza; (7.) utwórz dopełnienie algebraiczne względem elementu ai + 1, 1, (8.) wylicz wartość dodawaną do aktualnej wartości wyznacznika i (9.) usuń tymczasową macierz. Na koniec (11.) zwróć wartość zmiennej w.

Testowanie funkcji

Poniżej znajduje się funkcja main(), która wczytuje od użytkownika macierz, a następnie wypisuje jej wyznacznik. W przypadku błędu zostaje on wypisany na konsolę.

  1. int main () {
  2.   Matrix* mat = readMatrix();
  3.   try {
  4.     cout << "Wyznacznik: " << wyznacznik(mat) << endl;
  5.   } catch (const char* msg) {
  6.     cout << msg << endl;
  7.   }
  8.   deleteMatrix(mat);
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz funkcję pokazObliczenia(), która wypisze postać równania po ostatnim uproszczeniu, ale bez jeszcze nie wyliczonego żadnego jej fragmentu. Przykładowo dla macierzy:

poprawnym wynikiem jest:

  1. (-1)(6) + (2)(5)