WaBis

walter.bislins.ch

JavaScripts: Nullstellensuche mit Newton-Verfahren

Mit dem JavaScript NewtonSolver.js kannst du Nullstellen von Funktionen nach dem Newton-Verfahren berechnen lassen.

 NewtonSolver.js

Numerisches Lösen von Gleichungen

Gegeben sei eine Funktion y = f(x). Wenn man die Umkehrfunktion braucht, so muss man die Funktion nach x auflösen, sodass man eine neue Funktion x = f −1(y) erhält. Viele Funktionen sind zu kompliziert und lassen sich nicht nach x auflösen und haben eventuell mehrere Lösungen. Für solche Funktionen lassen sich oft nur Lösungen mit numerischen Verfahren finden.

Beispiel Warp-Funktion

Die Formel zur Berechnung der Geschwindigkeit y aus dem Warp-Faktor x laute:

Speed als Funktion des Warp-Faktors

(1)
y = f(x) = x^{ 10 / (3 \cdot a) }
mit
a = 1 - \left( { x \over 10 } \right)^b
und
b = {91.28 \over \left( 10 - x \right)^{0.27} }
wobei'
x ' =' 'Warp-Faktor 0...9,99
y ' =' 'Geschwindigkeit als Vielfaches der Lichtgeschwindigkeit

Diese Funktion weist jedem x genau ein y zu. Sie ist zudem monoton ansteigend. Der gültige Wertebereich für x ist [0..10), wobei Werte über 9,99 bereits den Wertebereich eines Rechners überschreiten können.

Wir wollen nun zu einem Geschwindigkeitswert y0 den zugehörigen Warp-Faktor x0 berechnen. Dazu brauchen wir die Umkehrfunktion von (1). Wir müssten also die obige Gleichung nach x auflösen. Die Variable x kommt in der Funktion f(x) mehrfach vor auf eine Weise, dass sich die Funktion nicht nach x auflösen lässt.

Mit einem numerischen Verfahren, welches Nullstellen einer Funktion findet, kann das Problem gelöst werden. Die Funktion (1) kann umgeschrieben werden:

(2)
g(x) = f(x) - y_0 = 0

An jener Stelle x wo die Funktion g(x) mit dem gegebenen Wert y0 gleich Null wird, erhalten wir den gesuchten Warp-Faktor x0. Wenn wir dem Nullstellen-Suchprogramm die Funktion f(x) zusammen mit dem gegebenen Geschwindigkeitswert y0 übergeben, so liefert es uns den zugehörigen Warp-Faktor x0.

Anwendung des Newton-Solvers

Nach dem Include der Datei NewtonSolver.js steht das globale Objekt NewtonSolver und die Funktion SolveWithNewton bereit.

Anwendung der Funktion SolveWithNewton:

var result = SolveWithNewton(
  Function, Target, Guess, Precision, Data );
Function: function(x,data)
Eine JavaScript Funktion f(x).
Target: number, Default = 0
Vorgegebener Ziel-Wert y0.
Guess: number, Default = 0
Schätzwert für x0 = f −1(y0).
Precision: number, Default = 0.0001
Gewünschte Genauigkeit der Lösung.
Data: Object, Default = NewtonSolver
Dieses Objekt wird der Function als zweiter Parameter übergeben. Damit können weitere Daten an die Funktion übergeben werden. In diesem Objekt kann auch die maximale Anzahl Schleifendurchgänge festgelegt werden und Rückgabewerte des NewtonSolvers werden in diesem Objekt gespeichert. Wenn Data nicht definiert wird, wird das globale Objekt NewtonSolver verwendet.
Data = {
  MaxLoops: 1000,  // Input:  maximale Anzahl Schleifendurchgänge
  Status: string,  // Output: Fehlermeldung oder '' bei Erfolg
  Result: number,  // Output: Resultat der Nullstellensucht
  NLoops: integer, // Output: Anzahl benötigte Schleifendurchgänge
}

Parameter können vor dem Aufruf von SolveWithNewton dem globalen Objekt NewtonSolver zugewiesen erden:

NewtonSolver.MaxLoops = 1000;
MaxLoops: integer(>0)
Maximale Anzahl Schleifendurchläufe. Wenn die gesuchte Lösung mehr als MaxLoops Durchgänge benötigt, bis sie die Genauigkeit Precision erreicht hat, wird die Berechnung abgebrochen und in Status die Meldung max loops exceedet zurückgegeben.
Ouput( NewtonSolver.NLoops );
Status: String
Gibt bei einem Fehler eine Fehlermeldung zurück. Bei einem Fehler gibt ist der Returnwert von SolveWithNewton = 0.
Result: Number
Resultat der Nullstellensuche. Gleicher Wert wie der Returnwert von SolveWithNewton.
NLoops: Integer
Gibt zurück, wieviele Schleifendurchgänge (a 3 Funktionsaufrufe) für die Berechnung benötigt wurden.

Wenn in der Funktion Function in Data.Status ein String zugewiesen wird und die Funktion 0 zurückgibt, wird die Nullstellensuche abgebrochen. Auf diese Weise kann Function eine Fehlermeldung generieren.

Beispiel 1

Ich möchte wissen, welcher Warp-Faktor der Geschwindigkeit 100 · c entspricht. Ich habe eine Funktion f(x): WarpToCspeed, welche zu einem Warp-Faktor x die Geschwindigkeit y berechnet. Folgendes Programm berechnet mit Hilfe des NewtonSolvers den gesuchten Warp-Faktor Warp zur Geschwindigkeit 100 · c:

