3. Gauß-Seidel Verfahren

3.1 Grundprinzip

Das Programm für dieses Verfahren unterscheidet sich, genauso wie das Verfahren selbst, von den beiden vorherigen fast völlig. Folglich läßt sich von den beiden vorherigen, abgesehen von der Ein- und Ausgaberoutine und Pivotierung, nichts übernehmen.
Bevor das Iterationsverfahren starten kann, muß zuerst das beste Pivotelement gesucht werden, um ein divergieren des Iterationsprozesses zu vermeiden. Im Gegensatz zu den beiden vorherigen Verfahren wird beim Gauß-Seidel Verfahren in einem Zug durchpivotiert, d.h. die Pivotierung steht getrennt vor den Iterationsanweisungen.
Zur Pivotierung benötigt man drei Schleifen, wobei zwei in einer verschachtelt sind. Die äußerste Schleife ist die k- Schleife, die von 1 bis n-1 läuft und die Spalten durchläuft, aus welchen das Pivotelement ermittelt werden soll. Der nun folgende Programmteil aus i- und j-Schleife ist aus den beiden vorher beschriebenen Programmen bekannt.
Nun kommt die Überprüfung des Gleichungssystems. Die äußere i-Schleife durchläuft die zeilenweise das Gleichungssystem. Stößt die innere j-Schleife nur auf eine Zeile, in der das Pivotelement nicht überwiegt, ist das Gleichungssystem bereits ungeeignet, bricht die i-Schleife ab und eine Meldung wird ausgegeben. An dieser Stelle könnte man auch gleich das Programm abbrechen.
Die Variable SZeile enthält immer die Summe der Beträge der Koeffizienten der Zeile i ohne das Diagonalelement.
Aber nun zur Umsetzung des Iterationsprozesses. Zuerst einmal muß man die initiale Näherung bestimmen, d.h. alle Felder des Arrays "Lösung" auf Null setzen, dann kann man den Iterationsprozeß starten. Man benötigt zur Programmierung drei ineinander verschachtelte Schleifen. Die äußerste bestimmt die Dauer des Iterationsprozesses. Dieser soll nämlich, nach folgenden Kriterien abgebrochen werden. Entweder wenn die Lösung gefunden wurde, d.h. wenn sich die Näherung gegenüber der vorherigen nicht mehr verbessert, oder wenn die Zahl der Iterationen über einen vorgegebenen Wert hinaus gewachsen ist. Hierzu bietet sich eine REPEAT-DO-UNTIL-Schleife an, da man die Anzahl der Durchläufe vorher nicht kennt. Zu Beginn dieser Schleife wird die Laufvariable um
eins erhöht, dann startet die nächste Schleife, die i-Schleife. Diese beginnt bei dem Wert eins und endet bei n. In dieser Schleife werden jeweils die x_i mit i=1..n berechnet. Jetzt folgt bereits die innerste Schleife, die j-Schleife, die ebenfalls die Werte von eins bis n durchläuft. Mit dieser Schleife wird jeweils der Zähler aus den vorherigen Iterationen bzw. der initialen Näherung und den dazugehörigen Koeffizienten berechnet. Nach dieser Schleife kann nun das neue x_i berechnet werden, wobei vorher wieder ein "Division by Zero"-Fehler abgefangen werden muß. Nun wird noch verglichen, ob sich Genauigkeit der neuberechneten Lösung gegenüber der alten verbessert hat. Ist dies nicht der Fall, so wird der Iterationsvorgang beendet. Die andere Möglichkeit wäre, daß die Maximalzahl der Iterationen überschritten wurde und somit keine genaue Lösung gefunden wurde. Diesen Fall mit einzubeziehen ist wichtig, da das Programm vom Computer bis in die Ewigkeit weitergeführt würde, ohne eine Lösung zu finden. Hier der Programmtext:

PROCEDURE GaussSeidel;                                                  
VAR Pivotelement, Zähler, NeueLösung, SZeile: REAL;                     
    Pivotzeile, i, j, k, Iteration: INTEGER;                            
    Fertig, geeignet: BOOLEAN;                                          
BEGIN                                                                   
  FOR k:= 1 TO n - 1 DO                                                 
    BEGIN                                                               
      Pivotelement:= 0;                                                 
      FOR i:= 1 TO n DO  {* Pivotelement suchen}                        
        IF Abs(Koeffizient[i, k]) > Pivotelement THEN BEGIN             
          Pivotelement:= Abs(Koeffizient[i, k]);                        
          Pivotzeile:= i;                                               
        END;                                                            
      IF k <> Pivotzeile THEN {* wenn k=i, Pivotelement bereits günstig}
      FOR j:= 1 TO n + 1 DO {* Zeilen vertauschen}                      
        Exchange(Koeffizient[k, j], Koeffizient[Pivotzeile, j]);        
    END;                                                                
                                                                        
  geeignet:= TRUE;       {* überprüfen, ob Gleichungssystem geeignet}   
  i:= 1;                                                                
  REPEAT                                                                
    SZeile:= 0.0;                                                       
    FOR j:= 1 TO n DO                                                   
      IF i <> j THEN SZeile:= SZeile + Abs(Koeffizient[i, j]);          
    IF SZeile >= Abs(Koeffizient[i, i]) THEN geeignet:= FALSE;          
    i:= i + 1;                                                          
  UNTIL (i > n) OR NOT geeignet;                                        
  IF NOT geeignet THEN                                                  
  WriteLn('Gleichungssystem ungeeignet');                               
  WriteLn;                                                              
                                                                        
  FOR i:= 1 TO n DO                                                     
    Lösung[i] := 0;  {* erste Lösungsnäherung}                          
                                                                        
  Iteration:= 0;                                                        
                                                                        
  REPEAT                                                                
    Iteration:= Iteration + 1;                                          
    Fertig:= TRUE;                                                      
    FOR i:= 1 TO n DO                                                   
      BEGIN                                                             
        Zähler:= Koeffizient[i, n + 1];                                 
        FOR j:= 1 TO n DO                                               
          IF i <> j THEN Zähler:= Zähler - Koeffizient[i, j]*Lösung[j]; 
        IF Koeffizient[i, i] = 0 THEN Abbruch;                          
        NeueLösung:= Zähler / Koeffizient[i, i];                        
        IF NeueLösung <> Lösung[i] THEN Fertig:= FALSE;                 
        Lösung[i] := NeueLösung;                                        
      END;                                                              
  UNTIL Fertig OR (Iteration >= MaxIterationen);                        
END;