WaBis

walter.bislins.ch

Lösen linearer Gleichungssysteme (JavaScript)

Donnerstag, 15. September 2016 - 17:38 | Autor: wabis | Themen: Wissen, Mathematik, Interaktiv
Viele geometrische Probleme können in Form von linearen Gleichungssystemen beschrieben werden. Hier wird der Gauss-Jordan-Algorithmus verwendet, um solche Gleichungssysteme zu lösen. Der Algorithmus kann interaktiv bei der Arbeit verfolgt werden. Das zugehörige JavaScript für beliebig grosse Gleichungssysteme wird aufgelistet.

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:

(1)
\vec S = \vec P + a \cdot \vec r

Geradengleichung

(2)
\vec T = \vec Q + b \cdot \vec u + c \cdot \vec v

Ebenengleichung

wobei'
\vec P ' =' 'Punkt auf der Geraden
\vec r ' =' 'Richtung der Geraden
\vec Q ' =' 'Punkt auf der Ebene
\vec u, \vec v ' =' 'Zwei nicht parallele Vekroren auf der Ebene

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:

(3)
\vec X = \vec P + a \cdot \vec r

oder

(4)
\vec X = \vec Q + b \cdot \vec u + c \cdot \vec v

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

(5)
P_i + a \cdot r_i = Q_i + b \cdot u_i + c \cdot v_i

für i = 1...3

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:

(6)
r_1 \cdot a - u_1 \cdot b - v_1 \cdot c = Q_1 - P_1
(7)
r_2 \cdot a - u_2 \cdot b - v_2 \cdot c = Q_2 - P_2
(8)
r_3 \cdot a - u_3 \cdot b - v_3 \cdot c = Q_3 - P_3

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

(9)
\pmatrix{ r_1 & -u_1 & -v_1 \\ r_2 & -u_2 & -v_2 \\ r_3 & -u_3 & -v_3 } \cdot \pmatrix{ a \\ b \\ c } = \pmatrix{ Q_1 - P_1 \\ Q_2 - P_2 \\ Q_3 - P_3 }

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:

(10)
\left[ \matrix{ r_1 & -u_1 & -v_1 & ( Q_1 - P_1 ) \\ r_2 & -u_2 & -v_2 & ( Q_2 - P_2 ) \\ r_3 & -u_3 & -v_3 & ( Q_3 - P_3 ) } \right]

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.
Dein Kommentar zu diesem Artikel
Name
Email optional; wird nicht angezeigt
Kommentar
  • Name wird bei deinem Kommentar angezeigt.
  • Email ist nur für den Administrator, sie wird nicht angezeigt.
  • Du kannst deine Kommentare eine Zeit lang editieren oder löschen.
  • Du kannst Formatierungen im Kommentar verwenden, z.B: Code, Formeln, usw.
  • Externen Links und Bilder werden nicht angezeigt, bis sie der Admin freischaltet.

Copyright

Die Software auf dieser Seite und der Download dürfen frei verwendet, abgeändert und weitergegeben werden, auch in kommerziellen Produkten.
Weitere Infos zur Seite
Erzeugt Donnerstag, 15. September 2016
von wabis
Zum Seitenanfang
Geändert Donnerstag, 23. März 2017
von wabis