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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyznacznik macierzy

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy obliczyć wyznacznik macierzy kwadratowej An×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:

det A

n

Σ

j=1

(-1)i+j×ai,j×Mi,j

A : macierz kwadratowa o rozmiarze n, której wyznacznik liczymy; n ∈ N, A ∈ R.
i : ustalony wiersz macierzy A, wg którego dokonujemy rozwinięcia Laplace'a; i ∈ C.
j : kolejne numery kolumn w macierzy A; j ∈ C.
ai,j : element macierzy A leżący w i-tym wierszu i j-tej kolumnie; ai,j ∈ R.
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; Mi,j ∈ R.

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:

A =
 
1 2 3
6 5 4
3 7 2
 
   
   

Jako wiersz rozwinięcia wybierzemy pierwszy wiersz zawierający elementy 1, 2 i 3. Dla każdego z tych elementów musimy wyznaczyć minory:

M1,1 = det
 
5 4
7 2
 
   
M1,2 = det
 
6 4
3 2
 
   
M1,3 = det
 
6 5
3 7
 
   

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
 

obrazek
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 ∈ C.
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 ∈ C 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 : Elementy pomocnicze dla pętli; i,j,k ∈ C.
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):
  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, ; sprawdzamy zakończenie rekurencji – zwracamy wynik funkcji
     to zakończ z wynikiem A[w][WK[0]]
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:    ; rozpoczynamy pętlę obliczającą rekurencyjnie
     wykonuj kroki K06…K12 ; 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, ; pomijamy kolumnę z bieżącym wyrazem
         to kk+1
K09:     KK[j] ← WK[k] ; przepisujemy kolumny z WK do KK pomijając bieżącą
K10:     kk+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 n2 liczb określaja 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); // 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; // 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 ' 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) ' wyznacznik

For i = 0 To n-1 ' usuwamy tablice dynamiczne
  Delete [] A[i]
Next
Delete [] A
Delete [] WK

End
Python (dodatek)
# Wyznacznik wg rekurencyjnego
# rozwinięcia Laplace'a
# Data 20.04.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

# Rekurencyjna funkcja obliczająca
# rozwinięcie Laplace'a
#---------------------------------

def det(n,w,WK,A):
    if(n == 1): # sprawdzamy warunek zakończenia rekurencji
        return A[w][WK[0]] # macierz 1 x 1
                           # wyznacznik równy elementowi
    else:
        KK = [0] * (n-1) # tworzymy dynamiczny wektor kolumn
        s = 0 # zerujemy wartość rozwinięcia
        m = 1 # początkowy mnożnik
        for i in range(n): # pętla obliczająca rozwinięcie
            k = 0 # tworzymy wektor kolumn dla rekurencji
            for j in range(n-1): # ma on o 1 kolumnę mniej niż WK
                if k == i: k += 1 # pomijamy bieżącą kolumnę
                KK[j] = WK[k] # pozostałe kolumny przenosimy do KK
                k += 1
            s += m*A[w][WK[i]]*det(n-1,w+1,KK,A)
            m = -m # kolejny mnożnik

        del KK   # usuwamy zbędną już tablicę dynamiczną
        return s # wartość funkcji

# *** PROGRAM GŁÓWNY ***
# ----------------------

n = int(input()) # odczytujemy stopień macierzy
A = [] # odczytujemy macierz
for i in range(n):
    a = input().split()
    a = [float(a[j]) for j in range(n)]
    A.append(a)
    del a

WK = [i for i in range(n)] # tworzymy wiersz kolumn

print()
print(det(n,0,WK,A)) # wyznacznik
del A,WK # usuwamy tablice dynamiczne
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
©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: i-lo@eduinf.waw.pl

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

Informacje dodatkowe.