\mnb150<nb wrap="0" txtwidth="80" autowidth="0" pprint="1" typeset="1" xface="Times New Roman" xsize="280" xbold="0" xitalic="0" xcolor="#0000FF" slidents="1" sizemult="71" minsize="160" ifont="0 280 255 0 49 Courier New" ofont="0 280 16711680 0 49 Courier New" tfont="0 280 0 0 34 Arial"></nb>ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fmodern\fprq1 Courier New;}{\f4\fswiss\fprq2 Arial;}{\f5\fswiss\fprq2 Helvetica;}{\f6\fmodern\fprq1\fcharset1 Courier New;}{\f7\fswiss\fprq2\fcharset1 Arial;}}
{\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;\red255\green0\blue0;\red0\green0\blue128;}
\deflang1031\pard\ri4\plain\f3\fs20\cf0\b ________________________________________________________________________________
\par 
\par \plain\f3\fs20\cf0 Inhalt....: Minimierung mit dem Goldenen Schnitt Verfahren
\par Kategorie.: Unterrichtsmaterial
\par Mathematik: Analysis, Numerik
\par MuPAD.....: 3.0.0
\par Datum.....: 2003-02-11
\par Autoren...: Alessandro Dell'Aere <dellaere@mupad.de>
\par Funktionen: plot, plot::Function2d, plot::Point2d, Color, PointSize, float, is
\par \plain\f3\fs20\cf0\b ________________________________________________________________________________
\par \plain\f4\fs36\cf0\b 
\par \plain\f4\fs40\cf0\b Minimierung mit dem Goldenen Schnitt
\par \plain\f4\fs22\cf0 
\par \plain\f4\fs24\cf2 Diese Lehreinheit bietet eine intuitive Einf\'fchrung in die Optimierung einer Funktion mit dem
\par \plain\f4\fs24\cf2\i Verfahren des Goldenen Schnittes\plain\f4\fs24\cf2  und gibt Anregungen zum Experimentieren. \plain\f4\fs22\cf0 
\par 
\par \plain\f4\fs28\cf0 Wir wollen ein Verfahren kennenlernen, mit dem man n\'e4herungsweise das
\par Minimum einer Funktion \plain\f6\fs28\cf3 f\plain\f4\fs28\cf0  finden kann.
\par 
\par Dazu betrachten wir folgende Funktion \plain\f6\fs28\cf3 f\plain\f4\fs28\cf0  in dem Intervall \plain\f3\fs28\cf3 [-PI/2, PI/2]\plain\f4\fs28\cf0 :
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}f := x -> exp(x) + x^6 - 20.0
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}l := float(-PI/2):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 r := float(PI/2):
\par 
\par F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
\par 
\par plot(F):
\par \pard\ri4\plain\f7\fs28\cf0 
\par Wir sehen am Graphen, dass diese Funktion eine Minimalstelle besitzt.
\par Diese k\'f6nnen wir zun\'e4chst nur grob sch\'e4tzen, jedoch sehen wir deutlich,
\par dass sie garantiert innerhalb des Intervalls \plain\f6\fs28\cf3 [l, r]\plain\f7\fs28\cf0  liegt.
\par 
\par Wir wollen nun den Funktionswert an den Intervallgrenzen und an einer
\par weiteren Stelle im Inneren des Intervalls berechnen. Dazu teilen wir das
\par Intervall zun\'e4chst im Verh\'e4ltnis des sog. \plain\f7\fs28\cf0\i Goldenen Schnittes\plain\f7\fs28\cf0  in zwei
\par Teilintervalle. Die Verh\'e4ltniszahl des \plain\f7\fs28\cf0\i Goldenen Schnittes\plain\f7\fs28\cf0  werden wir im
\par folgenden mit \plain\f6\fs28\cf3 T\plain\f7\fs28\cf0  bezeichnen.
\par 
\par Sie berechnet sich wie folgt:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}T := float( 2/(1 + sqrt(5)) )
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 
\par \pard\ri4\plain\f4\fs28\cf0 Die zus\'e4tzliche Stelle, an der wir die Funktion berechnen wollen und die wir
\par nun \plain\f3\fs28\cf3 p\plain\f4\fs28\cf0  nennen wollen, finden wir ganz einfach. Wir gehen von der linken
\par Intervallgrenze einfach das \plain\f3\fs28\cf3 T\plain\f4\fs28\cf0 -fache der Intervalll\'e4nge weiter nach rechts:
\par \plain\f4\fs22\cf0 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}p :=  l + T*(r - l)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 
\par \pard\ri4\plain\f7\fs28\cf0 Die beiden Teilintervalle sind nun gegeben durch:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}[l, r], [r, p]
\par \pard\ri4\plain\f7\fs28\cf0 
\par Nun werten wir die Funktion \plain\f3\fs28\cf3 f \plain\f7\fs28\cf0 an den Randepunkten der Teilintervalle aus:\plain\f4\fs28\cf3 
\par \plain\f3\fs22\cf3 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}y_l := f(l);
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_r := f(r);
\par y_p := f(p)
\par 
\par \pard\ri4\plain\f7\fs28\cf0 Mit Hilfe der x-Koordinaten \plain\f3\fs28\cf3 l\plain\f7\fs28\cf0 , \plain\f3\fs28\cf3 r\plain\f7\fs28\cf0 , \plain\f3\fs28\cf3 p\plain\f7\fs28\cf0  und den zugeh\'f6rigen y-Koordinaten \plain\f3\fs28\cf3 y_l\plain\f7\fs28\cf0 , \plain\f3\fs28\cf3 y_r\plain\f7\fs28\cf0 ,
\par \plain\f3\fs28\cf3 y_p\plain\f7\fs28\cf0  lassen sich jetzt die entsprechenden Punkte definieren und zusammen mit
\par der Funktion \plain\f3\fs28\cf3 f\plain\f7\fs28\cf0  in ein gemeinsames Koordinatensystem einzeichnen:
\par \plain\f7\fs22\cf0 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
\par P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
\par plot(F, L, R, P):
\par \pard\ri4\plain\f7\fs28\cf0 
\par Wir hatten die Stelle \plain\f6\fs28\cf3 p\plain\f7\fs28\cf0  gefunden, indem wir von der linken Intervallgrenze
\par aus das \plain\f3\fs28\cf3 T\plain\f7\fs28\cf0 -fache der Intervalll\'e4nge weiter nach rechts gegangen waren.
\par 
\par Nun berechnen wir analog eine weitere Stelle \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0 , indem wir von der rechten
\par Intervallgrenze \plain\f6\fs28\cf3 r\plain\f7\fs28\cf0  aus um das \plain\f3\fs28\cf3 T\plain\f7\fs28\cf0 -fache der Intervalll\'e4nge \plain\f3\fs28\cf3 r-l\plain\f7\fs28\cf0  weiter nach links
\par gehen. Wir berechnen auch gleich den zugeh\'f6rigen Funktionswert:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}q :=  r - T*(r - l);
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_q := f(q)
\par \plain\f3\fs22\cf3 
\par \pard\ri4\plain\f7\fs28\cf0 
\par Wir bekommen also einen neuen Punkt, den wir ebenfalls mit in unseren
\par Graphen aufnehmen wollen:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}Q := plot::Point2d(q, y_q, Color = RGB::Red, PointSize = 3*unit::mm):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 plot(F, L, R, P, Q):
\par \pard\ri4\plain\f7\fs28\cf0 
\par Nun \'fcberpr\'fcfen wir, an welcher der beiden Stellen \plain\f6\fs28\cf3 p\plain\f7\fs28\cf0  und \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0  unsere Funktion
\par den kleineren Wert annimmt:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}y_p;
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_q;
\par is(y_q < y_p)\plain\f3\fs22\cf3 
\par 
\par \pard\ri4\plain\f7\fs28\cf0 
\par Damit haben wir herausgefunden, dass die gesuchte Minimalstelle nicht nur
\par im Intervall \plain\f6\fs28\cf3 [l, r]\plain\f7\fs28\cf0 , sondern sogar in dem kleineren Intervall \plain\f6\fs28\cf3 [l, p]\plain\f7\fs28\cf0 . Wir
\par k\'f6nnen also das obige Prinzip erneut anwenden. Die Stelle \plain\f6\fs28\cf3 r\plain\f7\fs28\cf0  mit zugeh\'f6rigem
\par Funktionswert \plain\f6\fs28\cf3 y_r\plain\f7\fs28\cf0  ben\'f6tigen wir nun nicht mehr. Deshalb k\'f6nnen wir die
\par Bezeichnungen wechseln, womit wir dieselbe Ausgangssituation wie weiter
\par oben erhalten:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}r := p:
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_r := y_p:
\par R := P:
\par 
\par p := q:
\par y_p := y_q:
\par P := Q:
\par 
\par F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
\par 
\par \pard\ri4\plain\f7\fs28\cf0 Unseren Graphen brauchen wir jetzt nur noch im neuen, kleineren Intervall
\par darzustellen. Dieses hei\'dft aber nach Wahl unserer Bezeichnungen ebenfalls
\par wieder \plain\f6\fs28\cf3 [l, r]\plain\f7\fs28\cf0  und die neue Stelle dazwischen wieder \plain\f6\fs28\cf3 p\plain\f7\fs28\cf0 .
\par 
\par Um den neuen Graphen zu zeichnen, brauchen wir also nur zu wiederholen,
\par was wir zum Zeichnen des aller ersten Graphen weiter oben getan haben:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
\par P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
\par 
\par plot(F, L, R, P):
\par \plain\f3\fs22\cf3 
\par \pard\ri4\plain\f7\fs28\cf0 Wir gehen einen Schritt weiter und berechnen wieder eine weitere Stelle \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0 ,
\par und zwar diesmal, indem wir von der rechten Intervallgrenze \plain\f6\fs28\cf3 r\plain\f7\fs28\cf0  aus um das
\par \plain\f6\fs28\cf3 T\plain\f7\fs28\cf0 -fache der Intervalll\'e4nge \plain\f6\fs28\cf3 (r-l)\plain\f7\fs28\cf0  nach links gehen, denn die neue Stelle \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0 
\par mu\'df immer in dem gr\'f6\'dferen der beiden Teilintervalle \plain\f6\fs28\cf3 [l, p]\plain\f7\fs28\cf0  und \plain\f6\fs28\cf3 [p, l]\plain\f7\fs28\cf0 
\par liegen:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}q := r - T*(r - l):
\par \pard\ri4\plain\f7\fs28\cf0 
\par Da sich nun alles wiederholt, k\'f6nnen wir die folgenden Schritte bis zur
\par n\'e4chsten Graphik ohne weitere Kommentare durchf\'fchren:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}y_q := f(q):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 Q := plot::Point2d(q, y_q, Color = RGB::Violet, PointSize = 3*unit::mm):
\par 
\par plot(F, L, R, P, Q):
\par \pard\ri4\plain\f7\fs28\cf0 
\par Wieder stellt sich die Frage, an welcher der beiden Stellen \plain\f6\fs28\cf3 p\plain\f7\fs28\cf0  und \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0  die
\par Funktion den kleineren Wert annimmt:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}y_p;
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_q;
\par is(y_p < y_q)
\par \plain\f3\fs22\cf3 
\par \pard\ri4\plain\f7\fs28\cf0 
\par Diesmal wandert also die linke Intervallgrenze \plain\f6\fs28\cf3 l\plain\f7\fs28\cf0  dort hin, wo vorher die Stelle
\par \plain\f6\fs28\cf3 q\plain\f7\fs28\cf0  war:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}l := q:
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 y_l := y_q:
\par L := q:
\par F := plot::Function2d(f(x), x = l..r, Color = RGB::Blue):
\par 
\par \pard\ri4\plain\f7\fs28\cf0 Ein letztes Mal wollen wir den Graphen zeichnen lassen: Die y-Koordinaten
\par der neuen Punkte \plain\f6\fs28\cf3 L\plain\f7\fs28\cf0 , \plain\f6\fs28\cf3 P\plain\f7\fs28\cf0  und \plain\f6\fs28\cf3 R\plain\f7\fs28\cf0  sind nun viel n\'e4her zusammenger\'fcckt, als es
\par urspr\'fcnglich der Fall war. Deshalb wird MuPAD die y-Achse neu skalieren,
\par so dass wir den Verlauf des Graphen in dem f\'fcr uns relevanten Bereich viel
\par genauer beurteilen k\'f6nnen:
\par 
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf3 {\pntext\f1\'b7\tab}L := plot::Point2d(l, y_l, Color = RGB::Black, PointSize = 3*unit::mm):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf3 R := plot::Point2d(r, y_r, Color = RGB::Black, PointSize = 3*unit::mm):
\par P := plot::Point2d(p, y_p, Color = RGB::Green, PointSize = 3*unit::mm):
\par 
\par plot(F, L, R, P):
\par \plain\f3\fs22\cf3 
\par \pard\ri4\plain\f7\fs28\cf0 
\par Dieses Verfahren kann man nun so lange fortsetzen, bis die L\'e4nge des
\par Intervalls \plain\f6\fs28\cf3 [l, r]\plain\f7\fs28\cf0  der jeweiligen Anwendung entsprechend  klein genug ist.\plain\f3\fs20\cf0\b 
\par 
\par ________________________________________________________________________________
\par \plain\f4\fs22\cf1\b 
\par \plain\f4\fs22\cf4\b \'dcbungen:
\par \plain\f4\fs20\cf4\b 1.\plain\f4\fs20\cf4  Die hier untersuchte Funktion hat die Eigenschaft, in dem untersuchten Intervall ein Minimum zu haben und
\par     stets linksgekr\'fcmmt zu sein. Finden sie eine Funktion und dazu ein Startintervall, so dass das obige
\par     Verfahren kein absolutes, sondern nur ein lokales Minimum findet.
\par 
\par \plain\f4\fs20\cf4\b 2.\plain\f4\fs20\cf4  Diskutieren Sie, was zu tun ist, wenn die Funktion an den beiden inneren Stellen p und q den gleichen Wert
\par     annimmt.
\par 
\par \plain\f4\fs20\cf4\b 3.\plain\f4\fs20\cf4  Entwerfen sie eine kleine MuPAD-Prozedur, die bei Vorgabe einer (geeigneten) Funktion f und eines
\par     Startintervalls [l, r] ein L\'f6sungsintervall findet, welches die Minimalstelle umschlie\'dft und eine L\'e4nge hat,
\par     die kleiner als 0.001 ist. \plain\f3\fs20\cf0\b 
\par ________________________________________________________________________________
\par \plain\f4\fs22\cf0 
\par \plain\f4\fs22\cf2\b Anmerkungen:\plain\f4\fs22\cf2 
\par \plain\f4\fs20\cf2\b 1. \plain\f4\fs20\cf2  Das oben benutzte Teilungsverh\'e4ltnis von 1:T mit T = 0.61803... ergibt sich aus dem  Grenzwert der
\par      Quotienten der Fibonacci-Zahlen. Man kann zeigen, dass das Verfahren gerade mit diesem
\par      Teilungsverh\'e4ltnis am schnellsten zum Ergebnis f\'fchrt.
\par 
\par \plain\f4\fs20\cf2\b 2\plain\f4\fs20\cf2 .  Weitere Anregungen finden Sie in der Buchreihe \plain\f4\fs20\cf3 Mathematik 1 x anders\plain\f4\fs20\cf2 . In dieser Reihe
\par      wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par      B\'fccher k\'f6nnen unter \plain\f5\fs20\cf1 www.schule.mupad.de/literatur\plain\f4\fs20\cf2  kostenfrei kopiert werden. \plain\f4\fs20\cf1 
\par \plain\f3\fs20\cf0\b _______________________________________________________________________________
\par 
\par 
\par }