Algorithmensammlung: Numerik: Gauß-Jordan-Algorithmus
Erscheinungsbild
Gauß-Jordan-Algorithmus
[Bearbeiten]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
[Bearbeiten]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
[Bearbeiten]// 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
}