Algorithmus zum Lösen linearer Gleichungssysteme

Gegeben

a₀x₀ + ... + a_n-1x_n-1 = z;    a₀...a_n-1,z R

Globale Variablen

• Array für k nummerierte Gleichungen mit n Unbekannten x_i und n Parametern p_i der Form
  a0x0 + ... + an-1xn-1 = z + b0p0 + ... + bn-1pn-1;    a0...an-1,b0...bn-1,z R
  Ausgangszustand: Die gegebenen Gleichungen
• Array(s) mit n Feldern, dass für jede Unbekannte
  • festlegt, ob sie sich aus einer Gleichung ergibt, ein Parameter ist, oder dies noch unbekannt ist
  • ggf. die Nummer der entsprechenden Gleichung bzw. des entsprechenden Parameters angibt.
  Ausgangszustand: "unbekannt"
• Array mit k Feldern, dass für jede Gleichung angibt, ob sie noch "verfügbar" ist.
  Ausgangszustand: "verfügbar"
• Zähler paramzahl für die Anzahl der bereits vergebenen Parameter.
  Ausgangszustand: 0

Rechenschritte

1. Für i := 0,...,n-1
   Überprüfe, ob es verfügbare Gleichungen gibt, in denen x_i vorkommt
   • wenn ja:
     Wähle beliebig eine dieser Gleichungen und
     1. Markiere sie als nicht verfügbar.
     2. Markiere x_i als durch Gleichung gegeben und vermerke die Nummer der gewählten Gleichung.
     3. Addiere entsprechende Vielfache der gewählten Gleichung zu allen anderen Gleichungen, um x_i aus diesen zu eliminieren.
     4. Multipliziere die gewählte Gleichung so, dass x_i den Koeffizienten 1 erhält.
   • wenn nein:
     1. Markiere x_i als Parameter mit Nummer paramzahl.
     2. Erstelle eine temporäre Gleichung xi = pparamzahl.
     3. Addiere entsprechende Vielfache der temporären Gleichung zu allen anderen Gleichungen, um x_i aus diesen zu eliminieren.
        (Die temporäre Gleichung kann danach gelöscht werden.)
     4. paramzahl um 1 erhöhen
2. Überprüfe, ob alle noch verfügbaren Gleichungen wahr sind
   • wenn ja:
     Das Gleichungssystem ist lösbar.
     Die Lösung für jedes x_i ergibt sich
     • falls x_i als durch Gleichung gegeben gekennzeichnet ist, aus der Gleichung der angegeben Nummer. (Diese ist bereits nach x_i aufgelöst.)
     • falls x_i als Parmeter gekennzeichnet ist, als x_i = p_{angegebene Nummer}.
   • wenn nein:
     Das Gleichungssystem enthält einen Widerspruch und ist nicht lösbar.