Παράγωγοι στην C

[johnykim]

Παιδιά καλησπέρα.

 

Γνωρίζετε μήπως πως μπορεί να λυθεί μια παράγωγος από μια συνάρτηση;

 

Για παράδειγμα η παράγωγος της f(x)=5x+2.

 

Υπάρχει κάποια συνάρτηση, ή μπορεί να βρεθεί και με αλγόριθμο;

[Dr.Fuzzy]

Πάρε μια ιδέα,

 

Από τον ορισμό της παραγώγου:

 

df(x)/dt=lim(h->0)[(f(x+h)-f(x))/h]

 

οπότε ας πάρουμε για παράδειγμα την f(x)=x^2,

 

>
double f(double x)
{
    return pow(x,2);
}

double dfdt(double x)
{
  double h=0.000001;
  return (f(x+h)-f(x))/h;
}

 

Είναι προφανές ότι όσο πιο μικρό h (h->0) τόσο καλύτερη η προσέγγιση σου σε σύγκριση με την αναλυτική λύση.

[V.I.Smirnov]

H έκφραση "να λυθεί μια παράγωγος από μια συνάρτηση" δεν έχει νόημα. Προφανώς εννοείς να υπολογιστεί.

 

Αριθμητικός υπολογισμός παραγώγων είναι σχετικά εύκολο να γίνει.

Οι συναρτήσεις προσεγγίζονται με πεπερασμένες διαφορές που προέρχονται από ανάπτυξη της συνάρτησης σε σειρά Taylor.

Μια συνάρτηση f(x) μπορεί να προσεγγιστεί σε πρώτη τάξη από το ανάπτυγμά της κατά Taylor ως

f(x+h) = f(x) + h f'(x) + h**2 f''(ξ)/2!

όπου το ξ ανήκει στο (x,x+h). H παραπάνω σχέση λύνεται ως προς f'(x) και δίνει

f'(x) = ( f(x+h) - f(x) )/h - h**2 f''(ξ)/2

Για βήμα h αρκούντως μικρό ο όρος h**2 f''(ξ)/2 μπορεί να αγνοηθεί και η παράγωγος f'(x) προσεγγίζεται ως

f'(x) = ( f(x+h) - f(x) )/h , h>0.

Αυτή είναι η λεγόμενη σχέση διαφοράς προς τα εμπρός (forward difference formula).

Όμοια είναι και η σχέση διαφοράς προς τα πίσω (backward difference formula)

f'(x) = ( f(x) - f(x-h) )/h , h>0.

 

Σε αμφότερες τις δυο παραπάνω σχέσεις χρησιμοποιούνται μόνον δυο τιμές της συνάρτησης : στο x και στο x+h ή x-h.

To σφάλμα είναι τάξης Ο(h), δηλ. σχετικά μεγάλο.

Εξάλλου, μπορούν να διατυπωθούν σχέσεις χρησιμοποιώντας τιμές που προσαρμόζονται (fitting) με ένα πολυώνυμο παρεμβολής Lagrance (Lagrance interpolating polynomial).

Με αυτόν τον τρόπο λαμβάνονται σχέσεις ανώτερης τάξης που είναι σημαντικά ακριβέστερες.

Πχ. oι παρακάτω είναι Ο(h**2), δηλ. δεύτερης τάξης στο σφάλμα.

- σχέση forward difference (απαιτεί τρεις τιμές της συνάρτησης) :

f'(x) = (1/h) ( -3/2 f(x) + 2 f(x+h) - 1/2 f(x+2h) ) + h**2 f'''(ξ)/3

- σχέση midpoint difference :

f'(x) = (1/h) ( -1/2 f(x-h) + 1/2 f(x+h) ) + h**2 f'''(ξ)/6

H σχέση αυτή πλεονεκτεί διότι

- απαιτεί δυο τιμές της συνάρτησης αντί για τρεις, δηλ. υπολογιστικά είναι οικονομική όπως η προσέγγιση πρώτης τάξης ενώ ταυτόχρονα έχει ακρίβεια Ο(h**2), δηλ. δεύτερης τάξης

- είναι περίπου δυο φορές ακριβέστερη από την forward difference δεύτερης τάξης ( παρατήρησε ότι η εκείνη έχει (h**2)/3 ενώ αυτή έχει (h**2)/6 )

Οπότε αν θέλεις μεγαλύτερη ακρίβεια πρέπει να χρησιμοποιείς αυτήν.

Σχέσεις πέντε σημείων έχουν σφάλμα O(h**4) και είναι εξαιρετικά ακριβείς αλλά χρησιμοποιούνται σπάνια.

 

Σχέσεις για τις δεύτερες παραγώγους βρίσκονται με τον ίδιο τρόπο. Πχ. αναπτύσσοντας κατά Taylor μέχρι 3ης τάξης όρους τις f(x+h) και f(x-h) λαμβάνεται τελικά

f''(x) = (1/h**2) ( f(x-h) - 2f(x) + f(x+h) ) - h**2 f''''(ξ)/12

 

Oι σχέσεις διακριτοποίησης δίνονται στα περισσότερα βιβλία Αριθμητικής Ανάλυσης.

Το Numerical Recipes μάλιστα θυμάμαι ότι κάνει κάποιες ενδιαφέρουσες παρατηρήσεις στον προγραμματισμό των παραπάνω σχέσων.

 

Η πραγματική δυσκολία έγκειται στο να φτιαχτεί ρουτίνα που υπολογίζει ΑΝΑΛΥΤΙΚΑ την παράγωγο μιας συνάρτησης.

Αν ρωτάς αυτό, δεν πρόκειται να εξηγήσω πως μπορεί να γίνει.

Γίνεται πάντως και έκανα κάποτε τέτοιο πρόγραμμα στην C++ αλλά δεν σκοπεύω να εξηγήσω πώς, ούτε και να δώσω τον κώδικα...

[johnykim]

Ευχαριστώ και τους δυο για τις απαντήσεις.Δυστυχώς V.I.Smirnov, οι συναρήσεις με μπερδεύουν αρκετά(κάτι h**2 f''(ξ)/2, δεν τα κατάλαβα καθόλου)

 

 

Κάτι προσπάθειες:

>
#include <stdio.h>
#include <stdlib.h>

main()
{
 
float fx,fxx,x;
float h;

h=0.000001;
fx=10*x+2;

fxx= ((fx+h)+(fx))/h;


printf("f'(x)=%f",fxx);

printf("\n");
 
system("PAUSE");	
return 0;
}

(Το αποτέλεσμα βέβαια βγαίνει ό,τι να ναι..)

 

Δεν θέλω κάτι περίπλοκο.Μια βασική μεταβλητή(fxx) όπου θα κάνει τις πράξεις και θα εμφανίζω αργότερα το αποτέλεσμα θα μου έκανε.

[C6WGMN]

Η πραγματική δυσκολία έγκειται στο να φτιαχτεί ρουτίνα που υπολογίζει ΑΝΑΛΥΤΙΚΑ την παράγωγο μιας συνάρτησης.

Αν ρωτάς αυτό, δεν πρόκειται να εξηγήσω πως μπορεί να γίνει.

Γίνεται πάντως και έκανα κάποτε τέτοιο πρόγραμμα στην C++ αλλά δεν σκοπεύω να εξηγήσω πώς, ούτε και να δώσω τον κώδικα...

 

Κοτσάνες. Το πρόβλημα είναι άλυτο και απλούστατο.

[V.I.Smirnov]

Κοτσάνες. Το πρόβλημα είναι άλυτο και απλούστατο.

 

Φανερά, "κοτσάνα" είναι αυτό που είπες...

 

 

 

@johnykim

 

Tι σε μπερδεύει ;

Mάλλον δεν ξέρεις μαθηματικά.

 

Oι όροι της μορφής h**2 f''(ξ)/2 κλπ. είναι τα υπόλοιπα στο ανάπτυγμα Taylor.

To ανάπτυγμα μιας συνάρτησης σε δυναμοσειρά Taylor έχει άπειρους όρους.

Για την προσέγγιση της συνάρτησης παίρνουμε όσους όρους θέλουμε.

Οι υπόλοιποι που παραλείπονται (άπειροι στο πλήθος) περιλαμβάνονται συνοπτικά στον όρο

h**2 f''(ξ)/2 (είναι το λεγόμενο υπόλοιπο Lagrange ή Cauchy).

Προφανώς όσο μεγαλύτερο είναι αυτό το υπόλοιπο τόσο χειρότερη είναι η προσέγγιση της συνάρτησης από την δυναμοσειρά.

Στις προσεγγιστικές σχέσεις που τελικά χρησιμοποιούμε οι όροι αυτοί αγνοούνται.

Είναι σα να θες να προσεγγίσεις την f με την g .

H αληθής σχέση είναι g(x) = f(x) + k όπου k η διαφορά τους.

Η προσεγγιστική είναι g(x) = f(x).

Aντί της f(x), χρησιμοποιείς την προσέγγισή της, g(x), και το k το ξεχνάς, είναι το σφάλμα της προσέγγισης.

 

Και μια προειδοποίηση.

Με το να μειώνεις το βήμα h, δεν κερδίζεις αναγκαστικά σε ακρίβεια όπως απλοϊκά νομίζουν πολλοί.

Και καταρχήν, γιατί δεν χρησιμοποιείς τη σχέση f'(x) = ( f(x+h) - f(x-h) ) / (2h) που σου έδωσα ;

Eίναι πολύ ακριβέστερη διότι έχει σφάλμα (το k που λέγαμε παραπάνω) O(h**2) δηλ. πολύ μικρότερο από το O(h) που έχει αυτή που εφαρμόζεις τώρα.

 

Αν ενδιαφέρεσαι να κάνεις δουλειά στα σοβαρά, δες την παράγρ. 5.7 του Numerical Recipes in C (ή C++).

Εξηγεί γιατί η μείωση του h δεν αυξάνει αναγκαστικά την ακρίβεια και έχει μια καλή ρουτίνα που κάνει αριθμητικό υπολογισμό παραγώγων.

Χρησιμοποιεί κύρια την σχέση που σου δίνω κι εγώ, θα σε δυσκολέψει όμως διότι κάνει κι άλλα κόλπα.

Η ρουτίνα αυτή "αντιλαμβάνεται" το σχήμα της συνάρτησης και μεταβάλλει κατάλληλα το βήμα h εκεί όπου η συνάρτηση έχει απότομες μεταβολές.

[C6WGMN]

Φανερά, "κοτσάνα" είναι αυτό που είπες...

Γιατί? Θες να συζητήσουμε σε μαθηματικό ή προγραμματιστικό επίπεδο? Υπάρχει νόμος που να καλύπτει όλες τις παραγώγους (και ολοκληρώματα)? Προγράμματα που βρίσκουν παραγώγους και ολοκληρώματα είναι ή δεν είναι απλά pattern matchers?

[V.I.Smirnov]

Τι σημαίνει "άλυτο και απλούστατο" ;

Αντιφατικό δεν είναι ; Συνήθως τα προβλήματα που είναι απλά δεν είναι άλυτα.

Εκτός αν εννοείς ότι μπορείς να δεις το ζήτημα και από τις δυο πλευρές οπότε παρανόησα και ανακαλώ.

Όσο για την δυσκολία, προφανώς είναι πολύ πιο δύσκολο πρόβλημα ο συμβολικός υπολογισμός από τον αριθμητικό

διότι απαιτεί γνώσεις δομών δεδομένων. Ενώ ο αριθμητικός είναι κατά βάσην απλή εφαρμογή τύπων.

 

Τέλος, αν έχεις γνώση επί του συμβολικού υπολογισμού πες μου που μπορώ να ψάξω, έτσι για να ξέρω τι γίνεται.

Χρόνια πριν, είχα λύσει το πρόβλημα αυτό γράφοντας ένα parser στην C++ .

Δεν το είχα κάνει με pattern matchers - τότε είχα μακάρια άγνοια τι είναι αυτό (εξάλλου δεν είμαι προγραμματιστής).

Χρησιμοποίησα τον κανόνα της αλυσίδας που είναι βασική σχέση παραγώγισης σε συνδυασμό με τις σχέσεις των στοιχειωδών παραγώγων.

Η ιδέα ήταν από το βιβλίο "C++ Scientific Programming", Willey.

 

Σε ότι αφορά τα μαθηματικά, ναι, ο κανόνας της αλυσίδας φορμαλιστικά καλύπτει όλες τις συναρτήσεις/παραγώγους και εφαρμόζεται πάντα.

Θυμήσου τι κάνεις όταν παραγωγίζεις : χρησιμοποιείς τις στοιχειώδεις παραγώγους και τον κανόνα της αλυσίδας. Πάντα. Από εκεί ξεκίνησα λοιπόν.

Ενώ αντίθετα, σχέση ολοκλήρωσης που φορμαλιστικά να εφαρμόζεται πάντα, όχι, δεν υπάρχει.

Γι αυτό άλλωστε και η ολοκλήρωση είναι πολύ πιο δύσκολη. Χειροκίνητα, δουλεύεις ανάλογα με την μορφή του ολοκληρώματος.

 

Και τώρα που το θυμάμαι, parser είχα γράψει και στην fortran αλλά εκείνο δεν υπολόγιζε συμβολικά παραγώγους...

[Dr.Fuzzy]

...Με το να μειώνεις το βήμα h, δεν κερδίζεις αναγκαστικά σε ακρίβεια όπως απλοϊκά νομίζουν πολλοί.

 

Ναι αγαπητέ το γνωρίζουμε αυτό. Ο άνθρωπος όμως ζήτησε ένα απλό παράδειγμα (δεν νομίζω να θέλει να το πάει για δημοσίευση!) και κρίνοντας από το "στυλ" του ποστ, του έδωσα μια "απλοϊκή" αποδεκτή λύση.

 

Θέλω να πω ότι όποιος ασχολείται με μαθηματικά γνωρίζει όλα αυτά που αναφέρεις στο ποστ σου, απλά πολλές φορές χρειάζεται να "ζυγίσουμε" τον "ακροατή" μας και να προσαρμόζουμε την απάντηση μας στο επίπεδο γνώσης του. Αν πάλι τον "ζυγίσουμε" λάθος, μπορεί ανά πάσα στιγμή να ζητήσει περαιτέρω ανάλυση και τότε ευχαρίστως να του την δώσουμε.

 

[C6WGMN]

Τι σημαίνει "άλυτο και απλούστατο" ;

Αντιφατικό δεν είναι ; Συνήθως τα προβλήματα που είναι απλά δεν είναι άλυτα.

Απλή είναι η μερική λύση του προβλήματος. Η ολική είναι αδύνατη.

 

Τέλος, αν έχεις γνώση επί του συμβολικού υπολογισμού πες μου που μπορώ να ψάξω, έτσι για να ξέρω τι γίνεται.

Σου είπα είναι απλό pattern matching. Δηλαδή έχεις ένα σύνολο συναρτήσεων που υπολογίζουν η κάθε μια κάποιο ξεχωριστό είδος παραγώγων (πχ τριγωνομετρικές, πολυωνυμικές), και αναγνωρίζεις το την κατηγορία και τις επιμέρους κατηγορίες της συμβολικής παράστασης. Φυσικά χρειάζεσαι και ένα parser που θα πέρνει την είσοδο από τον χρήστη και θα την μετατρέπει σε κάποιο AST. Στο wolfram κάνουν τέτοια πράγματα.

[V.I.Smirnov]

@Dr.Fuzzy

 

Δυο φορές του δίνω καθαρά τον τύπο

f'(x) = ( f(x+h) - f(x-h) ) / (2h)

και του λέω γιατί πρέπει να τον χρησιμοποιήσει.

Kαι την δεύτερη φορά, του εξηγώ τι είναι οι όροι που δεν κατάλαβε.

Πόσο πιο σαφής να γίνω ;

 

 

@C6WGMN

 

Ξέρω ότι "απλό" δεν σημαίνει αναγκαστικά "εύκολο" και ότι "σύνθετο" δεν σημαίνει αναγκαστικά "δύσκολο".

(Και συνεπώς ούτε η μερική λύση είναι αναγκαστικά απλή.)

Το "άλυτο και απλούστατο" δεν μου είναι σαφές...

 

Στο "wolfram" ; Προφανώς εννοείς το Mathematica.

Στο manual έγραφε ότι για τον υπολογισμό των ολοκληρωμάτων η βασική αρχή είναι τελείως διαφορετική από την χειροκίνητη δουλειά.

Μετατρέπει αρχικά, έγραφε, την μορφή της συνάρτησης στην απλούστερη δυνατή μορφή κλπ.

 

Το parser ήταν δύσκολο να το κάνω. Αλλά η ιδέα με τον κανόνα της αλυσίδας δούλεψε πολύ καλά (για τις παραγώγους μόνον, να εξηγούμαστε).

[Dr.Fuzzy]

Και όσο για το βήμα h, δες τον κώδικά του : η συνάρτηση που δοκιμάζει είναι εκθετική.

 

fx=10*x+2;

 

εκθετική;

[V.I.Smirnov]

Δική μου απροσεξία.

Το είδα βιαστικά, επηρεασμένος από τη Fortran όπου γράφεις 10**2+x.

Διορθώνω την απάντησή μου...

[johnykim]

@V.I.Smirnov, βασικά δεν ξέρω καν τι σημαίνει ** στο h**2 f''(ξ)/2.Θα χρησιμοποιούσα ευχαρίστως τη σχέση «f'(x) = ( f(x+h) - f(x-h) ) / (2h)»,αλλά είχες πει αρκετές στο προηγούμενο ποστ και δεν κατάλαβα ποια είναι τελικά η ιδανική.Γι’αυτό χρησιμοποίηση τη σχέση που είχε Dr.Fuzzy στην return.

 

Παιδιά συγνώμη για την αναστάτωση.Δεν θέλω κάποια μαθηματική ανάλυση.Απλά θέλω να μάθω ποια σχέση χρειάζεται για την επίλυση μια παραγώγου.Σε μια απλή συνάρτηση όπως στα παραδείγματά μου ,όχι σε κάποια σύνθετη.

Αυτό που θα ήθελα δηλαδή μια συνάρτηση, (π.χ f(x)=10x+5), την μεταβλητή με την σχέση ,και μια print για εμφανίζει το αποτέλεσμα. Την ανάλυση για την σχέση θα βγάλω νομίζω άκρη με τα βιβλία των μαθηματικών.

 

Επίσης θα ήθελα να μου πείτε ,μήπως κάνω εγώ κάποια βλακεία με το συντακτικό της C;Εννοώ οι συναρτήσεις έχουν f(x),ενώ εγώ χρησιμοποιώ fx..

 

Με την σχέση του @V.I.Smirnov :

>
#include <stdio.h>
#include <stdlib.h>

main()
{
 
float fx,fxx,x,h;

h=0.000001;
fx=10*x+2;

fxx= ((fx+h)-(fx-h))/(2*h);

printf("f'(x)=%f",fxx);

printf("\n");
 
system("PAUSE");	
return 0;
}

 

Αλλά ότι και να βάλω στην συνάρτηση(fx) ,παίρνω 1.000000.

[virxen75]

όταν σου είναι εκ των προτέρων γνωστή η συνάρτηση μπορεις να την ορίσεις

όπως πιο κάτω

 

>

#include <stdio.h>
double f(double);

double f(double x){
return 10*x+5;
}

int main(){
   double x=0.05;
   printf("\nx=%f ,f(%f)=%f",x,x,f(x));
   getchar();
return 0;
}