Java Gleichungslöser bauen

CPU · 16. November 2009

Hallo zusammen,

ich möchte mich in meinem nächsten Projekt zunächst einem Gleichungslöser widmen und dann einen Funktionsplotter basteln.

Die Mathematik hab' ich drauf, um Gleichungen/Gleichungssysteme zu lösen. Aber wie bringe ich das dem PC bzw. der JVM bei?

Ich wäre dankbar, wenn Ihr mir einige Kommentare, Tipps (und gerne Codebruchstücke) hinterlassen würdet, so dass ich einen Anlauf bekomme, um soetwas zu basteln!

Danke

CPU

Gluehwurm · 16. November 2009

Hi,

erstmal: Welchen Gleichungslöser? Eine einzelne Gleichung, eine System von linearen Gleichungen (Matrix), Polynome?

Wenn du die Mathematik drauf hast, und von Programmieren eine Ahnung hast, sollte das doch keine Problem sein das zu implementieren...

CPU · 17. November 2009

Ein Gleichungslöser für einzelne Gleichungen. Zunächst vielleicht einfach mal folgende Gleichungen:

Code:

4x=5 (nach x)
0=x^2+3*x+5 (nach x)
(oder)
122=4*e^x (nach x)

Aber, wie gehe ich/geht das Programm vor? Z.B. so:
1.) Ein Tokenizer wandelt die Eingabe in Objekte um und prüft die Richtigkeit (Klammerfehler etc)?
2.) Eine Art Kompiler kompiliert die Gleichung und stellt sie um (algebraisch).
3.) Der "Finalizer" wandelt das Endergebnis in eine Zahl um (vollzieht also die numerische Rechnung)

CPU

Gluehwurm · 17. November 2009

Hi,

1.) Ein Tokenizer wandelt die Eingabe in Objekte um und prüft die Richtigkeit (Klammerfehler etc)?
2.) Eine Art Kompiler kompiliert die Gleichung und stellt sie um (algebraisch).

So etwas erledigt ein Parser (passendes Beispiel auch auf http://de.wikipedia.org/wiki/Parser#Beispiel) und ist genau das was du brauchst. Vll. suchst du auch, ob es für dein Problem nicht schon existierende Packages/Libraries gibt. Ich hab durch googeln (java mathematical expression parser) mal dies gefunden http://sourceforge.net/projects/jep/ .Das ist zumindest von der Beschreibung schon mal nicht schlecht.

3.) Der "Finalizer" wandelt das Endergebnis in eine Zahl um (vollzieht also die numerische Rechnung)

Das ist dann der tricky Part. An was für eine "numerische Rechnung" hast du gedacht? Beachtest du auch, dass, je nach Typ der Gleichung, eine direkte Lösung existieren kann?

CPU · 17. November 2009

Das ist dann der tricky Part. An was für eine "numerische Rechnung" hast du gedacht? Beachtest du auch, dass, je nach Typ der Gleichung, eine direkte Lösung existieren kann?

Also, einfach, dass eine Gleichung z.B. nach x aufgelöst wird und am Ende da ein Ausdruck wie

Code:

x=ln(134*23)/ln(3)

steht, der dann nur noch in eine Zahl umgewandelt wird.

An dem Parsebaum nehme ich dann die Thermumformungen vor, oder?

Was mache ich bzw. wie fange ich die Ereignisse, wie nicht lösbare Gleichung oder so ab (klar, wenn es mehr Variablen als Gleichungen gibt ...)?

CPU

Gluehwurm · 17. November 2009

Also, einfach, dass eine Gleichung z.B. nach x aufgelöst wird und am Ende da ein Ausdruck wie
Code:

x=ln(134*23)/ln(3)

steht, der dann nur noch in eine Zahl umgewandelt wird.

Ich befürchte, dass es ganz so einfach nicht ist. Für dieses Beispiel geht das natürlich, aber weiter oben hast du die Gleichung

Code:

0=x^2+3*x+5 (nach x)

Die kann man dann nicht mehr so einfach nach x auflösen (korrigiert mich wenn ich falsch liege). Durch die "Mitternachtsformel" (auch wenn man die aus numerischen Gründen vermeiden sollte) kommst du natürlich zur Lösung. Allerdings muss dann dein Programm erkennen, dass es sich bei der Gleichung um ein Polynom 2ten Grades handelt. Was machst du wenn du ein Polynom höheren Grades hast? Oder andere Gleichungen die ebenfalls nicht leicht nach der Variable aufgelöst werden können? Oder soll sich dein Programm nur auf diese sehr einfachen Fälle beschränken?

