Techniklexikon

Gauss-Seidel-Verfahren

Mathematische Methoden und Computereinsatz, Methode zur numerischen Lösung mehrdimensionaler Optimierungsprobleme, also von Problemen der Form: min_x Î ⁿ f(x), mit n im Vektor x zusammengefassten Optimierungsvariablen x_1,...n. Die Aufgabe besteht darin, ein lokales Minimum auf einer n-dimensionalen Hyperfläche (Sattelfläche) zu finden, d.h. einen Vektor x^*, für den der Gradient f_x(x^*) verschwindet. Das Prinzip einer iterativen Struktur von numerischen Verfahren zur Lösung dieses Problems besteht nun darin, ausgehend von einem Startpunkt x⁰ eine Suchrichtung s⁰ zu bestimmen und mit einer bestimmten Schrittweite a den Startpunkt in diese Richtung zu variieren, wobei sich a aus der Lösung des Minimierungsproblems min f(x⁰ + as⁰) ergibt. Anschliessend setzt man x¹ = x⁰ + as⁰, sucht erneut eine Suchrichtung usw. Die Suchrichtung muss dabei auf jeden Fall mit dem Gradienten einen stumpfen Winkel, d.h. ein negatives Skalarprodukt bilden, um eine Abstiegsrichtung zu sein und tatsächlich dem Minimum zuzustreben. Beim Gauss-Seidel-Verfahren sucht man nun bei jeder Iteration abwechselnd in eine der Koordinatenrichtungen: s^k = (0,...,0,-sign(f_x)_j(x^k), 0,...)^T, s^k+1 = (0,...,0,-sign(f_x)_j+1(x^k+1), 0,...)^T usw. Damit ist automatisch die Bedingung des stumpfen Winkels erfüllt. Das Gauss-Seidel-Verfahren hat den Vorteil, dass es ohne eine vollständige Berechnung des Gradienten auskommt, sondern immer nur eine Komponente benötigt. Allerdings leidet die Effizienz unter der erheblichen Anzahl an Iterationen.