AUTOR: Ulrich Omasits (0307190)
KONTAKT: ulrich.omasits@estudy.cc
AUFGABENSTELLUNG:
Ein lineares inhomogenes Gleichungssystem von drei Gleichungen in drei Unbekannten soll gelöst werden.
z.B: a11*x1 + a12*x2 + a13*x3 = b1
a21*x1 + a22*x2 + a23*x3 = b2
a31*x1 + a32*x2 + a33*x3 = b3
kurz: a11 a12 a13 b1
a21 a22 a23 b2
a31 a32 a33 b3
Wobei a11 bis b3 (in der Reihenfolge a11 a12 a13 b1 a21 a22 a23 b2 a31 a32 a33 b3 jeweils durch
ein Leerzeichen bzw. Enter getrennt) eingegeben und x1, x2 und x3 berechnet werden sollen.
MEINE LOESUNG:
-- Der Algortihmus:
Zur Loesung dieses Problems habe ich das Gauss'sche Eliminationsverfahren verwendet.
Diesen will ich nun anhand eines Beispiels erklaeren:
Gegeben sei folgendes Gleichungssystem (die linke Seite stellt ein spezielles Beispiel dar, waehrend die rechte
immer allgemein gehalten ist):
1 2 3 4 a11 a12 a13 b1
2 2 4 5 <-> a21 a22 a23 b2
1 -1 1 7 a31 a32 a33 b3
Der erste Hauptschritt besteht nun in der ELIMINATION:
Zuerst eliminiere man durch Addition geeigneter Vielfacher der ersten Gleichung zu jeder der anderen
Gleichungen die erste Variable in allen Gleichungen mit Ausnahme der ersten. Dann eliminiere man durch
Addition geeigneter Vielfacher der zweiten Gleichung zu jeder der Gleichungen von der dritten bis zur N-ten
die zweite Variable in allen Gleichungen mit Ausnahme der ersten zwei... u.s.w
In diesem Fall beenden wir nach der dritten Variable die Elimination, da wir nur N=3 Gleichungen haben.
Am Beispiel:
- die erste Zeile bleibt
- die zweite ergibt sich nun aus der ehemaligen zweiten - 2 * der ersten (-2 weil -a21/a11 = -2/1 = -2)
- die dritte Zeile ergibt sich aus der ehem. dritten - 1 * der ersten (-1 weil -a31/a11 = -1/1 = -1)
1 2 3 4 a11 a12 a13 b1
2-2*1 2-2*2 4-2*3 5-2*4 <-> a21-a21/a11*a11 a22-a21/a11*a12 a23-a21/a11*a13 b2-a21/a11*b1
1-1 -1-2 1-3 7-4 a31-a31/a11*a11 a32-a31/a11*a12 a33-a31/a11*a13 b3-a31/a11*b1
- nach Addition (bzw. Subtraktion) ergibt sich die neue Matrix:
1 2 3 4 a11 a12 a13 b1
0 -2 -2 -3 <-> 0 a22 a23 b2
0 -3 -2 3 0 a32 a33 b3
- im zweiten Druchlauf bleibt die erste und die zweite Zeile gleich
- die dritte ergibt sich aus der vorigen dritten Zeile - 3/2 * der zweiten (-3/2 weil -a32/a22 = -(-3/-2) = -3/2)
1 2 3 4 a11 a12 a13 b1
0 -2 -2 -3 <-> 0 a22 a23 b2
0 -3-3/2*(-2) -2-3/2*(-2) 3-3/2*(-3) 0 a32-a32/a22*a22 a33-a32/a22*a23 b3-a32/a22*b2
- nach Addition (bzw. Subtraktion) ergibt sich die neue Matrix:
1 2 3 4 a11 a12 a13 b1
0 -2 -2 -3 <-> 0 a22 a23 b2
0 0 1 -7.5 0 0 a33 b3
- nun kann die Elimination abgeschlossen werden, da die Matrix in der sogenannten Halbdiagonalform vorliegt (nur
Nullen unter der Diagonale)
Das einzige Problem besteht nun darin, dass a11 oder a22, durch welche ja dividiert wird, null sein kann. Um dies
zu verhindern tauscht man, in dem Falle das a11 oder a22 null ist einfach mit einer anderen folgenden Zeile, die
an der Stelle 1 bzw. 2 einen Koeffizienten ungleich null hat, sodass dann dividiert werden kann!
Das Gleichungssystem sieht nun folgendermaßen aus:
x1 + 2*x2 + 3*x3 = 4 a11*x1 + a12*x2 + a13*x3 = b1
-2*x2 - 2*x3 = -3 <-> a22*x2 + a23*x3 = b2
x3 = 7.5 a33*x3 = b3
Die Lösung dieser Gleichungen ist ja nicht sonderlich schwierig...
Der zweite Hauptschritt besteht aus dem RUEKWAERTS-EINSETZEN:
In jeder Zeile werden nun die bereits erhaltenen x-Werte mit ihren Koeffizienten ausmultipliziert, dann addiert und
alle auf die rechte Seite der Gleichung (die n+1 te Spalte in der erweiterten Matrix!) subtrahiert. Schließlich wird
die ganze Zeile noch durch den Koeffizient der gesuchten Variable dividiert, und somit erhält man eine weitere Lösung
für einen x-Wert. Dies wird insgesamt n=3 mal wiederholt.
Am Beispiel:
- man beginnt mit der untersten Zeile
1*x3 = 7.5 <-> a33*x3 = b3
x3 = 7.5 x3 = b3/a33
- nun die vorletzte bzw. die zweite Zeile, wobei man fuer x3 schon 7.5 einsetzen kann
-2*x2 - 2*x3 = -3
-2*x2 - 15 = -3 a22*x2 + a23*x3 = b2
-2*x2 = 12 <-> a22*x2 = b2-a23*x3
x2 = -6 x2 = (b2-a23*x3)/a22
- und nun noch, um x1 zu erhalten, die erste Zeile
1*x1 + 2*x2 + 3*x3 = 4
1*x1 - 12 + 22.5 = 4 a11*x1 + a12*x2 + a13*x3 = b1
1*x1 = 4 - 10.5 <-> a11*x1 = b1 - (a12*x2 + a13*x3)
x1 = -6.5/1 = -6.5 x1 = (b1 - (a12*x2 + a13*x3))/a11
Die nun erhaltenen Loesungen fuer x1, x2 und x3 muessen nun noch, vorausgesetzt es ist kein Fehler aufgetreten,
ausgegeben werden.
-- Zum Programm:
Das Programm besteht aus vier Abschnitten:
1.) Initialisierung der Konstanten und Variablen.
Wobei ich einfachheitshalber b1, b2 und b3 als vierte Spalte in die Koeffizientenmatrix integriert habe
(-> erweiterte Koeffizientenmatrix), sodass sich z.B. b2 als a[2][4] ergibt.
Die 3 Booleans verwende ich um das Auftreten eines Fehlers zu dokumentieren um ihn am Ende der Main-Methode
zu behandeln.
2.) Main-Methode
Hier werden die Zahlen eingelesen und es wird ueberprueft, ob sie einem Integer zwischen -20 und +20 entsprechen.
Anschliessend, falls kein Fehler aufgetreten ist, werden die beiden Rechenoperationen (Elimination und
Ruekwaerts-Einsetzen) durchgefuehrt.
Am Schluss wird dann das Ergebnis oder die entsprechende Fehlermeldung ausgegeben.
Die Integer i und j sind lediglich Laufvariablen, die die for-Schleifen steuern.
3.) Elimiations-Methode
Hier werden wie oben beschrieben die Koeffizienten eliminiert um die Matrix in eine Halbdiagonalform zu bringen.
Die gerade bearbeitete Zeile wird mit der getauscht, wo der Koeffizient am groeßten ist, um zu verhindern dass
a[i][i], durch welches ja dividiert wird, null ist. Falls a[i][i] nach dem Tausch noch immer null ist, heisst das,
dass es keine Zeile mehr gibt, in der der i-te Koeffizient ungleich null ist und daher das Gleichungssystem nicht
eindeutig loesbar ist. Ist es aber loesbar wird nun Subtrahiert und so schrittweise die Halbdiagonalform eingestellt.
Die Integer i, j und k sind wieder Laufvariablen, waehrend der Integer max zur Speicherung der Zeile mit dem groessten
i-ten Koeffizienten benoetigt wird. Zur Bestimmung des absolut groessten Koeffizienten dient die Funktion Math.abs(float).
Der Float t ist lediglich Zwischenspeicher beim Koeffiziententausch zwischen zwei Zeilen.
4.) Rueckwaerts-Einsetz Methode
Als erstes wird hier ueberprueft ob das Gleichungssystem ueberhaupt loesbar ist, oder ob man waehrend der Elimination
herausgefunden hat, dass zum Beispiel a[3][3] = 0 ist, was bedeuten wuerde, dass z.B. 0*x3 = 4 ist und das
Gleichungssystem dann keine eindeutige Loesung besitzt. Ist dies nicht der Fall wird wie oben beschrieben eine
Loesung nach der anderen berechnet.
Die Integer j und k dienen als Laufvariablen und der Float t dient zur Summation der ausmultiplizierten Koeffizienten.
-----------------------------------------------------------------------------------------------
Das Programm funktioniert wirklich einwandfrei. Ich habe es ausfuehrlichst getestet und saemtlich Fehler ausgebessert.
Ausserdem ist es durch die Konstante n=3 so allgemein wie moeglich gehalten, sodass man damit eigentlich auch ein allgemeines
Gleichungssystem mit n Gleichungen und n Unbekannten loesen kann (man muss nur die Konstante veraendern oder sie in eine Variable
umwandlen und den Benutzer eingeben lassen!!).
Ich hoffe irgendjemand kann dieses Programm vielleicht noch einmal weiterverarbeiten oder sich zumindest davon inspirieren lassen!
Der Autor.