Programmiertechnik: Zielwert/Nullstellensuche, Verfahren?

[Jens Chamberley]

Hallo Forumgemeinde,

als stiller Mitleser stehe ich nun selbst gerade vor einem Problem, wobei ich nun auf Hilfe angewiesen bin. Dabei handelt es sich zwar um kein HTML/PHP/CSS-spezifisches Problem, wohl aber um eines aus der Programmiertechnik. Leider wüsste ich selbst kein Forum, in welchem ich sonst diese Frage (Cross?)-Posten könnte.

Nun. Vereinfacht gesagt, geht es um eine Nullstellen- bzw. Zielwertsuche, die ich mir schreiben muss. Ich habe eine Funktion f(x,a,b,c,d) = y die von verschiedenen Parametern abhängig ist, wobei der einzig veränderliche Parameter x ist. (Klingt etwas komisch, aber ich übergebe beim Funktionsaufruf sämtliche andere Konstanten). Für jede x, bei festgehaltenen a,b,c,d gibt es also ein y.

Nun habe ich einen Wert für y vorgegeben und möchte nun das dazugehörige x bestimmen. Quasi eine Nullstellensuche. Ich habe nun das Problem, dass besagte (eindimensionale) Funktion f(x) zwar stetig, aber nicht analytisch differenzierbar ist: beim Aufruf von f(x) wird y über einige Schleifen etc. ermittelt. Und hier komme ich irgendwie nicht weiter bzw. weiß nicht, wie ich überhaupt anfangen soll ...

Bisher habe ich das Problem in Matlab gelöst, eben über eine Nullstellensuche bzw. der Matlab-Funktion fzero().

Nun bin ich auf der Suche nach einem möglichst schnellen Algorithmus, mit dem ich das x für mein gegebenes y hinreichend genau bestimmen kann (z.B. über ein Toleranzkriterium o.ä.).

Aus dem Studium ist mir noch Newton-Raphson, Sekantenmethode o.ä. ein Begriff, aber leider ist das schon viel zu lange her, als dass ich wüsste, wie man es auf meine nicht differenzierbare Funktion übertragen/anwenden könnte. Gut wäre auch, wenn es ein Verfahren gäbe, welches schnell konvergiert.

Einziges Problem ist noch: Ich muss o.g. in einer internen "Skriptsprache" eines Programmes (Sofistik) umsetzen, das leider sehr wenig Funktionalität bzgl. Programmierung bietet. D.h. es stehen mir nur die allernotwendigsten Dinge zur Verfügung: Bedingungen, Schleifen und einige mathematische Basisfunktionen. "Höchster" möglicher Datentyp sind eindimensionale Arrays.

Hat jemand von Euch evtl. eine Idee oder vielleicht gar ein fertiges Skript, das obige Aufgabe erfüllen könnte und das ich "nur" noch übersetzen müsste?

Vielen lieben Dank im Voraus, Jens C.

[JürgenB]

Hallo,

… aber nicht analytisch differenzierbar ist …

hast du es schon mal mit einer Näherung (f(x2)-f(x1))/(x2-x1) für df/dx versucht?

Gruß
Jürgen

[Rolf ẞ]

Hallo JürgenB,

das nennt man dann letztlich Sekantenverfahren 😀

Rolf

[Rolf ẞ]

Hallo Jens,

was sagt man denn hier ?

Wieauchimmer - was weißt Du denn sonst noch über die Funktion? Du sagst, sie sei stetig. Ist sie auch monoton? Weil - wenn sie das nicht ist, bekommst Du ggf. mehrere X, die auf dein Y führen können. Willst Du dann alle X wissen oder reicht ein beliebiges?

Nullstellensuche mit 1. Ableitung, ja ok, beim Newton Verfahren braucht man das. Beim Sekantenverfahren nicht, und alternativ gibt's immer noch die gute alte Bisektion :)

Sekanten- und Bisektionsverfahren brauchen beide ein Start-Intervall. Dazu musst Du den Wertebereich für x "abtasten", d.h. in sinnvollen Schritten Funktionswerte für mehrere x berechnen. Findest Du zwei Werte $$x_1, x_2$$, für die $$f(x_1) \leq y \land f(x_2) \geq y$$ gilt - oder umgekehrt, bei fallenden Werten - dann hast Du ein solches Intervall gefunden. Bei einer bekannt monotonen Funktion kannst Du die Randwerte des Definitionsbereichs als Startintervall nehmen. Bei einer differenzierbaren Funktion KÖNNTE man die lokalen Extrema nehmen, hast Du aber nicht.

Risiko ist, dass zwischen den so gefundenen Startwerten nicht nur ein passendes X liegt, sondern möglicherweise drei, fünf oder mehr. In diesem Fall kann es passieren, dass die Iterationsverfahren nicht konvergieren.

Passieren kann bei nicht-monotonen Funktionen auch, dass Du zwei Werte prüfst, und beide Funktionswerte zu groß sind (oder zu klein). Die Funktion hat zwischen diesen beiden Punkten aber eine gerade Anzahl von y-Stellen. Dann überspringst Du dieses Intervall, obwohl es hier eine Lösung gegeben hätte.

Das ist immer das Risiko bei numerischen Verfahren. Die Abtastbreite für das Startintervall hängt vom Charakter der Funktion ab - den musst Du kennen.

Bei bekanntem Startintervall ist die Bisektion nun relativ einfach. Ich schreibe es erstmal für $$f(x_1) \leq f(x_2)$$ auf. Du berechnest $$ x_m = \frac{x_1+x_2}{2}, y_m = f(x_m, a,b,c,d)$$, also den Funktionswert in der Intervallmitte. Ist $$y_m \leq y$$, ist das gesuchte x größer als $$x_m$$, ansonsten kleiner. Abhängig davon setzt Du $$x_1 := x_m$$ oder $$x_2 := x_m$$ und wiederholst die Schleife solange, bis $$x_2-x_1 \le \epsilon$$ für eine vorgegebene Genauigkeit ϵ ist.

Das Sekantenverfahren konvergiert schneller, kann aber in die Irre laufen wenn Du mehrere y-Stellen hast. Du brauchst wieder zwei Startwerte. Ist f monoton, reichen zwei beliebige Werte. Andernfalls musst Du wieder mit Abtastung arbeiten und zwei Startwerte in der Nähe des gesuchten X finden. Das ist aber keine Garantie, das Verfahren kann abdriften.

Du berechnest nun zu $$x_1, x_2$$ die Funktionswerte $$y_1=f(x_1)y$$ und $$y_2=f(x_2)$$. Daraus bestimmst Du ein neues $$x_m = x_2 - \frac{x_2-x_1}{y_2-y_1}(y_2-y)$$. Dann setzt Du $$x_1 := x_2, y_1 := y_2, x_2 := x_m$$ und $$y_2 = f(x_m)$$ und fängst von vorn an. So lange, bis $$f(x_m)$$ nahe genug an y liegt.

Newton kannst Du vergessen - dafür brauchst Du die Ableitung von f.

Rolf

[Null]

Bisher habe ich das Problem in Matlab gelöst, eben über eine Nullstellensuche bzw. der Matlab-Funktion fzero().

Matlab nutzt Brent's Method, was die von Rolf genannten Methoden kombiniert. Was besseres fiele mir sponatan auch nicht ein.