Rechner

Unten kann ein Gleichungssystem mit 3 Unbekannten gelöst werden, indem die Koeffizienten in die Felder eingetragen werden. Die entsprechende 3x4 Matrix wird dann vom JavaScript SolveLinEQ() so bearbeitet, dass in der letzten Spalte die Lösungen des Gleichungssystems stehen. Ein Anwendungsbeispiel findest du unter Anwendung.

Statt durch Klicken auf Lösen kann das Lösen des Gleichungssystems mit Schritt Schrittweise ausgeführt werden, wobei jeder Schritt beschrieben wird.

Algorithmus

Der Gauß-Jordan-Algorithmus verwendet lediglich 3 Operationen:

• Vertauschen von Zeilen
• Normieren: Dividieren der Zeile n durch den Wert ihres Diagonalelementes, damit dieses zu 1 wird
• Nullen: Abziehen des Vielfachen der Zeile n, welche im Diagonalelement den Wert 1 hat, von einer anderen Zeile z, sodass das Element der Spalte n dieser Zeile zu 0 wird.

Diese Schritte werden für jede Zeile ausgeführt bis die Diagonalelemente 1 und alle anderen Elemente ausser der letzten Spalte 0 sind:

Für jede Zeile n der Matrix:

Wenn das Element(n,n) gleich 0 ist

Suche eine Zeile z unterhalb der Zeile n, welche in der Spalte n keine 0 hat

Wenn keine solche Zeile existiert

hat das Gleichungssystem keine Lösung

sonst

Vertausche die Zeilen n und z

Normieren: Dividiere alle Elemente der Zeile n durch den Wert im Element(n,n)

Für jede Zeile z ausser n:

Nullen: Subtrahiere von jedem Element der Zeile z das Element(z,n)-fache der Zeile n

Die Lösungen stehen in der letzten Spalte.

Anwendung

Es sollen die Koordinaten eines Schnittpunktes einer Geraden mit einer Ebene berechnet werden. Die Gleichungen für die Gerade und die Ebene lauten:

Für den Schnittpunkt $\vec X$ gilt, dass er sowohl auf der Geraden, als auch auf der Ebene liegen muss. Dies wird dadurch ausgedrückt, dass $\vec S = \vec T$ sein muss. Für diesen Punkt müssen die Parameter a, b, c berechnet werden. Sind diese Parameter bekannt, kann der Schnittpunkt einfach wiefolgt berechnet werden:

oder

Setzen wir also Gleichung (1) gleich (2) und schreiben diese für jede Koordinate einzeln:

Wir stellen die Gleichung (5) so um, dass alle Terme mit den Unbekannten a, b, c auf der linken Seite und alle anderen Terme auf der rechten Seite des Gleichheitszeichens stehen:

Dieses lineare Gleichungssystem mit 3 Gleichungen für die 3 Unbekannten a, b, c können wir in Matrixschreibweise notieren:

Alle Elemente in der Matrix und im Vektor rechts des Gleichheitszeichens sind bekannte Zahlenwerte. Um das Gleichungssystem mit dem Computer zu lösen, werden alle diese Zahlenwerte wiefolgt in eine 3x4 Matrix eingegeben:

Nachdem die Werte im Rechner eingegeben wurden, kann auf Lösen geklickt werden. Die Matrix wird solange umgeformt, bis in der Diagonalen lauter 1 stehen und die restlichen Elemente ausser der letzten Spalte 0 sind. In der letzten Spalte stehen dann die Lösungen für a, b, c.

JavaScript

Das folgende JavaScript löst lineare Gleichungssysteme beliebiger Grösse. Die Koeffizientenmatrix m wird so neu berechnet, dass in der letzten Spalte schliesslich die Lösungen des Gleichungssystems stehen.

function SolveLinEQ( m ) {
  // solves linear equation of rank d with coefficients in m using Gauss Jordan algorithm
  // m: array[d][d+1]
  // returns solution in m[i][d+1]
  // returns false if no solution found
  //
  // usage:
  //
  // EQ 1: a * x + b * y = c
  // EQ 2: e * x + f * y = g
  //
  // var m = [ [ a, b, c ], [ e, f, g ] ];
  // if ( SolveLinEQ( m ) ) {
  //   x = m[0][2];
  //   y = m[1][2];
  // } else {
  //   no solution
  // }

  function findNotZeroRow( r ) {
    for ( var nzr = r + 1; nzr < d; nzr++ ) {
      if ( m[nzr][r] != 0 ) return nzr;
    }
    return -1;
  }

  function swapRows( r1, r2 ) {
    for ( var c = 0; c <= d; c++ ) {
      var tmp = m[r1][c];
      m[r1][c] = m[r2][c];
      m[r2][c] = tmp;
    }
  }

  function normRow( r ) {
    // require m[r][r] != 0
    var a = m[r][r];
    if ( a == 1 ) return;
    m[r][r] = 1;
    for ( var c = r + 1; c <= d; c++ ) {
      m[r][c] /= a;
    }
  }

  function zeroCell( zr, zc ) {
    var a = m[zr][zc];
    if ( a == 0 ) return;
    m[zr][zc] = 0;
    for ( var c = zc + 1; c <= d; c++ ) {
      m[zr][c] -= a * m[zc][c];
    }
  }

  var d = m.length;
  for ( var r = 0; r < d; r++ ) {
    if ( m[r][r] == 0 ) {
      var nzr = findNotZeroRow( r );
      if ( nzr == -1 ) return false;
      swapRows( r, nzr );
    }
    // assert m[r][r] != 0
    normRow( r );
    for ( var zr = 0; zr < d; zr++ ) {
      if ( zr != r ) {
        zeroCell( zr, r );
      }
    }
  }
  return true;
}

Laut Wikipedia kann obiger Algorithmus stabiler gemacht werden, indem beim Tauschen der Zeilen nicht die erstbeste Zeile verwendet wird, sondern die Zeile mit dem grössten Wert:

Das gaußsche Eliminationsverfahren ist im Allgemeinen nicht ohne Zeilenvertauschungen durchführbar. Für die Berechnung mit Hilfe eines Computers ist es sinnvoll, das betragsgrößte Element zu wählen, um einen möglichst stabilen Algorithmus zu erhalten.