EPROG Bsp. 3036 Inverse Matrix bestimmen (nach Gauss) Autor: Iris Attensam Matrikelnummer.: 0126732 ------------------------------------------------ Invertieren einer Matrix mittels Einheitsmatrix ------------------------------------------------ Problembeschreibung: -------------------- Die inverse Matrix soll mittels dem erweitertem Gauss'schen Eliminationsverfahren, ermittelt werden, wobei wie folgt vorgegangen werden soll: Eine Einheitsmatrix wird neben die zu invertierenden Matrix geschrieben: a1,1 a1,2 a1,3 1 0 0 a2,1 a2,2 a2,3 0 1 0 a3,1 a3,2 a3,3 0 0 1 Die Dimension wird durch Eingabe vom Benutzer bestimmt. Dannach werden die Elemente vom Benutzer in eine Matrix eingelesen und die inverse Matrix als Bruchzahlen ausgegeben werden. Als Eingaben sind nur Integer-Werte erlaubt bzw. nur bestimmte Intervalle, so darf die Dimension max. 5 und und nicht kleiner als 1 sein. Der Wertebereich der Elemente der Matrix muss zwischen [-100;100] liegen, werden diese überschritten meldet das Programm "Falsche Eingabe" bzw. im Fall von ungültigen Eingabewerten "?". Lösungsweg: ----------- Ich habe eine Hilfsklasse Fraction geschrieben, die eine Integer-Zahl in einen Bruch umwandelt. Weiters enthält diese Klasse Methoden die für die Berechnungen, Ausgabe und Vergleiche von Brüchen nötig sind. Für die Lösung des Gleichungssystem hab ich das Programm Dreigl.java (für Funktionsweise des Programms siehe Dokumentation am Ende) welches zur Verfügung gestellt wurde herangezogen und modifziert. Durch Änderung des Datentyps der Matrix erfolgen die Berchnungen, Überprüfungen und Ausgabe jetzt durch Aufrufe der Methoden der Klasse Fraction. Geändert wurde die Konstante Rang die jetzt durch Einlesen die Dimension der Matrix angibt und nun durch [RANG][2*RANG] bestimmt ist. Weiters hab ich eine for-Schleife eingefügt wodurch die Einheitsmatrix erzeugt wird. Angepasst wurden auch die Variablen INPUTMAX und INPUTMIN auf den in der Spezifikation verlangten Wertebereich. ______________________________________________________________________ ______________________________________________________________________ --------------------------------------- Dokumentation des Programms Dreigl.java --------------------------------------- EPROG Uebungsbeispiel Nummer 1118 - Gleichung mit drei Variablen Autor: Johannes Strodl Matrikelnummer: 9509605 eMail: e9509605@student.tuwien.ac.at ---------------------------------------------------------------------------- Loesen eines Gleichungssystems mittels des Gaus'schen Eliminationsverfahrens ---------------------------------------------------------------------------- Problembeschreibung: Ein lineares Gleichungssystem von drei Gleichungen und drei Unbekannten soll geloest werden. Die allgemeine Form der Gleichungen soll folgendermassen aussehen: a11*x1 + a12*x2 + a13*x3 = b1 a21*x1 + a22*x2 + a23*x3 = b2 a31*x1 + a32*x2 + a33*x3 = b3 Die Koeffizienten (a11 bis a33) und die Ergebnisse (b1 bis b3) werden vom Benutzer in eine Matrix eingelesen und das Ergebnis (x1 bis x3) ausgegeben. Es werden als Eingabe nur Integer-Werte akzeptiert. Moeglicherweise kann das lineare Gleichungssystem nicht mit den eingegebenen Werten nicht, bzw. nicht eindeutig geloest werden, in einem solchen Fall gibt das Programm "FALSCHE EINGABE" aus. Bei der Eingabe werden nur Zahlen in einem bestimmten Intervall (in diesem Beispiel [-20;20]) akzeptiert, ueberschreitet der Benutzer dieses Intervall ist ebenso "FALSCHE EINGABE" zu melden. Im Falle von ungueltigen Eingabewerten (ungleich Integer) liefert das Programm "?". Loesungsweg: Als Methode zum Loesen des Gleichungssystems wird das Gaus'sche Eliminationsverfahren verwendet, das kurz hier beschrieben wird: Die Matrix a11 a12 a13 b1 a21 a22 a23 b2 a31 a32 a33 b3 wird vom Benutzer eingelesen und so veraendert, dass ausgenommen der Diagonales (a11, a22, a33) und den Ergebnisswerten (b1, b2, b3) nur noch die Werte 0 in der Matrix steht. Also: a11 0 0 b1 0 a22 0 b2 0 0 a33 b3 Zu diesem Zwecke kann immer ein Vielfaches einer Zeile der Matrix zu einer anderen Zeile Addiert werden. Weiteres werden dann die Zeilen durch die jeweiligen inversen Werte in der Diagonalen dividiert, sodass in der Diagonalen nur noch der Wert 1 stehen bleibt. Nun kann man in b1, b2 und b3 die Werte von x1, x2 und x3 ablesen. 1 0 0 b1 => x1 = b1 0 1 0 b2 => x2 = b2 0 0 1 b3 => x3 = b3 Bei diesem Loesungsweg koennen Schwierigkeiten auftreten: Befindet sich in der Diagonale der Wert 0, kann das Gleichungssystem auf diese Art nicht geloest werden. In solch einem Fall werden solange Zeilen der Matrix vertauscht, bis eine Matrix gefunden wurde, in deren Diagonale keine 0 vorkommt. Ein anderes Problem besteht in dem Fall, wenn die Koeffizienten einer Gleichung ein Vielfaches einer anderen Gleichung sind. In diesem Fall werden bei der Addition der einen Zeile mit dem Vielfachen der anderen alle Koeffizienten gleich 0 und somit auf jeden Fall auch die Diagonale. Tritt dieser Fall auf, kann das Gleichungssystem nicht geloest werden. Das Programm: Das Programm behandelt den Rang (Anzahl der Gleichungen und Unbekannten) flexibel, d.h. durch umstellen der Variabel RANG kann das Programm auch mit anderen Gleichungssystemen hoeher oder niedriger als 3 umgehen. Aus diesem Grund sind auch alle anderen Funktionen dynamisch und koennen sich an die jeweilige Anforderung anpassen. Zunaechst wird die Matrix vom Benutzer mittels der Funktion readInput eingelesen. Diese teilt dem Hauptprogramm mit, ob die Eingabe der Spezifikation entspricht, oder nicht. Wird der Typ der Eingabewerte verletzt (Integer) erzeugt die Funktion eine Exception, die abgefangen werden kann. Stimmen die Typen der Eingabe und deren erlaubtes Intervall, wird vom Programm ueberprueft, ob die Diagonale Werte gleich 0 enthaelt. Zu diesem Zweck wird die Funktion checkDiagonal aufgerufen, die true zurueckliefert, wenn die Diagonale in Ordnung ist, andernfalls false. Ist die Diagonale nicht in Ordnung, muss die Matrix umgestellt werden, sodass ein Zustand erreicht wird, in dem die Diagonale in Ordnung ist. Die einzige erlaubte Operation auf die Matrix, ist das umsortieren der einzelnen Zeilen der Matrix, da ja die Reihenfolge der einzelnen Gleichungen im Gleichungssystem irrelevant ist. Dies ist sicher der komplexeste Bereich im Programm. Das Programm erzeugt eine Liste aller moeglichen Anordnungen der Zeilen der Matrix, also: Zeile 1 - Zeile 2 - Zeile 3 Zeile 2 - Zeile 1 - Zeiel 3 Zeile 1 - Zeile 3 - Zeile 2 etc. Um solch eine Liste zu erstellen baut das Programm einen Baum mit allen Moeglichkeiten auf, d.h. alle Permutationen der Zeilenanordnung werden durchgegangen. Fuer diese Aufgabe ist die sich rekursiv aufrufende Funktion permutation zustaendig. Sie erzeugt diesen Baum und arbeitet Blatt fuer Blatt den Baum aller moeglichen Anordnungen ab. Findet die Funktion eine Anordnung, in der die Diagonale in Ordnung ist, bricht sie die Suche ab und liefert eine Referenz auf diese neue Matrix der aufrufenden Funktion zurueck. Findet die Funktion permuatation keine Matrix die tauglich ist, liefert sie null zurueck und signalisiert die Niederlage. In diesem Fall kann das Gleichungssystem nicht geloest werden. (Zur Erklaerung: das Array order, bzw. tmporder beinhalten die aktuell berechnete Anordnung der Zeilen, also 1,2,3 oder 2,1,3 oder 3,2,1 .... die Variable pos kennzeichnet die Position in diesem Array, die gerade veraendert werden darf. Diese gekennzeichnete Position wird nun mit den verbleibenden anderen Positionen getauscht. Die Funktion ruft sich mit dem neuen order nun selbst auf und erhoeht pos um eins, damit ist die naechst Position in der Reihe. Sind keine Positionen mehr uebrig wurde ein Blatt des Baumes erreicht und mit der Anordung kann eine neue Matrix erzeugt werden, die mit checkDiagonal getestet wird.) Zum loesen der Gleichung wird nun die Funktion solveEquations aufgerufen. Diese kann, mittel der Funktion addMultipleEquation Vielfache eine Zeile zu anderen Zeilen addieren. Dies tut sie mittels jenem Faktor, mit dem die Werte abseits der Diagonale 0 werden. Die Funktion berechnet in zwei Schleifen die gesamte Matrix neu. Am Ende multipliziert die Funktion mit Hife der Funktion multiplyEquation den reziprokwert der Werte in den Diagonalen (z.B. 1/a11) zu der aktuellen Zeile und erzeugt so den Wert von 1 in der Diagonalen. Das letzte Problem besteht in dem Fall, dass eine Zeile der Matrix ein Vielfaches einer anderen Zeile war. In diesem Fall steht in der betreffenden Zeile nun nicht 1 sondern 0. Aus diesem Grund wird die Diagonale noch einmal ueberprueft. Ist diese nicht in Ordnung kann das Gleichungssystem nicht geloest werden. Ist die Diagonale jedoch in Ordnung, koennen die Werte fuer x1, x2, ... in b1, b2, ... ausgelesen werden. Genau das ist die Aufgabe der Funktion printResult. Diese liefert das Ergebnis in einer Zeile formatiert aus. Fuer Probleme bzw. Fragen stehe ich jederzeit gerne zur Verfuegung Johannes Strodl