Obliczanie wyznacznika macierzy


Tematy pokrewne Podrozdziały  

 

Dla układów równań zawierających więcej niż dwie niewiadome dochodzenie do rozwiązania opisaną w poprzednim rozdziale drogą jest bardzo pracochłonne. Dlatego matematycy starali się znaleźć jakąś ogólną metodę prowadzącą do znalezienia rozwiązań układu równań. Jedną z tych metod jest metoda Cramera (ang. Cramer's Rule). Zanim ją omówimy, musimy wprowadzić kilka pojęć.

 

Macierz

Macierz (ang. matrix) jest złożonym tworem matematycznym, którego dokładna definicja jest dosyć skomplikowana. Na nasze potrzeby wystarczy przyjąć, iż macierz jest tablicą dwuwymiarową przechowującą wiele wartości. Macierz przechowuje dane w wierszach i kolumnach. Ilość wierszy i kolumn macierzy nazywamy jej wymiarami (ang. dimensions).

 

Przykład:

Poniżej przedstawiamy macierz A o wymiarach 3 x 4 (trzy wiersze po cztery kolumny) wraz z przechowywanymi w tej macierzy liczbami:

 

  1 2 3 4  
A = 1   5 11 -4 3  
2   29 -3 12 91  
3   82 0 3 -2  

 

Poszczególne elementy macierzy są numerowane wg wierszy i kolumn, w których się znajdują.

 

Przykład:

W przykładowej macierzy A o wymiarach 3 x 4 zastąpmy liczby wartościami symbolicznymi ai,j. Otrzymamy następujący układ:

 

  1 2 3 4  
A := (ai,j)3x4 = 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  

 

Dzięki numeracji możemy precyzyjnie określić położenie każdego elementu macierzy. Np. element a2,3 znajduje się w wierszu 2 i kolumnie 3. Jeśli odniesiemy tą macierz do macierzy z poprzedniego przykładu, to element a2,3 = 12.

 

Jeśli ilość wierszy i kolumn w macierzy jest taka sama, to mówimy, iż macierz jest macierzą kwadratową (ang. square matrix). Jeśli jeden z wymiarów macierzy (wiersze lub kolumny) równy jest 1, to macierz nazywamy wektorem odpowiednio wierszowym (ang. row vector) lub kolumnowym (ang. column vector).

 

Przykład:

Macierz kwadratowa Wektor wierszowy Wektor kolumnowy
  a1,1 a1,2 a1,3  
  a2,1 a2,2 a2,3  
  a3,1 a3,2 a3,3  
  a1 a2 a3  
  a1  
  a2  
  a3  

 

Wyznacznik macierzy

Wyznacznik n-tego stopnia (ang. determinant) macierzy kwadratowej A o wymiarach n x n jest liczbą, którą obliczamy rekurencyjnie w sposób następujący:

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

 

det A1x1 = 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. Sposób ten nosi nazwę metody Laplace'a i niestety jest mało efektywny, ale nam zupełnie wystarczy.

 

Przykład:

Obliczmy wg opisanej powyżej metody wyznacznik 2 stopnia macierzy:

 

  a1,1 a1,2  
  a2,1 a2,2  

 

Elementy oznaczyliśmy symbolicznie, aby otrzymać wzór symboliczny na wartość wyznacznika 2 stopnia. Do wyliczeń wybieramy pierwszy wiersz. W wierszu tym znajdują się dwa wyrazy macierzy: a1,1 oraz a1,2.

 

det   a1,1 a1,2   = (-1)1+1 a1,1 det [a2,2] + (-1)1+2 a1,2 det [a2,1] = a1,1 a2,2 - a1,2 a2,1
  a2,1 a2,2  

 

Wyraz a1,1 mnożymy przez wyznacznik macierzy, która powstaje przez skreślenie pierwszego wiersza i pierwszej kolumny. Wynikowa macierz zawiera jedynie wyraz a2,2. Wyznacznik takiej macierzy jest równy wartości wyrazu a2,2. Ponieważ suma numeru wiersza i numeru kolumny jest parzysta (1 + 1 = 2), nie zmieniamy znaku iloczynu.

Wyraz a1,2 mnożymy przez wyznacznik macierzy powstałej po skreśleniu pierwszego wiersza i drugiej kolumny. Macierz wynikowa zawiera tylko element a2,1, zatem jej wyznacznik jest równy wartości wyrazu a2,1. Ponieważ suma numeru wiersza i kolumny jest teraz nieparzysta (1 + 2 = 3), zmieniamy znak iloczynu.

Otrzymane iloczyny sumujemy otrzymując wzór na wyznacznik 2 stopnia.

 

Zapamiętaj:

det   a1,1 a1,2   = a1,1 a2,2 - a1,2 a2,1
  a2,1 a2,2  

 

Mnemotechnicznie: przekątna z lewa na prawo (a1,1 a2,2) minus przekątna z prawa na lewo (a1,2 a2,1)

Przykład:

Wykorzystując wzór na wyznacznik 2 stopnia wyprowadzimy wzór na wyznacznik stopnia trzeciego:

 

det   a1,1 a1,2 a1,3    
  a2,1 a2,2 a2,3   = ?
  a3,1 a3,2 a3,3    

 

Do wyliczenia wyznacznika wybierzemy pierwszy wiersz z wyrazami a1,1, a1,2 oraz a1,3. Każdy z tych wyrazów mnożymy przez wyznacznik podmacierzy powstałej przez usunięcie pierwszego wiersza oraz kolumny danego wyrazu. Iloczyn dodatkowo przemnażamy przez -1 podniesione do potęgi równej sumie numeru kolumny i wiersza wybranego wyrazu.

 

d1 = a1,1 det   a2,2 a2,3   = (-1)1+1 a1,1(a2,2 a3,3 - a2,3 a3,2)  =  a1,1 a2,2 a3,3 - a1,1 a2,3 a3,2
  a3,2 a3,3  

 

d2 = a1,2 det   a2,1 a2,3   = (-1)1+2 a1,2(a2,1 a3,3 - a2,3 a3,1)  =  - a1,2 a2,1 a3,3 + a1,2 a2,3 a3,1
  a3,1 a3,3  

 

d3 = a1,3 det   a2,1 a2,2   = (-1)1+3 a1,3(a2,1 a3,2 - a2,2 a3,1)  =  a1,3 a2,1a3,2 - a1,3 a2,2 a3,1
  a3,1 a3,2  

 

Sumujemy otrzymane iloczyny częściowe d1, d2 oraz d3 otrzymując wartość wyznacznika:

 

det A = d1 + d2 + d3

det A = a1,1 a2,2 a3,3 - a1,1 a2,3 a3,2 - a1,2 a2,1 a3,3 + a1,2 a2,3 a3,1 + a1,3 a2,1a3,2 - a1,3 a2,2 a3,1

 

i ostatecznie po uporządkowaniu wg dodawania i odejmowania:

 

det A = a1,1 a2,2 a3,3 + a1,2 a2,3 a3,1 + a1,3 a2,1a3,2 - a1,3 a2,2 a3,1 - a1,1 a2,3 a3,2 - a1,2 a2,1 a3,3

 

Zapamiętaj:

Otrzymany wzór

det A = a1,1 a2,2 a3,3 + a1,2 a2,3 a3,1 + a1,3 a2,1a3,2 - a1,3 a2,2 a3,1 - a1,1 a2,3 a3,2 - a1,2 a2,1 a3,3

można wyprowadzić z prostej do zapamiętania reguły Sarrusa dla wyznaczników 3 stopnia. W tym celu do wyrazów macierzy dopisujemy z prawej strony dwie pierwsze kolumny:



Trzy przekątne czarne sumujemy ze znakiem +, a trzy przekątne czerwone sumujemy ze znakiem - i otrzymujemy wyprowadzony wcześniej wzór wyznacznika 3 stopnia:

det A = a1,1 a2,2 a3,3 + a1,2 a2,3 a3,1 + a1,3 a2,1a3,2 - a1,3 a2,2 a3,1 - a1,1 a2,3 a3,2 - a1,2 a2,1 a3,3

 

Algorytm

Podany tutaj algorytm wyliczania wyznacznika macierzy jest algorytmem dydaktycznym z uwagi na jego klasę złożoności obliczeniowej równą 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. Jednakże w naszym (szkolnym) przypadku nie będziemy wychodzić poza n = 8, a 8! = 40320, czyli nie tak wiele jak dla współczesnych komputerów. Jeśli potrzebujesz praktycznego algorytmu wyliczania wyznaczników dużych macierzy, to proponuję poszukać w sieci Internet opisów algorytmów rozkładu macierzy kwadratowej na iloczyn macierzy LU (ang. Lower / Upper Matrix). Ponieważ jest to zagadnienie wykraczające poza program szkoły średniej, nie będę się nim tutaj zajmował.

 

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.

 

Specyfikacja problemu

Dane wejściowe

stopień - określa stopień wyznacznika do obliczenia.  stopień N
wiersz - określa numer wiersza, w którym rozpoczyna się podmacierz.  wiersz 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.
A[ ] - macierz, której wyznacznik liczymy. Wymiar macierzy, to 8 x 8.

Dane wyjściowe

det - wartość wyznacznika podmacierzy.  det R

Zmienne pomocnicze i funkcje

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).
kolumny[ ] - wektor kolumn umożliwiający rekurencyjne przekazywanie numerów kolumn podmacierzy, dla których liczone są wyznaczniki. Elementami wektora kolumn są liczby całkowite.
suma - zlicza sumę iloczynów wyrazów wiersza przez wyznaczniki niższych stopni. suma R

 

