Eindimensionale Suche


(Contents)(Previous)(Next)

Aus der Mathematik ist bekannt, dass eine Funktion f(x) ihre Extremalwerte entweder auf den Grenzen des Definitionsbereichs oder dann dort einnimmt, wo die erste Ableitung nach x verschwindet, d.h., f'(x)=0. Die Suche besteht also aus zwei Teilen: 1) Grenzen des Definitionsbereichs (explizite Berechnung in zwei Punkten aus Trivialitätsgründen im folgenden nicht explizite betrachtet) und 2) eigentliche Extremalsuche. Dies gilt allerdings nur für überall differenzierbare Funktionen. Ist die Funktion oder deren Ableitung in einzelnen Punkten unstetig, so müssen die Funktionswerte in allen Unstetigkeitspunkten berechnet werden. Dies ist dann schwierig, wenn nicht zum Vornherein bekannt ist, wo die Unstetigkeiten auftreten. Wie in der Literatur üblich, lassen wir derartige Probleme hier ausser Acht und setzen voraus, dass f(x) im ganzen Definitionsbereich x1<x<x2 stetig differenzierbar sei.

Da die numerische Suche nach Nullstellen einer Funktion einfacher ist als die Suche nach Extremalwerten, gibt es prinzipiell zwei Varianten von Suchalgorithmen: A) Nullstellensuche von f'(x)=0 und B) direkte Extremalsuche. Erstere werden Gradientenverfahren genannt, da die einfache Ableitung bei mehrdimensionalen Problemen durch den Gradienten der Funktion ersetzt wird und f' der eindimensionale Gradient ist.

Algorithmen vom Typ A sind meist zuverlässiger und effizienter. Das Hauptproblem ist dabei, dass gerade bei Ingenieurproblemen f(x) durch ein Simulationsprogramm bestimmt ist und die zugehörige Ableitung f'(x) nicht bekannt oder nur sehr schwer zu bestimmen ist. Es gibt dann zwei mögliche Problemlösungen. Ist der Code zur Berechnung von f(x) einfach genug, so können Softwarepakete zum Einsatz kommen, welche die betreffenden Subroutinen analysieren und einen passenden Code für f'(x) generieren. Andernfalls wird f'(x) durch numerische Ableitung approximiert, z.B. durch Bildung finiter Differenzen. Es gibt verschiedenartigste Verfahren zu numerischen Approximation f'approx von Ableitungen. Diese erfordern mindestens zwei Aufrufe der Subroutine, welche f(x) berechnet und sind problematisch da oft eine beschränkte Genauigkeit erzielt wird, welche die numerische Nullstellensuche von f'approx=0 behindern. Es ist daher oft besser, in solchen Fällen direkte Suchalgorithmen vom Typ B zu verwenden.

More:

Gradientensuche - Nullstellensuche

Direkte Suchalgorithmen ohne Gradienteninformation


(Contents)(Previous)(Next)