Που "χτυπάει" το πρόγραμμά μου?

Διδάσκοντες: Α. Αραμπατζής, Λέκτορας

Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό Stokos » 31 Μαρ 2009, 16:07

Κώδικας: Επιλογή όλων
#include <iostream.h>
#include <math.h>

void main(){
   void Newton2d(double x0, double y0, int max_loops, double tol);
   Newton2d( 13,14,100,pow(10,-6) );
}

inline double f(double x,double y) {
   double sin(double);
   return 1-x-y*sin(3.14159*x/2);
}

inline double f_x(double x,double y){
   double cos(double);
   return -1-y*cos(3.14159*x/2)*3.14159/2;
}

inline double f_y(double x,double y){
   double sin(double);
   return -sin(3.14159*x/2);
}

inline double g(double x,double y){
   double exp(double),cos(double);
   return exp(-y)+10*cos(3.14159*x)-2;
}

inline double g_x(double x,double y){
   double sin(double);
   return -31.4159*sin(3.14159*x);
}

inline double g_y(double x,double y){
   double exp(double);
   return -exp(-y);
}

inline double dbl_abs(double num){
   return num>0?num:-num;
}

void Newton2d(double x0, double y0, int max_loops, double tol) {
   
   //Variable Declaration
   double f(double,double),g(double,double),
   f_x(double,double),g_x(double,double),
   f_y(double,double),g_y(double,double),
   dbl_abs(double),x,y;
   int i=1;

   //main function
   while(i<=max_loops){

      x = x0 - ( f(x0,y0)*g_y(x0,y0) - g(x0,y0)*f_y(x0,y0) )/( f_x(x0,y0)*g_y(x0,y0) - g_x(x0,y0)*f_y(x0,y0) );
      y = y0 - ( g(x0,y0)*f_x(x0,y0) - f(x0,y0)*g_x(x0,y0) )/( f_x(x0,y0)*g_y(x0,y0) - g_x(x0,y0)*f_y(x0,y0) );
      
      //Test-------------------------------------------------
      cout << "Loop "<< i << ":(" << x << "," << y << ").\n";
      //-----------------------------------------------------

      if( dbl_abs(x-x0) < tol && dbl_abs(y-y0) < tol ){
         cout << "The solution is: (" << x <<","<< y <<").\n";
         return;
      }

      ++i;
      x0=x;
      y0=y;
   }
   cout << "The method has failed after " << max_loops << " loops.\n";
}


Χτυπάει στο 3ο loop (μάλλον στο δεκαδικό μέρος των αριθμών) αν και έχω ορίσει τα πάντα ως double...
Ο αλγόριθμός είναι 100% σωστός, είναι κάποιο τεχνικό πρόβλημα της C++, κάποιο overflow μάλλον... :-\

Εdit: Αγνοήστε τις συναρτήσεις f,g προκύπτουν από την εκφώνηση του προβλήματος και δε δημιουργούν αυτές το πρόβλημα (εξάλλου έχουν πεδίο ορισμού το R).
Stokos
 

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό James » 31 Μαρ 2009, 16:48

http://www.cplusplus.com/reference/clib ... h/sin.html

EDIT: Μιας και το εξαντλήσαμε το θέμα (και καταλήξαμε ότι φταίει η αρχική τιμή) ας πάμε λίγο να ηρεμήσουμε μετά από τόσο πονοκέφαλο ...
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό Stokos » 31 Μαρ 2009, 17:35

Μα σε rad τα έχω ;)

EDIT: Τελικά είναι ανώμαλη η συνάρτηση και δε δουλεύει η μέθοδος για όλα τα σημεία εκκίνησης... Μια χαρά δουλεύει το πρόγραμμα. (Thnx στο James που το ανακάλυψε :P )

Τελική μορφή (αλλαγές στο Interface μόνο):
Κώδικας: Επιλογή όλων
#include <iostream.h>
#include <math.h>
#define pi 3.14159

void main(){
   //variable declaration
   void Newton2d(double x0, double y0, int max_loops, double tol);
   double sin(double),f(double,double),g(double,double),x,y;
   char choice='y';
   //main program
   while(choice=='y' || choice=='Y'){
      cout << "Input x: "; cin >> x;
      cout << "Input y: "; cin >> y;
      Newton2d( x , y , 100 , pow(10,-6) );
      cout << "Try a different starting point? (y/n): ";
      cin >> choice;
   }
}

inline double f(double x,double y) {
   double sin(double);
   return 1-x-y*sin(pi*x/2);
}

inline double f_x(double x,double y){
   double cos(double);
   return -1-y*cos(pi*x/2)*pi/2;
}

inline double f_y(double x,double y){
   double sin(double);
   return -sin(pi*x/2);
}

inline double g(double x,double y){
   double exp(double),cos(double);
   return exp(-y)+10*cos(pi*x)-2;
}

inline double g_x(double x,double y){
   double sin(double);
   return -31.4159*sin(pi*x);
}

inline double g_y(double x,double y){
   double exp(double);
   return -exp(-y);
}

inline double dbl_abs(double num){
   return num>0?num:-num;
}