Lista kroków

Funkcja rekurencyjna det(stopień, wiersz, wk[ ], A[ ])
    K01: Jeśli stopień = 1, to det ← A[wiersz, wk[1]]   i zakończ
    K02: suma 0;    m 1
    K03: Dla i = 1, 2, ..., stopień:   wykonuj K04...K10
  K04:     k 1
  K05:     Dla j = 1, 2,..., stopień - 1:   wykonuj K06...K08
K06:         Jeśli k = i,   to k ← k + 1
K07:         kolumny[j] wk[k]
K08:         k ← k + 1
  K09:     suma ← suma + m × A[wiersz, wk[i]] × det(stopień-1, wiersz+1, kolumny[ ])
  K10:     m (-m)
    K11: det ← suma
    K12: Zakończ

 

Schemat blokowy

Wyznacznik obliczany jest algorytmem rekurencyjnym. Na początku sprawdzamy warunek zakończenia rekurencji - jeśli stopień wyznacznika jest równy 1, to jego wartością jest wyraz macierzy i kończymy algorytm.

Jeśli stopień wyznacznika jest większy od 1, to musimy rekurencyjnie obliczać jego wartość.

W zmiennej suma będziemy zliczali iteracyjnie sumę iloczynów kolejnych wyrazów pierwszego wiersza macierzy przez wyznaczniku podmacierzy. Zmienną suma ustawiamy na zero.

