Algorithmensammlung: Numerik: Determinante

Algorithmensammlung: Numerik


Determinante

Bearbeiten

Die Determinante einer quadratischen Matrix ist ein wichtiges Hilfsmittel der Linearen Algebra. Siehe   Determinante.

Die Berechnung einer Determinante kann mit dem Gauß'schen Eliminationsverfahren erfolgen. Eine Kopie der ursprünglichen Matrix wird durch Zeilenumformungen (Subtraktion eines Vielfachen einer anderen Zeile, Vertauschung zweier Zeilen) auf Stufenform gebracht, sodass eine obere Dreiecksmatrix entsteht. Die Determinante dieser Dreiecksmatrix ergibt sich als Produkt der Hauptdiagonalenelemente.

Pseudocode

Bearbeiten
function determinante (m)
  n ← Zeilen- bzw. Spaltenzahl von m
  a ← Kopie von m
  d ← 1
  for j ← 1 to n do
    begin
    p ← j
    while p ≤ n and a[p][j] = 0 do p ← p + 1
    if p = n + 1 then return 0
    if p ≠ j then
      begin
      Vertausche in Matrix a Zeile j und Zeile p
      d ← -d
      end
    d ← d * a[j][j]
    for i ← j + 1 to n do
      begin
      f ← a[i][j] / a[j][j]
      Subtrahiere in Matrix a von Zeile i das f-fache von Zeile j
      end
    end
  return d
  // Determinante einer quadratischen Matrix:
  // m ... Matrix
  
  public static double determinant (double[][] m) {
  	
  	int n = m.length;                                      // Anzahl der Zeilen
  	
  	// Überprüfung, ob die gegebene Matrix quadratisch ist:
  	
  	for (int i=0; i<n; i++) {                              // Für alle Zeilenindizes ...
  	  if (m[i].length != n) {                              // Falls abweichende Zeilenlänge ...
  	    System.out.println("Matrix nicht quadratisch!");   // Fehlermeldung
  	    return Double.NaN;                                 // Rückgabewert
  	    }
  	  }
  	  
  	// Kopie der gegebenen Matrix:
  	
  	double[][] a = new double[n][n];                       // Zweifach indiziertes Array für Kopie von m
  	for (int i=0; i<n; i++)                                // Für alle Zeilenindizes ...
  	  for (int j=0; j<n; j++)                              // Für alle Spaltenindizes ...
  	  	a[i][j] = m[i][j];                                 // Matrixelement
  	
  	// Berechnung:  	
  		
  	double d = 1;                                          // Startwert Determinante
  	for (int j=0; j<n; j++) {                              // Für alle Spaltenindizes ...
  	  int p = j;                                           // Variable für Zeilenindex
  	  while (p < n && a[p][j] == 0) p++;                   // Index erhöhen, bis Spaltenelement ungleich 0
  	  if (p == n) return 0;                                // Rückgabewert, falls Suche erfolglos
  	  if (p != j) {                                        // Falls Zeilentausch nötig ...
  	  	double[] temp = a[j];                              // Zeile mit Index j
  	  	a[j] = a[p];                                       // Zeile mit Index j neu
  	  	a[p] = temp;                                       // Zeile mit Index p neu
  	  	d = -d;                                            // Vorzeichenänderung wegen Zeilentausch
  	    }
  	  d = d*a[j][j];                                       // Multiplikation mit Element der Hauptdiagonale
  	  for (int i=j+1; i<n; i++) {                          // Für alle Zeilenindizes ab j+1 ...
  	  	double f = a[i][j]/a[j][j];                        // Faktor
  	  	for (int k=0; k<n; k++)                            // Für alle Spaltenindizes ...
  	  	  a[i][k] -= a[j][k]*f;                            // Subtraktion eines Vielfachen von Zeile j 
  	    } // Ende for (i)
  	  } // Ende for (j)
  	  
  	return d;                                              // Rückgabewert
  	
    }