Discussion:
Minimumsuche mit ABCD-Methode
(zu alt für eine Antwort)
Rainer Rosenthal
2020-06-27 14:32:39 UTC
Permalink
Gegeben eine stetige Funktion f auf den reellen Zahlen mit Werten, die
ebenfalls reelle Zahlen sind. Nehmen wir an, wir wüssten, dass f ein
Minimum hat im Bereich a < x < d, und wir wollten es genauer bestimmen.
Zusätzlich nehme ich an, dass die Funktion im Intervall [a,d] kein
weiteres Minimum hat. Ich schränke noch weiter ein, indem ich fordere,
dass f streng monoton fällt und nach dem Minimum streng monoton wächst.

Als Beispiel denke man sich etwa f(x) = (x-sqrt(2))^2 + 1.
Diese Beispielfunktion hat ein Minimum zwischen a=1 und d=2, und niemand
käme auf den Gedanken, es mit einem Rechenverfahren zu suchen. Niemand
außer mir :-)
Ich tue mal so, als wüsste ich nicht, dass Quadrate nie kleiner als 0
sein können, weil mir dies Wissen sofort die Lösung x = sqrt(2) gäbe.

Dann kann ich ein Verfahren anwenden, das ich als ABCD-Verfahren
bezeichnen möchte. Es ist gewiss nicht neu, aber ich habe es bislang
auch noch nicht beschrieben gefunden. Darum nehme ich gerne Hinweise
entgegen, wo man es nachlesen kann.

Ich teile das Intervall [a,d] in drei gleichgroße Teile a < b < c < d.
Die entsprechenden Funktionswerte seien A, B, C und D.
Aus den oben gennnten Voraussetzungen weiß ich, dass genau eine der
folgenden drei Beziehungen gilt:

A > B > C < D (GGL)
A > B = C < D (GIL)
A > B < C < D (GLL)

Mir war nun aufgefallen, dass das ursprüngliche Intervall [a,d] auf zwei
Drittel seiner Größe verkleinert werden kann, so dass immer noch
gewährleistet ist, dass das Minimum von f in dem neuen Intervall [A',D']
liegt.
Da ist im Fall von (GGL) das Intervall [A',D'] = [B,D]
und im Falle (GLL) das Intervall [A',D'] = [A,C].
Im Fall (GIL) kann man für [A',D'] entweder [A,C] oder [B,D] wählen.

Wiederholte Anwendung dieses Verfahrens liefert immer feinere Bestimmung
des Minimums. Hat das Verfahren gar einen hübschen Namen entsprechend
"regula falsi" für die Nullstellensuche einer stetigen Funktion? Wie
wäre es mit "regula trisecta" :-? Sonst halt wie voechlagen "ABCD-Methode".

