Matroids Matheplanet Forum Index
Moderiert von Wally haerter
Gewöhnliche DGL » Systeme von DGL » System von gewöhnlichen Differenzialgleichungen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich System von gewöhnlichen Differenzialgleichungen
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-24 22:27


Könnet Ihr mir bitte helfen bei der Lösung für folgendes System von gewöhnlichen Differenzialgleichungen?

\(\dot{s}_{i}=\frac{d s_{i}}{d t}=-\frac{\partial}{\partial s_{i}} V(\boldsymbol{a}, \boldsymbol{s})=\sum_{m=1}^{M} 2 a_{m} c_{m i} K_{m i} K_{m} \quad i=1, \ldots, N\)

\(\dot{a}_{m}=\frac{d a_{m}}{d t}=a_{m} K_{m}, \quad m=1, \ldots, M
\)

mit

\(K_{m i}=2^{-k} \prod_{j=1 \atop j \neq i}^{N}\left(1-c_{m j} s_{j}\right)=\frac{K_{m}}{1-c_{m i} s_{i}}
\)

Ich brauche es für einen Algorithmus.

Vielen Dank



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1688
Wohnort: Bochum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-25 08:48


Hallo,

wie ist die letzte Zeile  

\(K_{m i}=2^{-k} \prod_{j=1 \atop j \neq i}^{N}\left(1-c_{m j} s_{j}\right)=\frac{K_{m}}{1-c_{m i} s_{i}}
\)

zu verstehen?

Da stehen zwei Gleichheitszeichen. Wird hier etwas definiert? Soll das einen Zusammenhang zwischen verschiedenen Konstanten beschreiben?

Insgesamt ist natürlich nicht klar, ob es hier überhaupt eine geschlossen darstellbare Lösung gibt. Du kannst zunächst die a-Gleichungen integrieren und erhälst dann $a_m(t)= a_m(0)e^{K_m t}$, aber wenn man das dann in die s-Gleichungen einsetzt, ist nicht klar, was man damit anfangen soll.

Viele Grüße,
haerter



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-25 13:04


Erstmal vielen Dank das du es dir mal angeschaut hast.

Zu deinen Fragen:
1. Ja, hier wird K_mi definiert. Also nehme ich \({K_{m i}}=\frac{K_{m}}{1-c_{m i} s_{i}}\)

2. Ja, a-Gleichung integrieren und in die s-Gleichung einfügen. Ich scheitere an dem oben genannten K_mi.

Hintergrund des ganzen ist, das es sich um eine Optimierung eines (zeitkontinuierlichen) dynamischen Systems für k-SAT (Erfüllbarkeitsproblem) handelt (hier):
-Die s_i sind die kontinuierlichen Variablen des jeweiligen Problems mit s_i=-1 wenn FALSE und s_i=1 wenn TRUE

-c_mi sind die Literale mit c_mi=1 für die direkte, c_mi=-1 für die negierte und c_mi=0 wenn die Variable in der Klausel nicht vorkommt

-K_m sind die Klauseln mit K_m=0 wenn diese erfüllt ist

So lässt sich eine Energie-Funktion hier formulieren zusammen mit einem Lagrange-Multiplikator (um nicht zur Lösung gehörende Atraktoren zu vermeiden): V(s,a)

Ich würde gerne mit beschriebenem System die Lösungen von k-SAT Problemen noch genauer untersuchen können.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1688
Wohnort: Bochum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-05-26 08:01


Hallo,

ok, mit dem Artikel zusammen habe ich jetzt ungefähr verstanden, wie die Gleichungen aussehen. Wenn ich das richtig sehe, erhält man nach Einsetzen der a-Lösungen in die s-Gleichungen ein System von N Differentialgleichungen mit zeitabhängiger, polynomialer rechter Seite (vom Grad \(2N-1\), glaube ich).

Leider sind ja Differentialgleichungen mit polynomialen rechten Seiten (schon ohne Zeitabhängigkeit) nicht irgendwie besonders einfach.
Zunächst einmal sehe ich da also keinen Grund, warum man auf eine explizite Lösung der DGL hoffen könnte.
Auch der Artikel zeigt ja ausschließlich numerische Berechnungen. Oder gibt es aus Deiner Sicht eine besondere Struktur, die darauf hoffen lässt, dass man hier analytisch irgendwie weiterkommen könnte?

Viele Grüße,
haerter



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-26 12:19


Oh du kommst meiner Unwissenheit stringent auf die Schliche und hilfst mir damit unglaublich viel weiter. Ich hab langsam schon die Hoffnung aufgegeben.

Ich habe angefangen, einen Algorithmus zu bauen aber ich wusste nicht, wie ich das mit einer Differentialgleichung hinbekommen sollte, also dachte ich, wenn ich sie als Lösung hätte, wäre das machbar.
Klar, das ganze lässt sich nicht explizit lösten, das war ja auch der Ansatz den die Wissenschaftler verfolgt haben. Mir reicht ein numerischer Ansatz vollkommen aus.
Ich möchte ja nur das Verhalten des dynamischen Systems untersuchen.
Der Vorteil dieses Ansatzes ist ja vor allem, das er die "Kosten" jeder einzelnen Formel eines k-SAT Problems viel genauer wiedergeben kann als eine Analyse eines z.B. DPLL Algorithmus.

Hast du einen Tip wie man da einen Algorithmus (Python o.Ä.) baut der das ganze lösen könnte?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1688
Wohnort: Bochum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-05-26 13:51


Hallo,

ich bin leider kein Numerik-Experte. Auf den ersten Blick sieht es so aus als ob ein "normales" Verfahren (so etwas wie Runge-Kutta) gut funktionieren sollte, weil die rechte Seite der DGL ja einigermaßen harmlos ist.

Ich hatte allerdings erst jetzt gemerkt, dass die $K_m$ ja alle noch von $s$ abhängen, d.h. man erhält auf der rechten Seite nicht einfach $a_m(t)=a_m(0)e^{K_mt}$ und setzt das ein, sondern es ist $a_m(t)=a_m(0)e^{\int_0^tK_m(s)\,ds}$, was das Ganze noch etwas komplizierter macht.

Kritisch wird es vermutlich, wenn man die Einzugsbereiche der verschiedenen Gleichgewichte sehr genau voneinander abgrenzen will, das kommt ja in dem von Dir oben erwähnten Artikel deutlich heraus. Die dort erwähnte "5-th order adaptive Cash-Karp Runge-Kutta method" kenne ich nicht, das wäre aber dann ein Kandidat für die schwierigen Situationen.

Viele Grüße,
haerter


-----------------
"The best way to have a good idea is to have lots of ideas."
 - Linus Pauling



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-05-26 22:14


Hallo,

das hilft mir schonmal weiter. Mir war nicht klar das man eine DGL auch numerisch lösen kann. Vielen Dank.

Ich werde jetzt nach dieser Cash-Karp Methode suchen und versuchen das dann irgendwie in Python zu implementieren.

Kann ich dir irgendwo was kleines in die Kaffeekasse spenden für den Denkschmalz?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
nzimme10
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.11.2020
Mitteilungen: 419
Wohnort: Köln
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-05-26 23:29


2021-05-26 22:14 - Nunie in Beitrag No. 6 schreibt:
Mir war nicht klar das man eine DGL auch numerisch lösen kann.

In den "meisten" Fällen kann man eine DGL nur numerisch versuchen zu lösen😁

LG Nico



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3522
Wohnort: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-05-27 09:31


Huhu zusammen,

dieser Artikel hier enthält ein wenig Pseudocode für das genannte Cash/Karb-Verfahren.

Dabei handelt es sich im Übrigen um ein normales RK-Verfahren, allerdings wird der exponentiell wachsenden rechten Seite durch die Schrittweitensteuerung Rechnung getragen.

lg, AK



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-27 11:44


2021-05-26 23:29 - nzimme10 in Beitrag No. 7 schreibt:
2021-05-26 22:14 - Nunie in Beitrag No. 6 schreibt:
Mir war nicht klar das man eine DGL auch numerisch lösen kann.

