Lineare Gleichungssysteme

Gauß-Elimination

Gedachte Darstellung des Gleichungssystems ist:

a₁₁* x₁+ a₁₂* x₂+ ... + a_1n* x_n= b_{1
... ...}

a_n1* x₁+ a_n2* x₂+ ... + a_nn* x_n= b_n

Die Koeffizienten a_ij des Systems aus n Gleichungen mit n Unbekannten liegen im Array A(1..n, 1..n), die rechten Seiten der Gleichung b_i sind als (n+1)te Spalte in das Array A() aufgenommen. Die Lösung wird in den Vektor X(1..n) geschrieben. S ist eine Hilfsgröße (vom Typ Single), i, j, k sind Integer.

Bei diesem Algorithmus werden Spalte für Spalte (Zähler ist k) die jeweils unterhalb der Hauptdiagonalen stehenden Glieder eliminiert, indem von der zu behandelnden Gleichung ein geeignetes Vielfaches der k-ten Gleichung abgezogen wird. Es entsteht eine Dreiecksmatrix, die anschließend rückwärts aufgelöst wird.

Es handelt sich hier noch um den "Roh-Algorithmus", denn die Divisionen durch A_(k,k) könnten schiefgehen (bei A_(k,k)=0). Das würde den Programmabbruch zur Folge haben. An dieser Stelle ist eine Routine zum Auffangen des Fehlers erforderlich, weil eine Meldung allemal besser als ein Fehlerabbruch ist. Der Einbau von Fehlerroutinen gehört beim Hobbyprogrammierer eher zur "Schönheitspflege", im professionellen Bereich ist er natürlich Pflicht.

Wenn das GS nicht lösbar ist, was wir mal außen vor lassen wollen, kann das Verfahren ungenau werden oder, trotz Lösbarkeit versagen, wenn eines der Hauptdiagonalelemente der Matrix A(i,j) zu klein ist oder im Zuge der Elimination zu klein wird oder gar verschwindet.
Das Zauberwort heißt "Pivotsuche".
Man bestimmt vor jeder Eliminationsrunde das größte in Frage kommende Element der Restmatrix für die Division. Damit unter den Gleichungen die Chancen gleichmäßig verteilt sind, wird zuvor "normalisiert". Für die theoretischen Überlegungen dazu lese man die einschlägige Literatur. (Einschlägig heißt hier, daß das Lesen so viel Freude macht, wie eine Tracht Prügel zu empfangen).
Es folgt eine komplette Prozedur, n ist der Grad des Gleichungssystems, A () ist wie im oberen Beispiel belegt (Achtung, der Inhalt von A() wird verändert!), in x() wird die Lösung zurückgeliefert.

Householder-Algorithmus

Wenn die Koeffizientenmatrix des GS symmetrisch ist, transformiert das Householder-Verfahren diese in tridiagonale Form, die sich dann leicht auflösen läßt. Der Vorteil ist hohe numerische Stabilität des Verfahrens; der Rechenaufwand etwa doppelt so hoch, wie beim Gauß-Verfahren.

Matrizeninversion

Beispiel für einen komplexeren mathematischen Algorithmus (wer ihn braucht, weiß wozu!), dynamische Variable, Prozeduraufrufe mit Variablenübergabe, Dimensionierung.
Es werden zunächst nur die Variablen für die Matrix und den Rang der Matrix deklariert. Dann folgt die eigentliche Matrixinversion. Sie benötigt eine kleine Tauschroutine, die ebenfalls gezeigt wird.

Das war es schon. Und was macht man mit einer Routine allein? Nicht mal testen kann man sie. Deshalb brauchen wir einen Aufruf, der beispielsweise eine Testmatrix mit Zufallszahlen belegt. Ob unsere Matrixinversion richtig rechnet, kann man bei der Gelegenheit ebenfalls testen, denn die Inverse der Inversen muß wieder die Ausgangsmatrix ergeben.

Damit sich niemand wundert: Die auskommentierten Zeilen bauen einen String auf, der die Matrix selbst sowie die Matrix der Differenzen anzeigt. Für die Anzeige dient ein Textfeld namens txtText.

Eine wichtige Anwendung der Matrizeninversion ist die Lösung von linearen Gleichungssystemen. Dieses Lösungsverfahren hat ja den immensen Vorteil, sofern man nur die invertierte Matrix kennt, besonders elegant zu sein. Denn wenn Ax = b das Gleichungssystem in vektorieller Schreibweise beschreibt, dann ist x = A^-1Ax = A^-1b bereits die Lösung. Deshalb:

Gauß-Seidel-Iteration

Iterative Verfahren zur Lösung linearer GS, von denen es gleich mehrere gibt, (Jacobi, Gauß-Seidel, SOR), beruhen auf der Überlegung, daß man das Gleichungssystem Ax = b (vektoriell geschrieben) schrittweise lösen kann, indem man, immer im Kreis,x^(neu) = x^(alt) - Korr rechnet, wobei Korr ein Korrekturvektor ist, der irgendwie aus der Differenz von Ax^(alt) und b, also dem Fehler gerechnet wird, den der alte x-Vektor im GS erzeugt. Man beginnt mit geratenen Werten und wenn man einen guten Tag hat, dann verschwindet irgendwann das Korrekturglied. Das nennt man dann: "Die Iteration steht". Der absolute Glücksfall.

Die Gauß-Seidel-Iteration ist speziell für schlecht konditionierte GS geeignet. Sie reagiert zudem weniger empfindlich auf fehlerbehaftete Koeffizienten als das Gauß-Verfahren. Der Nachteil ist, daß natürlich die Rechenzeit erheblich größer ist, als bei direkten Algorithmen. Dazu vergleiche man den Test am Ende dieser Seite.

Vergleichender Test

Ein Vergleich der Leistungsfähigkeit der gezeigten Algorithmen ist deshalb nicht sehr sinnvoll, weil diese für unterschiedliche Anforderungen optimiert sind. Aber interessant ist es allemal. Ich wähle hier ein schwach konditioniertes Gleichungssystem, dessen Koeffizientenmatrix, die sog. "Hilbertmatrix" zudem symmetrisch ist.

Die Koeffizientenmatrix mußte jeweils neu geholt werden, weil die Verfahren das aufrufende Array überschreiben (Bei Arrays gibt es leider keinen ByVal-Aufruf!)

zunächst 12 Gleichungen mit 12 Unbekannten

Wie es aussieht, ist die Welt in Ordnung. Aber, schon eine Variable mehr verändert die Situation erheblich. Der Versuch mit dreizehn Gleichungen und dreizehn Unbekannten zeigt, daß wir numerisch im Grenzbereich wandeln:

Nur Gauß-Seidel hat die Fassung bewahrt; keine Kunst, dieses Verfahren ist ja speziell für diese Sorte Gleichungssystem gedacht. Da kann man die größere Rechenzeit schon tolerieren.