Für Interessierte: Mein Programm zum lösen von LGS (n,n)-Systeme

Hallo

@dummer kommentar
Dabei handelt es sich um ein Matheprogramm, dass in der Oberstufe nutzlich ist und demnach ist das abfangen von zeichen nicht nötig- Man soll schon in der Lage sein Zahlen einzugeben. (ich weis.. bin nicht ganz DAU-freundlich)

@jester
Ich bin ganz deiner Ansicht. Die Sache ist nur die, dass ich dann noch paar Bruchfunktionen implementieren müsste und ich hab mich spontan dazu entschlossen mit kommazahlen zu rechnen. Der datentyp den ich für die Zahlen nutze operiert mit Kommazahlen bis zur 16ten Nachkommastelle.
Die Ergebnisse sind EXTREM gut angenähert.
Sicher wären Brüche schöner aber zum kontrollieren der Ergebnisse die man shcriftlich ermittelt hat genügt die jetzige bAusgabe vollkommen.
Außerdem kommen in Schulaufgaben NIE irrationale Werte raus sondern fast immer Ganzzahlen.

"Außerdem haben viele LGS keine oder unendlich viele Lösungen. Die kann man im Moment garnicht lösen."
--> Wenn dein Gleichungsystem keine Lösungen hat wird dir das gesagt. Mehr kann ich nicht machen. Wie soll er ein LGS ohne Lösungen lösen? Dann sagt er dir dass es keine Lösungen gibt!
Zu unendlich vielen Lösungen: Wenn unendlich viele Lösungen vorliegen sagt er dir dass es unendlich viele Lösungen gibt. Sämtliche Lösungen könnte man noch sukzessiv berechnen (mit Parametern) aber darauf habe ich verzichtet denn wenn man die braucht kann man einfach die endform des LGS vom Bildschrim abschreiben und in paar S ekunden schriftlich ermitteln. Das ganze orientiert sich sehr an meinen Bedrüfnissen in der Schule und der Lehrer sagt er verlangt keine Berechnung der Lösungen mit Parametern sondern es genügt ihm wenn man sagen kann dass es unendliche sind.

LGS-Master 1.0 ist sicher keine Profi-LGS-Software ist aber FreeWare und deckt alle Bedürfnisse des 0815 Schülers in der Oberstufe.

MfG.

PS: Hmmm.. Version 2.0 könnte ja vll bischen mehr... aber wenn dann nächstes Jahr.

henselstep

Du hast vermutlich den Gauss-Algorithmus verwendet, nicht wahr? Du wirst feststellen, dass dein Programm bei einigen Matrizen, die etwas grösser sind, grob falsche Werte berechnen wird, was nicht an einer evtl. falschen Programmierung liegt. Gebe z.B. mal die (20x20) Hilbert-Matrix ein. Das ergibt eine totale Katastrophe. Bruchzahlen würden hier zwar etwas helfen (Da bis zu einem gewissen Grade nicht gerundet wird) Wenn dich das Thema aber interessiert, informier dich mal über das Householder-Verfahren oder das Gauss-Seidel-Verfahren. Die sind genauer.
(Achtung: Gauss-Seidel könnte versagen, aber wenn es nicht versagt, ist es genauer)

Ringding

Ich könnte nachschauen, aber du kannst es mir bestimmt schneller sagen: Besteht nicht der einzige Unterschied darin, dass man als Pivot-Element das betragsmäßig größte wählt?

henselstep

Nein
Das Gaussverfahren führt im Prinzip auf die sogenannte LR-Zerlegung. Es versagt aber manchmal, und daher gibt es die Variante mit der Pivotisierung
P*A = L*R
Wobei P eine Permutationsmatrix ist, in L die Schritte des Gaussverfahrens gespeichert ist (linke untere Dreiecksmatrix) und R die bekannte rechte obere Dreiecksmatrix ist, die man haben will. Indem man die Operationen auch auf den Lösungsvektor mitanwendet, tut man ihn im Prinzip mit L und P^(-1) multiplizieren, worauf man ihn mit R lösen kann.

Das Householder-Verfahren dagegen führt auf die sogenannte QR-Zerlegung, wobe R wieder eine obere rechte Dreiecksmatrix ist, aber Q nun eine orthoganale Matrix ist. (D.h. det Q = 1). Der grosse Vorteil ist, dass nun auch die Kondition, ein Mass für den relativen Fehler, 1 ist, also im Prinzip minimal.

