Einführungskurs/Extremwertsuche

Wiki-Quelltext dieser Seite.

<language>Java</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="4d2a2c431b9c6">
public double fkt(double x) {
 double y = 3*Math.sin(2*x);
 return y;
}

public Object ExtremwertSuche(double von, double bis, double dx) {
 final double gs = (Math.sqrt(5)-1)/2;
 int genau = 4;

 private double Runden(double x, int n) {
  return Math.round(x*Math.pow(10, n))/Math.pow(10, n);
 }

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

 private int TeilAusgabe(int k) {
  int anzahl = 0;
  double schnitt = gs*dx;
  double 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 = Suche(k, xl, xr-schnitt, xl+schnitt, xr);
    y = fkt(x);
    if (k*y > k*yl && k*y > k*yr) {
     anzahl++; 
     System.out.println("f("+Runden(x, genau)+") "+(char)9+"= "+Runden(y, genau));
    }
   }
   xl = xr; yl = yr;
  }
  return anzahl;
 }
 
 public void Ausgabe() {
  int anzahl;
  System.out.println("Lokale Maxima:");
  anzahl = TeilAusgabe(1);
  if (anzahl == 0) System.out.println("--> Keine lokalen Maxima gefunden!");
  System.out.println();
  System.out.println("Lokale Minima:");
  anzahl = TeilAusgabe(-1);
  if (anzahl == 0) System.out.println("--> Keine lokalen Minima gefunden!");
 }
  
 return this;
}
</code>

<run id="4d29dc2fc26ac">
Object ExtremwertSuche1 = ExtremwertSuche(-10, 10, 0.33);
ExtremwertSuche1.Ausgabe();
</run>

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