Automatisches Differenzieren und Newton-Verfahren



  • Hallo zusammen,

    ich habe eine Klasse (s.u.), die automatisches Differenzieren ermöglicht und das Newton Verfahren zur Berechnung von Nullstellen implementiert hat. Nun möchte ich diese erweitern, sodass die erweiterte Klasse ein geordnetes Tripel (also nun 3 Komponenten, statt bisher nur 2) besitzt. Mit dieser erweiterten Klasse möchte ich dann konvexe Funktionen mit dem Newton-Verfahren minimieren.

    Der Code der bisherigen Klasse ist:

    #include <iostream>
    #include <cassert>
    #include <cmath>
    
    using namespace std;
    class autodiff
    {
    public:
        double M_value;
        double M_deriv;
    
        explicit autodiff (double value = 0.0, double deriv = 0.0)
        {
            M_value = value; M_deriv = deriv;
        }
        void print() const{
            cout << "Wert: " << M_value << ", Ableitung: " << M_deriv << "\n";
        }
    
        autodiff operator-() const
        {   return autodiff (-M_value, -M_deriv); }
    
        //autodiff operator+() const
        autodiff const& operator+() const
        {   cout << "Mein +! \n";
            return *this; }
    
        autodiff& operator= (autodiff const& U)
        {
            cout << "Meine Zusweisung! \n";
            M_value = U.M_value; M_deriv = U.M_deriv;
    
            return *this; }
    
    };
    
    inline autodiff id(double const& x)
    {    return autodiff(x, 1.0);}
    
    inline autodiff operator+ (autodiff const& U, autodiff const& V)
    {    return autodiff (U.M_value+V.M_value, U.M_deriv+V.M_deriv);}
    
    inline autodiff operator+ (autodiff const& U, double const c)
    {    return autodiff (U.M_value+c, U.M_deriv);}
    
    inline autodiff operator+ (double const c, autodiff const& U)
    {    return autodiff (U.M_value+c, U.M_deriv);}
    
    inline autodiff operator- (autodiff const& U, double const c)
    {    return autodiff (U.M_value-c, U.M_deriv);}
    
    inline autodiff operator- (double const c, autodiff const& U)
    {    return autodiff (-U.M_value+c, -U.M_deriv);}
    
    inline autodiff operator- (autodiff const& U, autodiff const& V)
    {    return autodiff (U.M_value-V.M_value, U.M_deriv-V.M_deriv);}
    
    inline autodiff operator* (autodiff const& U, autodiff const& V)
    {    return autodiff (U.M_value*V.M_value,
                         U.M_deriv*V.M_value + U.M_value*V.M_deriv);}
    
    inline autodiff operator* (autodiff const& U, double const c)
    {    return autodiff (U.M_value*c, U.M_deriv*c);}
    
    inline autodiff operator* (double const c, autodiff const& U)
    {    return autodiff (U.M_value*c, U.M_deriv*c);}
    
    inline autodiff operator/ (autodiff const& U, autodiff const& V)
    {
        assert (0 != V.M_value);
        double const ratio = U.M_value / V.M_value;
        return autodiff (ratio,
                         (U.M_deriv - ratio*V.M_deriv) / V.M_value );
    }
    
    inline autodiff sin (autodiff const& U)
    {
        return autodiff (sin(U.M_value), cos(U.M_value) * U.M_deriv);
    }
    
    inline autodiff cos (autodiff const& U)
    {
        return autodiff (cos(U.M_value), -sin(U.M_value) * U.M_deriv);
    }
    
    inline autodiff exp (autodiff const& U)
    {
        return autodiff (exp(U.M_value), exp(U.M_value) * U.M_deriv);
    }
    
    inline autodiff ln (autodiff const& U)
    {
        assert (0 < U.M_value);
        return autodiff (log(U.M_value), U.M_deriv / U.M_value);
    }
    inline autodiff F (double const x)
    {
        //return   ln (1.0+id(x)*id(x))
        //  - sin ( exp (id(3.0/2.0*x)*id(x)*id(x) - cos(id(x))) );
        return id(x)-cos(id(x))*cos(id(x));
        //  return cos(id(x)*id(x));
    }
    
    double Newton (double const x0, double const tol=1.0e-6)
    {
        int k=0;
        double x = x0;
        double d;
        do {
            autodiff y = F(x);
            cout << "  x: " << x << endl;
            cout << "  y: " << y.M_value << ", " << y.M_deriv << endl;
            d = -y.M_value / y.M_deriv;
            cout << "  d: " << d << "  (d/x = " << d/x << ")" << endl << endl;
            x += d;
            k++;
        } while (fabs (d/x) > tol);
    
        cout << k << " Schritte benoetigt." << endl;
    
        return x;
    }
    
    int main()
    {
        double const c = 1;
        autodiff exp0 = autodiff(1,1);
        exp0.print();
        autodiff cos0 = autodiff(1,0);
        cos0.print();
        //exp0 = 42;
        autodiff cosm0;
        cosm0 =-cos0;
        cosm0.print();
    
        autodiff myid = id(2);
    
        autodiff a;
        a = cosm0+cos0;
        a.print();
        a = a+1;a.print();
    
        a = cos0*2; a.print();
    
        cout << Newton (1, 1.0e-6);
    
    };
    

    Kann mir dort jemand weiterhelfen, wie ich das umsetzen kann?
    Danke für eure Hilfe!

    Edit durch Arcoth: Code-Tags



  • Hallo fenestil,

    Willkommen im Cpp-Forum!

    fenistil schrieb:

    ich habe eine Klasse (s.u.), die automatisches Differenzieren ermöglicht und das Newton Verfahren zur Berechnung von Nullstellen implementiert hat. Nun möchte ich diese erweitern, sodass die erweiterte Klasse ein geordnetes Tripel (also nun 3 Komponenten, statt bisher nur 2) besitzt. Mit dieser erweiterten Klasse möchte ich dann konvexe Funktionen mit dem Newton-Verfahren minimieren.

    Ich verstehe die Frage nicht ganz. Meinst Du 'konvexe Funktionen' oder 'komplexe Funktionen'?
    Deine Klasse autodiff hat zwei Member. Den Funktionswert M_value und die Ableitung M_deriv . Was verstehst Du in diesem Zusammenhang unter einem 'geordneten Tripel'?

    Gruß
    Werner



  • Das ist, was die Aufgabenstellung sagt.
    Also ich denke, mit dem Tripel ist gemeint, dass nun die zweite Ableitung hinzugefügt werden soll, was ja im Sachzusammenhang Sinn macht. Konvexe Funktionen haben ein Minimum und mit der zweiten Ableitung kann man ja die hinreichende Bedingung verifizieren.
    Also muss man ja für den neuen dritten Eintrag die Ableitung der Ableitung bilden, also nochmal die Ableitung der Ableitung irgendwo implementieren. Ich weiß nur nicht, wo bzw wie genau ich das nun einfügen soll...



  • Ich denke du differenzierst am besten näherungsweise.
    Also berechnest nur einen Differenzenquotient, mit einer kleinen Differenz.
    Dann brauchen die Funktionen auch nicht konvex sein oder so. Musst nur darauf achten, dass du an bestimmten Stellen eine Ableitung rausbekommst, wo es eigentlich keine gibt, da die Steigung von der einen Seite anders ist, als von der anderen.



  • Bengo schrieb:

    Ich denke du differenzierst am besten näherungsweise.
    Also berechnest nur einen Differenzenquotient, mit einer kleinen Differenz.

    Automatisches differenzieren ist aber exakt, also ist Differenzenquotient wahrscheinlich falsch...



  • Muss ich jetzt nicht einfach das Ergebnis noch einmal ableiten und fertig? Dann natürlich noch gucken wo die erste Ableitung 0 ist und dort ist dann das Minimum...
    Aber wie binde ich das nochmalige Differenzieren ein? Kann doch nicht so schwer sein oder? 😮



  • keine ahnung und habs noch nicht gemacht, aber warum nicht mal einfach rum probieren?

    inline autodiff id(double const& x)
    {    return autodiff(x, 1.0, 0.0);}
    
    inline autodiff operator+ (autodiff const& U, autodiff const& V)
    {    return autodiff (U.M_value+V.M_value, U.M_deriv+V.M_deriv, U.m_dd, V.M_dd);}
    
    inline autodiff sin (autodiff const& U)
    {//hoffentlich richtig zweilam abgelitten
        return autodiff (sin(U.M_value), cos(U.M_value) * U.M_deriv, cos(U.M_value)*U.mdd-U.M_deriv*U.M_deriv*sin(U.M_value));
    }
    


  • fenistil schrieb:

    Muss ich jetzt nicht einfach das Ergebnis noch einmal ableiten und fertig? Dann natürlich noch gucken wo die erste Ableitung 0 ist und dort ist dann das Minimum...
    Aber wie binde ich das nochmalige Differenzieren ein? Kann doch nicht so schwer sein oder? 😮

    Ist die Klasse so vorgegeben? Es ist nämlich eigentlich ziemlich ungünstig das direkt auszurechen, besser wäre erstmal den Baum aufzubauen. Dann kannst du nämlich beliebig oft hintereinander ableiten, ohne jede Ableitung wieder explizit implementieren zu müssen (was nämlich sehr schnell sehr mühsam wird).



  • happystudent schrieb:

    Bengo schrieb:

    Ich denke du differenzierst am besten näherungsweise.
    Also berechnest nur einen Differenzenquotient, mit einer kleinen Differenz.

    Automatisches differenzieren ist aber exakt, also ist Differenzenquotient wahrscheinlich falsch...

    Wenn du damit sowieso Newton machst, ist das ja nicht so ausschlaggebend, es sollte sich trotzdem an die Nullstelle annäheren.



  • Bengo schrieb:

    Wenn du damit sowieso Newton machst, ist das ja nicht so ausschlaggebend, es sollte sich trotzdem an die Nullstelle annäheren.

    Kann sein (wobei auch das von der Funktion abhängt).

    Wenn aber die Aufgabe automatisches Differenzieren ist, und man dann stattdessen einfach (f(x + h) - f(x))/h rechnet, ist das (vermutlich) eher eine Themaverfehlung und der Prof. dementsprechend enttäuscht.



  • Vielen Dank, ihr habt mir sehr geholfen, ich habe die Lösung nun hinbekommen!!


Log in to reply