Wie berechet man diese Zerlegung?
Angenommen, man ist im k-ten Schritt
Dann betrachte man die Matrix A´ ohne die ersten k-1 Spalten und Zeilen.
Sei dann der erste Spaltenvektor a. Dann setze v=a+||a||(1,0,0,..,0) (n-k-1 Nullen).
Nun berechne für jede Spalte b: b´=b-2(b^T*v)*v/(vT*v)
Dieses ^T bedeutet dabei transponiert.
Mache dies dann auch mit dem Lösungsvektor.
sobald k=n ist, hast du dein R, und du kannst wie bei Gauss, dann ganz schnell lösen. Und das Ergebnis ist fast immer genauer.

fubar

henselstep schrieb:

Das Gaussverfahren führt im Prinzip auf die sogenannte LR-Zerlegung. Es versagt aber manchmal, und daher gibt es die Variante mit der Pivotisierung
P*A = L*R

Hmm? Man kann zeigen, daß es zu jeder regulären Matrix A eine Permutationsmatrix P gibt, sodaß PA in LR zerlegbar ist. Das hat aber soweit noch nichts mit Pivotstrategien zu tun. Die Existenz der Zerlegung läßt ja die Wahl des nächsten Pivotelements offen. Und da gibt es nun verschiede Strategien dieses zu wählen ... Oder habe ich dich nur falsch verstanden?

Korbinian

es gibt ein (oft) deutlich schelleres verfahren zum lösen von LGS als gauss und konsorten: betrachtet man die jeweiligen funktionen als geraden im n-dimensionalen raum, so müssen sie sich in einem punkt schneiden, insofern es eine lösung gibt. es gibt flotte verfahren (aehnlich dem eulerverfahren), die die lösung ziemlich flott (iterativ) berechnen. aber das ist vielleicht ot

Jester

Korbinian schrieb:

betrachtet man die jeweiligen funktionen als geraden im n-dimensionalen raum

Wie denn das? Meinst Du die einzelnen Zeilen der Matrix? Die beschreiben Hyperebenen. Und die Schnittberechnung ist genau das was der Gauß-Algo macht.
Und zwar ebenfalls iterativ...

Kannst Du genauer erläutern was Du meinst?

fubar

Jester schrieb:

... was der Gauß-Algo macht.
Und zwar ebenfalls iterativ...

Das Gauß-Verfahren ist - wie auch das Cholesky-Verfahren - ein "direktes" Lösungsverfahren.
Iterative Verfahren wären z.B. JOR-, SOR- oder cg-Verfahren. IMHO.

Korbinian

die methode die ich meinte, ist unter dem namen kaczmarz methode oder nah verwandt cimmino methode (wird bei algebraischer rekonstruktion von bildern bei z.b. CT verwendet), wobei jeweils die graphische idee dahinter steckt:
man stellt sich die jeweiligen zielen der matrix als geraden vor. man beginnt jetzt an einer beliebigen stelle, und fällt immer das lot auf eine der nächsten geraden. hat man alle durch und es existiert ein schnittpunkt, so hat man ihn bei der letzten geraden erreicht. ein etwas veränderter ansatz den man besser parralellisieren kann ist: beliebiger startpunkt, dann lot auf alle geraden und den schwerpunkt dieses polygons als nächsten iterationsschritt (simultaneus algebraic reconstruction)
das ist v.a. bei diesen rekonstruktionsgeschichten schick, weil es da z.b. um lineare gleichungssysteme mit 3 unbekannten handelt, jedoch aber ein paar hundert gleichungen da sind (und man die bestmögliche näherungslösung sucht).

aber kann man das lösen von großen systemen nicht besser durch single value decomposition machen? oder ist das schwer zu implementieren (also maple kanns

Walli

henselstep schrieb:

Gebe z.B. mal die (20x20) Hilbert-Matrix ein. Das ergibt eine totale Katastrophe.

Na, da hast du dir aber ein Beispiel für eine extrem schlecht konditionierte Matrix ausgesucht .

Das Problem bei Gauß und den anderen direkten Lösungsverfahren ist AFAIR der hohe Speicher-/Rechenbedarf, so daß man bei extrem großen Gleichungssystemen um iterative Verfahren (mit entsprechender Vorkonditionierung) nicht herum kommt. Es gibt aber auch hier kein Kochrezept, weswegen man die anzuwendenden Verfahren je nach Struktur des gegebenen Problems auswählen muss um bestmögliche Ergebnisse zu erhalten.