Programmiertechnik: Zielwert/Nullstellensuche, Verfahren?

[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