void Newton2d(double x0, double y0, int max_loops, double tol) {
   
   //Variable Declaration
   double f(double,double),g(double,double),
   f_x(double,double),g_x(double,double),
   f_y(double,double),g_y(double,double),
   dbl_abs(double),x,y;
   int i=1;

   //main function
   while(i<=max_loops){

      x = x0 - ( f(x0,y0)*g_y(x0,y0) - g(x0,y0)*f_y(x0,y0) )/( f_x(x0,y0)*g_y(x0,y0) - g_x(x0,y0)*f_y(x0,y0) );
      y = y0 - ( g(x0,y0)*f_x(x0,y0) - f(x0,y0)*g_x(x0,y0) )/( f_x(x0,y0)*g_y(x0,y0) - g_x(x0,y0)*f_y(x0,y0) );
      
      cout << "Loop "<< i << ":(" << x << "," << y << ") | Difference: " << dbl_abs(x-x0) << " and " << dbl_abs(y-y0)  <<"\n";
      
      if( dbl_abs(x-x0) < tol && dbl_abs(y-y0) < tol ){
         cout << "\nThe solution is: (" << x <<","<< y <<")\n\n";
         cout << "f(" << x << "," << y << ")=" << f(x,y) << "\n";
         cout << "g(" << x << "," << y << ")=" << g(x,y) << "\n\n";
         return;
      }

      ++i;
      x0=x;
      y0=y;
   }
   cout << "The method has failed after " << max_loops << " loops.\n";
}
Stokos
 

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό nuovo » 01 Απρ 2009, 01:20

Δεν έτρεξα το πρόγραμμα... δεν είδα τι ακριβώς γίνεται απλά δίνω την παρακάτω ιδέα ελλείψει χρόνου:
H μέθοδος Newton είναι γνωστό ότι δεν συγκλίνει πάντα και ότι πρακτικά υπάρχει πρόβλημα με την επιλογή του αρχικού σημείου.
http://en.wikipedia.org/wiki/Newton's_method, http://en.wikipedia.org/wiki/Newton's_method_in_optimization.
Έχει ένα κριτήριο για καθολική σύγκλιση στην 1D περίπτωση η wikipedia --> "In practice these results are local and the neighborhood of convergence are not known a priori, but there are also some results on global convergence, for instance, given a right neighborhood $U_{+}$ of $\alpha$, if $f$ is twice differentiable in $U_{+}$and if $f^{\prime} \neq 0, f f^{\prime \prime}> 0$, in $U_{+}$, then, for each $x_{0}$ in $U_{+}$ the sequence $x_{k}$ is monotonically decreasing to $\alpha$".

Υπάρχουν αντίστοιχα κριτήρια και για περισσότερες διαστάσεις... τώρα δεν βρίσκω κάτι στο google, αλλά σε βιβλία nonlinear optimization υπάρχουν αναλυτικά αυτά από ότι θυμάμαι.
nuovo
Jr. Member
 
Δημοσιεύσεις: 65
Εγγραφή: 17 Οκτ 2008, 09:49

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό Stokos » 01 Απρ 2009, 09:26

nuovo έγραψε:Δεν έτρεξα το πρόγραμμα... δεν είδα τι ακριβώς γίνεται απλά δίνω την παρακάτω ιδέα ελλείψει χρόνου:
H μέθοδος Newton είναι γνωστό ότι δεν συγκλίνει πάντα και ότι πρακτικά υπάρχει πρόβλημα με την επιλογή του αρχικού σημείου.
http://en.wikipedia.org/wiki/Newton's_method, http://en.wikipedia.org/wiki/Newton's_method_in_optimization.
Έχει ένα κριτήριο για καθολική σύγκλιση στην 1D περίπτωση η wikipedia --> "In practice these results are local and the neighborhood of convergence are not known a priori, but there are also some results on global convergence, for instance, given a right neighborhood $U_{+}$ of $\alpha$, if $f$ is twice differentiable in $U_{+}$and if $f^{\prime} \neq 0, f f^{\prime \prime}> 0$, in $U_{+}$, then, for each $x_{0}$ in $U_{+}$ the sequence $x_{k}$ is monotonically decreasing to $\alpha$".

Υπάρχουν αντίστοιχα κριτήρια και για περισσότερες διαστάσεις... τώρα δεν βρίσκω κάτι στο google, αλλά σε βιβλία nonlinear optimization υπάρχουν αναλυτικά αυτά από ότι θυμάμαι.


Ναι για συναρτήσεις 1D το ξέρω αυτό, για 2D δε βρίσκω τίποτα στο internet για το κριτήριο σύγκλισης... Προσπάθησα να πάω με τη γραφική παράσταση των συναρτήσεων (τις έκανα με Matlab) και να πάρω σημεία εκκίνησης κοντά στις ρίζες αλλά δε δούλευε πάντα (το σύστημα έχει πολλαπλές αλλά πεπερασμένες ρίζες)... Tο αν θα συγκλίνει ή όχι εξαρτάται από το αρχικό σημείο, αλλά ακόμα και μερικές φορές που συγκλίνει έχει κάτι απότομες αλλαγές (όχι πάντα) που με προβληματίζουν αρκετά. Βέβαια αν τελικά συγκλίνει για τη λύση (x,y) που βρίσκω ισχύει f(x,y)=g(x,y)= περίπου 0, οπότε παρ όλη την ανώμαλη πορεία της μεθόδου καταλήγω σε σωστό αποτέλεσμα!
Stokos
 

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό nuovo » 01 Απρ 2009, 13:23

Εδώ έχει ένα κριτήριο σύγκλισης για πολυμεταβλητή συνάρτηση για την Newton.
nuovo
Jr. Member
 
Δημοσιεύσεις: 65
Εγγραφή: 17 Οκτ 2008, 09:49

Re: Που "χτυπάει" το πρόγραμμά μου?

Δημοσίευσηαπό Stokos » 01 Απρ 2009, 13:46

nuovo έγραψε:Εδώ έχει ένα κριτήριο σύγκλισης για πολυμεταβλητή συνάρτηση για την Newton.

Ευχαριστώ ;)
Stokos
 

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης