Lösung von Gleichungen mit diskreten Variablen

[positronium]

Hallo allerseits,

gerne würde ich ein paar Gleichungen lösen, bei denen die Variablen nur diskrete Werte annehmen können. Gibt es dafür ein Verfahren, abgesehen vom Durchrechnen aller Möglichkeiten?

Ein Beispiel ist:

mit
a, b, c Element Integer > 0
a + b > c && b + c > a && c + a > b
Weil dabei (vermutlich ?) eine unendliche Lösungsmenge heraus kommt, käme noch eine Bedingung wie 3 <= a + b + c < z.B. 20000 in Frage.
Hier müsste man zu einer endlichen Lösungsmenge kommen können.

Oder fällt so etwas unter die Diophantischen Gleichungen? Auf Wikipedia (http://de.wikipedia.org/wiki/Diophantische_Gleichung) steht ganz unten "...die Lösbarkeit einer Diophantischen Gleichung unentscheidbar ist.". Bedeutet das, dass man immer alle Parameterkombinationen durchprobieren muss?

Danke!

Gruss

positronium

[tomS]

Mit den Diophantischen Glechungen liegst du richtig; das ist aber ein etwas unübersichtliches Gebiet, insbs. wenn's um höhere Polynome geht (bei dir: sechsten Grades!) es gibt Klassen von Diophantischen Glechungen da ist das eher trivial, dann gibt es welche, wo man zumindest die Anzahl der Lösungen (keine, endlich viele, unendlich viele) ganz gut bestimmen kann; aber bei Gleichungen sechsten Grades ist das i.A. wohl Fields-Medaillen-verdächtig - außer du findest eine spezielle Symmetrie.

Mal bei Mathematika nachgeschaut?

[positronium]

Vielen Dank für Deine Antwort!

Wenn ich nichts übersehen habe, bietet Mathematica, natürlich neben Reduce, das die Lösungsmenge in dem Fall aber auch nur beschreiben kann, es sei denn, ich setze das 3<=a+b+c<20000 ein, was aber wegen der Rechenleistung nie ein Ergebnis liefert, nur eine Funktion Namens FindInstance. Diese sollte einen oder optional eine bestimmbare Anzahl Parametersätze liefern, welche die Gleichung erfüllen. Aber auch hier ist das Problem, dass die Funktion nicht mehr zurück kommt... und eine Möglichkeit festzustellen, wie weit die Berechnung gerade ist, um abschätzen zu können, ob jemals ein Ergebnis kommen könnte, gibt es scheinbar auch nicht.

[tomS]

Da ist aber noch nicht berücksichtigt, dass es sich um eine diophantische Gleichung mit ganzzahligen Koeffizienten handelt ;-)

[positronium]

Vielen Dank für Deinen Versuch, Yukterez!

Bei Reduce kann ich zwar schon angeben, dass nur Integer erwünscht sind, aber das Ergebnis ist auch nicht gerade einladend.

Wenn ich noch den Wertebereich 3 <= a+b+c < 20000 angebe, sieht Reduce wahrscheinlich die Möglichkeit, eine exakte, endliche Lösungsmenge zu ermitteln - das aber wohl nur durch Berechnen aller möglichen Parameterkombinationen.

Als Notlösung habe ich schon versucht, alle Kombinationen (wegen der Geschwindigkeit in einem compilierten Programm mit double precision) durchrechnen zu lassen, und dabei durch den Vergleich mit einem Wertebereich, also nicht = 1, sondern > 0.999.. && < 1.00..1 potentielle Kandidaten heraus zu finden, die ich dann exakt nachrechnen könnte, aber ich fürchte, dass ich wegen der Zahlengenauigkeit mit meinem Geschätzten Intervall total falsch liegen könnte. - Es kommen ja für hohe Zahlen bis zu 6er Potenzen vor, die wiederum mit recht kleinen Werten wie 2/3*b addiert werden.

[tomS]

Eine Implementierung in C/C++ wäre schon sinnvoll, aber dann musst du auf jeden Fall die Gleichung umstellen:

2(-ab+b-c)(a+b-c)(-a+b+c)(a+b+c)(-a²+b²+c²) = 3b³c²

Und damit kannst du mit LONG INTEGER arbeiten, keinesfalls mit DOUBLE!

Dann solltest du evtl. nochmal prüfen, ob ggf. sinnvollere Kombinationen p=a+b und q=a-b o.ä. eine Vereinfachung bringen.

[positronium]

Die Idee ist gut! Danke!
Ich hab's gerade in Java mit der Klasse BigInteger programmiert. So muss ich nicht mit dem Überlauf hantieren, weil ja 64 Bit nicht ausreichen. Das ist jetzt zwar nicht besonders schnell, aber mal schauen...

[tomS]

64 Bit in C++ reichen nicht?

[positronium]

Nein, wenn ich bis 20000 rechne, kann eine Variable bis zu 10000 erreichen. Die höchste Potenz ist 6, also 10000^6=
1000000000000000000000000
und 2^64=
18446744073709551616
Der einzige Ausweg wäre, doch wieder die Divisionen auf der einen Seite zu lassen, und die Potenzen als Reihe von Multiplikationen zu schreiben, und die Divisionen dazwischen zu schieben, aber dann kriege ich Probleme mit der Integer-Rundung.

Mit der Lösung über die Klasse BigInteger geht die Geschwindigkeit bald in die Knie. bis a+b+c <= 2000 ging es; dann habe ich abgebrochen - bis 20000 ist noch ein weiter, weiter Weg.

[tomS]

stimmt