2. Verfahren: Dreiteilen und richtig kappen

In Taschenrechnern wird meist ein optimiertes Verfahren verwendet. Die Details sind kompliziert, die Grundidee ist jedoch verständlich. Gesucht wird ein lokales Minimum zwischen einer linken Grenze l und einer rechten Grenze r. Durch wiederholtes Verkleinern dieses Bereiches (der Unsicherheit), nähert man sich dem Minimum. Die Funktionskurve muss innerhalb dieser Grenzen folgende Bedingungen erfüllen:

• Dreiteilen und kappen

  

• Optimierter Algorithmus:

  Eingabe: f : Funktiom
           r : Rechte Grenze
           l : Linke Grenze
  
  Wähle l2,r2 zwischen l und r;
  WHILE ABS(r-l) > eps DO
      IF f(l2) > f(r2) THEN
          l:=l2; l2:=r2;
          Wähle neues r2 zwischen l2,r;
      ELSE(*f(r2) > f(l2)*)
          r:=r2; r2:=l2;
          Wähle neues l2 zwischen l,r2;
      END
  END                                                             END
  
  Ausgabe: r oder l
  

Die Kunst des Dreiteilens

Unklar ist noch, nach welchen Verfahren die neuen Punkte ausgewählt werden sollen. Man könnte die Strecke zwischen l und r einfach dritteln, dies wäre die einfachste Wahl. Eine andere Möglichkeit wäre, l2 und r2 zufällig zu wählen. Beide erwähnten Ideen sind jedoch nicht optimal. In Taschenrechner wird häufig die Strecke lr mit Hilfe der Fibonacci-Reihe dreigeteilt. Studieren Sie dazu die untenstehende Abbildung und die Fibonacci-Reihe:

• Dreiteilen mit Fibonacci-Reihe

  

• Die Fibonacci-Reihe wird wie folgt erzeugt:
  F0 := 1; F1 := 1; Fn+2 := Fn+1 + Fn
  Die Fibonacci-Reihe : 1, 1, 2, 3, 5, 8, 13 ...

Dieses Verfahren hat den Nachteil, dass die Anzahl Iterationsschritte am Anfang gewählt werden muss (Hier 5). Unter dem Namen 'Golden- Section- Search' findet man in der Literatur ein Verfahren, bei dem zu Beginn die Anzahl der Schritte nicht festgelegt werden muss. Interessierte können mehr Informationen bei der Lehrperson beziehen.