Gleichungen lösen

[Firefall]

Wie funktioniert das eigentlich programmiertechnisch, wenn man z.B. die GleichungSin(x) ^ x / PI = x ^ 0.5 + x + 7lösen lassen möchte? Wir haben mal in Mathematik so ein Newton-Verfahren kurz angesprochen, aber nicht wirklich behandelt... Ich denke, das wäre dazu geeignet. Und dann müsste es sogar zimlich einfach sein, soweit ich mich an das Verfahren erinnere. Kann/Wird das so gemacht? (Ich beziehe mich jetzt erstmal auf Gleichungen mit einer Unbekannten)

[Jidder]

Ja, das kann man mit dem Newton-Verfahren machen. Wenn du die Gleichung durch eine Nutzereingabe bekommst, musst du sie umstellen und ableiten können. Wenn die Gleichung bis auf meinetwegen die Koeffizienten immer die selbe ist, dann kannst du die umgestellte und abgeleitete Version einfach in den Code schreiben.

Du musst die Gleichung nach 0 umstellen => 0 = x ^ 0.5 + x + 7 - Sin(x) ^ x / PI. Dann kannst du sagen f(x) = x ^ 0.5 + x + 7 - Sin(x) ^ x / PI und gesucht sind die Nullstellen von f(x). Bei so Sinusgeschichten und auch einfachen Polynomen ist allerdings das Problem, dass du da mehrere (im Falle von Sinus unendlich) Nullstellen rauskriegst. Ich würde sagen, dass einfachste ist dann einfach genug Anfangsbedinungen der Newton-Iteration durchzuprobieren und dich auf einen bestimmten Bereich für x beschränken.

[Firefall]

Wieso muss ich Ableiten? Gehört das zu Newton? :confused:
Ich hatte eigentlich die Vorstellung, mal eben ein kleines 25-Zeilen Script zu schreiben, welches dann eine beliebige Gleichung lösen kann. Ist das so einfach also doch nicht möglich?

[Jidder]

Ja, ich kenn es nur mit Ableiten: Wenn x_n deine erste Näherung ist, dann ist x_(n+1) = x_n - f(x_n) / f'(x_n) eine bessere Näherung. (Meistens.)

Vielleicht reden wir ja auch über unterschiedliche Methoden. Wie hast du dir das denn genau vorgestellt? Ich kann mir nicht mal ein einfaches Skript vorstellen, dass Werte für Variablen in beliebige Gleichungen einsetzt.

[Firefall]

Ja, ich kenn es nur mit Ableiten: Wenn x_n deine erste Näherung ist, dann ist x_(n+1) = x_n - f(x_n) / f'(x_n) eine bessere Näherung. (Meistens.)

Vielleicht reden wir ja auch über unterschiedliche Methoden. Wie hast du dir das denn genau vorgestellt? Ich kann mir nicht mal ein einfaches Skript vorstellen, dass Werte für Variablen in beliebige Gleichungen einsetzt.
Naja ich weiss eben nicht mehr genau wie das Newton-Verfahren funktioniert, und aus der Wikipedia wurde ich nicht richtig schlau. Wir hatten eine Version ohne Ableitung damals. Ich stelle mir das so vor, das man die Gleichung erstmal Null setzt, und dann setzt man eine Variable X auf einen ersten Wert. Man setzt den Wert ein (z.B. mit eval in VBS) und kriegt dann ein Ergebnis. Dieses wiederum verändert man dann irgendwie und setzt es wieder als x ein, bis das Ergebnis 0 wird. Die Frage ist, was man mit dem Ergebnis machen muss :D Unser Verfahren in Mathe konnte man damals mit einem normalen Taschenrechner durchführen...

[Jidder]

Stimmt, einfach Raten geht auch. Das Newton-Verfahren liefert dir halt einen guten Wert, wie du dein x Verändern musst.

