Optimierung des Austauschverfahrens für inverse Matrizen |
09.02.2004, 21:06 | MatheBlaster | Auf diesen Beitrag antworten » | ||
Optimierung des Austauschverfahrens für inverse Matrizen 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 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 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 |
||||
10.02.2004, 05:03 | epikur | Auf diesen Beitrag antworten » | ||
Numerisch gesehen ist es am klügsten das betragsmässig grösste Pivotelement zu wählen. |
||||
12.02.2004, 20:05 | MatheBlaster | Auf diesen Beitrag antworten » | ||
Inwiesofern das? Da kommen dann doch furchtbare Brüche raus? Hm...sonst keiner Ideen? |
||||
12.02.2004, 20:15 | 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. |
||||
13.02.2004, 05:18 | Poff | Auf diesen Beitrag antworten » | ||
Ungeachtet dessen nicht genau zu wissen worum es hier geht, trotzdem mal reinmeckern muss.
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. ... |
||||
13.02.2004, 10:13 | 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]. |
||||
Anzeige | ||||
|
||||
13.02.2004, 13:38 | Poff | Auf diesen Beitrag antworten » | ||
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. ... |
||||
13.02.2004, 15:17 | 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. |
||||
13.02.2004, 20:13 | 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. ... |
||||
19.02.2004, 01:04 | 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? |
||||
19.02.2004, 12:46 | 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 |
||||
19.02.2004, 14:01 | 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 |
||||
20.02.2004, 11:59 | 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... |
||||
20.02.2004, 12:18 | 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. |
||||
20.02.2004, 13:17 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Das ist wahr! |
||||
02.03.2004, 20:44 | Thomas | Auf diesen Beitrag antworten » | ||
Bewundern kann man das Ergebnis jetzt im Mathe Tools-Bereich :] Gute Arbeit! 8) Gruß, Thomas |
||||
26.07.2005, 14:23 | ich2 | Auf diesen Beitrag antworten » | ||
unter jeder Matrix steht immer K.Z. drunter, was bedeutet das und wie komme ich auf die zahl |
||||
26.07.2005, 15:17 | ich2 | Auf diesen Beitrag antworten » | ||
hat sich erledig: K.Z. = Kellerzeile und erechnet werden die werte: : -(element in der spalte)/pivotelement |
||||
18.02.2008, 16:05 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|