Send a PR on GitHub

progintro @ dit

Newton - Raphson method

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

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

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

  1. Έλεγχο εισόδου.
  2. Τον υπολογισμό της $f(x_0)$.
  3. Τον υπολογισμό της $f’(x_0)$.
  4. Τον υπολογισμό της $x_1 = x_0 - \frac{f(x_0)}{f’(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’(x_0)$

    Αυτή η συνάρτηση είναι η παράγωγος της $f(x)$ για το $x_0$ που επεξεργάζεται το πρόγραμμα κάθε χρονική στιγμή. Η μορφή της λοιπόν, από κανόνες παραγώγισης, θα είναι: \(f'(x_0) = a_1 +2 a_2 x_0 +3 a_3 x_0 ^ {2} +4 a_4 x_0 ^ {3} +5 a_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’(x_0)}$

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

    x  =  x0  -  fx0/dfx0;

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

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

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

Για την προσέγγιση της λύσης του πολυωνύμου θα πρέπει επαναληπτικά να υπολογίζουμε την $x_1 = x_0 - \frac{f(x_0)}{f’(x_0)}$ όπου κάθε φορά θα περνάμε ως καινούργιο $x_0$ το προηγούμενο $x_1$. Με αυτό τον τρόπο θα υλοποιούμε την $x_{n+1} = x_n - \frac{f(x_n)}{f’(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’(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” και θα τερματίζει.