progintro @ dit

Newton - Raphson method

Η μέθοδος Newton-Raphson είναι μία αναδρομική διαδικασία που μας επιτρέπει να προσεγγίσουμε με πολύ μικρό σφάλμα μία ρίζα μιας πολυωνυμικής συνάρτησης 5ου βαθμού αν έχουμε μία πραγματική συνάρτηση $f(x)$, την παράγωγό της $f^{\prime }(x)$ και ένα τυχαίο $x_0$ με τα οποία μπορούμε να βρουμε μια καλύτερη προσέγγιση της ρίζα της $f(x)$, $x_1$. Το $x_1$ δίνεται κάθε φορά από τον τύπο: $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$και αναδρομικά: $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

Λογική προγράμματος

Το πρόγραμμα καλείται να επιλύσει 5 βασικά υποπροβλήματα:

1. Έλεγχο εισόδου.
2. Τον υπολογισμό της $f(x_0)$.
3. Τον υπολογισμό της $f^{\prime }(x_0)$.
4. Τον υπολογισμό της $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$.
5. Έλεγχος εξόδου.

   Έλεγχος εισόδου:

   Το πρόγραμμα θα πρέπει να δέχεται αυστηρά 7 ορίσματα τα οποία θα είναι οι συντελεστές του πολυωνύμου και το $x_0$. Αυτό θα το ελέγχουμε με την χρήση του ορίσματος της main(), int argc. Καθώς δεχόμαστε και ως όρισμα το όνομα του προγράμματος που εκτελούμε ο έλεγχος θα πρέπει να γίνει για 8 ορίσματα:

   if(argc  !=  8) {
   return  1;
   }
   

   Υπολογισμός $f(x_0)$

   Για την υλοποίηση του προγράμματος θα πρέπει να υπολογίζουμε κάθε φορά την $f(x_0)$. Αυτό επιτυγχάνεται με τη συνάρτηση:

   long  double  f(long  double  x0, double  FACT[6])
   {
   return (FACT[0] +  FACT[1] *  x0  +  FACT[2] *  pow(x0, 2) +  FACT[3] *  pow(x0, 3) +  FACT[4] *  	pow(x0, 4) +  FACT[5] *  pow(x0, 5)); //Υπολογισμός f(x0).
   }
   

   Η συνάρτηση δέχεται ως όρισμα έναν δεκαδικό $x_0$ καθώς και τον πίνακα με τους συντελεστές του πολυωνύμου που έχει δωθεί πιο πριν ως είσοδος από τον χρήστη. Για τον υπολογισμό της $f(x_0)$ προσθέτει τα γινόμενα των συντελεστών με τις αντίστοιχες δυνάμεις του $x_0$. Υλοποιεί δηλαδή την συνάρτηση: $f(x_0)=a_0+a_1{x}_0+a_2{x}_0^2+a_3{x}_0^3+a_4{x}_0^4+a_5{x}_0^5$

   Η συνάρτηση double pow(double, double)

   Η συνάρτηση αυτή περιέχεται στην βιβλιοθήκη math.h και λειτουργεί ως εξής:

   • Η συνάρτηση δέχεται δύο ορίσματα ($x$, $y$). Το όρισμα $x$ είναι ο αριθμός που θέλουμε να υψώσουμε σε κάποια δύναμη και ο αριθμός $y$ είναι η δύναμη στην οποία θέλουμε να υψώσουμε.
   • Ύστερα από καποιους υπολογισμούς η συνάρτηση επιστρέφει τον αριθμό που δώσαμε υψωμένο στην δύναμη που δώσαμε.

   Η συνάρτηση $f^{\prime }(x_0)$

   Αυτή η συνάρτηση είναι η παράγωγος της $f(x)$ για το $x_0$ που επεξεργάζεται το πρόγραμμα κάθε χρονική στιγμή. Η μορφή της λοιπόν, από κανόνες παραγώγισης, θα είναι: $f^{\prime }(x_0)=a_1+2a_2{x}_0+3a_3{x}_0^2+4a_4{x}_0^3+5a_5{x}_0^4$ και υλοποιείται από την συνάρτηση:

   long  double  df(long  double  x0, double  FACT[6])
   {
   return (FACT[1] +  2  *  FACT[2] *  x0  +  3  *  FACT[3] *  pow(x0, 2) +  4  *  FACT[4] *  pow(x0, 3) +  5  *  FACT[5] *  pow(x0, 4)); //Υπολογισμός f'(x0).
   }
   

   Υπολογισμός της $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$

   Ο πολογισμός αυτός υλοποιείται πολύ εύκολα με την εντολή εκχώρησης:

   x  =  x0  -  fx0/dfx0;
   

   Έλεγχοι εξόδου

   Το πρόγραμμα θέλουμε να τερματίζει κανονικά σε 3 περιπτώσεις:

   1. Έξοδος λόγω απόκλεισης.
   2. Έξοδος με σωστό αποτέλεσμα.
   3. Έξοδος λόγω αδυναμίας προσέγγισης σε 1000 επαναλήψεις.