Zmienna m będzie na przemian przyjmować wartości 1 i -1. Dzięki temu iloczyny wyrazów znajdujących się na nieparzystych kolumnach będą sumowane ze znakiem +, a iloczyny wyrazów znajdujących się w parzystych kolumnach będą sumowane ze znakiem -. Zmienną m ustawiamy na 1.

Pętla nr 1 przebiega kolejno przez wszystkie wyrazy pierwszego wiersza macierzy. Dla każdego wyrazu w pętli nr 2 obliczany jest wektor kolumn podmacierzy w tablicy kolumny[ ]. Wektor ten jest taki sam jak otrzymany w parametrach wektor wk[ ], jednakże z usuniętym numerem kolumny, w której znajduje się i-ty wyraz.

Po wyznaczeniu wektora kolumn do zmiennej suma dodajemy iloczyn i-tego wyrazu pierwszego wiersza przez wyznacznik niższego poziomu obliczany rekurencyjnie. Cały iloczyn dodatkowo mnożony jest przez m, dzięki temu sumowany zostaje ze znakiem + (dla m=1)  lub - (dla m=-1).

Po wykonaniu sumowania zmieniamy znak m na przeciwny - następne sumowanie odbędzie się z przeciwnym znakiem.

Pętla nr 1 jest kontynuowana, aż do zsumowania wszystkich iloczynów wyrazów pierwszego wiersza przez wyznaczniki niższego poziomu. Po jej zakończeniu zwracamy w det wyliczoną wartość wyznacznika i kończymy algorytm.


 

