________________________________________________________________________________
Inhalt....: Minimierung mit dem Goldenen Schnitt Verfahren
Kategorie.: Unterrichtsmaterial
Mathematik: Analysis, Numerik
MuPAD.....: 3.0.0
Datum.....: 2003-02-11
Autoren...: Alessandro Dell'Aere <dellaere@mupad.de>
Funktionen: plot, plot::Function2d, plot::Point2d, Color, PointSize, float, is
________________________________________________________________________________
Minimierung mit dem Goldenen Schnitt
Diese Lehreinheit bietet eine intuitive Einführung in die Optimierung einer Funktion mit dem
Verfahren des Goldenen Schnittes und gibt Anregungen zum Experimentieren.
Wir wollen ein Verfahren kennenlernen, mit dem man näherungsweise das
Minimum einer Funktion f finden kann.
Dazu betrachten wir folgende Funktion f in dem Intervall [-PI/2, PI/2]:
f := x -> exp(x) + x^6 - 20.0
l := float(-PI/2):
r := float(PI/2):
F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
plot(F):
Wir sehen am Graphen, dass diese Funktion eine Minimalstelle besitzt.
Diese können wir zunächst nur grob schätzen, jedoch sehen wir deutlich,
dass sie garantiert innerhalb des Intervalls [l, r] liegt.
Wir wollen nun den Funktionswert an den Intervallgrenzen und an einer
weiteren Stelle im Inneren des Intervalls berechnen. Dazu teilen wir das
Intervall zunächst im Verhältnis des sog. Goldenen Schnittes in zwei
Teilintervalle. Die Verhältniszahl des Goldenen Schnittes werden wir im
folgenden mit T bezeichnen.
Sie berechnet sich wie folgt:
T := float( 2/(1 + sqrt(5)) )
Die zusätzliche Stelle, an der wir die Funktion berechnen wollen und die wir
nun p nennen wollen, finden wir ganz einfach. Wir gehen von der linken
Intervallgrenze einfach das T-fache der Intervalllänge weiter nach rechts:
p := l + T*(r - l)
Die beiden Teilintervalle sind nun gegeben durch:
[l, r], [r, p]
Nun werten wir die Funktion f an den Randepunkten der Teilintervalle aus:
y_l := f(l);
y_r := f(r);
y_p := f(p)
Mit Hilfe der x-Koordinaten l, r, p und den zugehörigen y-Koordinaten y_l, y_r,
y_p lassen sich jetzt die entsprechenden Punkte definieren und zusammen mit
der Funktion f in ein gemeinsames Koordinatensystem einzeichnen:
L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
plot(F, L, R, P):
Wir hatten die Stelle p gefunden, indem wir von der linken Intervallgrenze
aus das T-fache der Intervalllänge weiter nach rechts gegangen waren.
Nun berechnen wir analog eine weitere Stelle q, indem wir von der rechten
Intervallgrenze r aus um das T-fache der Intervalllänge r-l weiter nach links
gehen. Wir berechnen auch gleich den zugehörigen Funktionswert:
q := r - T*(r - l);
y_q := f(q)
Wir bekommen also einen neuen Punkt, den wir ebenfalls mit in unseren
Graphen aufnehmen wollen:
Q := plot::Point2d(q, y_q, Color = RGB::Red, PointSize = 3*unit::mm):
plot(F, L, R, P, Q):
Nun überprüfen wir, an welcher der beiden Stellen p und q unsere Funktion
den kleineren Wert annimmt:
y_p;
y_q;
is(y_q < y_p)
Damit haben wir herausgefunden, dass die gesuchte Minimalstelle nicht nur
im Intervall [l, r], sondern sogar in dem kleineren Intervall [l, p]. Wir
können also das obige Prinzip erneut anwenden. Die Stelle r mit zugehörigem
Funktionswert y_r benötigen wir nun nicht mehr. Deshalb können wir die
Bezeichnungen wechseln, womit wir dieselbe Ausgangssituation wie weiter
oben erhalten:
r := p:
y_r := y_p:
R := P:
p := q:
y_p := y_q:
P := Q:
F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
Unseren Graphen brauchen wir jetzt nur noch im neuen, kleineren Intervall
darzustellen. Dieses heißt aber nach Wahl unserer Bezeichnungen ebenfalls
wieder [l, r] und die neue Stelle dazwischen wieder p.
Um den neuen Graphen zu zeichnen, brauchen wir also nur zu wiederholen,
was wir zum Zeichnen des aller ersten Graphen weiter oben getan haben:
L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
plot(F, L, R, P):
Wir gehen einen Schritt weiter und berechnen wieder eine weitere Stelle q,
und zwar diesmal, indem wir von der rechten Intervallgrenze r aus um das
T-fache der Intervalllänge (r-l) nach links gehen, denn die neue Stelle q
muß immer in dem größeren der beiden Teilintervalle [l, p] und [p, l]
liegen:
q := r - T*(r - l):
Da sich nun alles wiederholt, können wir die folgenden Schritte bis zur
nächsten Graphik ohne weitere Kommentare durchführen:
y_q := f(q):
Q := plot::Point2d(q, y_q, Color = RGB::Violet, PointSize = 3*unit::mm):
plot(F, L, R, P, Q):
Wieder stellt sich die Frage, an welcher der beiden Stellen p und q die
Funktion den kleineren Wert annimmt:
y_p;
y_q;
is(y_p < y_q)
Diesmal wandert also die linke Intervallgrenze l dort hin, wo vorher die Stelle
q war:
l := q:
y_l := y_q:
L := q:
F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
Ein letztes Mal wollen wir den Graphen zeichnen lassen: Die y-Koordinaten
der neuen Punkte L, P und R sind nun viel näher zusammengerückt, als es
ursprünglich der Fall war. Deshalb wird MuPAD die y-Achse neu skalieren,
so dass wir den Verlauf des Graphen in dem für uns relevanten Bereich viel
genauer beurteilen können:
L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
plot(F, L, R, P):
Dieses Verfahren kann man nun so lange fortsetzen, bis die Länge des
Intervalls [l, r] der jeweiligen Anwendung entsprechend klein genug ist.
________________________________________________________________________________
Übungen:
1. Die hier untersuchte Funktion hat die Eigenschaft, in dem untersuchten Intervall ein Minimum zu haben und
stets linksgekrümmt zu sein. Finden sie eine Funktion und dazu ein Startintervall, so dass das obige
Verfahren kein absolutes, sondern nur ein lokales Minimum findet.
2. Diskutieren Sie, was zu tun ist, wenn die Funktion an den beiden inneren Stellen p und q den gleichen Wert
annimmt.
3. Entwerfen sie eine kleine MuPAD-Prozedur, die bei Vorgabe einer (geeigneten) Funktion f und eines
Startintervalls [l, r] ein Lösungsintervall findet, welches die Minimalstelle umschließt und eine Länge hat,
die kleiner als 0.001 ist.
________________________________________________________________________________
Anmerkungen:
1. Das oben benutzte Teilungsverhältnis von 1:T mit T = 0.61803... ergibt sich aus dem Grenzwert der
Quotienten der Fibonacci-Zahlen. Man kann zeigen, dass das Verfahren gerade mit diesem
Teilungsverhältnis am schnellsten zum Ergebnis führt.
2. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________