rekurentné metódy. Všeobecné a partikulárne riešenia rekurentných vzťahov Vypočítajte determinanty rádu n metódou rekurentných vzťahov
S veľkým množstvom pozorovaných údajov X konečné metódy riešenia pravdepodobnostnej rovnice vedú k značným výpočtovým ťažkostiam spojeným s potrebou zapamätať si veľké množstvo počiatočných údajov a medzivýsledkov výpočtov. V tomto ohľade sú obzvlášť zaujímavé rekurentné metódy, v ktorých sa odhad maximálnej pravdepodobnosti počíta v krokoch s postupne sa zvyšujúcou presnosťou, pričom každý krok je spojený so získavaním nových pozorovacích údajov a rekurentný postup je konštruovaný tak, aby bol uložený v pamäte čo najmenej údajov z predchádzajúcich.krokov. Ďalšou a veľmi významnou výhodou z praktického hľadiska rekurzívnych metód je pripravenosť vydať výsledok v akomkoľvek medzikroku.
Vďaka tomu je účelné používať rekurentné metódy aj v prípadoch, keď je možné získať presné riešenie rovnice maximálnej pravdepodobnosti konečnou metódou, a o to cennejšie, keď nie je možné nájsť presné analytické vyjadrenie pre odhad maxima. pravdepodobnosť.
Nech je množinou pozorovacích údajov sekvencia, na ktorej popis zavedieme vektor . (Ako vždy, každý z jeho komponentov môže byť vektor, segment náhodného procesu atď.). Nech je funkcia pravdepodobnosti a
jeho logaritmus. Ten môže byť vždy reprezentovaný ako
Logaritmická pravdepodobnosť súboru pozorovacích údajov bez poslednej hodnoty a
Logaritmus hustoty podmienenej pravdepodobnosti hodnoty pre dané hodnoty a .
Znázornenie (7.5.16) pre logaritmus pravdepodobnostnej funkcie je základom na získanie opakujúceho sa postupu na výpočet odhadu maximálnej pravdepodobnosti. Zoberme si bežný prípad. V tomto prípade možno ako riešenie rovnice nájsť odhad maximálnej pravdepodobnosti
ktorý sa od (7.1.6) líši len zavedením indexu p y logaritmus pravdepodobnostnej funkcie.
Označme riešenie tejto rovnice tak, že zdôrazníme, že tento odhad bol získaný z celkového počtu pozorovaných údajov. Podobne označme riešením rovnice odhad maximálnej pravdepodobnosti získaný zo súboru údajov .
Rovnicu (7.5.19) je možné prepísať s prihliadnutím na (7.5.16) v nasledujúcom tvare:
Rozviňme ľavú stranu (7.5.20) na Taylorov rad v blízkosti bodu . V čom
(7.5.22)
Vektor gradientu funkcie v bode ; člen zaniká v dôsledku skutočnosti, že , je riešením pravdepodobnostnej rovnice pre predchádzajúcu (P - 1) krok:
Symetrická matica druhých derivácií logaritmu pravdepodobnostnej funkcie v bode , braná s opačným znamienkom, nepísané členy expanzie majú kvadratický a vyšší rád maličkosti vzhľadom na rozdiel . Ak ich zanedbáme, získame nasledujúce približné riešenie rovnice maximálnej pravdepodobnosti:
kde je inverzná matica.
Toto riešenie je prezentované vo forme rekurentného vzťahu, ktorý určuje ďalšiu hodnotu odhadu cez odhad v predchádzajúcom kroku a korekciu , závisí od dostupných pozorovacích údajov priamo a prostredníctvom predchádzajúceho hodnotenia. Korekcia sa vytvorí ako súčin gradientu logaritmu hustoty podmienenej pravdepodobnosti novo získanej hodnoty X n v bode, ktorý sa rovná predchádzajúcemu odhadu, na maticu váh . Ten je určený výrazom (7.5.23) a závisí aj od odhadu v predchádzajúcom kroku a jeho závislosť od nových pozorovacích údajov je úplne určená formou logaritmu hustoty podmienenej pravdepodobnosti .
Forma vzťahu (7.5.24) je veľmi podobná (7.5.8), ktorá implementuje iteratívny spôsob výpočtu maximálneho pravdepodobnostného odhadu Newtonovou metódou. V skutočnosti sa však navzájom výrazne líšia. V (7.5.8) je korekcia na predchádzajúcu hodnotu odhadu určená veľkosťou gradientu logaritmu celej pravdepodobnostnej funkcie, ktorá vždy závisí od všetkých dostupných pozorovacích údajov, čo si vyžaduje zapamätanie celej populácie. V súlade s (7.5.24) je korekcia určená veľkosťou gradientu, ktorý vzhľadom na vlastnosti podmienenej hustoty pravdepodobnosti v skutočnosti závisí iba od tých hodnôt (), ktoré sú v silnom štatistickom vzťahu. s X n. Tento rozdiel je dôsledkom špeciálneho výberu predchádzajúcej aproximácie ako maximálneho odhadu pravdepodobnosti zisteného zo súboru pozorovacích údajov znížených o jednu hodnotu a je obzvlášť výrazný pre nezávislé hodnoty (). V tomto poslednom prípade
vďaka čomu závisí len od a X n a gradient je len z predchádzajúcej hodnoty odhadu a novo získanej P- Krok údajov sledovania. Preto pre nezávislé hodnoty na vytvorenie vektora nie je potrebné ukladať žiadne ďalšie informácie z predchádzajúceho kroku, okrem hodnoty odhadu .
Podobne v prípade Markovovej postupnosti pozorovacích údajov, teda kedy
vektor závisí len od , aktuálnej a jednej predchádzajúcej hodnoty . V tomto prípade je pre výpočet potrebné zapamätať si z predchádzajúceho kroku okrem hodnoty len hodnotu , ale nie celú množinu pozorovaných údajov, ako napr. v iteratívnom postupe. Vo všeobecnosti môže výpočet vyžadovať uloženie väčšieho počtu predchádzajúcich hodnôt (), avšak kvôli potrebe brať do úvahy iba tie hodnoty, ktoré sú štatisticky závislé od , je toto číslo takmer vždy menšie ako celkový objem súboru pozorovaných údajov. Ak teda vektor opisuje časovú sekvenciu, potom počet zapamätaných členov tejto sekvencie je určený časom jej korelácie a ich relatívny podiel klesá nepriamo úmerne n ako v prípade nezávislých hodnôt.
Uvažujme teraz o štruktúre váhovej matice , zahrnutej v rekurentnom vzťahu (7.5.24). Podľa definície (7.5.23) v dôsledku prítomnosti termínu vo všeobecnosti závisí od všetkých hodnôt, dokonca aj pre nezávislé hodnoty , čo zbavuje vzťah opakovania (7.5.24) výhod spojených s možné zníženie množstva údajov uložených z predchádzajúceho kroku. Existuje niekoľko spôsobov, ako aproximovať maticu , ktoré tento nedostatok napravia.
Prvý z nich je založený na dôslednejšom využívaní základného predpokladu malého rozdielu medzi dvoma po sebe nasledujúcimi hodnotami odhadu a , ktorý je základom pre získanie vzťahu opakovania (7.5.24). To nám umožňuje získať podobný vzťah opakovania pre maticu váh .
Zavedením notového zápisu
z (7.5.24) a (7.5.25) dostaneme systém rekurentných vzťahov pre vektor a maticu váh.
Tento systém spolu s počiatočnými hodnotami úplne určuje hodnotu odhadu v ktoromkoľvek kroku, pričom v každom z nich vyžaduje vypočítať iba gradient a maticu druhých derivácií logaritmu hustoty podmienenej pravdepodobnosti pre aktuálnu pozorovanú hodnotu. Počiatočné hodnoty sa vyberajú s prihliadnutím na dostupné apriórne údaje o možných hodnotách a rozsahu zmeny parametrov, a ak tieto údaje neexistujú, považujú sa za nulové (,).
Pre nezávislé hodnoty systém rekurentných vzťahov (7.5.27) evidentne opisuje viacrozmerný (rozmerný) Markovov náhodný proces, ktorého zložka konverguje k skutočnej hodnote parametra a zložka konverguje k Fisherovej informačnej matici (7.3. 8), kde je skutočná hodnota odhadovaného parametra a zvyšuje sa na neurčito ako P. Systém (7.5.27) má podobné konvergenčné vlastnosti za všeobecnejších podmienok, ak je postupnosť ergodická.
Druhá zo spomínaných metód je založená na nahradení matice druhých derivácií logaritmu pravdepodobnostnej funkcie jej matematickým očakávaním - Fisherovou informačnou maticou, ktorú je možné s prihliadnutím na (7.5.16) zapísať ako:
kde podobne ako (7.5.26)
Nahradením matice v (7.5.24) maticou získame rekurentný vzťah
pre približný výpočet odhadov maximálnej pravdepodobnosti navrhnutých Sakrisonom (v origináli pre nezávislé identicky rozdelené , kedy a . Tento vzťah opakovania je jednoduchší ako systém (7.5.27), pretože matica optimálnej váhy je nahradená jej matematickým očakávaním , a na jeho nájdenie nie sú potrebné dostupné observačné údaje, okrem tých, ktoré sú sústredené v hodnote odhadu Zároveň je zrejmé, že takáto náhrada znamená nutnosť splniť dodatočnú požiadavku oproti (7.5.27). ), že matica druhých derivácií bude blízka jej matematickému očakávaniu.
Ak sa distribúcia hustoty pravdepodobnosti a matica menia z kroku na krok, nájdenie každého kroku priamo môže vyžadovať príliš veľa výpočtov. Zároveň je možné v dôsledku dodatočného zníženia presnosti výsledkov, ktoré je určené nulovou nerovnosťou malých rozdielov, pristúpiť k opakovanému výpočtu približnej hodnoty matice. Ak sa vrátime k predchádzajúcemu označeniu tejto približnej hodnoty, získame ďalší systém rekurentných vzťahov
Matematické očakávanie matice (Fisherova informačná matica pre jedno pozorovanie), prijaté v bode . Tento systém sa líši od (7.5.27) tým, že druhý z rekurentných vzťahov (7.5.31) priamo nezahŕňa pozorovacie údaje.
Ktorýkoľvek zo systémov rekurentných vzťahov uvažovaných vyššie je dokonale presný, ak funkcia závisí kvadraticky od , a navyše matica druhých derivácií nezávisí od . V skutočnosti to zodpovedá prípadu nezávislých normálne rozdelených (nie nevyhnutne rovnomerne) hodnôt s neznámym matematickým očakávaním, čo je odhadovaný parameter.
Systém rekurentných vzťahov (7.5.24) dáva presné riešenie rovnice maximálnej pravdepodobnosti za oveľa širších podmienok s jedinou požiadavkou, že funkcia závisí kvadraticky od . V tomto prípade je závislosť ľubovoľná, čo zodpovedá širokej triede rozdelenia pravdepodobnosti populácie s nezávislými aj závislými hodnotami.
Spolu s uvažovanými všeobecnými metódami existuje množstvo metód na výber matice váhových koeficientov vo vzťahu rekurencie (7.5.24), prispôsobených určitým špecifickým obmedzeniam. Najjednoduchším z nich je výber vo forme diagonálnej matice, takže , ( ja je matica identity), kde je klesajúca postupnosť číselných koeficientov, zvolených bez ohľadu na vlastnosti pravdepodobnostnej funkcie rovnakým spôsobom ako v postupe Robins-Monroeovej stochastickej aproximácie, o ktorej budeme diskutovať v nasledujúcich kapitolách.
Treba poznamenať, že akékoľvek opakované alebo opakujúce sa postupy na nájdenie odhadov maximálnej pravdepodobnosti sú vo všeobecnosti približné. Preto, všeobecne povedané, pre odhady získané ako výsledok aplikácie týchto postupov sa musí znovu dokázať konzistencia, asymptotická účinnosť a asymptotická normalita. Pre iteračné postupy sú potrebné vlastnosti odhadov zaručené tým, že v zásade takéto postupy s primeraným počtom iterácií dávajú riešenie pravdepodobnostnej rovnice s akoukoľvek vopred stanovenou presnosťou. Pre opakujúce sa postupy ako (7.5.27), (7.5.30), (7.5.31) a iné existujú špeciálne dôkazy. Zároveň sa okrem požiadavky pravidelnosti ukladajú niektoré ďalšie požiadavky:
O správaní funkcie (7.2.2) pre rôzne hodnoty ||, aby sa pomocou opakovaného postupu dosiahlo globálne maximum tejto funkcie v bode zodpovedajúcom skutočnej hodnote parametra;
V poradí rastu druhých momentov derivátov logaritmu pravdepodobnostnej funkcie pre veľké modulové hodnoty . Tieto požiadavky sú dôsledkom všeobecnejších podmienok pre konvergenciu všetkých alebo časti komponentov Markovovho náhodného procesu k bodu, ku ktorému vedie jeden alebo druhý opakujúci sa postup.
Na záver tiež poznamenávame, že v prípade, že existuje presné riešenie rovnice maximálnej pravdepodobnosti, môže byť takmer vždy reprezentovaná v rekurzívnej forme. Uvádzame dva jednoduché heterogénne príklady. Teda elementárny odhad neznámeho matematického očakávania normálnej náhodnej premennej v agregáte n jeho vzorové hodnoty vo forme aritmetického priemeru
je odhad maximálnej pravdepodobnosti a môže byť vyjadrený v rekurzívnej forme:
čo je najjednoduchší špeciálny prípad (7.5.30) pre
Ďalším príkladom je nepravidelný odhad maximálnej pravdepodobnosti pre parameter - šírka pravouhlého rozdelenia - z (7.4.2), ktorý možno určiť aj pomocou vzťahu opakovania
s počiatočným stavom. Tento rekurentný vzťah je iného typu: jeho pravú stranu nemožno znázorniť ako súčet predchádzajúceho odhadu a malej korekcie, čo je dôsledkom nepravidelnosti tohto príkladu; má však všetky výhody rekurzívneho prístupu: vyžaduje si zapamätať si len jedno číslo z predchádzajúceho kroku – odhad – a drasticky redukuje enumeráciu na jedno porovnanie namiesto porovnávania všetkých hodnôt.
Uvedené príklady ilustrujú výhody rekurzívnych metód aj v prípade, keď rovnica maximálnej pravdepodobnosti pripúšťa presné riešenie, pretože jednoduchosť analytického znázornenia výsledku nie je totožná s výpočtovou jednoduchosťou jeho získania.
7.5.3. Prechod na nepretržitý čas. Diferenciálne rovnice pre odhady maximálnej pravdepodobnosti
Uvažujme teraz o špeciálnom prípade, kde sú dostupné pozorovacie údaje X nie sú opísané súborom vzorových bodov , ale predstavujú segment realizácie nejakého procesu , v závislosti od parametrov, uvedených na intervale , navyše dĺžka tohto intervalu sa môže počas pozorovania predĺžiť (čas t je variabilný).
Pre štatistický popis pozorovaných údajov je v tomto prípade zavedený funkcionál pravdepodobnostného pomeru, čo je limit pri , max pomeru hustoty pravdepodobnosti množiny hodnôt pri ľubovoľne danej hodnote k podobnej pravdepodobnosti. hustota na nejakej pevnej hodnote a v niektorých prípadoch, keď pripúšťa reprezentáciu, kde je náhodný proces nezávislý od hustoty pravdepodobnosti množiny hodnôt za predpokladu, že . Použitie funkcionálu pravdepodobnostného pomeru umožňuje eliminovať formálne ťažkosti pri určovaní hustoty pravdepodobnosti, ktoré vznikajú pri prechode na spojitý čas.
Logaritmus funkcionálu pravdepodobnostného pomeru možno znázorniť ako
kde je nejaký proces funkčný na intervale . V niektorých prípadoch sa funkcia zvrhne na funkciu, ktorá závisí iba od hodnoty . Ak teda
kde je známa funkcia času a parametrov a je delta-korelovaný náhodný proces ("biely" šum) so spektrálnou hustotou N o, potom výberom ako menovateľa pomeru pravdepodobnosti rozdelenia pravdepodobnosti X o , budeme mať
Let - odhad maximálnej pravdepodobnosti parametra, postavený na implementácii procesu na intervale, tj riešenie rovnice maximálnej pravdepodobnosti
Získame diferenciáciu ľavej strany tejto rovnice vzhľadom na čas
Predstavenie notácie
a riešením rovnice (7.5.42) vzhľadom na , získame diferenciálnu rovnicu pre odhad maximálnej pravdepodobnosti
Maticu podľa (7.5.37) zase určuje diferenciálna rovnica
Rovnako ako v diskrétnom prípade, maticu v (7.5.45), (7.5.47) možno nahradiť jej matematickým očakávaním - Fisherovou informačnou maticou s hodnotou a diferenciálnou rovnicou (7.5.46) pre maticu váh. - podľa rovnice
kde podobne ako v diskrétnom prípade
Matematické očakávanie matice druhých derivácií.
Súbor diferenciálnych rovníc (7.5.45), (7.5.46) alebo (7.5.45), (7.5.48) spolu s počiatočnými podmienkami, pri výbere ktorých zostáva v platnosti všetko uvedené pre diskrétny prípad, úplne určuje odhad maximálnej pravdepodobnosti pre akýkoľvek časový bod. Túto množinu je možné simulovať pomocou vhodných, všeobecne povedané, nelineárnych analógových zariadení, alebo s vhodným časovým vzorkovaním riešiť počítačom. Na záver si všimneme jednu z úprav týchto rovníc, ktorá umožňuje vyhnúť sa potrebe invertovať maticu.
Predstavenie notácie
, kde ja
a diferencovanie vzťahu vzhľadom na čas , kde ja je matica identity, získame pomocou (7.5.46) diferenciálnu rovnicu, ktorá priamo určuje maticu:
(a podobne, keď sa nahradí ), čo spolu s rovnicou (7.5.45)
určuje skóre , bez potreby inverzie matice. V tomto prípade dochádza k prechodu od najjednoduchšej lineárnej diferenciálnej rovnice (7.5.46) k nelineárnej vzhľadom na diferenciálnu rovnicu (7.5.51) Riccatiho typu.
Kombinatorické výpočty na konečných množinách
Úvod do kombinatoriky
Predmetom teórie kombinatorických algoritmov, často nazývaných kombinatorické výpočty, sú výpočty na diskrétnych matematických štruktúrach. V tejto teórii sa veľká pozornosť venuje algoritmickému prístupu k riešeniu problémov diskrétnej matematiky, optimalizácii enumerácie možností a redukcii počtu uvažovaných riešení.
Oblasť kombinatorických algoritmov zahŕňa úlohy, ktoré vyžadujú počítanie (odhad) počtu prvkov v konečnej množine alebo vypísanie týchto prvkov v špeciálnom poradí (príloha B). V tomto prípade je široko používaný postup výberu prvkov s návratom a jeho variantov.
Existujú dva typy problémov s počítaním. V jednoduchom prípade je daná konkrétna súprava a tá je potrebná určiť presný počet prvkov v ňom. Vo všeobecnom prípade existuje rodina množín definovaná nejakým parametrom a mohutnosť množiny je definovaná ako funkcia parametra. Zároveň je to často dostatočný odhad poradia funkcie a niekedy len potrebujete hodnotenie jeho tempa rastu. Napríklad, ak sila uvažovanej množiny rastie exponenciálne v niektorom parametri, potom to môže stačiť na opustenie navrhovaného prístupu k štúdiu problému bez toho, aby sme zachádzali do rôznych detailov. Pre tento všeobecnejší typ problému sa aplikujú postupy asymptotických expanzií, rekurentných vzťahov a generujúcich funkcií.
Asymptotické
Asymptota je špeciálna čiara (najčastejšie priamka), ktorá je limitom pre uvažovanú krivku.
Asymptotika je umenie odhadovať a porovnávať rýchlosti rastu funkcií. Hovoria, že o X®¥ funkcia „správa ako X“, alebo „zvyšuje rovnakým tempom ako X“, a o X®0 "sa správa ako 1/ X Hovorí sa, že „log X pri X®0 a ľubovoľné e>0 sa správajú ako X e a čo n®¥ nerastie rýchlejšie ako n log n Takéto nepresné, ale intuitívne jasné vyhlásenia sú užitočné pri porovnávaní funkcií rovnakým spôsobom ako vzťahy<, £ и = при сравнивании чисел.
Definujme tri hlavné asymptotické vzťahy.
Definícia 1. Funkcia f(X) je ekvivalentné g(X) pri X® x0, vtedy a len vtedy, ak =1.
V tomto prípade sa hovorí o funkcii f(X) sa asymptoticky rovná funkcii g(X) alebo čo f(X) rastie rovnakým tempom ako g(X).
Definícia 2. f(X)=o( g(X)) pri X® x0, vtedy a len vtedy, ak =0.
Hovoria, že o X® x 0 f(X) rastie pomalšie ako g(X), alebo čo f(X) „existuje o-malé“ z g(X).
Definícia 3 . f(X)=O( g(X)) pri X® x0, vtedy a len vtedy, ak existuje konštanta C taká, že sup =C.
V tomto prípade to hovoria f(X) nerastie rýchlejšie ako g(X), alebo čokoľvek X® x 0 f(X) „je tam veľké O“ od g(X).
pomer f(X)=g(X)+o(h(X)) pri X®¥ to znamená f(x)-g(X)=o(h(X)). Podobne f(X)=g(X)+O(h(X)) znamená to f(X)-g(X)=O(h(X)).
V nerovniciach možno použiť aj výrazy O( ) a o( ). Napríklad nerovnosť X+o(X)2 £ X pri X®0 znamená, že pre akúkoľvek funkciu f(X) také, že f(X)=o(X), o X®¥ x+f(X)2 £ X pre všetky dostatočne veľké hodnoty X.
Ukážme niekoľko užitočných asymptotických rovnosti.
Polynóm sa asymptoticky rovná svojmu najvyššiemu členu:
pri X®¥; (4.1)
pri X®¥; (4.2)
pri X®¥ a a k¹0. (4.3)
Súčty mocnin celých čísel spĺňajú vzťah:
pri n®¥. (4.4)
Preto máme najmä n®¥
Vo všeobecnejšom prípade, kedy n®¥ a pre akékoľvek celé číslo k³0
; (4.6)
. (4.7)
Opakujúce sa vzťahy
Ilustrujme koncept rekurentných vzťahov s klasickým problémom, ktorý položil a študoval Fibonacci okolo roku 1200.
Fibonacci vyjadril svoj problém vo forme príbehu o rýchlosti rastu populácie králikov za nasledujúcich predpokladov. Všetko to začína jedným párom králikov. Každý pár králikov sa stane plodným (plodným) po mesiaci, potom každý pár porodí každý mesiac nový pár králikov. Králiky nikdy neumierajú a ich rozmnožovanie sa nikdy nezastaví. Nechaj F n- počet párov králikov v populácii po n mesiacov a nech sa táto populácia skladá z N n vrhové páry a O n„staré“ páry, t.j. F n = N n + O n. V nasledujúcom mesiaci teda nastanú tieto udalosti:
Stará populácia v ( n+1)-tý moment sa zvýši o počet pôrodov v danom čase n, t.j. O n+1 = O n + N n= F n;
Každý starý v určitom okamihu n pár produkuje v čase ( n+1) pár potomkov, t.j. Nn+1= C n.
Nasledujúci mesiac sa tento vzorec opakuje:
O n+2 = O n+1+ Nn+1= Fn+1,
Nn+2=O n+1;
spojením týchto rovností dostaneme Fibonacciho vzťah opakovania:
O n+2 + Nn+2=Fn+1 + O n+1,
Fn+2 = Fn+1 + F n. (4.8)
Voľba počiatočných podmienok pre Fibonacciho postupnosť nie je dôležitá; podstatné vlastnosti tejto postupnosti určuje rekurentný vzťah (4.8). Zvyčajne veril F0=0, F1= 1 (niekedy F0=F1=1).
Rekurencia (4.8) je špeciálny prípad homogénnych lineárnych rekurentných vzťahov s konštantnými koeficientmi:
x n = a 1 x n-1 + a 2 x n-2 +…ak x n-k, (4.9)
kde koeficienty a i nezávisia od n a x 1, x2, …, x k sa považujú za dané.
Existuje všeobecná metóda riešenia (t. j. nájdenie x n ako funkciu n) lineárne rekurentné vzťahy s konštantnými koeficientmi. Uvažujme túto metódu pomocou vzťahu (4.8) ako príkladu. Riešenie nájdeme vo formulári
F n=crn (4.10)
s trvalým S a r. Dosadením tohto výrazu do (4.8) dostaneme
cr + 2 = crn+ 1 + crn,
crn(rn-r-1)=0. (4.11)
Znamená to, že F n=crn je riešením, ak buď S=0, alebo r= 0 (a teda Fn = 0 pre všetkých n), a tiež (a to je zaujímavejší prípad), ak r 2 - r -1 = 0 a konštanta S svojvoľný. Potom z (4.11) vyplýva
r= alebo r = . (4.12)
Číslo "1,618" je známe ako "zlatý" pomer, od staroveku sa verilo, že trojuholník (obdĺžnik) so stranami 1 má najpríťažlivejšie proporcie.
Súčet dvoch riešení homogénnej lineárnej rekurencie je samozrejme tiež riešením a možno skutočne ukázať, že všeobecné riešenie Fibonacciho postupnosti je
F n= 
, (4.13)
kde sú konštanty S a s' sú určené počiatočnými podmienkami. Ak F 0 = 0 a F 1 = 1, dostaneme nasledujúcu sústavu lineárnych rovníc:
, (4.14)
ktorého riešenie dáva
c = -c" = . (4.15)
Lineárne rekurentné vzťahy s konštantnými koeficientmi. Základné definície a príklady rekurentných vzťahov Často sa riešenie jedného kombinatorického problému dá zredukovať na riešenie podobných problémov menšieho rozmeru pomocou nejakého vzťahu nazývaného rekurencia z latinského slova recurrere – vrátiť sa. Riešenie zložitého problému teda možno získať postupným hľadaním riešenia ľahších problémov a následným prepočítaním podľa rekurentných vzťahov, aby sme našli riešenie zložitého problému. Recidivujúci vzťah...
Zdieľajte prácu na sociálnych sieťach
Ak vám táto práca nevyhovuje, v spodnej časti stránky je zoznam podobných prác. Môžete tiež použiť tlačidlo vyhľadávania
Aranov Viktor Pavlovič Diskrétna matematika. Sekcia 2. Prvky kombinatoriky.
Prednáška 5
Prednášky 5. METÓDA OPAKOVANÝCH VZŤAHOV
Plán prednášok:
- Základné definície a príklady rekurentných vzťahov.
- Lineárne rekurentné vzťahy s konštantnými koeficientmi. Vzorec
Binet.
- Základné definície a príklady rekurentných vzťahov
Často sa riešenie jedného kombinatorického problému môže zredukovať na riešenie podobných problémov nižšej dimenzie pomocou nejakého vzťahu nazývaného rieka. R nájom (z latinského slova opakujúce sa - návrat). Riešenie zložitého problému teda možno získať postupným hľadaním riešenia ľahších problémov a ďalej n e výpočtom pomocou rekurentných vzťahov nájsť riešenie zložitého problému.
Rekurentný vzťah -tého rádumedzi prvkami postupnosti čísel sa nazýva vzorec formulára
(1)
Súkromné rozhodnutierekurentný vzťah je akýkoľvek nástupca b vzťah, ktorý mení vzťah (1) na identitu. Vzťah (1) im e existuje nekonečne veľa konkrétnych riešení, pretože prvé prvky sú sekvenčné O sti je možné nastaviť ľubovoľne. Napríklad postupnosť je p e opakujúci sa vzťah O riešenia, keďže identita platí.
Riešenie rekurencie -tého rádu sa nazýva bežné, ak ide o a závisí od ľubovoľných konštánt a výberom týchto konštánt môžeme dobre ale získajte akékoľvek riešenie tohto vzťahu. Napríklad pre pomery e niya
(2)
všeobecné riešenie by bolo
. (3)
V skutočnosti je ľahké skontrolovať, či sekvencia (3) mení vzťah (2) na identitu. Preto treba len ukázať, že každé riešenie vzťahu (2) môže dobre ale reprezentovať vo forme (3). Ale každé riešenie tohto vzťahu je jednoznačne určené. T s hodnotami a. Preto musíme dokázať, že pre ľubovoľné čísla a existuje m a aké hodnoty a aké
Keďže tento systém má riešenie pre ľubovoľné hodnoty a, potom riešenie (3) je skutočne všeobecným riešením vzťahu (2).
Príklad 1. Fibonacciho čísla.V roku 1202 slávny taliansky matematik Le O nardo z Pisy, ktorý je známejší pod prezývkou Fibonacci ( Fib o nacci - skrátene filius Bonacci , teda syna Bonacciho), bola napísaná kniha „ Liber abacci "(" Kniha a ha o počítadle“). Táto kniha sa k nám dostala vo svojej druhej verzii, ktorá sa datuje do roku 1228. Pozrime sa na jeden z mnohých problémov uvedených v tejto knihe.
Pár králikov prináša raz za mesiac potomstvo dvoch králikov (samice a samca) atď. a ako novonarodené králiky, dva mesiace po narodení, už rodia potomstvo. Koľko králikov sa objaví e res rok, ak na začiatku roka bol jeden pár králikov?
Zo stavu problému vyplýva, že o mesiac budú dva páry králikov. O dva mesiace neskôr som len prvý pár králikov dá potomstvo a vy dostanete 3 páry. A o ďalší mesiac dá pôvodný pár králikov aj pár králikov, ktorý sa objavil pred dvoma mesiacmi, potomstvo. Celkovo teda bude 5 párov králikov atď.
Označíme počtom párov králikov po mesiacoch od začiatku r O Áno. Potom o niekoľko mesiacov budú tieto páry a oveľa viac novonarodených párov. O tváre, koľko ich bolo na konci mesiaca, teda viac párov. Existuje teda r e aktuálny pomer
. (4)
Pretože potom postupne nájdeme: atď. Tieto čísla tvoria postupnosť
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,
volal blízko Fibonacciho a jeho členov - Fibonacciho čísla. Majú množstvo úžasných vlastností. Fibonacciho čísla súvisia s nasledujúcim kombinátorom ale náročná úloha.
Nájdite počet binárnych slov dĺžky, v ktorých sa nezhodujú žiadne dve 1 d riadok.
Nazvime tieto slová správne a ich počet označte . Rozdeľme množinu týchto pravidelných slov do dvoch tried: slová končiace na nulu a slová končiace na jednotku. Označme počet slov v týchto triedach a T zodpovedný. Podľa pravidla sčítania
(5)
Je zrejmé, že pre slovo končiace nulou tvoria prvé znaky obyčajné slovo dĺžky, alebo inými slovami, existuje bijekcia medzi množinou slov s pravidelnou dĺžkou končiacou nulou a množinou slov s pravidelnou dĺžkou, tj.
Ak platná dĺžka slova končí jednotkou, predchádzajúci znak tohto slova musí byť nula a prvé znaky musia tvoriť slovo platnej dĺžky. Rovnako ako v predchádzajúcom prípade máme opäť bijekciu medzi množinou regulárnych slov dĺžky končiacich na jednotku a množinou regulárnych slov dĺžky. Preto . Zo vzorca (5) získame rekurzívny vzťah O
. (6)
Pre tento výpočet je potrebné použiť rekurentný vzťah S zmena všetkých predchádzajúcich hodnôt. Napríklad, ak potrebujeme poznať počet pravidiel b slová s 10 znakmi, potom ho možno nájsť postupným vyplňovaním nasledujúcej tabuľky b tvár:
stôl 1
Prvé dve hodnoty sa nachádzajú priamo (-slová 0 a 1; - slová 000, 010, 101) a zvyšok - podľa vzorca (6).
Príklad 2 Problém umiestnenia zátvoriek vo výraze s neasociatívnou priehradkou prevádzka. Nech „“ označuje nejakú binárnu operáciu. Zvážte v s výraz, v ktorom symbol označuje nejakú binárnu neasociáciu a aktívna prevádzka. Koľko rôznych spôsobov usporiadania zátvoriek je v tomto s raz e nii?
Príkladom neasociatívnej operácie je vektorový súčin. Ďalším príkladom je obvyklé sčítanie a násobenie vykonávané na počítači. V s a že zastúpenie každého čísla v pamäti počítača je obmedzené určitým n počet číslic, pri vykonávaní každej operácie sa vyskytne chyba a m Očakávaný výsledok týchto chýb závisí od usporiadania zátvoriek. Nechajte - stroj nula . Znamená to, že. Potom kým.
Označme počet možných spôsobov usporiadania zátvoriek pomocou. Potom
Operáciu nazývame podmienene produkt. Pre ľubovoľné rozdeľujeme všetky spôsoby usporiadania zátvoriek do tried, vrátane v -tej triede spôsobov, ako a chala, súčin prvého a posledného operandu sa počíta s určitou vzdialenosťou a nové zátvorky a potom sa vypočíta ich súčin:
(7)
kde.
Podľa definície je počet spôsobov usporiadania zátvoriek na výpočet prvých operandov rovnaký, posledný - . Podľa produktového pravidla počet aranžmánov O strana pre výraz (4) je rovnaká. Podľa pravidla sčítania
, (8)
Napríklad .
- Lineárne rekurentné vzťahy s konštantnými koeficientmi
Nech funkcia vo vzťahu (1) je priamka th noe
, (9)
kde sú nejaké čísla. Takéto pomery sa nazývajú lineárne pomery riešenia -tého rádu s konštantnými koeficientmi.
Najprv podrobne preskúmame vzťahy druhého rádu a potom pristúpime k o b aktuálna príležitosť. At , zo vzorca (9) dostaneme
, . (10)
Riešenie týchto vzťahov je založené na nasledujúcich ľahko dokázateľných tvrdeniach nijakh.
Lema 1. Nech je riešením vzťahu (10) a je ľubovoľné číslo. Potom sa rieši aj postupnosť a jesť tento pomer.
Lema 2. Nechajte a buďte riešeniami O riešenia (10). Potom je postupnosť tiež som je riešením tohto vzťahu.
Tieto dve jednoduché lemy vedú k nasledujúcemu dôležitému záveru. naberačka P existencia všetkých možných sekvencií s operáciami pokoja R dinatické sčítanie a násobenie skalárom tvorí vektorový priestor. naberačka P počet postupností, ktoré sú riešením vzťahu (10) predstavuje s O bojovať s podpriestorom tohto priestoru. Obklopujúci priestor všetkého možného O postupnosti je nekonečne-rozmerný, ale podpriestor riešení lineárneho rekurentu T vzťah má konečný rozmer rovný rádu rovnice e niya.
Lema 3. Rozmer priestoru riešenia rekurentného vzťahu (10) je rovný dvom.
Z Lemy 3 vyplýva, že na určenie všetkých riešení rovnice (12) je potrebné nájsť dve lineárne nezávislé riešenia. Akékoľvek iné riešenie bude b je lineárna kombinácia týchto základných riešení.
Zvážte rekurentný vzťah prvého rádu
, (11)
kde je konštanta.
Ak, potom od (11) máme
, (12)
to znamená, že riešením rekurzívnej rovnice prvého rádu je geometrická postupnosť.
Riešenie rekurencie druhého rádu budeme hľadať aj v tvare (12). Potom dosadením (12) do (9) dostaneme
. (13)
Pre =0 máme nulové riešenie, ktoré nás nezaujíma. Vzhľadom na to, rozdelíme posledný pomer takto:
(14)
Geometrická progresia (12) je teda riešením rekurentného vzťahu (10), ak je menovateľom progresie koreň kvadratickej rovnice. e nija (14). Táto rovnica sa nazývacharakteristická rovnicapre opakujúce sa coo t nosenie (9).
Konštrukcia základných riešení závisí od koreňov a charakteristickej rovnice (14).
- (). V tomto prípade máme dve riešenia a, ktoré l a neznámy sims. Aby sme si to overili, ukážeme to zo vzorca
(15)
vhodnou voľbou konštánt možno získať akékoľvek riešenie vzťahu (10). Zvážte ľubovoľné riešenie. Vyberáme konštanty a tak, že pre a:
(16)
Determinant lineárneho systému (16)
systém má teda jedinečné riešenie, čo znamená, že vzorec (15) je všeobecný р e vzťah (10).
- . V prípade viacerých koreňov má charakteristická rovnica (13) tvar resp. Potom a pre vzťah (10) p O dostaneme rovnicu, ktorá dáva dve základné riešenia a. Všeobecné riešenie je znázornené ako
. (17)
V prípade vzťahu t. rádu (9) sa vyskytujú výroky podobné tým, ktoré sa uvažujú pre rovnice 2. rádu.
- Množina všetkých riešení rovnice (9) je podpriestor v pr O priestor všetkých sekvencií.
- Rozmer tohto priestoru je rovnaký, to znamená, že každé riešenie je jednoznačne určené svojimi prvými hodnotami.
- Na určenie základu podpriestoru riešení, charakteristika e rovnica
. (18)
Polynóm
(19)
volal charakteristický polynómrekurzívny vzťah (9).
- Ak má charakteristická rovnica rôzne korene, potom všeobecné riešenie rekurentného vzťahu (9) má tvar
. (20)
Pre dané počiatočné hodnoty riešenia sú konštanty n a odísť zo systému
- Ak je koreňom charakteristickej rovnice násobnosti, potom vzťah (9) má nasledujúce riešenia
Nech charakteristická rovnica (18) má korene: ,…, násobnosti s O zodpovedne, ..., navyše. Potom charakteristický súbor O pojem a všeobecné riešenie vzťahu (9) sú znázornené ako
Príklad 3. Binetov vzorec . Stanovme si úlohu získať vzorec v explicitnom tvare pre h a sedel Fibonacci. Aby sme to dosiahli, nájdeme riešenie pre rekurentný vzťah (4) za podmienky, že. Zostavíme charakteristickú rovnicu, nájdeme jej korene a získame všeobecné riešenie. Konštanty a definície e lim z počiatočných podmienok: . Potom buď
, (21)
kde je zlatý rez. Vzorec (21) sa nazýva Binetov vzorec . V čom. Z Binetovho vzorca to vyplýva.
Ďalšie súvisiace diela, ktoré by vás mohli zaujímať.vshm> |
|||
| 3792. | Racionalita pomerových ukazovateľov v majetku podniku | 113,83 kB | |
| Súvaha je hlavnou formou účtovnej závierky. Charakterizuje majetok a finančný stav organizácie ku dňu, ku ktorému sa zostavuje účtovná závierka. Súvaha odzrkadľuje zostatky všetkých účtovných účtov k dátumu zostavenia účtovnej závierky. Tieto ukazovatele sú v súvahe uvedené v určitom zoskupení. | |||
| 8407. | konštantná metóda | 17,82 kB | |
| O objektovej metóde sa hovorí, že má vlastnosť nemennosti (stálosti), ak sa po jej vykonaní stav objektu nezmení. Ak vlastnosť nemennosti neovládate, jej poskytnutie bude závisieť výlučne od zručnosti programátor. Ak nemenná metóda vytvára počas vykonávania cudzie účinky, výsledok môže byť najneočakávanejší a je veľmi ťažké ladiť a udržiavať takýto kód. | |||
| 13457. | Metóda fázovej roviny | 892,42 kB | |
| Metódu fázovej roviny prvýkrát aplikoval na štúdium nelineárnych systémov francúzsky vedec Henri Poincaré. Hlavnou výhodou tejto metódy je presnosť a viditeľnosť analýzy pohybov nelineárneho systému. Metóda je kvalitatívna | |||
| 2243. | METÓDA MOŽNÝCH NÁVODOV | 113,98 kB | |
| Myšlienka metódy možných smerov MRI spočíva v tom, že v každom nasledujúcom bode existuje smer zostupu, takže pohyb bodu v tomto smere na určitú vzdialenosť neporušuje obmedzenia problému. Smer určený vektorom sa nazýva možný smer v bode, ak dostatočne malý pohyb zo smeru neprejde bod mimo povolenú plochu m. Je zrejmé, že ak je vnútorným bodom množiny, potom akýkoľvek smer v tomto smere bod je možný. Možné... | |||
| 12947. | METÓDA HARMONICKEJ LINEARIZÁCIE | 338,05 kB | |
| Pokiaľ ide priamo o metódu harmonickej linearizácie, budeme predpokladať, že skúmaný nelineárny systém je zredukovaný na formu znázornenú v. Nelineárny prvok môže mať akúkoľvek charakteristiku, pokiaľ je integrovateľný bez diskontinuít druhého druhu. Transformácia tejto premennej na príklad nelineárnym prvkom s mŕtvou zónou je znázornená na obr. | |||
| 2248. | Grafická metóda riešenia LLP | 219,13 kB | |
| Body ležiace vo vnútri a na hranici tejto oblasti sú platnými rovinami. Totiž všetky body segmentu AB sú optimálnymi plánmi úlohy, na ktorých je dosiahnutá maximálna hodnota lineárneho tvaru. Metóda postupného zlepšovania plánu Metóda je založená na usporiadanom sčítaní rohových bodov množiny problémových plánov v smere zväčšovania alebo zmenšovania lineárneho tvaru a obsahuje tri podstatné body. Najprv je špecifikovaná metóda výpočtu základnej línie. | |||
| 7113. | Metóda harmonickej linearizácie | 536,48 kB | |
| Metóda harmonickej linearizácie Keďže táto metóda je približná, dosiahnuté výsledky sa budú blížiť pravde iba vtedy, ak budú splnené určité predpoklady: Nelineárny systém by mal obsahovať iba jednu nelinearitu; Lineárnou časťou systému by mal byť dolnopriepustný filter, ktorý tlmí vyššie harmonické, ktoré sa vyskytujú v limitnom cykle; Metóda je použiteľná len pre autonómne systémy. Študujeme voľný pohyb systému, teda pohyb za nenulových počiatočných podmienok pri absencii vonkajších vplyvov.... | |||
| 10649. | Indexová metóda analýzy | 121,13 kB | |
| jednotlivé indexy. Všeobecné agregované indexy. Priemerné prevedené indexy. Indexy variabilného a konštantného zloženia indexy štrukturálnych posunov. | |||
| 12914. | Metóda najmenších štvorcov | 308,27 kB | |
| Z teoretických úvah to vieme. Preto môžeme povedať, že našou úlohou je nakresliť priamku čo najlepším spôsobom. Budeme predpokladať, že celá chyba spočíva v. Z úvah vyberieme požadované koeficienty tak, aby náhodné sčítanie bolo najmenšie. | |||
| 9514. | Účtovná metóda | 1002,23 kB | |
| Účtovné rahunki, ktoré їх pobudova. Vіn sladєtsya z počet prvkovіv golovnі z yakikh: dokumentácia; inventár; rahunki; podzáznam; hodnotenie; kalkulácia; rovnováha; solídnosť. Rahunki účtovníctvo uznané za výskyt prítomnosti aktív a pasív. Účtovné rahunki, ktoré їх pobudova. | |||
OPAKOVANÉ VZŤAHY
OPAKOVANÉ VZŤAHY
(z lat. recur-rens, rod case recurrentis - vracajúci sa) - f-ky rovnakého typu, ktoré spájajú určitú postupnosť za sebou (môže ísť o postupnosť čísel, f-cie atď. ). Podľa povahy objektov spojených s R. s. môžu byť tieto vzťahy algebraické, funkčné, diferenciálne, integrálne atď.
Naíb. známa trieda R. s. sú rekurentné funkcie pre špeciálne funkcie.Áno, pre valcové funkcie Z m (x)P. S vyzerať ako
Umožňujú podľa funkcie Z m0 (x) nájsť funkcie Z m (x)at T= T 0 b 1, T 0 b 2 atď. alebo napríklad podľa hodnôt funkcií 
v určitom okamihu X 0 0 nájdite (v numerických výpočtoch) hodnotu ktorejkoľvek z funkcií
V tom istom bode (tu m 0 - akékoľvek reálne číslo).
DR. významná trieda R. s. uveďte početné metódy postupných aproximácií (porov. iteračná metóda); tu sú metódy poruchy teórie.
V kvantovej mechanike existuje ešte jeden typ R. s., spájajúci vektory v Hilbertovom priestore stavov. Napríklad stacionárne harmónie, oscilátory sú parametrizované nezápornými celými číslami. Zodpovedajúce vektory, označené , kde n- celý, s rôznym n možno navzájom získať pôsobením operátorov vytvárania + a ničenie a:
Tieto vzťahy možno vyriešiť vyjadrením ľubovoľného vektora v termínoch (stav najnižšej energie, h = 0):
Zovšeobecnením tejto konštrukcie je reprezentácia druhá kvantizácia v kvantovej štatistike. mechanika a kvantová teória poľa (pozri Fock priestor).
Typickým príkladom R. s. v štatistike mechanika - rovnice pre parciálne distribučné funkcie, ktoré tvoria Bogolyubov reťazec (pozri. Bogolyubovove rovnice); znalosť takýchto f-tionov vám umožňuje nájsť všetky termodynamické. charakteristiky systému.
V kvantovej teórii poľa dynamika. obsiahnutých napríklad v Greenove funkcie. Pre ich výpočet rôzne aproximácie, najčastejšie - výpočty poruchovej teórie. Alternatívny prístup je založený na integro-diferenciálnom Dysonove rovnice, ktoré sú R. s.: rovnica pre dvojbodovú Greenovu funkciu obsahuje štvorbodovú atď. Podobne ako Bogolyubovova rovnica, aj táto sústava sa dá vyriešiť iba „prerušením“ reťazca (miesto „pretrhnutia“ sa zvyčajne vyberá z fyzikálnych hľadísk a určuje výsledný ).
Iný typ R. s. v kvantovej teórii poľa - Horda identít v teóriách kalibračné polia. Tieto identity predstavujú aj reťaz integro-diferenciálnych vzťahov spájajúcich Greenove funkcie s dec. počet vonkajších čiar, p sú dôsledkom meracej invariantnosti teórie. Zohrávajú rozhodujúcu úlohu pri kontrole kalibračnej symetrie počas postupu renormalizácia.
Napokon, sama osebe je tiež opakujúcim sa postupom: v každom kroku (v každej nasledujúcej slučke) protitermíny, získané z výpočtu diagramov s menším počtom slučiek (podrobnejšie pozri R prevádzka).A. M. Malokostov.
Fyzická encyklopédia. V 5 zväzkoch. - M.: Sovietska encyklopédia. Šéfredaktor A. M. Prochorov. 1988 .
Pozrite si, čo je „RECURRENT RELATIONS“ v iných slovníkoch:
opakujúce sa vzťahy-- [L.G. Sumenko. Anglický ruský slovník informačných technológií. M .: GP TsNIIS, 2003.] Témy informačné technológie vo všeobecnosti EN rekurentné vzťahy ... Technická príručka prekladateľa
- (Weberove funkcie) všeobecný názov pre špeciálne funkcie, ktoré sú riešeniami diferenciálnych rovníc získaných aplikáciou metódy separácie premenných pre rovnice matematickej fyziky, ako je Laplaceova rovnica, rovnica ... ... Wikipedia
Alebo Josephusov rým je známy matematický problém s historickým podtextom. Úloha je založená na legende, že oddiel Josephusa Flavia, ktorý bránil mesto Yodfat, sa nechcel vzdať nadvláde Rimanov, ktorí zablokovali jaskyňu. ... ... Wikipedia
Pafnuty Lvovich Chebyshev V matematike sa nekonečná postupnosť reálnych polynómov nazýva postupnosť ortogonálnych polynómov ... Wikipedia
Tento článok je navrhnutý na vymazanie. Vysvetlenie dôvodov a zodpovedajúcu diskusiu možno nájsť na stránke Wikipédie: Na vymazanie / 22. novembra 2012. Kým prebieha diskusia ... Wikipedia
Padovanova postupnosť je celočíselná postupnosť P(n) s počiatočnými hodnotami a lineárnym rekurentným vzťahom. Prvé hodnoty P(n) sú 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 , 37, 49, 65, 86, 114, 151, 200, 265 ... Wikipedia
Hermitove polynómy určitého tvaru sú postupnosťou polynómov v jednej reálnej premennej. Hermitove polynómy vznikajú v teórii pravdepodobnosti, v kombinatorike a fyzike. Tieto polynómy sú pomenované po Charlesovi Hermiteovi. Obsah 1 ... ... Wikipedia
- (Besselove funkcie) riešenia Zv(z) Besselovej rovnice, kde parameter (index) v je ľubovoľné reálne alebo komplexné číslo. V aplikáciách sa často stretávame s rovnicou, ktorá závisí od štyroch parametrov: ktorých riešenia sú vyjadrené v C... Fyzická encyklopédia
Metóda riešenia sústavy lineárnej algebraiky. rovnice A x= b s hermitovskou nesingulárnou maticou A. Spomedzi priamych metód je najúčinnejšia pri implementácii na počítači. Výpočtová schéma metódy je vo všeobecnosti založená na Hermitovskej faktorizácii ... ... Matematická encyklopédia
Modifikované Besselove funkcie sú Besselovými funkciami čisto imaginárneho argumentu. Ak v diferenciálnej Besselovej rovnici nahradíme výraz, bude mať tvar Táto rovnica sa nazýva modifikovaná Besselova rovnica ... Wikipedia
Recidívny vzťah má rozkaz k , ak umožňuje vyjadrenie f(n+k) pomocou f(n), f(n+1), …, f(n+k-1).
Príklad.
f(n+2)=f(n)f(n+1)-3f2(n+1)+1 je rekurencia druhého rádu.
f(n+3)=6f(n)f(n+2)+f(n+1) je opakujúci sa vzťah tretieho rádu.
Ak je daný rekurentný vzťah k-tého rádu, potom ho môže spĺňať nekonečne veľa postupností, keďže prvých k prvkov postupnosti možno nastaviť ľubovoľne - neexistujú medzi nimi žiadne vzťahy. Ale ak je zadaných prvých k členov, potom sú všetky ostatné prvky jednoznačne určené.
Pomocou rekurentného vzťahu a počiatočných členov je možné vypísať členy postupnosti jeden po druhom a skôr či neskôr dostaneme ktorýkoľvek z jej členov. Ak však potrebujete poznať iba jeden konkrétny člen postupnosti, potom nie je racionálne počítať všetky predchádzajúce. V tomto prípade je vhodnejšie mať vzorec na výpočet n-tého členu.
Riešenie rekurentného vzťahu volá sa ľubovoľná postupnosť, pre ktorú daný vzťah platí identicky.
Príklad. Postupnosť 2, 4, 8, …, 2 n je riešením vzťahu f(n+2)=3∙f(n+1) – 2∙f(n).
Dôkaz. Spoločný člen postupnosti je f(n)=2 n . Takže f(n+2)= 2 n+2, f(n+1)= 2n+1. Pre ľubovoľné n platí identita 2 n+2 =3∙2 n+1 – 2∙2 n. Preto pri dosadení postupnosti 2 n do vzorca f(n+2)=3f(n+1) – 2f(n) je vzťah splnený identicky. 2 n je teda riešením uvedeného vzťahu.
Riešenie rekurentného vzťahu volá sa k-tý rád všeobecný, ak závisí od k ľubovoľných konštánt α 1 , α 2 , … α k a výberom týchto konštánt možno získať ľubovoľné riešenie tohto vzťahu.
Príklad. Vzťah opakovania je daný: f(n+2)=5f(n+1)-6f(n). Dokážme, že jeho všeobecné riešenie má tvar: f(n)= α 2 n + β3 n .
1. Najprv dokážeme, že postupnosť f(n)=α 2 n + β3 n je riešením rekurentného vzťahu. Dosaďte túto postupnosť do vzťahu opakovania.
f(n)= α 2 n + β 3 n, takže f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 teda
5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙ (α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f( n+2).
Platí rekurentný vzťah, preto α 2 n + β 3 n je riešením tohto rekurentného vzťahu.
2. Dokážme, že akékoľvek riešenie vzťahu f(n+2)=5f(n+1)–6f(n) možno zapísať ako f(n)= α 2 n + β 3 n . Ale akékoľvek riešenie rekurencie druhého rádu je jednoznačne určené hodnotami prvých dvoch členov sekvencie. Preto stačí ukázať, že pre ľubovoľné a=f(1) ab=f(2) existujú α a β také, že 2 α +3 β =a a 4 α +9 β =b. Je ľahké vidieť, že systém rovníc má riešenie pre akékoľvek hodnoty a a b.
Teda f(n)= α 2 n + β 3 n je všeobecným riešením rekurentného vzťahu f(n+2)=5f(n+1)–6f(n).
Lineárne rekurentné vzťahy s konštantnými koeficientmi
Neexistujú žiadne všeobecné pravidlá na riešenie rekurentných vzťahov, ale existuje často sa vyskytujúca trieda rekurentných vzťahov, pre ktorú je známy algoritmus na ich riešenie. Ide o lineárne rekurentné vzťahy s konštantnými koeficientmi, t.j. typové pomery:
f(n+k)=c1f(n+k-1)+c2f(n+k-2)+...+ckf(n).
Nájdime riešenie všeobecného lineárneho rekurentného vzťahu s konštantnými koeficientmi prvého rádu.
Lineárny rekurentný vzťah s konštantnými koeficientmi prvého rádu má tvar: f(n+1)=c f(n).
Nech f(1)=a, potom f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, podobne ako f(4)=c 3 ∙a a tak ďalej, všimnite si, že f(n)=cn -1 ∙f(1).
Dokážme, že postupnosť c n -1 ∙f(1) je riešením rekurencie prvého rádu. f(n)=c n -1 ∙f(1), teda f(n+1)=c n f(1). Dosadením tohto výrazu do vzťahu dostaneme identitu c n f(1)=с∙ c n -1 ∙f(1).
Uvažujme teraz podrobnejšie lineárne rekurentné vzťahy s konštantnými koeficientmi druhého rádu , teda vzťahy formy
f(n+2)=C1∙f(n+1)+C2∙f(n). (*).
Všimnite si, že všetky úvahy platia aj pre vzťahy vyššieho rádu.
Vlastnosti roztoku:
1) Ak je postupnosť x n riešením (*), potom postupnosť a∙x n je tiež riešením.
Dôkaz.
x n je riešenie (*), teda x n +2 = C1 x n + 1 + C2 x n . Obe strany rovnosti vynásobíme a. Dostaneme a∙x n +2 =a∙(С 1 ∙x n +1 + С 2 ∙x n)= С 1 ∙a∙x n +1 + С 2 ∙a∙x n . To znamená, že ax n je riešenie (*).
2) Ak postupnosti x n a y n sú riešenia (*), potom postupnosť x n + y n je tiež riešením.
Dôkaz.
x n a y n sú riešenia, takže platia nasledujúce identity:
x n +2 \u003d C 1 x n +1 + C 2 x n.
yn+2=Ciyn+1+C2yn.
Pridajme dve rovnosti po členoch:
xn +2 +yn +2 =С 1 ∙xn +1 +С 2 ∙xn + С 1 ∙yn +1 +С 2 ∙yn = С 1 ∙(xn +1 + yn +1)+С 2 ∙(xn +yn). To znamená, že x n + y n je riešením (*).
3) Ak je r 1 riešením kvadratickej rovnice r 2 =С 1 r+С 2, potom postupnosť (r 1) n je riešením vzťahu (*).
r 1 je riešením kvadratickej rovnice r 2 =C 1 r+C 2, teda (r 1) 2 =C 1 r 1 +C 2 . Vynásobme obe strany rovnosti (r 1) n . Získajte
r 1 2 r 1 n \u003d (C 1 r 1 + C 2) r n.
r 1 n +2 \u003d C 1 r 1 n +1 + C 2 r 1 n.
To znamená, že postupnosť (r 1) n je riešením (*).
Z týchto vlastností to vyplýva spôsob riešenia lineárne rekurentné vzťahy s konštantnými koeficientmi druhého rádu:
1. Zostavte charakteristickú (kvadratickú) rovnicu r 2 =C 1 r+C 2 . Nájdite jej korene r 1, r 2. Ak sú korene rôzne, potom všeobecné riešenie je f(n)= ar 1 n + βr 2 n .
2. Nájdite koeficienty a a β. Nech f(0)=a, f(1)=b. Systém rovníc
má riešenie pre ľubovoľné a a b. Tieto riešenia sú
Úloha . Poďme nájsť vzorec pre bežný člen Fibonacciho postupnosti.
Riešenie .
Charakteristická rovnica má tvar x 2 \u003d x + 1 alebo x 2 -x-1 \u003d 0, jej korene sú čísla, čo znamená, že všeobecné riešenie má tvar f (n) \u003d 
. Ako je ľahké vidieť, z počiatočných podmienok f(0)=0, f(1)=1 vyplýva, že a=-b=1/Ö5, a teda všeobecné riešenie Fibonacciho postupnosti má tvar :
.
Prekvapivo tento výraz preberá celočíselné hodnoty pre všetky prirodzené hodnoty n.