Wenn du ohne Ableitung auskommen willst, dann könntest du das mit dem Sekantenverfahren (http://de.wikipedia.org/wiki/Sekantenverfahren) machen. Das könnte in Kombination mit eval durchaus in wenigen Zeilen VBS umsetzen lassen ;)

[Firefall]

Stimmt, einfach Raten geht auch. Das Newton-Verfahren liefert dir halt einen guten Wert, wie du dein x Verändern musst.

Wenn du ohne Ableitung auskommen willst, dann könntest du das mit dem Sekantenverfahren (http://de.wikipedia.org/wiki/Sekantenverfahren) machen. Das könnte in Kombination mit eval durchaus in wenigen Zeilen VBS umsetzen lassen ;)
Ja, das liest sich gut! :) Ich glaube, das war es, was wir hatten. Wie sieht es da denn bei der Effizienz aus? Mal angenommen ich habe eine Durchschnittsgleichung und verwende eine Zufallszahl als Startwert, wie viele Schritte brauche ich dann etwa, bis das Ergebnis stimmt? Kann es sein, dass das eine Stunde lang rechnet oder geht's auch in 5 Sekunden?

[albernenase]

>Vielleicht reden wir ja auch über unterschiedliche Methoden. Wie hast du dir >das denn genau vorgestellt? Ich kann mir nicht mal ein einfaches Skript >vorstellen, dass Werte für Variablen in beliebige Gleichungen einsetzt.

Also ich denke nicht, dass es so einfach ist, ein Verfahren für jeden Gleichungstyp zu nutzen. Das sieht man zB auch sehr schön am Beispiel von algebraischen Systemen wie Maple. Auch solche ausgereiften Systeme sind nicht immer in der Lage, Nullstellen zu finden, obwohl sie in der Lage sind, eine Vielzahl verschiedener Lösungsalgorithmen zu verwenden.

Das Newton-Verfahren konvergiert nicht immer(!) und ist auch sehr abhängig von Startwert und Schrittweite.

[Jan Krüger]

Wie sieht es da denn bei der Effizienz aus? Mal angenommen ich habe eine Durchschnittsgleichung und verwende eine Zufallszahl als Startwert, wie viele Schritte brauche ich dann etwa, bis das Ergebnis stimmt? Kann es sein, dass das eine Stunde lang rechnet oder geht's auch in 5 Sekunden?
Du kannst Newton je nachdem beliebig lang rechnen lassen (wenn du mit Zahlen unbegrenzter Präzision rechnest). Jeder Schritt liefert dir eine ungenaue Lösung; die Genauigkeit wird halt immer besser -- vorausgesetzt, man hat einen vernünftigen Startwert.
Da sind wir schon beim Nachteil von Newton: das Verfahren ist ein bisschen wählerisch, was Startwerte angeht. Der Startwert muss ziemlich nah an der Nullstelle liegen, sonst kannst du den größten Blödsinn rauskriegen (man nennt das lokale Konvergenz). Man verwendet deshalb in der Praxis meistens andere Verfahren bzw. eine Kombination von verschiedenen Verfahren, z.B. das Gradientenverfahren ("steepest descent") gefolgt von Newton-Iterationen.

Schwierig wird's auch, wenn deine Gleichung mehrere Lösungen hat und du die alle finden willst. Bei vielen Gleichungen ist es schwer abschätzbar, wie viele Nullstellen es gibt; dann kannst nur darauf hoffen, eine möglicherweise unvollständige Auswahl der Nullstellen zu finden (durch mehrfaches Anwenden eines Verfahrens mit ausreichend unterschiedlichen Startwerten). Das ist aber ein allgemeines Problem iterativer Lösungsmethoden.

[Diogenes]

Eine Alternative ist die Regula Falsi (http://de.wikipedia.org/wiki/Regula_falsi), bei der man nicht abzuleiten braucht, allerdings zwei Startwerte braucht. Wenn die allerdings verschiedene Vorzeichen haben, hat man gute Chancen, daß man dazwischen eine Nullstelle hat.

Durch Kombination aus Intervalschachtelung und Rekursion kann man mehrere Nullstellen finden. Ich hab das einmal auf einem Commodore 128D (http://de.wikipedia.org/wiki/Commodore_128) (!) gecodet...

[Jan Krüger]

Mehrere ja, alle nein. Wäre ja sonst auch zu einfach...

[Diogenes]

Wenn man sich sehr viel Zeit läßt und sehr viel Platz auf dem Stack hat, könnte man theoretisch alle finden... :)

[Firefall]

Wenn man sich sehr viel Zeit läßt und sehr viel Platz auf dem Stack hat, könnte man theoretisch alle finden... :)
Wieviel denn? Eine Stunde und 2 GB RAM oder ein Jahr und 1 TB RAM?

[claW]

Wieviel denn? Eine Stunde und 2 GB RAM oder ein Jahr und 1 TB RAM?


zeig mir nen rechner mit 1 tb ram, den nehm ich dir sofort ab :D also für die berechnung von pi per php-script braucht man für 2048 stellen... naja, so ca 1 1/2 minuten... mehr stellen machts aber nich mit, da kommt immer ein error :(

aber mal kleine frage am rande:

wie löst man solche gleichungen eigentlich? muss man da wirklich so ein verfahren anwenden mit näherungswerten oder kann man sich eine art parser schreiben, der intern dann alles umstellt ( wie man es halt auf einem blatt papier macht )? das würde mich wirklich mal interessieren...

[scytheman]

ähm falls es weiter hilft (kenn mich zwar ned aus) auf wikipedia is das newton-verfahren erklärt http://de.wikipedia.org/wiki/Newton-Verfahren

[Firefall]

wie löst man solche gleichungen eigentlich? muss man da wirklich so ein verfahren anwenden mit näherungswerten oder kann man sich eine art parser schreiben, der intern dann alles umstellt ( wie man es halt auf einem blatt papier macht )? das würde mich wirklich mal interessieren...
Die habe ich mir auch gestellt. Ich denke nicht, dass dabei ene Ableitung so wichtig sein kann, denn ich kenne Programme, die Gleichungen lösen können aber keine Ableitungen berechnen können (Also nicht die Funktion der Ableitung). Das wäre ja dann wohl kaum schwer einzubauen.

[Jan Krüger]

Wenn man sich sehr viel Zeit läßt und sehr viel Platz auf dem Stack hat, könnte man theoretisch alle finden... :)
Nein. Du weißt ja nicht, in welchem Intervall die sich befinden. Im zweidimensionalen Fall kann man vielleicht noch großzügige Intervalle ausprobieren (aber auch so findet man nicht automatisch alle Nullstellen), aber spätestens im dreidimensionalen Fall kannst du das vergessen. Und was, wenn die Funktion unendlich viele Nullstellen hat?

[Jan Krüger]

Die habe ich mir auch gestellt. Ich denke nicht, dass dabei ene Ableitung so wichtig sein kann, denn ich kenne Programme, die Gleichungen lösen können aber keine Ableitungen berechnen können
Diese Programme verwenden eine Näherung der Ableitung im gewünschten Punkt.

Die Ableitung an der Stelle x ist die Steigung der Tangente am Punkt an der Stelle x. Grob gesagt ist die Tangente eine Gerade (Sekante) durch zwei "unendlich nahe" Punkte an dieser Stelle. Numerisch verwendet man also als Ableitung einfach die Differenz zweier sehr naher Punkte geteilt durch deren x-Abstand voneinander.

Beispiel: f(x) = x². f(1) = 1. f'(1) ~ (f(1.01)-f(1))/0.01 = 2,01 (exakter Wert ist 2).

Je kleiner man die Differenz wählt, desto genauer ist die errechnete Näherung der Ableitung; zumindest bei halbwegs braven Funktionen.

Es gibt sicher Varianten dieses Verfahrens, die numerisch stabiler sind, aber so funktioniert das im Wesentlichen.

[Baegsch]

Mehrere ja, alle nein. Wäre ja sonst auch zu einfach...
Allerdings ist dieser Intervallschatelungsgedanke wesentlich zielführender als das primitive Newton-Verfahren. Es gibt da das s.g. Intervall-Newton-Verfahren, welches _alle_ Nullstellen in einem gegebenen Intervall beliebig genau (im Sinne unserer geliebten Floating Points..) einschließen kann. D.h. du führst sowas wie inewton(x²-1, [-1,2]) aus und bekommst alle Nullstellen von x²-1 im Intervall -1 bis 2 in Intervallen eingeschlossen. Also hier in etwa [sqrt(2)-eps1, sqrt(2)+eps2], wobei du die Differenz der eps beliebig klein gestalten kannst.

Im Gegensatz zum einfachen Newton-Verfahren liefert das Intervall-Newton übrigens auch Existenzaussagen. D.h. wenn das normale Newton-Verfahren keine Nullstelle in einem gegebenen Intervall findet, so bedeuted das noch lange nicht, dass keine Nullstelle existiert. (Beispiele leicht konstruierbar). Findet das Intervall-Newton-Verfahren allerdings keine Nullstelle, so existiert auch keine Nullstelle! Das sind schon Welten zwischen diesen Verfahren. Im Übrigen konvergiert das Intervall-Newton-Verfahren immer!

Ich kann wirklich nur empfehlen sich die Grundlagen in Intervallarithmetik sowie das Intervall-Newton-Verfahren einmal anzuschauen. Das ganze hat keine 30 Jahre auf dem Buckel und ist auch in der akademischen Welt leider noch weit hinter seinen Ansprüchen..

[butterkeks]

wie löst man solche gleichungen eigentlich? muss man da wirklich so ein verfahren anwenden mit näherungswerten oder kann man sich eine art parser schreiben, der intern dann alles umstellt ( wie man es halt auf einem blatt papier macht )? das würde mich wirklich mal interessieren...
sogenannte CAS (http://de.wikipedia.org/wiki/Computer-Algebra-System) können einige Gleichungen auch analytisch lösen

[Firefall]

Numerisch verwendet man also als Ableitung einfach die Differenz zweier sehr naher Punkte geteilt durch deren x-Abstand voneinander.

Beispiel: f(x) = x². f(1) = 1. f'(1) ~ (f(1.01)-f(1))/0.01 = 2,01 (exakter Wert ist 2).

Je kleiner man die Differenz wählt, desto genauer ist die errechnete Näherung der Ableitung; zumindest bei halbwegs braven Funktionen.

Es gibt sicher Varianten dieses Verfahrens, die numerisch stabiler sind, aber so funktioniert das im Wesentlichen.So weit habe ich nicht gedacht :D Hatte immer das verarbeiten eines Strings zum Integral im Kopf... Aber mit der Genauigkeit eines PCs wird das schon beinahe unnötig.

[Diogenes]

Naja :mauer: Meiner Erfahrung nach sind angenäherte Ableitungen immer zu ungenau, weswegen ich nach Möglichkeit darauf verzichte. Darum habe ich auch vorhin die Regula Falsi empfohlen.

[Jan Krüger]

Es gibt auch noch Verfahren höherer Ordnung, siehe z.B. http://en.wikipedia.org/wiki/Numerical_differentiation. Da gibt es auch einen Verweis auf einen Artikel zum symbolischen (exakten) Differenzieren.

[Firefall]

Wie wärs eigentlich mit sowas wie einer Intervallschachtelung + Bruteforce? Müsste doch auch relativ schnell gehen, bei einer Variable.
Etwa so: Setze Gleichung 0. 3 Variablen: intBelow intAbove intStep, alle 0. Starte mit x = 0. Wenn > 0, dann intAbove = x. Wenn < 0, dann intBelow = x. x += intStep. Wenn Weiter von 0 entfernt als letztes Resultat, dann intStep = -intStep. Dann noch mit der Zeit intStep verkleinern usw. Mags jetzt nicht exakt aufschreiben :D

[Firefall]

Habe eben das von mir beschriebene Prinzip ausprobiert. Wie gut es umgesetzt ist, weiss ich nicht, habs in etwa 20 Minuten gemacht und nicht überprüft. Aber es läuft ganz gut. Gleichungen wie:
2^x = 4096
x^2 + 2 * x = 8können schnell (Sofort) gelöst werden.
Hier der Code (Bei unveränderter Weiterverwendung: Meinen Namen erwähnen)
strAppName = "SolvEquation"
strEquation = InputBox("Enter equation:", strAppName)
strEquation = Left(strEquation, InStr(strEquation, "=") - 1) & " - " & Right(strEquation, Len(strEquation) - InStr(strEquation, "="))
intPrecision = CDbl(InputBox("Enter precision:", strAppName, "0.001"))
x = 0
intAboveX = 0
intAboveXError = Eval(strEquation)
intBelowX = 0
intBelowXError = Eval(strEquation)
intCurrentX = 1
intStep = 1

Do
intError = Eval(strEquation)
If Abs(intError) <= intPrecision Then Exit Do
If intError > 0 Then
If intStep > 0 Then intStep = -intStep / 2
If intError < intAboveXError Then
intAboveX = intCurrentX
intAboveXError = intError
End If
Else
If intStep < 0 Then intStep = -intStep / 2
If intError > intBelowXError Then
intBelowX = intCurrentX
intBelowXError = intError
End If
End If

intCurrentX = intCurrentX + intStep
x = intCurrentX
Loop
MsgBox "Result: x = " & intCurrentX
EDIT: Alles funktioniert nicht.
Sin(x) = 0 -> x = 1
x^4 + 24*x^2 = 3 * x -> x = 1

[Diogenes]

Firefall: Is der Code VB? Bitte dazuschreiben. Es gibt auch Leute, wie z.B. mich, die auf Anhieb Java, C und anderes nicht voneinander unterscheiden können.

Tut die Eval-Funktion auch auswerten tun? :)

Im Prinzip funktioniert Intervallschachtelung und Brute Force, aber wie so oft ergeben konstruktive Beweise meist schwache Algorithmen. Außerdem würde ich auf Vorzeichenunterschied prüfen und nicht auf Vorzeichen. Grund: Monotonie - du weißt nicht, ob die eingegebene Funktion wächst oder sinkt. Das Ende (also Abs( Delta-Y) innerhalb Epsilon oder Delta-X innerhalb der Genauigkeitsgrenze - letzteres deutet vermutlich eine Sprungstelle über die X-Achse hinweg an) würde ich außerdem vor der Prüfung auf Vorzeichen(unterschied) abfangen.

[Firefall]

Firefall: Is der Code VB? Bitte dazuschreiben. Es gibt auch Leute, wie z.B. mich, die auf Anhieb Java, C und anderes nicht voneinander unterscheiden können.Es ist VBScript Code (*.vbs).
Tut die Eval-Funktion auch auswerten tun? :)Ja, sie kann Strings auswerten. Der String, der reinkommt ist z.B.
3 * x + 5 / x^2Wenn die Variable x gesetzt ist, dann rechnet eval() das Resultat aus, so wie wenn man schreiben würde:
result = 3 * x + 5 / x^2 ;)
Deine Vorschläge verstehe ich nicht wirklich, bin zu wenig versiert mathematisch. Habe aber folgenden "Einfall" gehabt: Gefährlich sind Funktionen, welche eine Kurve in Richtung 0 aufweisen, wenn diese in der Nähe von 0 liegt. Denn in diesem Fall wird der Algorithmus immer weiter nach unten gehen in der Kurve (Da die Näherung immer besser wird), bis er beim Scheitel ist. Dann wird entweder die gewünschte Genauigkeit erreicht und ein warscheinlich falsches Resultat ausgegeben, oder aber der Algo hängt sich auf weil er keine bessere Lösung finden kann.
Gibt es einen Ansatz, wie man die Gleichung mit purem Bruteforce lösen kann (theoretisch durch Probieren von -unendlich bis +unendlich für x) ohne immer um die kleinstmögliche Nachkommastelle zu erhöhen? Ich dachte mir das so, dass zuerst von -1 bis +1 probiert wird, oder auch von -100 bis + 100. Wenn keine Lösung gefunden wurde, die exakt stimmt, dann eben von -2 bis -1 und von 1 bis 2 (analog -200 bis -100, 100 bis 200) usw. Zeitlich sollte das ja schnell lösbar sein, wenn X nicht riesig ist. Die bisherige Funktion arbeitet meiner Meinung nach sehr schnell, obwohl total ineffizient programmiert.

