Näherungsverfahren für Gleichungssysteme

20/09/2008 - 01:10 von Roland Damm | Report spam
Moin,

ich habe mir die letzten Tage ein Programm gebastelt, welches ein
Potentialfeld ausrechnet. Also das Potential an gewissen Stellen
ist bekannt, an den Stellen dazwischen muss es errechnet werden.
Nun ist mein Verfahren sicher nicht gerade ideal, weil es nur
eine langsam konvergierende Lösung liefert.

Vereinfacht: Für jeden Punkt der Matrix wird der Mittelwert
seiner 4 Nachbarn eingesetzt und das immer wieder, bis sich
nichts nennenswertes mehr am Ergebnis àndert. Ergebnis ist dann
eine Minimalflàche (Mathematisch: d^2U/dx^2 + d^2U/dy^2 = 0).
Natürlich steckt in meinem Algorithmus inzwischen viel mehr drin
was die Sache beschleunigt, aber im Kern ist es dieses simple
Verfahren.

Durch allerlei Optimierungen bin ich inzwischen so weit, eine
Matrix von 200^2 Elementen in geschàtzt 10 Sekunden hinreichend
genau auszurechnen *).

Frage: Wie machen das die Profis?

Man kann ja alles in ein Gleichungssystem stecken und mit
bekannten Verfahren lösen lassen (Octave wird das vielleicht
auch schon können). Nur: 200*200 Elemente sind 40000 Unbekannte.
Das Gleichungssystem hàtte 40000^2 Elemente was runde 10 Gig an
Speicher bràuchte - nur um das Gleichungssystem aufzustellen.
Verglichen damit ist mein Verfahren wohl doch gar nicht so
schlecht.

Nicht das ich mir die Mühe machen wollte, all zu komplizierte
Algorithmen zu implementieren, aber gibt's da noch schnelleres?

Mir kommt komisch vor, dass man doch normalerweise für große
Systeme sehr große Computer braucht. Kann es sein, dass solche
Nàherungsverfahren durchaus üblich sind? Kann/könnte man so ein
Problem wie eine Wettervorhersage (wo die DGL etwas
komplizierter aussieht) mit einem àhnliches Verfahren lösen?
Wird das so gemacht? Oder stellen die da Gigabytegroße Matritzen
auf?

*) Noch mal nachrechnen lassen:
275 * 250 = 68750 Unbekannte: 9 Sekunden
550 * 500 = 275000 Unbekannte: 30 Sekunden
Geschàtzter maximaler Rechenfehler unter 5%, im Gradienten des
Potentialfeldes - welcher mich hauptsàchlich interessiert -
sicher noch viel weniger.
Auf einem T5700-Prozessor (Laptop, nur eine CPU verwendet)

CU Rollo
 

Lesen sie die antworten

#1 Vogel
20/09/2008 - 09:06 | Warnen spam
Roland Damm wrote in news:48d4317b$0$6556$9b4e6d93
@newsspool4.arcor-online.net:

Moin,

ich habe mir die letzten Tage ein Programm gebastelt, welches ein
Potentialfeld ausrechnet. Also das Potential an gewissen Stellen
ist bekannt, an den Stellen dazwischen muss es errechnet werden.



Das geht wohl schlecht.
Entweder man kennt die Ladungen und ihre Position oder man kennt die
ràumliche Funktion des Potentials.
Aus deiner Ausführung geht nicht so klar hervor, was du aus was berechnest.

Nun ist mein Verfahren sicher nicht gerade ideal, weil es nur
eine langsam konvergierende Lösung liefert.

Vereinfacht: Fà¼r jeden Punkt der Matrix wird der Mittelwert
seiner 4 Nachbarn eingesetzt und das immer wieder, bis sich
nichts nennenswertes mehr am Ergebnis à¤ndert. Ergebnis ist dann
eine Minimalflà¤che (Mathematisch: d^2U/dx^2 + d^2U/dy^2 = 0).
Natà¼rlich steckt in meinem Algorithmus inzwischen viel mehr drin
was die Sache beschleunigt, aber im Kern ist es dieses simple
Verfahren.



Wegen der dürftigen Informationen deinerseits, kann man dazu wenig sagen.
In einem realen Problem müssen da viel mehr Bedingungen erfüllt sein und
geprüft werden, um zu wissen wie nahe das Ergebnis an der Wirklichkeit
liegt.
Du führst offenbar ein Aproximationsverfahren durch, indem du aus vier
Punkten den(die) Wert(e) in einem fünften Punkt berechnest. Da gilt es zu
wissen, welchen Grad(linear, parabolisch, usw.) der Aproximation hat deine
Berechnung, welchen lokalen Fehler, welchen globalen Fehler, usw.

Durch allerlei Optimierungen bin ich inzwischen so weit, eine
Matrix von 200^2 Elementen in geschà¤tzt 10 Sekunden hinreichend
genau auszurechnen *).

Frage: Wie machen das die Profis?



FEM-Methode.
Grosse Matrizen aufstellen und Gauss-Verfahren und àhnliche Anwenden.



Solange man aber nicht wirklich 100% weiss was du da tust,
kann dazu auch nicht wirklich was verbindliches sagen.



Du darfst aber davon ausgehen, dass auch die Profis allerlei Tricks zur
Berechnungsbeschleunigung speziell studieren und suchen, sowie diese auch
kennen und anwenden.
Allerdings erfüllen die Berechnungen der Profis eine Reihe zusàtzlicher
Bedingungen und müssen ein weites Feld an Problemstellungen lösen können.
Dazu braucht es natürlich auch die entsprechende Rechenzeit.




Selber denken macht klug.

Ähnliche fragen