Wyznacznik macierzy


Tematy pokrewne
Macierze
Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Potęgowanie macierzy
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
Wyznacznik macierzy
Rozkład LU
Rozkład LU – rozwiązywanie układu równań liniowych
Rozkład LU – macierz odwrotna
Rozkład LU – wyznacznik macierzy

Problem

Obliczyć wyznacznik macierzy kwadratowej An × 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 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. Najpierw wyznaczmy macierze minorowe:

 

 

Obliczamy wyznaczniki M. Rozwijamy je wg pierwszego wiersza. Minory macierzy o rozmiarze 2 są macierzami jednoelementowymi. Wyznacznik macierzy jednoelementowej jest równy temu elementowi:

 

M1,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 × M1,1 + (-1)3 × 2M1,2 + (-1)4 × 3M1,3

det A = M1,1 - 2M1,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
    1 2 4  
2   a2,1 a2,2 a2,4  
3   a3,1 a3,2 a3,4  
4   a4,1 a4,2 a4,4  
  wektor kolumn
  1 2 4  

numer wiersza = 2

1   a1,1 a1,2 a1,3 a1,4  
2   a2,1 a2,2 a2,3 a2,4  
3   a3,1 a3,2 a3,3 a3,4  
4   a4,1 a4,2 a4,3 a4,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.

 

Algorytm obliczania wyznacznika metodą rekurencyjną metodą rozwinięcia Laplace'a

Wejście
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
Wyjście:

Wynik działania funkcji det(n,w,WK,A) jest wartością wyznacznika

Elementy pomocnicze:
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
Lista kroków:

Funkcja rekurencyjna det(n,w,WK,A):

Parametrami funkcji są:
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 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 K08...K10  
K08:         Jeśli k = i, to kk + 1 ; pomijamy kolumnę z bieżącym wyrazem
K09:         KK[j] ← WK[k] ; przepisujemy kolumny z WK do KK pomijając bieżącą
K10:         kk + 1  
K11:     ss + 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

 

Program

Ważne:

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 dla programu:

 

3
1 2 3
6 5 4
3 7 2

 

Lazarus
// Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a
// Data   : 8.02.2011
// (C)2012 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.
Code::Blocks
// Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a
// Data   : 8.02.2011
// (C)2012 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;

}
Free Basic
' Wyznacznik wg rekurencyjnego rozwinięcia Laplace'a
' Data   : 8.02.2011
' (C)2012 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
 


List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.