Optimierung des Austauschverfahrens für inverse Matrizen

Neue Frage »

MatheBlaster Auf diesen Beitrag antworten »
Optimierung des Austauschverfahrens für inverse Matrizen
A hoi hoi,

ich arbeite gerade daran, dass Gauß- Jordansche- Austauschverfahren in PHP umzusetzen. Das klappt auch soweit schon ganz gut, allerdings lasse ich das Pivotelemnt einfach diagonal von (1,1) nach (n,n) durchwandern, wie langweilig Augenzwinkern

Stellt sich also die Frage, wie man das Verfahren optimieren kann. Am einfachsten ist es natürlich, zuerst einfach alle möglichen 1 als Pivotelemente zu wählen, damit man nicht so komplizierte Teiler bekommt. Was gibt es noch für Ansätze / Ideen? Ich bin für alle Hirngespinste dankbar smile

Desweiteren nur nochmal kurz zur Absicherung: das Austauschverfahren wird abgebrochen, wenn als Pivotelemente nur noch 0 zur Verfügung stehen, richtig? Folgt daraus zwangsläufig, dass es keine inverse Matrix gibt, oder kann man sich einfach nur verrant haben und den falschen Weg eingeschlagen? Gibt es noch andere Abbruchbedingungen?
Folgt aus der Anzahl der maximal möglichen Schritte der Rang der Matrix? Das steht im Tipps+Tricks Bereich. Ich hoffe nur, ich habe das richtig verstanden.

danke soweit
epikur Auf diesen Beitrag antworten »

Numerisch gesehen ist es am klügsten das betragsmässig grösste Pivotelement zu wählen.
 
 
MatheBlaster Auf diesen Beitrag antworten »

Zitat:
Original von epikur
Numerisch gesehen ist es am klügsten das betragsmässig grösste Pivotelement zu wählen.

Inwiesofern das? Da kommen dann doch furchtbare Brüche raus?

Hm...sonst keiner Ideen?
epikur Auf diesen Beitrag antworten »

Ja, aber die Zahlen bleiben klein, was dem Format für Fliesskommazahlen im Rechner entgegenkommt. Dadurch bleiben die unweigerlich auftreten Rundungsfehler im Rahmen. Wenn du natürlich einen Gauss mit rationalen Zahlen (z.b. http://www.swox.com/gmp ) implementierst hast du diese Probleme nicht. Allerdings wird dann dein Algorithmus unnötig langsam und zweitens hast du numerische Probleme immer noch nicht ausgeschlossen, da Nenner und Zähler in der rationalen Darstellung immer noch sehr gross (zu gross für den Arbeitsspeicher !!!) werden können. Desweiteren kannst du immernoch keine Gleichungssysteme exakt lösen die nicht rationale Koeffizienten enthalten. Will heissen: In der Praxis macht sowas kein Mensch. Wenn man tatsächlich den Gauss benutzen will kann man eine LU (LR) Zerlegung der Koeffizientenmatrix vornehmen, dies lohnt sich wenn man Ax = b für viele verschiedene Seiten b lösen will, was ja hier zutrifft. Ansonsten werden in der Praxis gerne sogenannte Iterationsverfahren genutzt, die aber nur für bestimmte Koeffizientenmatrizen funktionieren.
Poff Auf diesen Beitrag antworten »

Ungeachtet dessen nicht genau zu wissen worum es hier geht,
trotzdem mal reinmeckern muss.

Zitat:
Ja, aber die Zahlen bleiben klein, was dem Format für Fliesskommazahlen im Rechner entgegenkommt. Dadurch bleiben die unweigerlich auftreten Rundungsfehler im Rahmen


Es bleibt sich doch gleich ob die Zahlen nun groß oder klein sind,
entscheidend ist doch nur, dass möglichst alle die miteinander
verrechnet werden müssen in einer entsprechend ähnlichen Bandbreite
liegen. Sofern also nicht zwingend ständig kleine mit hinein verrechnet
werden müssen, machen die auch im Großen keine größeren
Rundungsfehler und umgekehrt ist doch die Problematik genauso.

Wenn sie anfangen bestimmte Schranken nach unten zu überschreiten,
kann das ebenfalls nur durch größere Speicherplatzzuweisung
abgefangen werden.

Die Formel große Zahlen großer Speicherplatz, kleine Zahlen kleiner
Speicherplatz, stimmt so jedenfalls nicht. Schwierigkeiten, die
Vergrößerungen der Genauigkeit erzwingen (und damit Speicherplatz
und Rechenzeit), entstehen doch nur wenn fortlaufend Zahlen sehr
unterschiedlicher Größenordnungen miteinander verrechnet werden
müssen.

Das Ziel muss bleiben möglichst viele aus passender Bandbreite und
möglichst wenige aus fremder verrechnen zu müssen. Ob die sich dann
im Großen oder Kleinen bewegen sollte eigentlich ohne nennenswerte
Bedeutung bleiben.
...
epikur Auf diesen Beitrag antworten »

Natürlich verbrauchen grosse Fliesskommazahlen nicht mehr Speicherplatz. In der Tat nimmt aber die Dichte der Zahlen ab, je grösser sie werden, wenn ich mich recht entsinne liegt bei den üblichen Formaten etwa die Hälfte aller darstellbaren Zahlen im Intervall [0,1].
Poff Auf diesen Beitrag antworten »

Zitat:
In der Tat nimmt aber die Dichte der Zahlen ab, je grösser sie werden,


Die Dichte der Zahlen nimmt ab wenn sie größer werden, richtig, aber nur
die relative Dichte und genau das gleiche erzwingen die kleineren Zahlen auch.

Nun weiß ich nicht ob hinter 'DEM Fließkommaformat' nicht etwa doch
noch ein spezieller raffinierter Darstellungstrick steht, der etwa einen
ganz spezifischen Bereich bevorzugt (in engeren Grenzen wenigstens).

Bei den Formen die mir dabei im Kopf rumgeistern, nicht unbedingt,
was aber nicht unbedingt was heißen muss. ;-)


