Γραμμική αναδρομική ακολουθία δεύτερης τάξης

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

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

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

 Παραδείγματα 

 Παράδειγμα 1ο: Ακολουθία Φιμπονάτσι 
Όπως αναφέραμε παραπάνω, η ακολουθία Φιμπονάτσι είναι η ακολουθία που ικανοποιεί την σχέση 
 για κάθε  
και επίσης . Αυτά είναι αρκετά για να υπολογίσουμε όλους τους όρους της ακολουθίας ως εξής

 Παράδειγμα 2ο 
Θεωρούμε την ακολουθία  με αναδρομιή σχέση 
 για κάθε  
και επίσης . Ξανά μπορούμε να υπολογίσουμε τους όρους της ως εξής:

 Γενικός τύπος για c=0 

Η χαρακτηριστική της εξίσωση είναι το τριώνυμο 

Έστω  οι ρίζες της χαρακτηριστικής εξίσωσης, τότε 
 Αν 
.
 Αν 
.

Πιο απλά, το παραπάνω θεώρημα λέει ότι αν 

για κάποιες σταθερές  που προσδιορίζονται από τις τιμές των ,
και αν , τότε
.

 Παράδειγμα 

 Διακριτές ρίζες (Ακολουθία Φιμπονάτσι) 

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

 Διπλή ρίζα 
Θεωρούμε την ακολουθία με αναδρομική σχέση 

και  και . 

Η χαρακτηριστική της εξίσωση είναι 
,  
η οποία έχει διπλή ρίζα το .

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

 Ως σχέση διανυσμάτων 

 Για c=0 

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

Από αυτήν την σχέση έπεται ότι 

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

Διαγωνιοποιώντας τον πίνακα
,
όπου  και  ένας διαγώνιος πίνακας, έχουμε ότι 

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

 Για c≠0 

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

 Εφαρμογές 

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

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

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

και επιπλέον  και . Επομένως, οι τιμές  είναι μέρος μίας αναδρομικής ακολουθίας δεύτερης τάξης. 

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

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

Έστω  το πλήθος των τρόπων να καλύψουμε ένα ορθογώνιο διαστάσεων . Τότε,  και .Συνήθως είναι πιο εύκολο να ορίσουμε .

Για την αναδρομική σχέση αρκεί να παρατηρήσουμε ότι για το τελευταίο ορθογώνιο που τοποθετήσαμε υπάρχουν τρεις επιλογές: τοποθετήσαμε (1) το κόκκινο, (2) το πράσινο ή (3) το μπλε ορθογώνιο. Στην πρώτη περίπτωση το υπόλοιπο ορθογώνιο είναι , ενώ στην δεύτερη και στην τρίτη είναι . Από την προσθετική αρχή απαρίθμησης καθώς οι τρεις περιπτώσεις είναι ανεξάρτητες, έχουμε ότι 
,
που είναι μία γραμμική αναδρομική σχέση δεύτερης τάξης. 
Χρησιμοποιώντας τον παραπάνω γενικό τύπο έχουμε ότιΗ χαρακτηριστική εξίσωση έχει ρίζες τις  και . Επομένως, 

Για , έχουμε ότι  και για ,  έχουμε ότι . 
Λύνοντας το σύστημα,  και . 
.

 Υπολογισμός 

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

// Αναδρομική εύρεση n-οστού όρου.
double get_term_recursive(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   if (n == 1) return u1;
   return a * get_term_recursive(a, b, u0, u1, n-1) 
      + b * get_term_recursive(a, b, u0, u1, n-2);
}

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

// Εύρεση n-οστού όρου με επανάληψη.
double get_term_iterative(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   if (n == 1) return u1;
   double un = u1, u_prev = u0;
   for (int i = 2; i <= n; ++i) {
      double u_next = a * un + b * u_prev;
      u_prev = un;
      un = u_next;
   }
   return un;
}

 Με τον γενικό τύπο 

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

// Λύση του τριωνύμου x^2 -ax + b = 0.
std::pair<double, double> get_roots(double a, double b) {
   double sqrt_D = sqrt(a*a + 4 * b);
   return { (a-sqrt_D)/2, (a + sqrt_D)/2 };
}

// Εύρεση n-οστού όρου με την 
double get_term_closed_form(double a, double b, double u0, double u1, int n) {
   auto [r1, r2] = get_roots(a, b);
   if (r1 != r2) { // Περίπτωση 1η: Δύο διακριτές ρίζες. 
      double r1_n = std::pow(r1, n);
      double r2_n = std::pow(r2, n);
      return (r1_n - r2_n) / (r1 - r2) * u1 + (r1_n * r2 - r1 * r2_n) / (r2 - r1) * u0; 
   }
   // Περίπτωση 2η: Διπλή ρίζα.   
   double r_n_minus_1 = std::pow(r1, n-1);
   double r_n = r_n_minus_1 * r1;
   return n * r_n_minus_1 * u1 + r_n * (1 - n) * u0;
}

 Με χρήση πινάκων 
Η παρακάτω υλοποίηση χρησιμοποιεί την αναδρομική σχέση με τους πίνακες που διατυπώσαμε παραπάνω για τον υπολογισμό του -οστού όρου. Χρειάζεται επίσης  προσθέσεις και πολλαπλασιασμούς. Επιπλέον έχει το πλεονέκτημα ότι αν οι αρχικοί όροι  και οι σταθερές  είναι ακέραιοι, τότε δεν χρειάζεται να χρησιμοποιήσει δεκαδικούς αριθμούς. Αυτό σημαίνει ότι είναι πιο αποδοτικός ο αλγόριθμος και το αποτέλεσμα πιο ακριβές. 
// Πολλαπλασιασμός πινάκων.
Matrix2D multiply(Matrix2D x, Matrix2D y) {
   return { x.a11 * y.a11 + x.a12 * y.a21, x.a11 * y.a12 + x.a12 * y.a22, 
            x.a21 * y.a11 + x.a22 * y.a21, x.a21 * y.a12 + x.a22 * y.a22 };
}

// Εύρεση n-οστού όρου με την χρήση πινάκων.
double get_term_matrix(double a, double b, double u0, double u1, int n) {
   if (n == 0) return u0;
   // Δυαδική εκθετοποίηση πίνακα.
   Matrix2D A = { a, b, 1, 0 }, ans = {1, 0, 0, 1};
   --n;
   while (n > 0) {
      if (n % 2 == 1) ans = multiply(ans, A);
      n /= 2;
      A = multiply(A, A);
   }
   // Πολλαπλασιασμός με αρχικό διάνυσμα.
   return ans.a11 * u1 + ans.a12 * u0;
}

 Δείτε επίσης 
 Γραμμική αναδρομική ακολουθία πρώτης τάξης
 Ακολουθία Φιμπονάτσι

 Σημειώσεις 

 Παραπομπές 

Κατηγορία:Ακολουθίες