Einführungskurs/Extremwertsuche

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
== Extremwertsuche nach dem Verfahren des Goldenen Schnitts ==

Die binäre Suche muss nicht zwingend zur Intervallhalbierung führen.<br /> 
Wir betrachten die Extremwertsuche nach dem Verfahren des Goldenen Schnitts zunächst für die Suche eines lokalen Minimums:

<table border="0">
<tr>
<td align="center">
[[Bild:Extremwert.gif]]<br />
Animation: Minimumsuche nach dem Verfahren des Goldenen Schnitts
</td>
<td>'''Algorithmus''' (Minimumsuche):
<ul>
<li>Lege ein Suchintervall durch zwei äußere Intervallgrenzen fest.</li>
<li>Zerlege dieses Suchintervall durch einen ''zweimaligen'' Goldenen Schnitt in 3 Teilintervalle.</li>
<li>Berechne die Funktionswerte an beiden Schnittstellen.</li>
<li>Das neue Suchintervall wird aus der Schnittstelle mit dem größeren der beiden Funktionswerte und einer der äußeren Intervallgrenzen derart gebildet, dass die Schnittstelle mit dem ''kleineren'' Funktionswert ''eingeschlossen'' wird.</li>
<li>Führe im neuen Suchintervall den Goldener Schnitt durch, der wieder zu 3 Teilintervallen führt.</li>
<li>Wiederhole das Verfahren solange, bis das Suchintervall einer hinreichend kleinen &epsilon;-Umgebung genügt.</li>
<li>Der Funktionswert eines Arguments aus dieser &epsilon;-Umgebung entspricht dem gesuchten Minimum.</li>
</ul>
</td>
</tr>
</table>

== Implementation ==

Mit einem kleinen Trick lässt sich ''ein und dieselbe'' Suchfunktion sowohl für lokale Minima als auch für lokale Maxima einsetzen. Der Vergleich der Funktionswerte wird mit einem Korrekturfaktor <math>k</math> geführt, der lediglich die Werte <math>1</math> oder <math>-1</math> annehmen kann, z.B.:

 if (k*fkt(li) > k*fkt(re)) ...

Dieser Faktor kann als Parameter übergeben werden und hat die gleiche Wirkung wie die Umkehr des Relationszeichens bei einem herkömmlichen Vergleich.

<code id="4d2ac43b9c">
function fkt(x) {
 return 3*Math.sin(2*x);
}

function ExtremwertSuche(von, bis, dx) {
 var gs = (Math.sqrt(5)-1)/2;
 var genau = 4;

 this.Runden = function (x, n) {
  return Math.round(x*Math.pow(10, n))/Math.pow(10, n);
 };

 this.Suche = function(k, xl, li, re, xr) {
  var eps = 1/Math.pow(10, genau+2);   
  if (xr-xl < eps)
   return (xl+xr)/2;
  else if (k*fkt(li) > k*fkt(re))
   return this.Suche(k, xl, re-gs*(re-xl), li, re);
  else
   return this.Suche(k, li, re, li+gs*(xr-li), xr);
 };

 this.TeilAusgabe = function(k) {
  var s = "";
  var anzahl = 0;
  var schnitt = gs*dx;
  var xl, xr, yl, yr, x, y;
  xl = von; yl = fkt(xl);
  while (xl < bis) {
   xr = xl+dx; yr = fkt(xr);
   if (yl*yr >= 0) {
    x = this.Suche(k, xl, xr-schnitt, xl+schnitt, xr);
    y = fkt(x);
    if (k*y > k*yl && k*y > k*yr) {
     anzahl++; 
     console.log("f("+this.Runden(x, genau)+") = "+this.Runden(y, genau));
    }
   }
   xl = xr; yl = yr;
  }
  return anzahl;
 };
 
 this.Ausgabe = function() {
  var anzahl;
  console.log("Lokale Maxima:");
  anzahl = this.TeilAusgabe(1);
  if (anzahl == 0) console.log("--> Keine lokalen Maxima gefunden!");
  console.log("Lokale Minima:");
  anzahl = this.TeilAusgabe(-1);
  if (anzahl == 0)  console.log("--> Keine lokalen Minima gefunden!");
 };
  
 return this;
}
</code>

<run id="4d29dc2fc26c">
var ExtremwertSuche1 =new  ExtremwertSuche(-10, 10, 0.33);
ExtremwertSuche1.Ausgabe();
</run>

Zurück zur [[Einführungskurs/Binäre Suche|Binären Suche]].