Obliczanie wyznacznika macierzy kwadratowej

Question

No i tym razem ja mam problem. Jestem w trakcie pisania aplikacji w JavaScriptcie do wykonywania różnych obliczeń na macierzach. Oczywiście, nie ma żadnego problemu znaleźć w sieci gotowe algorytmy obliczające m.in. wyznacznik macierzy kwadratowej, które zwracają gotowy wynik i działają poprawnie. Jednak ja chciałem stworzyć coś bardziej złożonego, tzn. wyświetlający kolejne kroki obliczeń wyznacznika macierzy - jako pomoc dla studentów na egzaminach . Niestety mam problem z rekursywnie wywoływaną funkcją determinant(), która choć zwraca prawidłowy końcowy wynik to nie podaje prawidłowych macierzy w przebiegu kolejnych kroków obliczeń. Gdybym był w posiadaniu (lecz nie mogłem znaleźć go w internecie) algorytmu bez rekursji (tj. w formie obliczeń iteracyjnych) takie dziwne rzeczy by się już nie działy bo wiedziałbym jak ten algorytm odpowiednio wykorzystać. Poniżej podaję fragmenty zrzutów ekranu jak ta sprawa wygląda:

Nie zamieszczam tutaj kodu, ze względu na jego obszerność - zapraszam natomiast to zapoznania się z wersją demo na JSFiddle: https://jsfiddle.net/sx4m1c7L/. Będę bardzo wdzięczny za pomoc, chciażby w przetłumaczeniu tej rekursji na obliczanie w pętli, bo ja już wymiękam. Podkreślam, że kod jest i będzie open source na GitHubie i pomożecie wielu innym osobom nie tylko w programowaniu ale w rozwiązywaniu zadań z macierzami. Dzięki.

Comments

A byłby ktoś w stanie chociaż zminić tą rekursywnie wywoływaną funkcję na iterację? To by mi bardzo ułatwio sprawę:

function determinant(inputMatrix, dim) {
  var det = 0, subDet = 0, subDim = dim;
  var subMatrix = new Array(10);
  for (var loop1 = 0; loop1 < subMatrix.length; loop1++) {
    subMatrix[loop1] = new Array(10);
    for (var loop2 = 0; loop2 < subMatrix[loop1].length; loop2++) {
      subMatrix[loop1][loop2] = 0;
    }
  }
  if (dim == 1) {
    return inputMatrix[0][0];
  } else if (dim == 2) {
    return ((inputMatrix[0][0] * inputMatrix[1][1]) - (inputMatrix[1][0] * inputMatrix[0][1]));
  } else {
    for (var loop1 = 0; loop1 < dim; loop1++) {
      var subi = 0;
      for (var loop2 = 1; loop2 < dim; loop2++) {
        var subj = 0;
        for (var loop3 = 0; loop3 < dim; loop3++) {
          if (loop3 == loop1) {
            continue;
          }
          subMatrix[subi][subj] = inputMatrix[loop2][loop3];
          subj++;
        }
        subi++;
      }
      subDet = det;
      // ta poniższa rekursja utrudnia mi sprawę :-(
      det = subDet + (Math.pow(-1, loop1) * inputMatrix[0][loop1] * determinant(subMatrix, dim - 1));
    }
  }
  return det;
}

var matrix = [[3, 5, 1], [8, 0, 4], [9, 7, 1]];
alert(determinant(matrix, 3));

Answer 1

https://jsfi­d­dle.net/84tx52bj/

Te­raz dzia­ła?

Nie wiem po co tam by­ło su­bDim zmniej­sza­ne o je­den w pę­t­li, gdy dim się nie zmie­nia­ło.

⁂

Jak jest napisane w https://en.wikipedia.org/wiki/Determinant#n_%C3%97_n_matrices do obliczenia w pętli trzeba by generować wszystkie permutacje od 1 do n (rozmiar macierzy), obliczać dla nich iloczyn wartości z tych indeksów i sumować. Więc obliczanie w pętli sprowadza się głównie do zrobienia funkcji obliczania następnej permutacji.

Comments

Aha, teraz rozumiem, dzięki! No jak widać niektórzy programiści nie są dobrymi matematykami. A tak poza tym, to każdy krok obliczeń mogę rozbić na szczegółowe podkroki np. Krok 1A, 1B itd. bo dodałeś w nawiasie w kodzie wyniki det macierzy wciąż "dużych wymiarowo", których wyznaczniki też trzeba obliczyć swoją drogą, tak?

---

Metoda, którą stosujesz jest opisana na wymienionej stronie Wikipedii pod tytułem Laplace expansion. Z tym że dla n = 1 i n = 2 są zastosowane wzory skrócone.

Tak, wyznacznik większej tablicy oblicza się tą metodą przez mnożenie kolejnych wartości z pierwszego rzędu macierzy przez wyznaczniki mniejszych macierzy (utworzonych z pominięciem kolumny bieżącej wartości). Tworzenie tych mniejszych macierzy masz w pętlach ze zmiennymi loop2 (rząd) i loop3 (kolumna), podczas gdy pętla z loop1 (kolumna) wybiera wartość z pierwszego rzędu macierzy.