Homogén és a nem-homogén lineáris rekurzív sorozat - studopediya
Definíció. A szekvencia az úgynevezett visszatérő, ha valamely k és az összes n a kapcsolatban az űrlap
ahol a konstans együtthatók pi; i = 1; 2; ...; k független n.
Ez az úgynevezett karakterisztikus polinomja a visszatérő szekvencia.
úgynevezett homogén lineáris rekurzív sorozat.
Től (15) képletű megtalálni a közös tagja, ez elegendő ahhoz, hogy megtalálják a generáló függvény - funkció. Bemutatjuk egy kiegészítő polinom, és megvizsgálja a terméket, a mértéke a C (t) nem haladja meg a K-1, mivel a koefficiensek t n + k, k = 0, 1, ... nulla értelmében (15) egyenletben. Tegyük fel, hogy a karakterisztikus egyenlet (14) van egy egyszerűbb (esetleg több) gyökerek, azaz a Ez lehetővé teszi bővítését formájában. Ezután
Karakterisztikus függvény felírható
Köztudott, hogy a tény, következésképpen. (17)
Egyenlet (17) adja a bomlás generáló függvény. Ahhoz, hogy megtalálja a általános kifejezés általános képletű kell találni a koefficiensek t n expanziós (17).
Example1. Keresse az általános kifejezés a szekvencia kielégíti a rekurzív sorozat.
Határozat. Írja át az eredeti rekurzív sorozat a forma (15)
A karakterisztikus polinomja L (t) a formája, majd
Módszer a meghatározatlan együtthatók megkapjuk
Módja, hogy megtalálják az általános megoldás rekurzív sorozat:
1. Ha a visszatérő szekvenciát (13) teljes mértékben eepervyh k opredelyaetsyazadaniem tagjai,
.
2. Ha t a gyökere a karakterisztikus polinomja (14), a szekvencia a kielégítése a összefüggést (13), majd.
3. Ha t1; t2; ...; tk egyszerű (nem több), a gyökerek a karakterisztikus polinom (14), akkor az általános megoldás a rekurzív sorozat (13) formájában van
4. Ha van egy polinom gyökér (14) sokaságának, az általános megoldás a rekurzív sorozat (13) formájában van
ahol c i, j = 1, 2, ..., R; j = 1; ...; - tetszőleges állandók, R - száma több gyökerek.
2. példa Find az általános megoldás az 1. példa.
Határozat. A karakterisztikus polinomja a root t1 = 1; t2 = 3, akkor a következő képlet szerint (18) kapjuk.
3. példa Hogy oldja nem egyenletes kiújulás.