Gruß,
Rainer Rosenthal
***@web.de
Helmut Richter
2020-06-27 18:20:14 UTC
Permalink
Post by Rainer Rosenthal
Ich teile das Intervall [a,d] in drei gleichgroße Teile a < b < c < d.
Die entsprechenden Funktionswerte seien A, B, C und D.
Aus den oben gennnten Voraussetzungen weiß ich, dass genau eine der folgenden
A > B > C < D (GGL)
A > B = C < D (GIL)
A > B < C < D (GLL)
Mir war nun aufgefallen, dass das ursprüngliche Intervall [a,d] auf zwei
Drittel seiner Größe verkleinert werden kann, so dass immer noch gewährleistet
ist, dass das Minimum von f in dem neuen Intervall [A',D'] liegt.
Da ist im Fall von (GGL) das Intervall [A',D'] = [B,D]
und im Falle (GLL) das Intervall [A',D'] = [A,C].
Im Fall (GIL) kann man für [A',D'] entweder [A,C] oder [B,D] wählen.
Geht dann nicht auch [B, C] oder macht das das Verfahren unnötig schnell?
--
Helmut Richter
Rainer Rosenthal
2020-06-27 21:28:51 UTC
Permalink
Post by Helmut Richter
Post by Rainer Rosenthal
Ich teile das Intervall [a,d] in drei gleichgroße Teile a < b < c < d.
Die entsprechenden Funktionswerte seien A, B, C und D.
Aus den oben gennnten Voraussetzungen weiß ich, dass genau eine der folgenden
A > B > C < D (GGL)
A > B = C < D (GIL)
A > B < C < D (GLL)
Mir war nun aufgefallen, dass das ursprüngliche Intervall [a,d] auf zwei
Drittel seiner Größe verkleinert werden kann, so dass immer noch gewährleistet
ist, dass das Minimum von f in dem neuen Intervall [A',D'] liegt.
Da ist im Fall von (GGL) das Intervall [A',D'] = [B,D]
und im Falle (GLL) das Intervall [A',D'] = [A,C].
Im Fall (GIL) kann man für [A',D'] entweder [A,C] oder [B,D] wählen.
Geht dann nicht auch [B, C] oder macht das das Verfahren unnötig schnell?
Mit [B,C] solltest Du nur weitermachen, wenn Du sicher sein kannst, dass
das Minimum in diesem Intervall gefunden werden kann. Genauer gesagt:
mit [b,c] solltest Du ... (s.u.)

Nehmen wir nämlich mal die von mir mitgelieferte Testfunktion:
"Als Beispiel denke man sich etwa f(x) = (x-sqrt(2))^2 + 1.
Diese Beispielfunktion hat ein Minimum zwischen a=1 und d=2"

Wir können auch sagen, diese Beispielfunktion habe ihr Minimum zwischen
a=-1 und d=2, dann ergibt Drittelung von [a,d] = [-1,2] die
Teilungspunkte b=0 und c=1 und wir bekommen

A=6.8 > B=3.0 > C=1.2 < D=1.3

haben also den Fall (GGL) mit Minimum in [b,d], nicht aber in [b,c].


Danke sehr für Deine Rückfrage, denn erst jetzt sehe ich, dass ich noch
sehr ins Unreine geschrieben hatte (Schande über mich).

Bereits bei der Konstruktion des Beispiels ist mir aufgefallen, dass ich
hätte sagen sollen, dass man [a,d] verkleinert zu [a,c] oder [b,d].
Der Bereich der x-Werte soll ja eingegrenzt werden. Siehe oben.

Richtig schlimm ist aber, dass ich den Fall A > B > C > D nicht
berücksichtigt hatte. Darauf stoße ich ja sofort, wenn ich statt Wurzel
aus 2 die Wurzel aus 3 verwende, also statt f(x) = (x-sqrt(2))^2 + 1 die
Funktion g(x) = (x-sqrt(3))^2 + 1.

Auch sie hat ihr Minimum zwischen 1 und 2. Es liegt somit auch zwischen
a=-1 und d=2 und meine Methode erfordert die Berechnungen
A = g(a) = g(-1) = 8.3
B = g(b) = g(0) = 4.0
C = g(c) = g(1) = 1.5
D = g(d) = g(2) = 1.1

Peinlich, peinlich, nun ist A > B > C > D und im Bedienungshandbuch zu
meiner ABCD-Methode scheint ein Blatt zu fehlen.

So lerne ich durch diese Diskussion genauer kennen, was ich da als
plötzlichen Einfall hatte.
Es scheint mir nun aber so, dass alle Fälle abgedeckt sind.
Naja, fast ... Es könnte auch A > B > C = D gelten.

Oh je, ich muss nochmal "back to the drawing board", weil mir auch der
Fall A < B < C < D noch durch die Lappen gegangen ist und auch A = B < C
< D.

Darf ich die verehrten Herrschaften herzlich um Verzeihung bitten?
Sie erhalten Ihr Geld an der Eingangskasse zurück!

