Lineare Algebra umsetzen!

[liquid]

Hiho!

Bin grade dabei mir ein paar Vektor und Matrix-Klassen zusammenzustellen, allerdings hänge ich jetzt etwas fest. Es geht um die Umsetzung der mathematischen Konzepte der LA in passende Algorithmen.
Zum Bleistift: lineare Abhängigkeit/Unabhängigkeit, Ray-Ray Intersection, Ray-Plane Intersection, Plane-Plane Intersection, Lösung einer Matrix bestimmen (Stufenform), etc.

Die notwendige Theorie hab ich drauf, könnte jederzeit sowas auf Papier machen, aber wie gesagt, bei der Umsetzung haperts. Einer ne' Idee wo man schöne Docus, Tutorials oder weitere Informationsquellen finden kann? Wäre nett, denn den Source von anderen Leute Engine will ich net nehmen, schließlich sagt der nix darüber aus, wie sie denn auf diese Idee gekommen sind.

cya
liquid

[Magnum]

Sag mal in welcher Programmiersprache du das machen willst!
Der Rest sind eigentlich nur Algorithmen nach Schema F. Fast alles läuft ja auf lösen linearer Gleichungen hinaus. Und dass lässt sich mit dem Gauss-Algorithmus leicht implementieren!

Greetz
Magnum

[Achill]

es gibt aber eine paar kleinigkeiten die man beachten muss, z.B. muss man die rechen ungenauigkeit mit beachten, sonst kommt man evtl. auf flasche ergebnis.

Bsp. du ziehst von einer sehr großen zahl eine sehr kleine ab, wenn die bitkette zu kleine ist, wird die kleine zahl nicht abgezogen, jedenfals nicht wirklich ;)

in mathematik beschäftigt sich man mit solche problemen in der "Computerorientierten Mathematik" -> CoMa :)

[Magnum]

Originally posted by Achill
in mathematik beschäftigt sich man mit solche problemen in der "Computerorientierten Mathematik" -> CoMa :)
Bei uns gabs das in Numerik!
Dort wird unter anderem die numerische Stabilität solcher Verfahren betrachtet!

[Achill]

wenn es dir was bringt, hier die seite von meinem prof. in CoMa...

solltest dir dann die scripte mal anschauen, dort wird das gut gezeit, zur umsetzung solltest du matlab nehmen, das kann schon alles was du vor hast - evtl. findes du auch informationen wie es funktioniert...

http://www.math.fu-berlin.de/~biocomp/Lehre/CoMaII_SS02/

[Achill]

numerik habe ich noch nicht gehört :) ...

[liquid]

Danke Leute, ich guck mir die Links morgen (bzw. heute *g*) mal an und frag dann nochmal, wenn ich was nicht kapiere.
Sprache ist C/C++

Von diesem Gauss-Verfahren hab ich auch was gehört. Frage, ist das eine Methode die in einer festen Anzahl von Schritten abläuft und dann ein Ergebnis liefert oder muss man da "mehr" investieren.

Aber wie gesagt, ich guck mir erstmal den Link an!

cya
liquid

[Vedek Bareil]

was das Problem mit der begrenzten Rechengenauigkeit angeht, es gibt hier:
http://www.swox.com/gmp/
ein Paket für Langzahlarithmetik zum Herunterladen. Damit werden Zahlenformate verfügbar, die eine wesentlich höhere Genauigkeit gewährleisten als float/double. Zu Lasten der Rechengeschwindigkeit, versteht sich. :)

[Achill]

Vedek Bareil, man sollte aber es auch intiligent lösen können. Es ist ja nichts weiter als das abziehen von zeilen - man muss also die zeilen nur intiligent voneinander abziehen bzw. vertauschen.

[Stone2001]

Originally posted by Achill
Vedek Bareil, man sollte aber es auch intiligent lösen können. Es ist ja nichts weiter als das abziehen von zeilen - man muss also die zeilen nur intiligent voneinander abziehen bzw. vertauschen.
Wenn man eine LR-Zerlegung, d.h. Zerlegung einer Matrix in eine obere und eine untere Dreiecksmatrix, durchführt, kann eventuell zu Instabilitäten kommen!
Führt man allerdings eine LR-Zerlegung mit Spaltenpivotsuche durch, treten die Instabilitäten nicht mehr auf!

Bei normelen Gauß'schen Umformungen treten meines Wissens nach keine Instabilitäten auf!

@liquid:
Der Aufwand eine Matrix in eine obere Dreiecksmatrix (per LR-Zerlegung / Gauß'schen Umformungen) zu bringen, liegt in O(n³). Genauer: man braucht 1/3 * (n³-n) Multiplikationen!
Um die obere Dreiecksmatrix zu lösen, braucht man n² Multipliaktionen.
Also brauchts du insgesamt 1/3*n³ + n² - 1/3 * n Multiplikationen!
Also liegt der Aufwand einer Gauß-Elimination in O(n³)!