Programy

Przykładowe programy przedstawione poniżej generują pseudolosową macierz kwadratową o wymiarach od 2x2 do 8x8. Następnie wyliczany jest wyznacznik tej macierzy wg podanego algorytmu rekurencyjnego. Programy uruchamiaj w projekcie konsoli (ang. Console Application).

 

Efekt uruchomienia programu
 
Demonstracja rekurencyjnego wyliczania wyznacznika macierzy
-----------------------------------------------------------
(C)2006 mgr Jerzy Wałaszek                  I LO w Tarnowie

  49  32  79  90 -18 -35 -64   7

  27  96 -11 -52 -50 -57  57 -27

  33  68   8  -6   4 -96 -91 -84

  12  12  37  25  58   2 -75  32

  73  97  68 -37  44 -52  79  96

  -6  97  86 -41   8 -99 -10 -38

 -85  86 -36  92  11 -24  11  58

  43 -56 -36  72  31 -59 -60  96

det A = 16434001870150584
-----------------------------------------------------------
Koniec. Naciśnij klawisz Enter...

 

Free Pascal
// Program wylicza wyznacznik macierzy w sposób
// rekurencyjny wykorzystując regułę Laplace'a.
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

program mzfl3;

type
  kwektor = array[1..8] of integer;
  macierz = array[1..8,1..8] of double;

// Rekurencyjna funkcja obliczania wyznacznika
//--------------------------------------------

function det(stopien, wiersz : integer;
             var wk : kwektor;
             var A  : macierz) : extended;
var
  i,j,k,m : integer;
  kolumny : kwektor; // wektor kolumn dla podmacierzy
begin
  if stopien = 1 then
    Result := A[wiersz,wk[1]]
  else
  begin
    Result := 0; m := 1;
    for i := 1 to stopien do
    begin
      k := 1;
      for j := 1 to stopien - 1 do
      begin
        if k = i then inc(k);
        kolumny[j] := wk[k];
        inc(k);
      end;
      Result := Result+m*A[wiersz,wk[i]]*det(stopien-1,wiersz+1,kolumny,A);
      m := -m;
    end;
  end;
end;

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

var
  A     : macierz;
  nk    : kwektor; // wektor kolumn
  n,i,j : integer;

begin
  writeln('Demonstracja rekurencyjnego wyliczania wyznacznika macierzy');
  writeln('-----------------------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek                  I LO w Tarnowie');
  writeln;

// Generujemy stopień wyznacznika

  randomize;
  n := 2 + random(7);

// Wypełniamy macierz A losowymi wartościami -99..99
// i wyświetlamy ją w oknie konsoli

  for i := 1 to n do
  begin
    for j := 1 to n do
    begin
      A[i,j] := -99 + random(199);
      write(A[i,j]:4:0);
    end;
    writeln; writeln;
  end;

