Funktion maximieren



  • Hallo,

    Ich möchte gerne in einem C-Programm eine Funktion float f(float x) maximieren, wenn möglich soll man noch ein Intervall für x angeben können. Kennt jemand eine entsprechende Funktion? Also ich denke, dies ist eigentlich etwas das man die ganze Zeit benötigt, es müsste also irgendwie eine Standardfunktion dazu geben.

    Habt Ihr irgendwelche Ideen?

    Danke schon mal für alle Antworten

    H.Feiss

    PS: Google lieferte mir nichts brauchbare, nur 1000 Leute, die ihr Fenster maximieren wollen 🙂



  • H.Feiss schrieb:

    Habt Ihr irgendwelche Ideen?

    Wenn über die Funktion weiter nichts bekannt ist, haste keine Chance.

    float f(float x)
    {
       if(x==3.55643265642344543f) return 1;
       return -x*x;
    }
    

    Kein Außenstehender kann das Maximum bei 3.55643265642344543f erraten, außer er probiert echt alle float-x-Werte durch.

    Wenn was bekannt ist, zum Beispiel, daß f nur ein Polynom ist, kann es anders aussehen.



  • Danke für Deine Antwort. Ok, das klingt logisch. 🙂 Meine Funktion f ist stetig und differenzierbar!

    Also, wenn ich das Problem von Hand lösen müsste, würde ich folgendermassen vorgehen:

    - Funktion Ableiten und evtl. Hochpunkte ausfindig machen.
    - Die beiden Intervallgrenzen mit dem Wert des Hochpunkts vergleichen und der grösste Wert wäre dann derjenige, für welchen f maximal wäre.

    Ich bin mir auch nicht zu 100% sicher, ob dieses Verfahren wirklich alle Spezialfälle abdecken würde, aber für meinen Fall würde es genügen.

    Das Problem ist, dass ich nicht weiss, wie ich obiges Verfahren in C implementieren kann, zudem glaub ich, dass das wohl schon irgendwer gemacht hat.

    Also, mein Taschenrechner hat aufjedenfalls ne Funktion fMax, die genau macht was ich suche, sowas müsste doch auch irgend in einer C-Bibliothek zu finden sein.

    lg H.Feiss



  • H.Feiss schrieb:

    Danke für Deine Antwort. Ok, das klingt logisch. 🙂 Meine Funktion f ist stetig und differenzierbar!

    Also, wenn ich das Problem von Hand lösen müsste, würde ich folgendermassen vorgehen:

    - Funktion Ableiten und evtl. Hochpunkte ausfindig machen.
    - Die beiden Intervallgrenzen mit dem Wert des Hochpunkts vergleichen und der grösste Wert wäre dann derjenige, für welchen f maximal wäre.

    mathematisch sieht das Verfahren so richtig aus.

    Das Problem ist, dass ich nicht weiss, wie ich obiges Verfahren in C implementieren kann, zudem glaub ich, dass das wohl schon irgendwer gemacht hat.

    Das kommt ganz darauf an, in welcher Form du die zu berechnende Funktion vorliegen hast. Wenn du sie in irgendeiner symbolischen Form hast (z.B. Liste der Polynom-Koeffizienten), kannst du direkt ableiten und Nullstellen suchen. Wenn du nur eine Defintionen double f(double x); in der Hand hältst, wird es mit dem Ableiten schwieriger.



  • So was wird heute eher mit Mathematica und dgl. gemacht.

    Frag doch mal http://www.wolframalpha.com/



  • CStoll schrieb:

    Wenn du nur eine Defintionen double f(double x); in der Hand hältst, wird es mit dem Ableiten schwieriger.

    Ach naja. Wenn die Funktion einigermaßen gutmütig ist, kann man über einen Differenzenquotienten die Ableitung nähern. Darauf lässt sich dann das Newton-Verfahren aufbauen, und damit kann man lokale Maxima in endlicher Zeit finden.

    Natürlich darf man nicht zu viel erwarten - um lokale Maxima zu finden, wirft man eine Näherung der Ableitung in das Newton-Verfahren, welches davon dann erneut die Ableitung nähert. Mehr als vier bis fünf Stellen Genauigkeit wird man damit ohne GMP o.ä. in der Regel nicht garantieren können. Und kommt ja nicht auf die Idee, das mit cos(x*x) zu versuchen.



  • Nachtrag: Code dazu beispielsweise

    #include <stdio.h>
    #include <math.h>
    
    int epsilon_equal(double x, double y, double eps) {
      return fabs(x - y) < eps;
    }
    
    double numeric_derivative(double (*func)(double), double x, double eps) {
      return (func(x + eps) - func(x - eps)) / (2 * eps);
    }
    
    double numeric_second_derivative(double(*func)(double), double x, double eps_1, double eps_2) {
      return
        (numeric_derivative(func, x + eps_2, eps_1) - 
         numeric_derivative(func, x - eps_2, eps_1)) / (2 * eps_2);
    }
    
    int newton_iterate_derivative(double *result,
                                  double (*func)(double),
                                  double target,
                                  double start,
                                  unsigned max_try,
                                  double eps_result,
                                  double eps_deriv,
                                  double eps_deriv2) {
      double val_new, val_old = start;
      unsigned i;
    
      for(i = 0; i < max_try; ++i) {
        val_new = val_old - (numeric_derivative(func, val_old, eps_deriv) - target) / numeric_second_derivative(func, val_old, eps_deriv, eps_deriv2);
    
        if(epsilon_equal(val_new, val_old, eps_result)) {
          *result = val_new;
          return 0;
        }
    
        val_old = val_new;
      }
    
      return -1;
    }
    
    double my_function(double x) {
      return (x + 4) * (x + 2) * (x + 1) * (x - 1) * (x - 3) / 20 + 2;
    }
    
    int main() {
      double start_values[] = { -4.0, -2.0, 0.0, 2.0 };
      unsigned i;
    
      for(i = 0; i < 4; ++i) {
        double result;
    
        if(0 == newton_iterate_derivative(&result, my_function, 0.0, start_values[i], 2000, 1e-7, 1e-7, 1e-7)) {
          printf("Lokales Min-/Maximum: %f\n", result);
        } else {
          printf("Newton-Iteration mit Startwert %f konvergiert nicht (schnell genug)\n", start_values[i]);
        }
      }
    
      return 0;
    }
    

    Jetzt mal so hingekladdet (bzw. von einem Stück C++-Code, das ich hier noch rumliegen hatte, angepasst). Kennt jemand eine brauchbare C-Bibliothek, die Funktionsbinder hat? Ich bin ja von C++ her durch std::tr1::bind verwöhnt 😉 Das wäre hier echt praktisch gewesen.


Anmelden zum Antworten