[Diogenes]

Schade, daß Du mich nicht verstanden hast :(

MitstrEquation = Left(strEquation, InStr(strEquation, "=") - 1) & " - " & Right(strEquation, Len(strEquation) - InStr(strEquation, "=")) wird also aus der Gleichung A(x) = B(x) eine Funktion f(x) := A(x) - B(x) erzeugt, richtig?

Ich habe im Übrigen mit Vorzeichenunterschied gemeint, daß die Funktionswert der verschiedenen Grenzen f(a) und f(b) verschiedene Vorzeichen haben. Sollte das der Fall sein, kannst Du unabhängig von der Qualität des Vorzeichens (+ oder -) davon ausgehen, daß eine ungerade Anzahl Nullstellen zwischen den Stellen a und b sind. Es ist dann genau eine, wenn die Funktion zwischen den Grenzen monoton ist, also entweder nur steigt oder nur fällt.

In diesem Falle kannst du praktisch beliebige Algos einsetzen, um die Nullstelle zu bestimmen. Ich empfehle hier Intervallschachtelung durch Binäre Suche oder Regula Falsi.

Erstere bestimmt die neue Teststelle x ganz einfach durch (a + b) / 2. Wenn f(x) nicht hinreichend nahe an 0 ist (will heißen, der Absolutwert des Funktionswertes ist kleiner als eine Genauigkeit EpY - Abbbruch durch heureka!), dann ersetzt man die Grenze durch x, deren Funktionswert das selbe Vorzeichen wie f(x) hat. Weitermachen bis Abbruch durch heureka!. Code in Pascal:
// Vordefiniert ist die Funktion F(X: Float): Float
// Alle Variablen sind Float
// Eingang: A, B, die wir als "keine Nullstelle" annehmen
// Heureka ist hingegen Boolean.

FA := F(A);
FB := F(B);
repeat
X := (A + B) / 2;
FX := F( X);
Heureka := (Abs( FX) < EpY)
if not Heureka
then if Sign( FX) = Sign( FA)
then begin
FA := FX;
A := X
end
else begin
FB := FX;
B := X
end
until Heureka;
// X enthält die Nullstelle
Die Zweite Methode namens "Regula Falsi" zieht sozusagen zwischen von den Funktionswerten f(a) und f(b) eine Strecke und nimmt als x den Punkt an, an dem diese Strecke die X-Achse schneidet. Dieses Verfahren, das zwar im Einzelschritt etwas teurer ist, aber auf die Gestalt der Kurve besssere Rücksicht nimmt und sich daher üblicherweise rechnet, erzeugt ähnlichen Code:
// Vordefiniert ist die Funktion F(X: Float): Float
// Alle Variablen sind Float
// Eingang: A, B, die wir als "keine Nullstelle" annehmen
// Heureka ist hingegen Boolean.

FA := F(A);
FB := F(B);
repeat
X := (A * FB - B * FA) / (FB - FA);
FX := F( X);
Heureka := Abs( FX) < EpY
if not Heureka
then if Sign( FX) = Sign( FA)
then begin
FA := FX;
A := X
end
else begin
FB := FX;
B := X
end
until Heureka;
// X enthält die Nullstelle
Allerdings kann hier das Problem der Schleifenden Nullstelle auftreten, das Du so schön beschrieben hast. (Aber was meinst Du mit "Scheitel"?) In dem Fall kannst du mit der oben beschriebenen Binärsuche weitermachen, aber mit Heureka := Abs( B - A) < EpX, wobei EpX ein maximales X-Intervall angibt. Diese Hintereinanderschaltung zweier mathematisch an sich gleichwertiger Algos führt dazu, daß zu zuerst mit Regial Falsi schnell in die Nähe der Nullstelle kommst und sie dann mit Binärsuche genau ausrechnest. Man sollte hier ein Kriterium angeben, ob die Binärsuche überhaupt notwendig ist. Auf Anhieb würde ich erst einmal (FB - FA) / (B - A) < EpY / EpX versuchen.

So, das war ein geradezu Xpyder-mäßig langer Artikel :) Ich hoffe, er hilft!

[Firefall]

Schade, daß Du mich nicht verstanden hast :(

MitstrEquation = Left(strEquation, InStr(strEquation, "=") - 1) & " - " & Right(strEquation, Len(strEquation) - InStr(strEquation, "=")) wird also aus der Gleichung A(x) = B(x) eine Funktion f(x) := A(x) - B(x) erzeugt, richtig?
Das ist korrekt! Vielen Dank für die ausführliche Erklärung! Wenn ich etwas mehr Zeit habe schaue ich mir das genau an und wage mich an eine Umsetzung. Jetzt muss ich aber Einkaufen gehen und dann wird die Crysis-Demo runtergeladen *träum* :D