Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyznacznik macierzy

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy obliczyć wyznacznik macierzy kwadratowej A n × n za pomocą rozwinięcia Laplace'a.

Rozwiązanie

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:

obrazek
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
a i, j  element macierzy A  leżący w i-tym wierszu i j-tej kolumnie
M i, j minor elementu a i, 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:

obrazek

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:

obrazek

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
M 1, 1 = ( -1 ) 2 × 10 + ( -1 ) 3 × 28
M 1, 1 = 10 - 28
M 1, 1 = -18

M 1, 2 = ( -1 ) 1+1 × 6 × 2 + ( -1 ) 1+2 × 4 × 3
M 1, 2 = ( -1 ) 2 × 12 + ( -1 ) 3 × 12
M 1, 2 = 12 - 12
M 1, 2 = 0

M 1, 3 = ( -1 ) 1+1 × 6 × 7 + ( -1 ) 1+2 × 5 × 3
M 1, 3 = ( -1 ) 2 × 42 + ( -1 ) 3 × 15
M 1, 3 = 42 - 15
M 1, 3 = 27

Mając policzone wartości minorów, możemy przystąpić do wyznaczenia wyznacznika macierzy A:

det A  = ( -1 ) 1+1 × 1 × M 1, 1 + ( -1 ) 1+2 × 2 × M 1, 2 + ( -1 ) 1+3 × 3 × M 1, 3
det A  = ( -1 ) 2 × M 1, 1 + ( -1 ) 3 × 2M 1, 2 + ( -1 ) 4 × 3M 1, 3
det A  = M 1, 1 - 2M 1, 2 + 3M 1, 3
det A  = -18 - 0 + 81
det A  = 63

Możemy już przystąpić do wstępnego określenia algorytmu.

Wyznacznik macierzy A n×n  obliczamy następująco:

Jeśli n = 1, to wyznacznik macierzy jest równy wartości elementu tej macierzy, czyli:

det A 1×1 = det [ a 1 ] = a 1

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 d 1 =    0 m 1 =    0
2 d 2 =    1  = 2d 1 + 1 m 2 =    2
3 d 3 =    5  = 3d 2 + 2 m 3 =    6  = 3m 2
4 d 4 =   23 = 4d 3 + 3 m 4 =   24 = 4m 3
5 d 5 = 119 = 5d 4 + 4 m 5 = 120 = 5m 4

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 a 1, 3:

    1 2 3 4   obrazek podmacierz
    1 2 4  
2   a 2, 1 a 2, 2 a 2, 4  
3   a 3, 1 a 3, 2 a 3, 4  
4   a 4, 1 a 4, 2 a 4, 4  
  wektor kolumn
  1 2 4  

numer wiersza = 2

1   a 1, 1 a 1, 2 a 1, 3 a 1, 4  
2   a 2, 1 a 2, 2 a 2, 3 a 2, 4  
3   a 3, 1 a 3, 2 a 3, 3 a 3, 4  
4   a 4, 1 a 4, 2 a 4, 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.

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

Wejście:

n  –  określa stopień wyznacznika do obliczenia.  nN
w  – określa numer wiersza, w którym rozpoczyna się podmacierz.  wN
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

Zmienne 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. sR

Lista kroków:

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

Przykładowe programy

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 n 2 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.
C++
// 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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.