An dem Parsebaum nehme ich dann die Thermumformungen vor, oder?

Im Prinzip ja. Einfach ist das aber nicht

.

\edit
Da hab ich was vergessen:

Was mache ich bzw. wie fange ich die Ereignisse, wie nicht lösbare Gleichung oder so ab (klar, wenn es mehr Variablen als Gleichungen gibt ...)?

1. Nicht lösbare Gleichungen:
Das wirst du (hoffentlich) beim Umformen feststellen

2. Mehr Variablen als Gleichungen
Ich dachte, es geht hier nur um eine Gleichung. Wenn du ein Gleichungssystem hast in dem die Variablen linear vorkommen, musst du aus deinen Gleichungen eine Matrix bilden (auch über den Baum), und diese dann "invertieren". Wenn diese Matrix singulär ist, dann ist dein Gleichungssystem nicht genau lösbar.
Wenn die Variablen aber nicht-linear in den Gleichungssystemen vorkommen dann kannst du den ganzen Auflösungs-Ansatz imho in die Tonne treten und du musst dich mit numerischer Nullstellensuche bzw. numerischer Optimierung beschäftigen. Das wirst du im übrigen auch machen müssen, wenn du eine Gleichung nicht auflösen kannst.

CPU · 17. November 2009

D.h. ich muss mich ersteinmal hinsetzen und eine Liste machen, was es für Gleichungstypen gibt und wann Gleichungen nicht lösbar sind bzw. wann ich Nullstellen "manuell" mit dem Newtonverfahren suchen muss.

Achso, das mit den Gleichungssystemen habe ich mir nur für die Golden-Version gedacht. Zunächst sollen nur einzelne Gleichungssysteme gelöst werden.

Wichtig ist mir die algebraische Lösung, da viele Gleichungslöser (z.B. Derive) da direkt das Ergebnis hinschreiben ...

P.S.: Richtig spannend wird es dann bei den Integralen

P.S.S.: Wer sich fragt, warum ich das mache: (1) ich beschäftige mich gerne mit Mahte, (2) bin gut in Informatik (*selbstlob* - bitte nicht falsch verstehen!) und (3) würde gerne mal lernen, wie soetwas funktioniert - wer ist nicht voller Stolz, wenn er später sagen kann: schaut mal, den Gleichungslöser habe ich zusammengeschraubt ...

Gluehwurm · 17. November 2009

D.h. ich muss mich ersteinmal hinsetzen und eine Liste machen, was es für Gleichungstypen gibt und wann Gleichungen nicht lösbar sind bzw. wann ich Nullstellen "manuell" mit dem Newtonverfahren suchen muss.

Ich wüsste halt z.B. nicht auf Anhieb wie ich

Code:

x*exp(x)/(sin(x)+1) - x^3 + 2 = 0