function WarpToCspeed( x ) {
  var b = 91.28 / Math.pow( 10.0 - x, 0.27 );
  var a = (10.0/3.0) / (1.0 - Math.pow( x / 10.0, b ) );
  return Math.pow( x, a );
}

function CspeedToWarp( c ) {
  NewtonSolver.MaxLoops = 100;
  return SolveWithNewton( WarpToCspeed, c, 9.99 );
}

var Cspeed = 100;
var Warp = CSpeedToWarp( Cspeed );
if (NewtonSolver.Status != '') alert( NewtonSolver.Status );

Ich habe also eine Umkehrfunktion CspeedToWarp programmiert, welche mir mit Hilfe des NewtonSolvers eine Cspeed in einen Warp Faktor umrechnet. Der NewtonSolver braucht die Originalfunktion WarpToCspeed und eine Cspeed.

Als Schätzwert habe ich hier 9.99 fest einprogrammiert. Aufgrund des Funktionsverlaufes garantiert mir dieser Schätzwert, dass immer eine Lösung gefunden wird. Ein kleinerer Schätzwert kann den NewtonSolver bei dieser Funktion zu einem Überlauf bringen, sodass er keine Lösung findet.

Schätzwert

Der Newton-Solver braucht einen Schätzwert Guess, welcher als Startwert für die Nullstellensuche verwendet wird. Mit der Wahl des Schätzwertes wird auch festgelegt, welche Lösung gefunden wird, wenn es mehr als eine Lösung gibt.

Der Newton-Solver findet je nach Schätzwert eine Lösung unter Umständen nicht. Es hängt von der Art der Funktion Function ab, ob ein Schätzwert zu einer Lösung führt oder nicht. Wenn man weiss, wie der Newton-Solver die Lösung sucht, kann man meist einen Geeigneten Schätzwert angeben, der zu einer Lösung führt.

Schauen wir uns das Beispiel mit der Warp-Funktion an. Die Funktion ist für Warp-Werte grösser oder gleich 10 nicht definiert. Wenn wir als Startwert einen Wert kleiner als die gesuchte Lösung angeben, so kann der Newton-Solver keine Lösung finden. Der Grund ist folgender:

Der Solver berechnet zuerst die Steigung der Kurve beim Schätzwert x1 und legt an dieser Stelle eine tangetiale Linie an die Funktion. Dann sucht er den Schnittpunkt dieser Tangente mit der horizontalen Linie beim Wert y0. Der zugehörige x-Wert x2 wird der neue Schätzwert für den nächsten Durchgang der Nullstellensuche.

Wenn nun im Beispiel der Warp-Funktion der Schätzwert kleiner als die gesuchte Lösung gewählt wird, so kann es passieren, dass der so berechnete Wert x2 grösser als 10 wird, weil die Kurve sehr flach ist und die Tangente die Achse y0 weit rechts schneidet. Dann kann die Funktion im nächsten Durchgang nicht mehr berechnet werden, weil sie nur bis zu Werten von maximal 9.99 definiert ist. Wenn im Beispie jedoch ein Schätzwert von beinahe 10 gewählt wird, so liegen alle berechneten Werte xi immer links vom letzten Schätzwert xi−1, weil die Kurve monoton Steigend ist.

Funktionsweise

Die folgende Animation zeigt, wie der Newton-Solver bei der Nullstellensuche vorgeht:

Informationen zum BildAnimation der Funktionsweise des Newton-Verfahrens

NewtonSolver-Objekt

Beim Suchen der Nullstelle können Fehler auftreten. Es kann sein, dass die Funktion Function nicht berechnet werden kann. Oder die Suche oszilliert um einen Punkt. Im letzteren Fall wird die Suche nach einer bestimmten Anzahl Iterationen abgebrochen.

Das NewtonSolver-Objekt hat ein Feld Status vom Typ String. Fehlermeldungen werden in diesem Feld gespeichert. Wenn eine Lösung gefunden werden kann, wird ist Status = ''.

Der Funktion SolveWithNewton kann man ein Objekt Data mitgeben werden. Dieses Objekt wird anstelle von NewtonSolver verwendet. Dieses Objekt wird als zweiter Parameter an die Funktion Function übergeben. Damit können weitere Daten an diese Funktion übergeben werden. Das Resultat der Nullstellensuche (Result, Status und NLoops) wird in diesem Objekt abgespeichert.

Die maximale Anzahl Iterationen ist standardmässig auf 1000 begrenzt. Dieser Wert sollte in den allermeisten Fällen ausreichen, um ein Resultat der gewünschten Genauigkeit Precision zu liefern.

Rekursion

Es ist möglich, in der Funktion, welche dem Newton-Solver übergeben wird, ebenfalls wieder die Funktion SolveWithNewton rekursiv zu rufen. Die Funktionen können entweder eigene Data Objekte erzeugen und verwenden, ein einziges globales Data Objekt verwenden oder NewtonSolver verwenden, indem der Parameter Data nicht verwendet wird.

Weitere Infos zur Seite
Erzeugt Montag, 18. Juni 2012
von wabis
Zum Seitenanfang
Geändert Donnerstag, 11. Mai 2017
von wabis