Gruß,
Rainer Rosental
***@web.de
Marc Olschok
2020-06-27 22:07:09 UTC
Permalink
Post by Rainer Rosenthal
Gegeben eine stetige Funktion f auf den reellen Zahlen mit Werten, die
ebenfalls reelle Zahlen sind. Nehmen wir an, wir wüssten, dass f ein
Minimum hat im Bereich a < x < d, und wir wollten es genauer bestimmen.
Zusätzlich nehme ich an, dass die Funktion im Intervall [a,d] kein
weiteres Minimum hat. Ich schränke noch weiter ein, indem ich fordere,
dass f streng monoton fällt und nach dem Minimum streng monoton wächst.
Als Beispiel denke man sich etwa f(x) = (x-sqrt(2))^2 + 1.
Diese Beispielfunktion hat ein Minimum zwischen a=1 und d=2, und niemand
käme auf den Gedanken, es mit einem Rechenverfahren zu suchen. Niemand
außer mir :-)
Ich tue mal so, als wüsste ich nicht, dass Quadrate nie kleiner als 0
sein können, weil mir dies Wissen sofort die Lösung x = sqrt(2) gäbe.
Dann kann ich ein Verfahren anwenden, das ich als ABCD-Verfahren
bezeichnen möchte. Es ist gewiss nicht neu, aber ich habe es bislang
auch noch nicht beschrieben gefunden. Darum nehme ich gerne Hinweise
entgegen, wo man es nachlesen kann.
Ich teile das Intervall [a,d] in drei gleichgroße Teile a < b < c < d.
Die entsprechenden Funktionswerte seien A, B, C und D.
Aus den oben gennnten Voraussetzungen weiß ich, dass genau eine der
A > B > C < D (GGL)
A > B = C < D (GIL)
A > B < C < D (GLL)
Vielleicht habe ich etwas übersehen, aber welche Beziehung
stellt sich denn z.B. im Fall von f(x) = (x-c)(x-d) ein?
Post by Rainer Rosenthal
Mir war nun aufgefallen, dass das ursprüngliche Intervall [a,d] auf zwei
Drittel seiner Größe verkleinert werden kann, so dass immer noch
gewährleistet ist, dass das Minimum von f in dem neuen Intervall [A',D']
liegt.
Da ist im Fall von (GGL) das Intervall [A',D'] = [B,D]
und im Falle (GLL) das Intervall [A',D'] = [A,C].
Im Fall (GIL) kann man für [A',D'] entweder [A,C] oder [B,D] wählen.
Wiederholte Anwendung dieses Verfahrens liefert immer feinere Bestimmung
des Minimums. Hat das Verfahren gar einen hübschen Namen entsprechend
"regula falsi" für die Nullstellensuche einer stetigen Funktion? Wie
wäre es mit "regula trisecta" :-? Sonst halt wie voechlagen "ABCD-Methode".
Gruß,
Rainer Rosenthal
Rainer Rosenthal
2020-06-27 22:56:28 UTC
Permalink
Post by Marc Olschok
Vielleicht habe ich etwas übersehen, aber welche Beziehung
stellt sich denn z.B. im Fall von f(x) = (x-c)(x-d) ein?
Hallo Marc,

Du hast wahrscheinlich aus der Antwort an Helmut gesehen, dass mir die
Mängel in der Darstellung und in den Fallunterscheidungen bereits klar
geworden sind.
Ich bin zuversichtlich, dass ich es noch hinbekommen werde, meinen
Einfall ordentlich zu präsentieren.

Die von Dir genannte Funktion legt sehr gut den Mangel meiner
Beschreibung bloß, danke!

Zu Deinem Beispiel:
Wir haben für a < b < c < d die Relationen A > B > C = D, und das zeigt
sehr gut, dass meine Fallunterscheidungen noch unvollständig waren.

Im vorliegenden Fall, den ich konsequenterweise (GGI) nennen möchte,
lautet die Anweisung: gehe vom Intervall [a,d] über zum Intervall [b,d].

Danke nochmal für den schnellen und richtigen Einwand!

Lieben Gruß,
Rainer

Loading...