In den "meisten" Fällen kann man eine DGL nur numerisch versuchen zu lösen😁

LG Nico

Ok, jetzt bin ich verwirrt. Du meinst damit für die meisten DGLs da draußen (ausserhalb des künstlichen Studienalltags) gibt es keine homogene Lösung?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1688
Wohnort: Bochum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2021-05-27 19:46


Ja, es gibt nur eine recht überschaubare Anzahl nichtlinearer Differentialgleichungen, die man explizit lösen kann.

Klassisch schaut man dafür zum Beispiel in das Buch von Kamke,
moderner geht man davon aus, dass es keine explizite Lösung gibt,
wenn Mathematica keine findet.
Ok, das ist etwas vereinfacht, aber "keine geschlossene Lösung"
ist für nichtlineare Differentialgleichungen der typische Fall.

Viele Grüße,
haerter


-----------------
"The best way to have a good idea is to have lots of ideas."
 - Linus Pauling



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2021-05-28 13:09


Ok, dann scheine ich was grundsätzlich missverstanden zu haben.
Dann ist es in diesem Teil der Mathematik also eher wie in der Informatik: Die Formel stellt hier eher einen Algorithmus dar und die Lösung wäre in dieser Allegorie dann die Ausführung desselben, also die numerische Annäherung?

Meine Verwirrung stammt wohl daher, dass ich von einer algebraischen Betrachtung ausging, also dass es ausreicht anhand von Verknüpfungen Mengen untereinander zu klassifizieren und Lösungsmengen daraus abzuleiten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 7123
Wohnort: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2021-05-28 13:43


Hallo Nunie,

das Problem ist recht vielschichtig. Da spielen im Fall der Nichtlinearität natürlich auch algebraische Problematiken mit hinein. Aber vor allem muss man sich immer eines klarmachen: jede Differentialgleichung bzw. jedes DGL-Sytem wird letztendlich durch (ggf. mehrfache) Integration gelöst. Und da haben wir zunächst und vor allem das Problem, das ja auch die geschlossene Darstellbarkeit von Stammfunktionen die absolute Ausnahme ist und keinesfalls die Regel.


Gruß, Diophant



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 22
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2021-06-10 21:19


Hab jetzt was schon vorgefertigtes auf stackoverflow.com gefunden, einen
Python-Code für Runge-Kutta Cash-Karp.

Wenn ich da jetzt die oben genannte Formel einsetzen will entstehen da einige Fragezeichen.

Das ganze ist ja ein  System von Differentialgleichungen mit den Komponenten:

\(
\dot{s}_{i} \ i=1, \ldots, N\ (Anzahl\ der\ Variblen)
\)

mit

\(
\dot{a}_{m} \ m=1, \ldots, M \ (Anzahl\ der\ Klauseln)
\)

Ich kann laut haerter die a-Funktion in das System der s-Funktionen einsetzen mit

\(a_{m}(t)=a_{m}\left(t_{0}\right) \exp \left[\int_{t_{0}}^{t} d \tau K_{m}(s(\tau))\right]

\)

Was repräsentiert dieses \(\tau\) ?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1688
Wohnort: Bochum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2021-06-14 19:29


Hallo,

ich fürchte, ich muss mich da korrigieren.
Das Statement, dass man die a-Gleichungen einfach integrieren kann, war zu einem Zeitpunkt als ich \(K_m\) noch für eine Konstante gehalten habe und nicht wusste, dass \(K_m=2^{-k}(1-c_{m1}s_1)\ldots(1-c_mN s_n)\) von \(s_1,s_2,\ldots, s_N\) abhängt.

Von daher ist es vermutlich am einfachsten, man betrachtet alles als DGL-System aus \(M+N\) Gleichungen, die alle miteinander gekoppelt sind.

Ich sehe jedenfalls keinen offensichtlichen Weg, der die Aufspaltung in "s-Variablen" und "a-Variablen" irgendwie sinnvoll nutzt.
Vielleicht hat aber hier jemand noch eine gute Idee.

Viele Grüße,
haerter


-----------------
"The best way to have a good idea is to have lots of ideas."
 - Linus Pauling



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]