Aber was anderes kommt hier aber ganz klar zum Ausdruck:

Eine numerische Lösung (besonders bei hoch iterativen Vorgängen)
ist nur insoweit brauchbar, als dass es eine vernüftige Abschätzung
des maximalen Fehlers gibt.

Das bedeutet andererseits, dass Optimierungsvorgänge ganz
BESONDERS darauf Rücksicht nehmen müssen. Der iterativ geschickt
schnellst mögliche Weg, mag aus formaler Sicht genial und schön sein,
aus realen numerischen Aspekten muss er das deswegen noch lange
nicht sein.

Es gilt also einen goldenen Kompromiss aus den sich meist
widersprechenden Anforderungen zu finden.

Auch sollte sich ein jeder darüber klar sein, dass die eigene, gerade
ausgetüftelte Lösung gegenüber den schon existierenden meist
NICHT (im entferntesten) bestehen kann.
...
epikur Auf diesen Beitrag antworten »

Ein einfaches Flieskommaformat, wie es im Prinzip auch auf dem Rechner verwendet wird: Jede Zahl wird dargestellt in der Form +/- 0.a1a2a3 * 2^k, wobei ai aus {0,1} und k aus {-1..2}. Wir benötigen hier 1 bit für das Vorzeichen, 3 bit für die Nachkommastellen und 2 bit für den Exponenten. Insgesamt erhalten wir also eine 6 bit Fliesskommazahl.

Wer Lust hat kann ja mal ausrechnen wieviele Zahlen 0 <= x <= 1 und wieviele Zahlen 1 < x dargestellt werden können.
Poff Auf diesen Beitrag antworten »

.. na so hab ich mir das eigentlich auch vorgestellt.

Dass eine Def. wenn sie denn nicht symetrisch fallen kann,
einen bestimmten Bereich zwangsweise bevorzugen muss, das
war mir ebenfalls klar. Alles weitere allerdings bleibt mir unklar.

Betrachte Fließkommaformat F* mit F* =( F) *2
Ich denke damit ist eine Bijektion zwischen den beiden Mengen definiert.
Die Verteilung liegt nun anderes und dennoch muss wegen der Bijektion
mit beiden gleichwertig zu rechnen sein.
...
MatheBlaster Auf diesen Beitrag antworten »

Danke für die ganzen Hirngespinste, nach denen ich dummerweise auch noch gefragt habe. :P

Kleine Kurskorrektur: das Programm soll so arbeiten, wie es auch einem Menschen am leichtesten fiele. Genauigkeit interessiert mich derzeit noch nicht so sehr, obwohl das später noch interessant werden dürfte. Hat denn also zum "menschlichen Rechnen" noch jemand gute Tipps?
Ben Sisko Auf diesen Beitrag antworten »

Ich hoffe, es hört sich nicht unverschämt an, aber welchen Sinn und Zweck soll dein Programm erfüllen? Also welche (didaktischen??) Ziele willst du damit erreichen?

Gruß vom Ben
jama Auf diesen Beitrag antworten »

Der Rechenweg wird ebenfalls angezeigt. Das Programm ist also zur Kontrolle und Fehlersuche geeignet. Missbrauch ist zwar auch möglich, aber das sollte jeder selbst wissen. In dem Alter, wo Matrizen behandelt werden, darf man schon Mündigkeit der Benutzer voraussetzen.

Gruß,

Jama
Ben Sisko Auf diesen Beitrag antworten »

Um das optimal zu erreichen müsste man dann ja auch eine Regel zur Pivotsuche angeben können, damit dass Programm dann auch genauso rechnet wie ich... Oder ich müsste immer rechnen wie das Programm...
epikur Auf diesen Beitrag antworten »

Die einfachste Methode hierzu ist doch den Benutzer das Pivotelement wählen zu lassen und dann einen Rechenschritt durchzuführen.
Ben Sisko Auf diesen Beitrag antworten »

Das ist wahr!
Thomas Auf diesen Beitrag antworten »

Bewundern kann man das Ergebnis jetzt im Mathe Tools-Bereich :]

Gute Arbeit! 8)

Gruß,
Thomas
ich2 Auf diesen Beitrag antworten »

unter jeder Matrix steht immer K.Z. drunter, was bedeutet das und wie komme ich auf die zahl
ich2 Auf diesen Beitrag antworten »

hat sich erledig:
K.Z. = Kellerzeile
und erechnet werden die werte: : -(element in der spalte)/pivotelement
ich5 Auf diesen Beitrag antworten »

Ich habe das Programm soeben ausprobiert und es liefert leider falsche Werte für die Inverse Matrix

Ich habe folgende 4x4 Matrix eingegeben: 2,0,1,2;1,0,0,0;0,1,-1,0;-1,0,0,-1

als Lösung kommt folgendes heraus: 1,1,0,2;0,1,0,2;0,0,1,0;0,0,-1,-1

die ist offensichtlich nicht richtig, wenn man als Probe A^-1 * A berechnet
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »