Επαναλαμβανόμενη συνάρτηση

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

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

Ορισμός
Η επαναλαμβανόμενη, ακριβέστερα η δεύτερη επαναλαμβανόμενη, μιας συνάρτησης f, που ορίζεται σε ένα σύνολο X και έχει τιμές στο ίδιο αυτό σύνολο X, είναι η συνάρτηση  όπου  σημειώνει τη σύνθεση συναρτήσεων. Με άλλα λόγια, για κάθε στοιχείο x του X

Γενικότερα, με το n να είναι ένας θετικός ή μηδενικός ακέραιος αριθμός, η n-η επαναλαμβανόμενη   μιας συνάρτησης f , που ορίζεται σε ένα σύνολο X και με τιμές στο ίδιο αυτό σύνολο X, ορίζεται με αναδρομή μέσω της σχέσης

Σύμφωνα με τη σύμβαση, για n = 0,  , όπου  είναι η συνάρτηση ταυτότητας στο .

Ο συμβολισμός  μπορεί να είναι διφορούμενος, καθώς χρησιμοποιείται όχι μόνο για την επανάληψη, αλλά και για την ύψωση σε δύναμη. Για το λόγο αυτό, ορισμένοι μαθηματικοί συμβολίζουν  την n-οστή επανάληψη μιας συνάρτησης .

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

Για ένα στοιχείο  του , η ακολουθία τιμών  είναι η τροχιά του .

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

Σταθερά σημεία
Αν  f(x) = x  για ένα στοιχείο x του X (με άλλα λόγια, η περίοδος της τροχιάς του x είναι 1), τότε το x είναι ένα σταθερό σημείο της επαναληπτικής ακολουθίας.  Το σύνολο των σταθερών σημείων συμβολίζεται με Fix(f).  Διάφορα θεωρήματα εγγυώνται την ύπαρξη σταθερών σημείων σε ορισμένες περιπτώσεις, όπως το Θεώρημα σταθερού σημείου του Μπάναχ ή το Θεώρημα σταθερού σημείου του Μπρόουβερ.

Διάφορες τεχνικές μπορούν να χρησιμοποιηθούν για την επιτάχυνση της σύγκλισης των ακολουθιών που παράγονται με επαναλήψεις σταθερού σημείου. L. Carleson et T. D. W. Gamelin, Complex dynamics, Berlin/New York, Springer-Verlag, coll. « Universitext: Tracts in Mathematics », 1993, 174 p. (ISBN 0-387-97942-5).

Κατά τη διάρκεια της επαναληπτικότητας, μπορεί να υπάρχουν σύνολα που συστέλλονται και συγκλίνουν σε ένα μόνο σημείο: στην περίπτωση αυτή, το σημείο αυτό είναι ένα ελκυστικό σταθερό σημείο. Η επαναληπτικότητα μπορεί επίσης να δώσει την εμφάνιση σημείων που απομακρύνονται από ένα σταθερό σημείο, το οποίο τότε ονομάζεται ασταθές σταθερό σημείοVasile Istratescu, Fixed Point Theory, An Introduction, D. Reidel, 1981 (ISBN 90-277-1224-7). Άλλες οριακές συμπεριφορές είναι επίσης δυνατές. Όταν τα σημεία της τροχιάς συγκλίνουν σε ένα ή περισσότερα όρια, το σύνολο των συσσωρευμένων σημείων της τροχιάς ονομάζεται οριακό σύνολο ή ω-οριακό σύνολο.

Οι ιδέες της έλξης και της απώθησης γενικεύονται: τα σταθερά και τα ασταθή σύνολα μπορούν να κατηγοριοποιηθούν ανάλογα με τη συμπεριφορά των μικρών γειτονιών κατά την επανάληψη.

Αμετάβλητο μέτρο
Αν μας ενδιαφέρει η εξέλιξη μιας κατανομής πυκνότητας και όχι μιας διακριτής κατανομής ή ενός μεμονωμένου σημείου, η οριακή συμπεριφορά δίνεται από το αναλλοίωτο μέτρο. Μπορεί να απεικονιστεί ως η συμπεριφορά ενός νέφους σημείων ή σκόνης υπό μία επανάληψη. Το αναλλοίωτο μέτρο είναι ένα ιδιοδιάνυσμα του τελεστή Ρουέλ-Φρομπένιους-Περόν ή του τελεστή μεταφοράς, που αντιστοιχεί στην ιδιοτιμή 1. Μικρότερες ιδιοτιμές αντιστοιχούν σε ασταθείς, συρρικνούμενες καταστάσεις.

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

 Κλασματική και αρνητική επανάληψη 
Υπό ορισμένες προϋποθέσεις, είναι δυνατόν να οριστεί μια κλασματική επαναληπτικότητα μιας συνάρτησης. Για παράδειγμα, η μισή επανάληψη μιας συνάρτησης  είναι μια συνάρτηση  τέτοια ώστε .  Αυτή η συνάρτηση  μπορεί να γραφτεί με εκθετικό συμβολισμό <. Παρομοίως,  είναι η συνάρτηση τέτοια ώστε , και  μπορεί να οριστεί ως , και ούτω καθεξής, με βάση την αρχή ότι .  Η ιδέα μπορεί να γενικευτεί στην περίπτωση όπου ο αριθμός των επαναλήψεων  γίνεται μια συνεχής παράμετρος- το σύστημα είναι τότε μια ροή που συνδέεται με μια εξίσωση Σρέντερ.

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


Τύποι για κλασματική επαναληπτικότητα
Υπάρχουν διάφορες μέθοδοι για τον προσδιορισμό της κλασματικής επαναληπτικότητας. Η παρακάτω βασίζεται στη χρήση ενός σταθερού σημείου. 

 Καθορίζουμε ένα σταθερό σημείο a της συνάρτησης, με άλλα λόγια ένα σημείο a τέτοιο ώστε .
 Σταθερό σημείο , για κάθε n που ανήκει στους πραγματικούς. Αυτό αντιστοιχεί στην πιο φυσική πρόσθετη συνθήκη που μπορεί να επιβληθεί στις επαναλήψεις.
 Γράφουμε το  στη γειτονιά του σταθερού σημείου a ως σειρά Τέιλορ :

 Αναπτύσσουμε :

 Χρησιμοποιώντας τη συνθήκη που τέθηκε στο βήμα 2 , για όλα τα k, έχουμε:

 Απλοποιούμε χρησιμοποιώντας τη γεωμετρική πρόοδο :

 Μια ειδική περίπτωση είναι όταν   - σε αυτή την περίπτωση : 

 Αν το n δεν είναι ακέραιος αριθμός, χρησιμοποιούμε τον τύπο .

Η διαδικασία αυτή μπορεί να συνεχιστεί επ' αόριστον, αλλά γενικά δεν είναι αποτελεσματική, καθώς οι όροι γίνονται όλο και πιο περίπλοκοι.

 Παράδειγμα 1 
Η συνάρτηση f ορίζεται από τη σχέση   με C ≠ 1, έχει σταθερό σημείο .

Η διαδικασία που αναλύσαμε παραπάνω δίνει :

 Παράδειγμα 2 
Έστω ότι θέλουμε να υπολογίσουμε την τιμή , για n επαναλήψεις. Εδώ η συνάρτηση ορίζεται από . Ένα σταθερό σημείο είναι .

Αναπτύσσοντας  όπως εξηγήθηκε παραπάνω στη γειτονιά του 2, και θέτοντας x=1, έχουμε,

Για n θετικό ακέραιο, οι τρεις πρώτοι όροι δίνουν το σωστό πρώτο δεκαδικό ψηφίο:  . 

(Σημειώστε ότι αν χρησιμοποιήσουμε το άλλο σταθερό σημείο  , αντί για το σταθερό σημείο 2, η σειρά αποκλίνει).

Για  η σειρά υπολογίζει την αντίστροφη συνάρτηση, .

Παράδειγμα 3 
Αναπτύσσοντας στην περιοχή του σταθερού σημείου 1 τη συνάρτηση , προκύπτει η σειρά

η οποία είναι απλά η σειρά Τέιλορ της x(bn) γύρω από το 1.

Τοπολογική συζυγία

Αν  και  είναι δύο επαναλαμβανόμενες συναρτήσεις, και αν υπάρχει ένας ομοιομορφισμός  τέτοιος ώστε , λέμε ότι  και } είναι τοπολογικά συζυγείς.

Η επαναληπτικότητα διατηρεί την τοπολογική σύζευξη: πράγματι, .   Έτσι, αν ξέρουμε πώς να προσδιορίσουμε ένα σύστημα επαναληπτικών συναρτήσεων, ξέρουμε επίσης πώς να προσδιορίσουμε όλα τα τοπολογικά συζυγή συστήματα. 

Παραδείγματος χάριν, η τριγωνική συνάρτηση είναι τοπολογικά συζυγής με τη λογιστική ακολουθία. Μια ειδική περίπτωση είναι η  η οποία δίνει ως επανάληψη της  

για οποιαδήποτε συνάρτηση .

Κάνοντας την αντικατάσταση , προκύπτει 
,  με άλλα λόγια την εξίσωση του Άμπελ.

Στην απουσία ενός πραγματικού συνολικού ομοιομορφισμού, είναι συχνά δυνατή η επίλυση της εξίσωσης Σρέντερστην περιοχή ενός σταθερού σημείου για μια  συνάρτηση.  Παραδείγματος χάριν, εάν  = 0, (0) = 0,   είναι τοπικά συζυγής με μια διαστολή, , με άλλα λόγια   

Η τροχιά της επανάληψης, ή float, υπό κατάλληλες συνθήκες (π.χ. ), γίνεται η συζυγής της τροχιάς του μονοωνύμου :

όπου  σε αυτή την έκφραση είναι ένας συνηθισμένος εκθέτης: με άλλα λόγια, η λειτουργική επανάληψη έχει μειωθεί σε έναν απλό πολλαπλασιασμό. Ο εκθέτης  δεν μπορεί να είναι ούτε θετικός ούτε ακέραιος- τότε αντιστοιχεί σε ένα συνεχή χρόνο εξέλιξης για την τροχιά.

Το παράδειγμα 2 παραπάνω ισοδυναμεί, επομένως, με ,  για οποιοδήποτε n (όχι απαραίτητα ακέραιο), όπου  είναι η λύση της αντίστοιχης εξίσωσης Σρέντερ, .  Αυτή η λύση είναι επίσης το όριο, για m που τείνει στο άπειρο, της .

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

Παραδείγματα
Για παραδείγματα επαναλαμβανόμενων συναρτήσεων, δείτε επίσης το σύνολο Μάντελμπροτ και τα Επαναλαμβανόμενα συστήματα συναρτήσεων.

Ο Έρνστ Σρέντερ μελέτησε ειδικές περιπτώσεις της λογιστικής ακολουθίας το 1870:

 (χαοτική περίπτωση) :  δίνει , ως εκ τούτου .
 (μη χαοτική περίπτωση) :  δίνει  , και επομένως  .

Επαναλαμβανόμενες συναρτήσεις με κλειστή έκφραση
Για τις περισσότερες συναρτήσεις, δεν υπάρχει κλειστή έκφραση για την επαναλαμβανόμενη επανάληψη ne.  Ο παρακάτω πίνακας παραθέτει ορισμένες συναρτήσεις για τις οποίες υπάρχει τέτοια έκφραση. Όλες αυτές οι εκφράσεις ισχύουν για n, αρνητικούς ή κλασματικούς, καθώς και για θετικούς ακέραιους αριθμούς.

 όπου: όπου:   κλασματικός γραμμικός μετασχηματισμός Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492.    onlineόπου:   εξίσωση Άμπελ      (Πολυώνυμο Τσέμπισεφ για ακέραιο m) 

Σημείωση:   είναι οι μόνες περιπτώσεις που έχουν λύση κλειστής μορφής. Επιλέγοντας αντίστοιχα b = 2 = –a and b = 4 = –a, ανάγονται στις μη χαοτικές και χαοτικές περιπτώσεις που συζητήθηκαν παραπάνω.

Μερικά από αυτά τα παραδείγματα συνδέονται με απλές συζυγίες

Αλυσίδες Μαρκόφ
Εάν η συνάρτηση είναι γραμμική και μπορεί να περιγραφεί από έναν στοχαστικό πίνακα, δηλαδή έναν πίνακα όπου το άθροισμα των καταχωρήσεων σε μια γραμμή (ή στήλη) είναι πάντα ίσο με 1, τότε το σύστημα των επαναλήψεων ονομάζεται αλυσίδα Μαρκόφ.

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

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

και το γινόμενο από :

Συναρτησιακή παράγωγος
Η συναρτησιακή παράγωγος μιας επαναλαμβανόμενης συνάρτησης δίνεται από τον εξής αναδρομικό τύπο

 Δείτε επίσης 
Αλγόριθμος διαμαντιού τετραγώνου
Καμπύλη που γεμίζει το χώρο
Νιφάδα του Κοχ 
Καμπύλη Χίλμπερτ
Καμπύλη του δράκου
Σπόγγος του Μένγκερ
Σύνολο Μάντελμπροτ 
Σύνολο Julia
Οικοδομήσιμο Σύμπαν

Παραπομπές



Κατηγορία:Φράκταλ
Κατηγορία:Δυναμικά συστήματα
Κατηγορία:Ακολουθίες και σειρές
Κατηγορία:Μαθηματικές συναρτήσεις