Για την προσέγγιση της λύσης του πολυωνύμου θα πρέπει επαναληπτικά να υπολογίζουμε την $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$ όπου κάθε φορά θα περνάμε ως καινούργιο $x_0$ το προηγούμενο $x_1$. Με αυτό τον τρόπο θα υλοποιούμε την $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$. Αυτό επιτυγχάνεται με τον παρακάτω κώδικα:

for(int  i  =  0; i  <  1000; i++){ //Επανάληψη υπολογισμού ρίζας που εκτελείται το πολύ για 1000 επαναλήψεις.
	fx0  =  f(x0, FACT); //Υπολογισμός f(x0).
	dfx0  =  df(x0, FACT); //Υπολογισμός f'(x0).
	
	x  =  x0  -  fx0/dfx0; //Υπολογισμός του τύπου προσέγγισης της ρίζας.
	
	if(isnan(x)) { //Έλεγχος αν το αποτέλεσμα του υπολογισμού ήταν nan.
		printf("nan\n");
		return  0;
	}
	if (fabsl(x  -  x0) <  pow(10, -6)) { //Έλεγχος αν η τρέχουσα προσέγγιση είναι 	αρκετά ακριβής. Αν είναι τότε εκτυπώνεται και το πρόγραμμα τερματίζει.
		printf("%.2Lf\n", x);
		return  0;
		}
	x0  =  x; //Αποθήκευση της τρέχουσας προσέγγισης της ρίζας στην μεταβλητή x0 για χρήση στην επόμενη επανάληψη.
}
printf("incomplete\n"); //Αυτή η εντολή εκτελείται μόνο αν η επανάληψη έχει εκτελεστεί 1000 φορές και δεν έχει προκύψει αποδεκτή προσέγγιση ή δεν πάει να γίνει διαίρεση με το 0.
return  0;
}

</br>

1. Έξοδος λόγω απόκλησης

Αν οποιαδήποτε στιγμή κατά τον υπολογισμό της ρίζας προκύψει απόκλειση, δηλαδή το αποτέλεσμα της $x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$ δώσει αποτέλεσμα NAN, τότε το πρόγραμμα θα εκτυπώνει “nan” και θα τερματίζει αμέσως. Αυτό γίνεται με τον παρακάτω έλεγχο:

if(isnan(x)) { //Έλεγχος αν το αποτέλεσμα του υπολογισμού ήταν nan.
		printf("nan\n");
		return  0;
	}

2. Έξοδος με σωστό αποτέλεσμα

θεωρούμε ότι το πρόγραμμα προσέγγισε αρκετά την λύση της συνάρτησης όταν η διαφορά μεταξύ του $x_1$ και του $x_0$ είναι σχεδόν μηδενική ( $|x_1-x_0|<{10}^{-6}$ ). Σε αυτή την περίπτωση το πρόγαμμα θα πρέπει να εκτυπώνει την λύση και να τερματίζει αμέσως. Αυτό γίνεται με την παρακάτω δομή:

if (fabsl(x  -  x0) <  pow(10, -6)) { //Έλεγχος αν η τρέχουσα προσέγγιση είναι αρκετά ακριβής. Αν είναι τότε εκτυπώνεται και το πρόγραμμα τερματίζει.
	printf("%.2Lf\n", x);
	return  0;
}

3. Έξοδος λόγω αδυναμίας προσέγγισης σε 1000 επαναλήψεις.

Σε περίπτωση που το πρόγραμμα δεν έχει βρεθεί σε κάποια από τις δύο καταστάσεις εξόδου που αναφέρονται παραπάνω μετά από 1000 επαναλήψεις τότε η δομή επανάληψης θα τερματίζει. Έτσι το πρόγραμμα θα συνεχίζει ακολουθιακά εκτυπώνοντας “incomplete” και θα τερματίζει.