algebraisch (analytisch) lösen sollte bzw. ob das überhaupt möglich ist. Da würde ich sofort auf ein numerisches Lösungsverfahren (z.B. Newton) zurückgreifen. Wenn du das Buch noch nicht kennst: such mal nach Numerical Recipes. Da werden numerische Verfahren ausführlichst beschrieben.
Ein algebraischer Löser (Computer Algebra) ist natürlich eine schöne Sache, aber eben sehr kompliziert. Ein, wie ich finde, sehr interessantes Gebiet ist die "automatische Differenzierung" (http://en.wikipedia.org/wiki/Automatic_differentiation). Vielleicht findest du auch da Ideen zur Umsetzung deines Lösers. Ansonsten vll mal in den Code von OpenSource-CAS schaun

.

Dann wünsch ich dir aber schon mal gutes Gelingen!

CPU · 17. November 2009

Also die Gleichung

((((x)^(x)))/(sin(x)+1))-((x)^(3))+2=0

löst mein Gleichungslöser nur numerisch auf ...

Irgendwie muss man halt so eine Art Sperre einbauen. D.h. wenn die Gleichungen zu komplex werden, dann wird das nur numerisch angenähert ...

Ach, das Ergebnis lautet überigens: x=1.5930652914191

Gluehwurm · 17. November 2009

Nur so am Rande:
Ich meinte eigentlich

Code:

((((x)*(e^(x))))/(sin(x)+1))-((x)^(3))+2=0

Aber das ist egal. Was mich noch interessieren würde: War das bei deiner Version die einzige Nullstelle? Bin grad zu faul das auf Plausibilität zu überprüfen, bzw. die Funktion zu plotten

Was für ein numerisches Verfahren hast du dann verwendet? Newton? Wenn ja, wie hast du die Ableitung bestimmt?

Intuitiv hätte ich das mit der Sperre auch gemacht. Die Frage ist nur: Wann ist eine Gleichung zu "komplex"? Je länger sie ist? Je mehr nicht-lineare Funktionen vorkommen? Also wichtig wäre hier wirklich, dass du alle Monome (so weit es geht) zusammenfasst. Auf der sicheren Seite mit der Sperre bist du aber sicher, wenn du die Anzahl von trigonometrischen Funktionen, Logarithmus (Exponentialfunktion) und ähnlichem zählst, und ab einer gewissen Schwelle (2

) auf die numerische Variante umschwenkst.

CPU · 19. November 2009

Aber das ist egal. Was mich noch interessieren würde: War das bei deiner Version die einzige Nullstelle? Bin grad zu faul das auf Plausibilität zu überprüfen, bzw. die Funktion zu plotten
Was für ein numerisches Verfahren hast du dann verwendet? Newton? Wenn ja, wie hast du die Ableitung bestimmt?

Irgendwie wollte Derive diese Funktion nicht "schlucken" und da habe ich einfach auf numerisch geklickt (wenn es denn so einfach wäre ...) und da kam der Wert raus.

Intuitiv hätte ich das mit der Sperre auch gemacht. Die Frage ist nur: Wann ist eine Gleichung zu "komplex"? Je länger sie ist? Je mehr nicht-lineare Funktionen vorkommen? Also wichtig wäre hier wirklich, dass du alle Monome (so weit es geht) zusammenfasst. Auf der sicheren Seite mit der Sperre bist du aber sicher, wenn du die Anzahl von trigonometrischen Funktionen, Logarithmus (Exponentialfunktion) und ähnlichem zählst, und ab einer gewissen Schwelle (2 ) auf die numerische Variante umschwenkst.

Das hört sich gut an ...

FlowFun · 19. November 2009

also irgendwie ist das ja kontrovers...

zum einen möchtest du einen algebraischen löser haben, was ein HÖLLENaufwand ist und zum andern möchtest du aber wenns zu komplex wird nen numerischen löser haben.

ich will jetz hier nicht den mut kaputtmachen, aber was du vor hast klingt nach einem symbolischen algebraprogramm - und das is bockelhart

was ziemlich spaß machen könnte wäre beispielsweise folgendes:

aufgabe1: formelparser
du baust dir einen formelparser (klammern setzen und anschließend empfehle ich einen stack aufzubauen, der abgearbeitet wird, das ist flott).
aufgabe2: finite differenzen
du leitest deine funktion nach allen variablen (oder halt x) mit (zentralen) finiten differenzen ab und bekommst so den gradient deiner funktion
aufgabe3: newton verfahren
du baust das newton verfahren und benutzt dabei deinen gradienten und rechnest dir damit ein x aus was deine funktion löst.

allein das hält dich bestimmt nen paar tage/wochen bei der stange ;]

arterius · 19. November 2009

Für sowas gibt es matlab, besorg die eine Lizenz und gut ist.

FlowFun · 19. November 2009

es gibt auch www.wolframalpha.com aber das macht dich auch nicht glücklich weil du es nicht selbst geschrieben hast.

generalad · 24. November 2009

Ich schließe mich da mal der Aussage von FlowFun an. Das von Dir ursprünglich gestellte Problem, einen generischen Solver zu schreiben, ist sehr starker Tobak.

Die 3 von FlowFun vorgeschlagenen Aufgabenstellungen halte ich für sehr sinnvoll, allerdings würde ich die noch genauer spezifizieren:

1. Formelparser: sehr guter Einstieg, allerdings sollte man anmerken, dass selbst die numerische Auswertung einer beliebigen Funktion schon problematisch werden kann. Ich vermute mal, dass sich die Aufgabe auf Funktionen von R nach R bezieht? R^m nach R wird als "Einstieg" zu schwer.

2. finite Differenzen: Machbar, wenn man nur Funktionen behandelt, bei denen der Gradient überhaupt existiert und stetig ist. Ansonsten wird es eklig.

3. Newton-Verfahren: Könnte man auch vom Rest isolieren, indem man z.B. nur univariate Polynome behandelt. Selbst dort ist das Newton-Verfahren sehr schnell am Ende.

Die Entscheidung, ob eine Funktion zu "komplex" ist, ist in der gestellten Form nicht machbar. Unter anderem deswegen, weil es Funktionen gibt, bei denen nicht einmal bewiesen werden kann, ob sie eine Nullstelle haben - geschweige denn, diese mit elementaren Funktionen darzustellen. (kann sein, dass ich mich beim ersten Teil der Aussage irre; die Nicht-Darstellbarkeit ist aber sicher, siehe Integral der Gauss-Funktion).

So rein aus Neugier: Was verstehst Du unter "gut in Informatik"?

Wenn Du Dich mit der Theorie hinter dem ganzen beschäftigen willst, empfehle ich Dir die folgenden beiden Bücher 1 2

sowie weitere Veröffentlichungen von Prof. Volker Weispfenning.

Stichwörter zur Suche: Computer Algebra (eh klar), Constraint Logic Programming, Eliminations Algorithmen, Gröbner-Basen

CPU · 24. November 2009

So rein aus Neugier: Was verstehst Du unter "gut in Informatik"?

Ich kann Swing/Awt, Datenstrukturen, OOP generell, Algorithmik (z.B. Backtracking, Travelling-Salesman etc.), Dateien/Dateiströme, XML, Netzwerkfirlefanz, Datenbankgedönse. Das "ich kann" bedeutet, dass ich mindestens ein halbes Jahr damit beschäftigt habe und es drauf hab. Netzwerkfirlefanz ist im überigen mein "Steckenpferd" - macht mir sau viel Spaß.

Nja, aber zu der Frage (von mir):
IHR HABT RECHT (wie immer...). Es ist wirklich viel zu viel ... Danke für den Hinweis. Dennoch werde ich etwas realisieren: einen Funktionsplotter, der Nullstellen, Maxima/Minima, Wendestellen findet und numerisch die erste Ableitung bilden kann und numerisch das Integral bilden kann ... Dürfte noch anstrengend genug sein ...

Danke

CPU

CoolHandLuke · 24. November 2009

Hmmm müsste es nicht auch möglich sein, für diese Gleichungssysteme eine Grammatik zu erstellen? Damit dann scanner, parser usw. für diese Sprache durchlaufen lassen. (Neben der syntaktischen und semantischen Analyse)

FlowFun · 24. November 2009

Eine Grammatik für ein GleichungsSYSTEM?

Beim Lösen würde eine Grammatik glaube ich nicht helfen, ich lasse mich aber gern vom Gegenteil überzeugen. Man könnte damit aber beispielsweise prüfen, ob die Formel richtig eingegeben wurde und nicht ein '3*/x' auftritt. Mein Parser stürzt dann ab, ist auche eine art Fehlermeldung :]

Ausserdem lassen sich Formelparser mit verhältnismäßig wenig aufwand implementieren. Wenn die Klammerung vollständig ist kann man nen Baum machen, rekursiv lösen oder nen Stack abarbeiten und es gibt bestimmt noch viele andere möglichkeiten. Man muss sich die anforderung anschauen, ob es darum geht die Formel nur wenige male auszuwerten oder ein paar hunderttausend mal (hatte mal so ein projekt). Daran kann man festmachen welche Datenstruktur man benutzt.

Tja und einen numerischen Integrator/Differenzierer und Nullstellenfinder zu bauen ist cool, sowas macht Spaß!
Übrigens, es gibt eine möglichkeit die exakte Anzahl an Nullstellen in einem Intervall zu finden, google mal nach 'Sturmsche Kette'

generalad · 25. November 2009

@CPU: OK damit bist Du denke ich gut gewappnet für Dein Vorhaben

Lass mich/uns wissen, wie Du vorankommst.

Zum Thema Grammatik hat FlowFun schon wieder (fast) alles gesagt, was mir auch dazu eingefallen wäre. Kann nur noch anfügen, dass die geparste Funktion als Baum im worst case für die numerische Auswertung maximal ungünstig ist.

Java Gleichungslöser bauen

Lieutenant

Cadet 4th Year

Lieutenant

Cadet 4th Year

Lieutenant

Cadet 4th Year

Lieutenant

Cadet 4th Year

Lieutenant

Cadet 4th Year

Lieutenant

Ensign

Commander

Ensign

Cadet 3rd Year

Lieutenant

Lt. Commander

Ensign

Cadet 3rd Year

Ähnliche Themen