Algorithmensammlung: Numerik: Gauß-Jordan-Algorithmus

Gauß-Jordan-Algorithmus

Der Gauß-Jordan-Algorithmus ist ein Verfahren zum Lösen eines linearen Gleichungssystems mit Hilfe von Zeilenumformungen (Zeilentausch, Subtraktion eines Vielfachen einer anderen Zeile).

Näheres siehe Gauß-Jordan-Algorithmus.

Pseudocode

Der hier skizzierte Algorithmus setzt eine invertierbare Koeffizientenmatrix m voraus, also ein eindeutig lösbares Gleichungssystem.

function gaussJordan (m, v)
  n ← Zeilenzahl von m
  a ← Neue Matrix mit n Zeilen und n+1 Spalten
  for i ← 1 to n do
    begin
    for j ← 1 to n do
      a[i][j] ← m[i][j]
    a[i][n+1] ← v[i]
    end
  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 undefiniert
    if p ≠ j then Vertausche Zeilen j und p von Matrix a
    f ← a[j][j]
    Dividiere Zeile j von Matrix a durch f
    for i ← 1 to n do
      begin
      if i ≠ j then
        begin
        f ← a[i][j]
        Subtrahiere in Matrix a von Zeile i das f-fache von Zeile j
        end
      end
    end
  x ← Neues Array der Länge n
  for i ← 1 to n do
    x[i] ← a[i][n+1]
  return x

Java

// Lösung eines linearen Gleichungssystems (Gauß-Jordan-Algorithmus):
// m ... Matrix der Koeffizienten (quadratisch, invertierbar)
// v ... Vektor für inhomogenen Teil des Gleichungssystems
  
public static double[] gaussJordan (double[][] m, double[] v) {
  	
  int n = m.length;                                         // Zeilenzahl
  	
  // Überprüfung, ob die 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 null;                                          // Rückgabewert
      }
    }
  	  
  // Dimensionsprüfung für Vektor:
  	
  if (v.length != n) {                                      // Falls falsche Dimension ...
    System.out.println("Dimensionsfehler!");                // Fehlermeldung
    return null;                                            // Rückgabewert
    }
  	  
  // Erweiterte Koeffizientenmatrix:
  	  
  double[][] a = new double[n][n+1];                        // Neues Array
  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];                                    // Element der Koeffizientenmatrix übernehmen
    a[i][n] = v[i];                                         // Element des Vektors übernehmen
    }

  // Berechnung:

  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) {                                           // Falls Suche erfolglos ...
      System.out.println("Matrix nicht invertierbar!");     // Fehlermeldung
      return null;                                          // Rückgabewert
      }
    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
      }
    double f = a[j][j];                                     // Element der Hauptdiagonale (ungleich 0)
    for (int k=0; k<=n; k++) a[j][k] /= f;                  // Zeile j durch f dividieren
    for (int i=0; i<n; i++) {                               // Für alle Zeilenindizes ...
      if (i == j) continue;                                 // Hauptdiagonalenelement überspringen
      f = a[i][j];                                          // Faktor für Multiplikation
      for (int k=0; k<=n; k++) a[i][k] -= f*a[j][k];        // Zeilenumformung
      }
    }
  double[] b = new double[n];                               // Neues Array für Lösungsvektor
  for (int i=0; i<n; i++) b[i] = a[i][n];                   // Arrayelemente übernehmen

  return b;                                                 // Rückgabewert

  }