// Inicjujemy wektor kolumn

  for i := 1 to n do nk[i] := i;

// Wyliczamy wyznacznik i wypisujemy jego wartość

  writeln('det A = ', det(n,1,nk,A):0:0);
  writeln;
  writeln('-----------------------------------------------------------');
  writeln('Koniec. Nacisnij klawisz Enter...');
  readln;
end.
Code::Blocks
// Program wylicza wyznacznik macierzy w sposób
// rekurencyjny wykorzystując regułę Laplace'a.
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

// Rekurencyjna funkcja obliczania wyznacznika
//--------------------------------------------

long double det(int stopien, int wiersz, int wk[], double A[][8])
{
  int i,j,k,m;
  int kolumny[8]; // wektor kolumn dla podmacierzy
  long double suma;

  if(stopien == 1)
    return A[wiersz][wk[0]];
  else
  {
    suma = 0; m = 1;
    for(i = 0; i < stopien; i++)
    {
      k = 0;
      for(j = 0; j < stopien - 1; j++)
      {
        if(k == i) k++;
        kolumny[j] = wk[k++];
      }
      suma += m * A[wiersz][wk[i]] * det(stopien - 1, wiersz + 1, kolumny, A);
      m = -m;
    }
  return suma;
  }
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

int main()
{
  double A[8][8];  // macierz
  int nk[8];       // wektor kolumn
  int n,i,j;

  cout << setprecision(0)     // 0 cyfr po przecinku
       << fixed;              // format stałoprzecinkowy

  cout << "Demonstracja rekurencyjnego wyliczania wyznacznika macierzy\n"
          "-----------------------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek                  I LO w Tarnowie\n\n";

// Generujemy stopień wyznacznika

  srand(time(NULL));
  n = 2 + rand() % 7;

// Wypełniamy macierz A losowymi wartościami -99..99
// i wyświetlamy ją w oknie konsoli

  for(i = 0; i < n; i++)
  {
    for(j = 0; j < n; j++)
    {
      A[i][j] = -99 + rand() % 199;
      cout << setw(4) << A[i][j];
    }
    cout << endl << endl;
  }

// Inicjujemy wektor kolumn

  for(i = 0; i < n; i++) nk[i] = i;

// Wyliczamy wyznacznik i wypisujemy jego wartość

  cout << "det A = " << det(n, 0, nk, A) <<
          "\n-----------------------------------------------------------\n\n";
  system("pause");
  return 0;
}
FreeBASIC
' Program wylicza wyznacznik macierzy w sposób
' rekurencyjny wykorzystując regułę Laplace"a.
'---------------------------------------------
' (C)2006 mgr J.Wałaszek       I LO w Tarnowie

Declare Function det(stopien As Integer,_
                     wiersz As Integer,_
                     wk() As Integer,_
                     A() As Double) As double

'-----------------------------------------------------
' Program główny
'-----------------------------------------------------

dim A(7,7) As double
Dim nk(7) As integer ' wektor kolumn
Dim As integer n,i,j

Print "Demonstracja rekurencyjnego wyliczania wyznacznika macierzy"
Print "-----------------------------------------------------------"
Print "(C)2006 mgr Jerzy Walaszek                  I LO w Tarnowie"
Print

' Generujemy stopień wyznacznika

Randomize
n = 2 + Int(Rnd() * 7)

' Wypełniamy macierz A losowymi wartościami -99..99
' i wyświetlamy ją w oknie konsoli

For i = 0 To n - 1
  For j = 0 To n - 1
     A(i, j) = -99 + Int(Rnd() * 199)
     Print Using "####"; A(i, j);
  Next
  Print
  Print
Next

' Inicjujemy wektor kolumn
For i = 0 To n - 1 : nk(i) = i : Next

' Wyliczamy wyznacznik i wypisujemy jego wartość

Print "det A = "; det(n,0,nk(),A())
Print
Print "-----------------------------------------------------------"
Print "Koniec. Nacisnij klawisz Enter..."

Sleep

End

' Rekurencyjna funkcja obliczania wyznacznika
'--------------------------------------------

Function det(stopien As Integer, wiersz As Integer, wk() As Integer, A() As Double) As Double
    Dim As Integer i, j, k, m
    Dim kolumny(7) As Integer ' wektor kolumn dla podmacierzy
    Dim suma As Double

    If stopien = 1 Then
      return A(wiersz, wk(0))
    Else
      suma = 0 : m = 1
      For i = 0 To stopien - 1
        k = 0
        For j = 0 To stopien - 2
          If k = i Then k += 1
          kolumny(j) = wk(k)
          k += 1
        Next
        suma += m * A(wiersz, wk(i)) * det(stopien - 1, wiersz + 1, kolumny(), A())
        m = -m
      Next
      Return suma
    End If
  End Function
JavaScript
<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset;
                   PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset;
                   PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px;
                   BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px;
                   BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66" name="frmbincode">
        <h3 id="out_t" style="TEXT-ALIGN: center">
          Demonstracja rekurencyjnego wyliczania wyznacznika macierzy
        </h3>
        <p style="TEXT-ALIGN: center">
          (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
        </p>
        <hr>
        <p style="TEXT-ALIGN: center">
          <input type="button" value="Generuj macierz i oblicz wyznacznik"
                 name="B1" onclick="main()">
        </p>
        <div id="output" align="center">&nbsp;</div>
      </form>

<script language=javascript>

// Program wylicza wyznacznik macierzy w sposób
// rekurencyjny wykorzystując regułę Laplace'a.
//---------------------------------------------
// (C)2006 mgr J.Wałaszek I LO w Tarnowie

// Rekurencyjna funkcja obliczania wyznacznika
//--------------------------------------------

function det(stopien, wiersz, wk, A)
{
  var i,j,k,m;
  var kolumny = new Array(8); // wektor kolumn dla podmacierzy
  var suma;

  if(stopien == 1)
    return A[wiersz][wk[0]];
  else
  {
    suma = 0; m = 1;
    for(i = 0; i < stopien; i++)
    {
      k = 0;
      for(j = 0; j < stopien - 1; j++)
      {
        if(k == i) k++;
        kolumny[j] = wk[k++];
      }
      suma += m * A[wiersz][wk[i]] * det(stopien - 1, wiersz + 1, kolumny, A);
      m = -m;
    }
    return suma;
  }
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

function main()
{
  var A; // Macierz, której wyznacznik jest liczony przez skrypt
  var nk = new Array(8); // wektor kolumn
  var n,i,j,t;

// Generujemy stopień wyznacznika

  n = 2 + Math.floor(Math.random() * 7);

// Wypełniamy macierz A losowymi wartościami -99..99
// i wyświetlamy ją w oknie konsoli

  A = new Array(n);
  t = "<table border='0' cellpadding='4' style='border-collapse: collapse'>"; 
  for(i = 0; i < n; i++)
  {
    A[i] = new Array(n);
    t += "<tr>";
    for(j = 0; j < n; j++)
    {
      A[i][j] = -99 + Math.floor(Math.random() * 199);
      t += "<td align='right'>" + A[i][j] + "</td>";
    }
    t += "</tr>";
  }
  t += "</table><p style='text-align: center'>";

// Inicjujemy wektor kolumn

  for(i = 0; i < n; i++) nk[i] = i;

// Wyliczamy wyznacznik i wypisujemy jego wartość

  t += "det A = " + det(n, 0, nk, A) + "</p>";
  document.getElementById("output").innerHTML = t;
}

</script> 
    </div>
  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Demonstracja rekurencyjnego wyliczania wyznacznika macierzy

(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie


 

 



List do administratora Serwisu Edukacyjnego 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

(C)2014 mgr Jerzy Wałaszek

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