Rekurentne metode. Opća i posebna rješenja rekurentnih relacija Metoda matričnih rekurentnih relacija i karakteristična jednačina

U matematici se često koriste termini kao što su “rekurzivne funkcije”, “ponavljajuće sekvence”, “rekurzivne relacije”, “rekurzivni algoritmi”. Svi ovi pojmovi imaju isti korijen, koji dolazi od latinske riječi hesiggege - vratiti se. Ono što je zajedničko rekurzivnim funkcijama, rekurzivnim algoritmima i rekurentnim sekvencama je da je da bi se izračunala sljedeća vrijednost funkcije, dobila sljedeća implementacija algoritma ili odredio sljedeći član niza, potrebno se pozvati na njihov prethodni vrijednosti, izračunate ranije. Zauzvrat, izračunavanje prethodnih vrijednosti zahtijeva pristup potrebnim vrijednostima ​​izračunatim prije toga, itd. Dakle, da bi se dobila vrijednost funkcije, implementacija algoritma ili vrijednost člana serije na um korak morate znati njihove vrijednosti (P- 1) korak, a samim tim i prvi korak. Pravilo koje određuje kako izračunati sljedeću vrijednost funkcije ili sljedećeg člana niza, uzimajući u obzir činjenicu da su ove vrijednosti poznate za prvi korak, naziva se relacija recidiva. Razvoj rekurentnih odnosa jedan je od metoda za rješavanje različitih problema. U kombinatorici se ova metoda vrlo široko koristi.

Najjednostavniji primjer rekurentne relacije su formule za izračunavanje broja permutacija skupa elemenata. Ove formule izgledaju kao R x = 1, R p = R p _ x p a može se dobiti na sljedeći način.

Neka bude P elementi /, /2, ..., /„, skupovi I. Liu

Bilo koja permutacija ovih elemenata može se dobiti na sljedeći način: uzmite neku permutaciju elemenata /, /2, ..., i na sve moguće načine između naznačenih elemenata, uključujući početak i kraj, postavite element / i. Jasno je da će takvih metoda biti P. Kao posljedica OVOG, IZ permutacije /, /2, ..., /d_, dobiće se P permutacije. To znači da su permutacije iz P elementi u P puta više od permutacija iz P-1 set elemenata I. Ovo uspostavlja relaciju recidiva R p = R p _ x p. Koristeći ovu relaciju, konzistentno dobijamo P p -pP p _ x =p(p-)P p _ 2 - p(p - )(p -2)...2P X. Ali R x - 1, budući da se od jednog elementa može napraviti samo jedna permutacija. Zbog toga P p = p(p-1)(« - 2)___2-1 = P. Na osnovu navedenog

Važi i sljedeći unos: R p = (P-jedanaest! = 1.

Hajde sada da damo primer ponavljajućeg niza brojeva, koji se često naziva Fibonačijevi brojevi, nazvan po italijanskom matematičaru iz 13. veka koji ga je uspostavio kao rezultat rešavanja sledećeg problema. Par zečeva proizvodi leglo od dva zeca (ženku i mužjaka) jednom mjesečno. Novorođeni kunići takođe imaju potomstvo dva mjeseca nakon rođenja. Koliko će zečeva biti za godinu dana ako je na početku bio jedan par zečeva?

Iz uslova zadatka proizilazi da će za mjesec dana biti dva para zečeva (prvi par zečeva će donijeti potomstvo). Za dva meseca - tri para, a za tri meseca - pet parova, pošto će par koji se pojavi posle prvog meseca roditi.

Označimo sa /„ broj parova zečeva iza P mjeseci od početka godine. Zatim na početku godine / 0 = 1, nakon mjesec dana /, = 2, nakon dva mjeseca / 2 = / 0 + /, = 3, nakon tri mjeseca / 3 = = / 2 + /1 = 5. Stoga, u opštem slučaju, da bismo izračunali broj zečeva na kraju bilo kojeg mjeseca, dobijamo rekurentnu relaciju /„ = + / i _ 2. Ovaj odnos to omogućava

izračunajte broj parova zečeva na kraju godine koristeći izraz /12 = /n + /Yu I pod uslovom da je / 0 = 1, /, = 2. To je jednako 377. Brojevi koji se dobiju kao rezultat primjene date rekurentne relacije, tj. Niz 1, 2, 3, 5, 8, 13, ... nazivaju se Fibonačijevi brojevi. Važno je napomenuti da se korištenjem rekurentne relacije koja ovo opisuje numeričke serije, mnogi problemi kombinatorike su riješeni. Evo jednog od njih.

Pronađite broj nizova nula i jedinica dužine P one u kojima dvije jedinice ne stoje jedna do druge. Uvjerimo se da je ovaj problem riješen korištenjem rekurentne relacije

/i = /“-1 + /i- 2-

Uzmite bilo koju sekvencu iz P+1 nule i jedinice takve da ne postoje dvije jedinice u nizu. Može završiti na nulu ili jedan. Ako se niz završava nulom, može se odbaciti i niz dužine P, u kojoj dvije jedinice nisu susjedne. Naprotiv, ako uzmemo ovaj niz i dodijelimo mu nulu na kraju, dobićemo niz dužine n + 1, u kojoj dvije cjeline nisu susjedne.

Neka broj sekvenci dužine P+1, u kojem dvije jedinice nisu susjedne i koje se završavaju na nulu, jednako je g n . Sada uzmite niz LENGTH /7 + 1, u kojem dva nisu susjedna i koji se završava jednim. Pošto dvije jedinice nisu susjedne, posljednjem u nizu prethodi nula, tj. niz se završava sa 01. Odbacivanjem ovih brojeva, dobijamo niz dužine P - 1, u kojoj dvije jedinice nisu u nizu. Broj takvih sekvenci g n_^. Pošto je svaki niz dužine n + 1, u kojem dvije jedinice nisu u nizu završava se na jedan ili nulu, za ukupan broj takvih nizova, koristeći pravilo sume dobijamo g n+ ^ - g n + g n_x. Štaviše, za sekvence dužine P= 1 postoje dva niza: 0 i 1, u kojima dva nisu susjedna, kao rezultat

vie what g l - 2. Za sekvence dužine P - 2 postoje tri niza u kojima dva nisu susjedna: 00, 01 i 10. Dakle = 3. Dakle, rekurentna relacija g n+l = g n + g n_( , g^ = 2, g 2=3 je ekvivalentno rekurentnoj relaciji / i+1 = /„ + /, =2, / 2 = 3, koja opisuje niz

Fibonacci. Stoga, za bilo koje /7 = 1,2, ..., koristeći ovu relaciju, možemo riješiti gore formulirani problem.

Treba napomenuti da je izvođenje rekurentnih odnosa ponekad jednostavno, a ponekad zahtijeva ozbiljan napor. Za neke probleme su rekurentni odnosi jednostavni, za druge složeni. Opšta neugodnost rekurentnih relacija je da je za izračunavanje člana niza potrebno izračunati sve njegove prethodne članove.

Relacija recidiva ima nalog k , ako vam omogućava da izrazite f(n+k) u terminima f(n), f(n+1), …, f(n+k-1).

Primjer.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – rekurentna relacija drugog reda.

f(n+3)=6f(n)f(n+2)+f(n+1) – rekurentna relacija trećeg reda.

Ako je data rekurentna relacija k-tog reda, onda je može zadovoljiti beskonačno mnogo nizova, budući da se prvih k elemenata niza može specificirati proizvoljno - među njima nema relacija. Ali ako je dato prvih k članova, onda su svi ostali elementi određeni jedinstveno.

Koristeći rekurentnu relaciju i početne članove, možemo ispisati članove niza jedan za drugim, i prije ili kasnije ćemo dobiti bilo koji od njegovih članova. Međutim, ako trebate znati samo jedan određeni član niza, onda je iracionalno izračunati sve prethodne. U ovom slučaju je zgodnije imati formulu za izračunavanje n-tog člana.

Rješavanje rekurentne relacije Svaki niz za koji ova relacija vrijedi identično se zove.

Primjer. Niz 2, 4, 8, …, 2 n je rješenje za relaciju f(n+2)=3∙f(n+1) – 2∙f(n).

Dokaz. Opšti član niza je f(n)=2 n . To znači f(n+2)= 2 n+2, f(n+1)= 2n+1. Za bilo koje n vrijedi identitet 2 n+2 =3∙2 n+1 – 2∙2 n. Dakle, kada se niz 2 n zameni u formulu f(n+2)=3f(n+1) – 2f(n), relacija je zadovoljena identično. To znači da je 2 n rješenje navedene relacije.

Rješavanje rekurentne relacije k-ti red se zove general, ako zavisi od k proizvoljnih konstanti α 1 , α 2 , … α k i odabirom ovih konstanti može se dobiti bilo koje rješenje ove relacije.

Primjer. Rekurentna relacija je data: f(n+2)=5f(n+1)-6f(n). Dokažimo to zajednička odluka ima oblik: f(n)= α 2 n + β3 n.

1. Prvo dokazujemo da je niz f(n)=α 2 n + β3 n rješenje rekurentne relacije. Zamijenimo ovaj niz u rekurentnu relaciju.

f(n)= α 2 n + β 3 n, što znači f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , onda

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).

Rekurentna relacija je zadovoljena, stoga je α 2 n + β 3 n rješenje za ovu rekurentnu relaciju.

2. Dokažimo da se svako rješenje relacije f(n+2)=5f(n+1)–6f(n) može zapisati kao f(n)= α 2 n + β 3 n. Ali svako rješenje rekurentne relacije drugog reda je jednoznačno određeno vrijednostima prva dva člana niza. Dakle, dovoljno je pokazati da za bilo koje a=f(1) i b=f(2) postoje α i β takvi da je 2 α +3 β =a i 4 α +9 β =b. Lako je vidjeti da sistem jednačina ima rješenje za bilo koje vrijednosti a i b.

Dakle, f(n)= α 2 n + β 3 n je opšte rešenje rekurentne relacije f(n+2)=5f(n+1)–6f(n).

Linearne rekurentne relacije sa konstantni koeficijenti

Za rješavanje rekurentnih odnosa opšta pravila ne, ali postoji često susrećena klasa rekurentnih relacija za koje je poznat algoritam za njihovo rješavanje. To su linearne rekurentne relacije sa konstantnim koeficijentima, tj. odnosi oblika:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Nađimo rješenje za opću linearnu rekurentnu relaciju sa konstantnim koeficijentima prvog reda.

Linearna rekurentna relacija sa konstantnim koeficijentima prvog reda ima oblik: f(n+1)=c f(n).

Neka je f(1)=a, tada je f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, slično f(4)=c 3 ∙a i tako dalje, imajte na umu da je f(n)=c n -1 ∙f(1).

Dokažimo da je niz c n -1 ∙f(1) rješenje rekurentne relacije prvog reda. f(n)=c n -1 ∙f(1), što znači f(n+1)=c n f(1). Zamjenom ovog izraza u relaciju dobijamo identičnost c n f(1)=s∙ c n -1 ∙f(1).

Pogledajmo sada izbliza linearne rekurentne relacije sa konstantnim koeficijentima drugog reda , odnosno odnosi oblika

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

Imajte na umu da sva razmišljanja ostaju ista za relacije višeg reda.

Svojstva rješenja:

1) Ako je niz x n rješenje za (*), onda je niz a∙x n također rješenje.

Dokaz.

x n je rješenje za (*), stoga vrijedi identitet x n +2 =C 1 x n +1 +C 2 x n. Pomnožimo obje strane jednakosti sa a. Dobijamo a∙x n +2 =a∙(C 1 ∙x n +1 +C 2 ∙x n)= C 1 ∙a∙x n +1 +C 2 ∙a∙x n. To znači da je ax n rješenje za (*).

2) Ako su nizovi x n i y n rješenja (*), tada je i niz x n + y n rješenje.

Dokaz.

x n i y n su rješenja, stoga vrijede sljedeći identiteti:

x n +2 =C 1 x n +1 +C 2 x n .

y n +2 =C 1 y n +1 +C 2 y n .

Izvodimo pojam po članu sabiranje dvije jednakosti:

x n +2 +y n +2 =S 1 ∙x n +1 +S 2 ∙x n + S 1 ∙y n +1 +S 2 ∙y n = S 1 ∙(x n +1 + y n +1)+S 2 ∙(x n +y n). To znači da je x n +y n rješenje za (*).

3) Ako je r 1 rješenje kvadratne jednačine r 2 =C 1 r+C 2, tada je niz (r 1) n rješenje relacije (*).

r 1 je rješenje kvadratne jednačine r 2 =C 1 r+C 2, što znači (r 1) 2 =C 1 r 1 +C 2. Pomnožimo obje strane jednakosti sa (r 1) n. Dobijamo

r 1 2 r 1 n =(C 1 r 1 +C 2) r n.

r 1 n +2 =S 1 r 1 n +1 +S 2 r 1 n .

To znači da je niz (r 1) n rješenje za (*).

Iz ovih svojstava slijedi metoda rješenja linearne rekurentne relacije sa konstantnim koeficijentima drugog reda:

1. Napravimo karakterističnu (kvadratnu) jednačinu r 2 =C 1 r+C 2. Nađimo njegove korijene r 1, r 2. Ako su korijeni različiti, onda opšte rješenje ima oblik f(n)= ar 1 n +βr 2 n.

2. Nađimo koeficijente a i β. Neka je f(0)=a, f(1)=b. Sistem jednačina

ima rješenje za bilo koje a i b. Ova rješenja jesu

Zadatak . Hajde da pronađemo formulu za opšti termin Fibonačijevog niza.

Rješenje . Karakteristična jednadžba ima oblik x 2 =x+1 ili x 2 -x-1=0, njeni korijeni su brojevi, što znači da opće rješenje ima oblik f(n)= . Kao što je lako videti, iz početnih uslova f(0)=0, f(1)=1 sledi da je a=-b=1/Ö5, pa stoga opšte rešenje Fibonačijevog niza ima oblik:

.

Iznenađujuće, ovaj izraz uzima cjelobrojne vrijednosti za sve prirodne vrijednosti n.

Ova metoda se sastoji u tome što se rješenje kombinatornog problema sa n objekata izražava kroz rješenje sličnog problema sa manjim brojem objekata korištenjem određene relacije koja se naziva rekurentna. Kaže se da niz elemenata u0 , u1 , … un , … iznad polja kompleksnih brojeva C zadovoljava rekurentnu relaciju reda k ako

gdje su a1, …, ak koeficijenti iz C. Relacije ovog tipa nastaju prirodno pri rješavanju kombinatornih problema.

Primjer. Neka postoji niz pozicija označenih brojevima 1, 2, ... , n, ... i u početnom trenutku objekt je na 1. poziciji. U jednom potezu, predmet se pomiče naprijed za 1 i 2 pozicije. Pronađite broj načina da dođete do n-te pozicije.

♦ Neka un bude broj koji nas zanima. Jasno je da je u2 = 1, u3 = 2. Zatim dijelimo sve načine dolaska na poziciju broj n u dvije klase: one u kojima se u posljednjem koraku objekt pomiče za 1 korak i one u kojima se pomiče za 2 koraka. Jasno je da u prvom slučaju imamo un-1 opcije, u drugom slučaju un-2 opcije. Dakle, imamo

Polinom P(x) se zove karakteristika za linearnu rekurentnu relaciju (2). Imajte na umu da je svaki ponavljajući niz k-tog reda jedinstveno određen specificiranjem njegovih prvih k članova.

Neka je λ korijen karakterističnog polinoma P(x).

Teorema 1. Niz u0, u1, … un, …, gdje je un = cλ n, c proizvoljna konstanta iz C, zadovoljava linearnu rekurentnu relaciju (2).

♦ Zamjenom ovih vrijednosti un, n = 0, 1, … u (2), imamo

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

Teorema 2. Neka nizovi un, vn, n = 0, 1, ... zadovoljavaju linearnu rekurentnu relaciju (2). Tada sekvenca ima ovo svojstvo.

rn , n = 0, 1, … , gdje su rn = α un + β vn , n , α, β proizvoljne konstante iz C.

♦ Dokaz je očigledan. ♦

Teorema 3. Neka su λ 1, …, λ k jednostavni (tj. ne višestruki) korijeni karakterističnog polinoma P(x) za niz (2).

Tada opšte rješenje ove rekurentne relacije ima oblik

gdje su c1, …, ck pogodne konstante iz C.

♦ Prema prethodnom, primjećujemo da je niz un, n = 0, 1, … rješenje relacije (2). Da bismo dokazali da bilo koje rješenje ima oblik (5), dovoljno je pokazati da je za proizvoljan niz vn, n = 0, 1, …, zadovoljavajući

(2), postoje konstante c1, …, ck, takve da je un = vn, n. Za to je dovoljno da je v0 = u0, v1 = u1, …, vk-1 = uk-1. Hajde da razmotrimo ove uslove

u odnosu na c1, c2, …, ck. Odrednica ovog sistema je Vandermondeova determinanta i prema (7, str. 118).

						= ∏ (λi − λj ) ≠ 0
		λ k− 1	λ k− 1	L λ k − 1

prema pretpostavci o korijenima λ 1, ..., λ k. Ovdje slijedi izjava. ♦ Kao primjer, razmotrite rekurentnu relaciju (3). Imamo karakterističan polinom

P(x) = x2 - x -1

Njegovi korijeni su jednaki λ 1 = 1 + 2 5, λ 2 = 1 − 2 5. Opće rješenje ima oblik

u n = c 1 1+ 2 5 n + c 2 1− 2 5 n

Sistem jednadžbi za konstante c1, c2: c1 1 + 2 5 + c2 1 − 2 5 = 1

								1− 5
Gdje ćemo dobiti c1								C2 = -

Neka je sada λ korijen višestrukosti r karakterističnog polinoma P(x). Slično kao i prethodno je dokazano

Teorema 4. Nizovi c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … za pro-

proizvoljne konstante c1 , … , cr iz C zadovoljavaju relaciju (2).

Teorema 5. Neka karakteristični polinom P(x) ima korijene λ 1 , … , λ s višestrukosti r1 , … , rs (r1 + … + rs = k) . Zatim opće rješenje rekurentne relacije

Istaknimo još jedno korisno svojstvo linearnih rekurentnih relacija. Teorema 6. Neka imamo relaciju

un = a1 un-1 + … + ak un-k

sa početnim uslovima u1 , … , uk . Tada relacija vrijedi za sve n ≥ k

a 1 a 2				A k n − k uk
							u k− 1		u n− 1
									u n− k+ 1

♦ Dokaz indukcijom na n. Za n = k vrijedi jednakost (8). Neka je istina za n. Za n + 1 imamo

a 1 a 2

A k n + 1 − k uk

u k− 1

0 . . 1 0

a 1 a 2

a k a 1 a 2

a k n − k uk

u k− 1

a 1 a 2

u n+ 1

u n− 1

1 0 un − k + 1

u n− k+ 2

U većini slučajeva, međutim, kada se proučavaju problemi nabrajanja, javljaju se nelinearne rekurentne relacije za čije rješavanje se koriste specifične tehnike. O nekima od njih će se dalje govoriti. Navedimo važan primjer nelinearne rekurentne relacije.

Teorema 7. Neka je C(n, k) broj permutacija skupa n elemenata koji ima tačno k ciklusa. Onda je pošteno

	C(n - 1, k - 1) + (n - 1)C(n - 1, k)
	1, C(0, 1) = 0

♦ Podijelimo skup permutacija skupa X = (1, 2, … n,) koji ima tačno k ciklusa na dvije klase - permutacije u kojima je element n sadržan u jediničnom ciklusu, i permutacije u kojima je element n u ciklus dužine l, l > 1. U prvom slučaju, broj supstitucija se poklapa sa brojem supstitucija skupa X′ = (1, 2, …, n - 1), koji ima k - 1 ciklusa, tj. C(n - 1, k - 1). U drugom slučaju, uklanjanjem elementa n, dobijamo

Razmatramo zamjenu skupa X′ = (1, 2, …, n - 1) sa k ciklusa, čiji je broj jednak C(n - 1, k). Hajde sada da saznamo na koji broj načina možemo dodati element n supstituciji stepena n - 1 sa k ciklusa. Ako postoji ciklus dužine i, to se može uraditi na i načine. Ukupan broj puteva jednaka je i1 + … + ik, gdje su i1, …, ik dužine supstitucijskih ciklusa. Međutim, i1 + … + ik = n - 1. To znači da je broj zamjena druge klase jednak

(n - 1)C(n - 1, k). Odavde dobijamo (9). ♦

Rezultirajući brojevi C(n, k) povezani su sa poznatim Stirlingovim brojevima prve vrste sn,k, koji su definirani na sljedeći način:

sn,k = (- 1)n+k C(n, k)

Evo tabele prvih nekoliko vrednosti brojeva sn,k.

		s n,1	s n,2	s n,3	s n,4	s n,5

Table Stirlingovi brojevi prve vrste

Sa velikom količinom podataka posmatranja X konačne metode za rješavanje jednadžbe vjerovatnoće dovode do značajnih računskih poteškoća povezanih s potrebom pamćenja veliki broj početni podaci i međurezultati proračuna. S tim u vezi, od posebnog su interesa rekurentne metode u kojima se procjena maksimalne vjerovatnoće izračunava u koracima sa postupno rastućom preciznošću, pri čemu je svaki korak povezan sa dobijanjem novih podataka posmatranja, a rekurentna procedura je konstruisana na način da se pohranjuje u memoriju najmanju moguću količinu podataka iz prethodnih koraka. Dodatna i vrlo značajna s praktične tačke gledišta prednost rekurentnih metoda je njihova spremnost da daju rezultate u bilo kojem međukorak.

Zbog toga je preporučljivo koristiti rekurentne metode čak i u slučajevima kada je moguće dobiti tačno rješenje jednačine maksimalne vjerovatnoće konačna metoda, i čini ih još vrijednijim kada se ne može pronaći precizan analitički izraz za procjenu maksimalne vjerovatnoće.

Neka skup podataka posmatranja bude niz za opisivanje kojeg uvodimo vektor. (Kao i uvijek, svaka od njegovih komponenti, zauzvrat, može biti vektor, segment slučajnog procesa, itd.). Neka je funkcija vjerovatnoće, i

njegov logaritam. Potonje se uvijek može predstaviti u obliku

Logaritam funkcije vjerovatnoće za populaciju podataka posmatranja bez posljednje vrijednosti, i

Logaritam uslovne gustine verovatnoće vrednosti za date vrednosti i .

Reprezentacija (7.5.16) za logaritam funkcije vjerovatnoće je osnova za dobijanje rekurentne procedure za izračunavanje procjene maksimalne vjerovatnoće. Hajde da razmotrimo redovan slučaj. U ovom slučaju, procjena maksimalne vjerovatnoće može se naći kao rješenje jednačine

koji se razlikuje od (7.1.6) samo uvođenjem indeksa p y logaritam funkcije vjerovatnoće.

Označimo rješenje ove jednačine naglašavajući da je ova procjena dobivena iz skupa podataka opservacije. Slično, označimo rješenjem jednačine procjenu maksimalne vjerovatnoće dobijene iz ukupnosti podataka.

Jednačina (7.5.19) se može prepisati uzimajući u obzir (7.5.16) u sljedećem obliku:

Proširimo lijevu stranu (7.5.20) u Taylorov red u susjedstvu tačke . Gde

(7.5.22)

Vektor gradijenta funkcije u tački ; izraz postaje nula zbog činjenice da je , rješenje jednadžbe vjerovatnoće za prethodni (P - 1. korak:

Simetrična matrica drugih izvoda logaritma funkcije vjerovatnoće u tački , uzeta sa suprotnim predznakom, nepisani članovi ekspanzije imaju kvadratni i viši red malenosti u odnosu na razliku . Zanemarujući ove posljednje, dobivamo sljedeće približno rješenje jednačine maksimalne vjerovatnoće:

gdje je inverzna matrica.

Ovo rješenje je predstavljeno u obliku rekurentne relacije koja određuje sljedeću vrijednost procjene kroz procjenu u prethodnom koraku i korekciju , zavisno od dostupnih podataka posmatranja direktno i kroz prethodnu procenu. Korekcija se formira kao proizvod gradijenta logaritma uslovne gustine verovatnoće novodobivene vrednosti X n u tački koja je jednaka prethodnoj procjeni, matrici težine . Potonji je određen izrazom (7.5.23) i također ovisi o procjeni u prethodnom koraku, a njegova ovisnost o novim podacima posmatranja u potpunosti je određena formom logaritma uslovne gustine vjerovatnoće.

Oblik relacije (7.5.24) je vrlo sličan (7.5.8), koji implementira iterativnu metodu izračunavanja procjene maksimalne vjerovatnoće koristeći Newtonov metod. Međutim, u stvarnosti se međusobno značajno razlikuju. U (7.5.8), korekcija prethodne vrijednosti procjene je određena gradijentom logaritma cijele funkcije vjerovatnoće, koja uvijek zavisi od svih dostupnih podataka posmatranja, što zahtijeva memorisanje cijelog ovog skupa. U skladu sa (7.5.24), korekcija do je određena veličinom gradijenta, koji, zbog svojstava uslovne gustine verovatnoće, zapravo zavisi samo od onih vrednosti () koje su u čvrstoj statističkoj vezi sa X n. Ova razlika je posljedica posebnog izbora prethodne aproksimacije kao procjene maksimalne vjerovatnoće koja se nalazi iz skupa podataka posmatranja umanjenih za jednu vrijednost, a posebno je izražena za nezavisne vrijednosti (). U ovom poslednjem slučaju

zbog čega zavisi samo od i X n , a gradijent je samo od prethodne vrijednosti procjene i onih novodobijenih na P- mstep podataka posmatranja. Stoga, sa nezavisnim vrijednostima, za formiranje vektora, nije potrebno zapamtiti bilo koju drugu informaciju iz prethodnog koraka osim vrijednosti evaluacije.

Slično, u slučaju Markovljevog niza podataka posmatranja, odnosno kada

vektor zavisi samo od , trenutne i jedne prethodne vrednosti.U ovom slučaju, za proračun je potrebno zapamtiti iz prethodnog koraka, pored vrednosti, samo vrednost, ali ne i ceo skup podataka posmatranja, kao u iterativnoj proceduri. Općenito, proračun može zahtijevati memorisanje više prethodne vrijednosti (), međutim, zbog potrebe da se uzmu u obzir samo one vrijednosti koje su statistički zavisne od , ovaj broj je gotovo uvijek manji od ukupnog volumena skupa podataka promatranja. Dakle, ako vektor opisuje vremenski niz, tada je broj članova ovog niza koji treba zapamtiti određen njegovim vremenom korelacije, a njihov relativni omjer se smanjuje u obrnutom proporciji n, kao u slučaju nezavisnih vrijednosti.

Razmotrimo sada strukturu matrice težine koja je uključena u rekurentnu relaciju (7.5.24). Prema definiciji (7.5.23), zbog prisustva pojma, on, općenito govoreći, ovisi o svim vrijednostima čak i sa nezavisnim vrijednostima , što rekurentnoj relaciji (7.5.24) lišava prednosti povezano s mogućim smanjenjem količine podataka pohranjenih iz prethodnog koraka. Postoji nekoliko načina za aproksimaciju matrice , koji otklanjaju ovaj nedostatak.

Prvi od njih zasniva se na dosljednijoj upotrebi osnovne pretpostavke o maloj razlici između dvije sljedeće vrijednosti procjene i , što je osnova za dobijanje rekurentne relacije (7.5.24). Ovo nam omogućava da dobijemo sličnu rekurentnu relaciju za matricu težine.Zaista, koristeći malenost iz (7.5.23), imamo

Unošenjem oznake

iz (7.5.24) i (7.5.25) dobijamo sistem rekurentnih relacija za vektorsku i matricu težine

Ovaj sistem, zajedno sa početnim vrednostima, u potpunosti određuje vrednost procene u bilo kom koraku, zahtevajući na svakom od njih da se izračuna samo gradijent i matrica drugih izvoda logaritma uslovne gustine verovatnoće za trenutno posmatranu vrednost. Početne vrijednosti se biraju uzimajući u obzir dostupne apriorne podatke o mogućim vrijednostima i rasponu varijacija parametara, a u potpunom nedostatku ovih podataka uzimaju se kao nula (,).

Za nezavisne vrijednosti, sistem rekurentnih relacija (7.5.27) očito opisuje višedimenzionalni (dimenzionalni) Markovljev slučajni proces, čija komponenta konvergira pravoj vrijednosti parametra , a komponenta konvergira Fisherovoj informacionoj matrici (7.3.). 8), gdje je prava vrijednost procijenjenog parametra , i raste neograničeno s rastom P. Sistem (7.5.27) ima slična svojstva konvergencije pod opštijim uslovima ako je niz ergodičan.

Druga od spomenutih metoda zasniva se na zamjeni matrice drugih izvoda logaritma funkcije vjerovatnoće sa njenim matematičkim očekivanjem – Fisherovom informacijskom matricom, koja se, uzimajući u obzir (7.5.16), može zapisati kao:

gdje je slično (7.5.26)

Zamijenivši matricu u (7.5.24) sa matricom , dobijamo rekurentnu relaciju

za približni izračun procjena maksimalne vjerovatnoće, koji je predložio Sakrison (u originalu za nezavisne identično raspoređene , kada i . Ovo je rekurentna relacija jednostavniji sistem(7.5.27), budući da je optimalna matrica težine zamijenjena njenim matematičkim očekivanjem, a za njeno pronalaženje nisu potrebni dostupni podaci opservacije osim onih koncentrisanih u procjeni vrijednosti. Istovremeno, očito je da takva zamjena znači potrebu ispunjavanja dodatnog zahtjeva, u odnosu na (7.5.27), da matrica drugih izvoda bude bliska svom matematičkom očekivanju.

Ako se funkcija gustoće vjerovatnoće i matrica mijenjaju od koraka do koraka, direktna lokacija svaki korak može zahtijevati previše proračuna. U ovom slučaju, zbog dodatnog smanjenja tačnosti rezultata, određenog nejednakošću malih razlika na nulu, može se preći na rekurentno izračunavanje približne vrijednosti matrice. Vraćajući se na prethodnu notaciju za ovu približnu vrijednost, dobijamo još jedan sistem rekurentnih odnosa

Očekivana vrijednost matrica (Fisherova informacijska matrica za jedno opažanje) uzeta u tački . Ovaj sistem se razlikuje od (7.5.27) po tome što druga od rekurentnih relacija (7.5.31) ne uključuje direktno podatke opservacije.

Bilo koji od gore navedenih sistema rekurentnih odnosa je potpuno tačan ako funkcija kvadratno zavisi od , i dodatno, matrica drugih izvoda ne zavisi od . Zapravo, ovo odgovara slučaju nezavisnih normalno raspoređenih (ne nužno identičnih) vrijednosti s nepoznatim matematičkim očekivanjem, koje predstavlja procijenjeni parametar.

Sistem rekurentnih odnosa (7.5.24) daje tačno rješenje jednačine maksimalne vjerovatnoće pod mnogo širim uslovima uz jedini zahtjev da funkcija kvadratno zavisi od . Štaviše, zavisnost od je proizvoljna, što odgovara širokoj klasi distribucija verovatnoće populacije sa nezavisnim i zavisnim vrednostima.

Uz razmatrane opšte metode, postoji niz metoda za odabir matrice težinskih koeficijenata u rekurentnoj vezi (7.5.24), prilagođenih određenim specifičnim ograničenjima. Najjednostavniji od njih je izbor u obliku dijagonalne matrice, tako da , ( I - matrica identiteta), gdje je opadajući niz numeričkih koeficijenata, odabranih nezavisno od svojstava funkcije vjerovatnoće na isti način kao u proceduri stohastičke aproksimacije Robins-Monroe, o kojoj će biti riječi u narednim poglavljima.

Vrijedi napomenuti da su sve iterativne ili ponavljajuće procedure za pronalaženje procjena maksimalne vjerovatnoće općenito približne. Stoga, općenito govoreći, za procjene dobijene kao rezultat primjene ovih postupaka, mora se iznova dokazati konzistentnost, asimptotska efikasnost i asimptotska normalnost. Za iterativne procedure, neophodna svojstva procjena su zagarantovana činjenicom da, u principu, takvi postupci, sa odgovarajućim brojem iteracija, daju rješenje jednačine vjerovatnoće sa bilo kojom unaprijed određenom tačnošću. Postoje posebni dokazi za ponavljajuće postupke kao što su (7.5.27), (7.5.30), (7.5.31) i drugi. Istovremeno, pored zahtjeva redovnosti, nameću se i neki dodatni zahtjevi:

O ponašanju funkcije (7.2.2) za različite vrijednosti ||, kako bi se pomoću rekurentne procedure postigao globalni maksimum ove funkcije u tački koja odgovara pravoj vrijednosti parametra;

Po redu porasta u drugim momentima derivacija logaritma funkcije vjerovatnoće za velike apsolutne vrijednosti. Ovi zahtjevi su posljedica opštijih uslova za konvergenciju na tačku svih ili dijela komponenti Markovljevog slučajnog procesa do kojeg vodi jedan ili drugi rekurentni postupak.

U zaključku, također napominjemo da u slučaju kada postoji tačno rješenje jednačine maksimalne vjerovatnoće, ono se gotovo uvijek može predstaviti u rekurentnom obliku. Navedimo dva jednostavna različita primjera. Dakle, elementarna procjena nepoznatog matematičkog očekivanja normale slučajna varijabla ukupno n njegove vrijednosti uzorka u obliku aritmetičke sredine

je procjena maksimalne vjerovatnoće i može se predstaviti u ponavljajućem obliku:

što je najjednostavniji specijalni slučaj (7.5.30) sa

Drugi primjer je nepravilna procjena maksimalne vjerovatnoće za parametar - širinu pravokutne distribucije - iz (7.4.2), koja se također može odrediti relacijom ponavljanja

sa početnim stanjem. Ova rekurentna relacija je drugačijeg tipa: njena desna strana se ne može predstaviti kao zbir prethodne procjene i male korekcije, što je posljedica nepravilnosti ovog primjera; međutim, on ima sve prednosti rekurentnog pristupa: zahtijeva pamćenje samo jednog broja iz prethodnog koraka - procjene - i oštro smanjuje pretragu na jedno poređenje umjesto poređenja svih vrijednosti.

Navedeni primjeri ilustruju prednosti rekurentnih metoda čak iu slučaju kada jednadžba maksimalne vjerovatnoće omogućava egzaktno rješenje, jer jednostavnost analitičkog prikaza rezultata nije identična računskoj jednostavnosti njegovog dobivanja.

7.5.3. Prelazak na kontinuirano vrijeme. Diferencijalne jednadžbe za procjene maksimalne vjerovatnoće

Razmotrimo sada poseban slučaj kada su dostupni podaci posmatranja X nisu opisani skupom tačaka uzorka , a predstavljaju segment implementacije nekog procesa , ovisno o parametrima navedenim u intervalu , a dužina ovog intervala može se povećati tokom posmatranja (vremenska tačka t je varijabilna).

Za statistički opis podataka posmatranja, u ovom slučaju, uvodi se funkcional omjera vjerovatnoće, koji je granica na , max omjera distribucije gustoće vjerovatnoće skupa vrijednosti na proizvoljno zadanoj vrijednosti prema sličnoj vjerovatnoći gustina na određenoj fiksnoj vrijednosti, au nekim slučajevima, kada dozvoljava reprezentaciju , gdje je slučajni proces , neovisno o , do gustoće vjerovatnoće skupa vrijednosti pod uvjetom da . Upotreba funkcionalnog omjera vjerovatnoće omogućava nam da eliminišemo formalne poteškoće u određivanju gustine vjerovatnoće koje nastaju pri prelasku na kontinuirano vrijeme.

Logaritam funkcionalnog omjera vjerovatnoće može se predstaviti kao

gdje je neki funkcionalni proces na intervalu . U nekim slučajevima, funkcional se degenerira u funkciju koja ovisi samo o vrijednosti . Sta ako

gdje je poznata funkcija vremena i parametara, i delta korelirani slučajni proces ("bijeli" šum) sa spektralnom gustinom N o, zatim, birajući kao nazivnik omjer vjerovatnoće distribucije vjerovatnoće X sa , imat ćemo

Neka je procjena maksimalne vjerovatnoće parametra, konstruirana iz implementacije procesa na intervalu, odnosno rješenje jednačine maksimalne vjerovatnoće

Diferencirajući lijevu stranu ove jednačine s obzirom na vrijeme, dobijamo

Uvođenje oznaka

i rješavanjem jednadžbe (7.5.42) za , dobijamo diferencijalnu jednačinu za procjenu maksimalne vjerovatnoće

Matrica je, pak, prema (7.5.37) određena diferencijalnom jednadžbom

Baš kao iu diskretnom slučaju, matrica u (7.5.45), (7.5.47) može se zamijeniti njenim matematičkim očekivanjem - Fisherovom informacijskom matricom na vrijednosti , i diferencijalnom jednadžbom (7.5.46) za težinu matrica - po jednačini

gdje je slično diskretnom slučaju

Matematičko očekivanje matrice drugih izvoda.

Skup diferencijalnih jednadžbi (7.5.45), (7.5.46) ili (7.5.45), (7.5.48), zajedno sa početnim uslovima, pri čijem izboru ostaje sve što je rečeno za diskretni slučaj, u potpunosti važi određuje procjenu maksimalne vjerovatnoće za bilo koji trenutak u vremenu. Ovaj skup se može modelirati korištenjem odgovarajućih, općenito govoreći, nelinearnih analognih uređaja ili, uz odgovarajuće vremensko uzorkovanje, rješavati pomoću kompjutera. U zaključku, napomenimo jednu od modifikacija ovih jednačina, koja nam omogućava da izbjegnemo potrebu za invertiranjem matrice.

Predstavljamo oznaku

, Gdje I

i diferenciranje u odnosu na vrijeme odnosa , Gdje I je matrica identiteta, koristeći (7.5.46) dobijamo diferencijalnu jednadžbu koja direktno određuje matricu:

(i slično kada se zameni sa ), što zajedno sa jednadžbom (7.5.45)

utvrđuje ocjenu , bez potrebe za inverzijom matrice. U ovom slučaju dolazi do prijelaza sa najjednostavnije linearne diferencijalne jednadžbe (7.5.46) na nelinearnu relativno diferencijalnu jednačinu (7.5.51) tipa Riccati.

Relacija recidiva, rekurentna jednačina ili ponavljajuća formula naziva se relacija oblika, koja vam omogućava da izračunate sve članove niza
, ako su dati njegovi prvi kčlanovi.

1. Formula
specificira aritmetičku progresiju.

2. Formula
definira geometrijsku progresiju.

3. Formula
postavlja sekvencu Fibonačijevi brojevi.

U slučaju kada je rekurentna relacija linearna i homogena, tj. relacija oblika

(str=const), sekvenca
pozvao povratno. Polinom

pozvao karakteristika za povratnu sekvencu
. Korijeni polinoma
su pozvani karakteristika.

Poziva se skup svih nizova koji zadovoljavaju datu rekurentnu relaciju opšta jednačina.

Opis opšte jednačine relacije (1) ima analogiju sa opisom rešenja obične diferencijalne jednačine sa konstantnim koeficijentima.

Teorema 1. 1. Neka- korijen karakterističnog polinoma (2). Zatim sekvenca
, Gdjecje proizvoljna konstanta koja zadovoljava relaciju (1).

2. Ako
- jednostavni korijeni karakteristični polinom (2), onda opšte rješenje rekurentne relacije (1) ima oblik, Gdje
- proizvoljne konstante.

3. Ako- korijen višestrukosti
karakteristični polinom (2), onda opšte rješenje rekurentne relacije (1) ima oblik
, Gdje- proizvoljne konstante.

Poznavajući opšte rešenje rekurentne jednačine (1), prema početnim uslovima,
moguće je pronaći neodređene konstante i time dobijemo rješenje jednačine (1) sa datim početnim uslovima.

Primjer 2. Pronađite niz
, zadovoljavajući rekurentnu relaciju
i početni uslovi
.

Korijeni karakterističnog polinoma
su brojevi
. Dakle, prema teoremi 3.1. opšte rešenje ima oblik
. Koristeći početne uslove, dobijamo sistem

rješavanje koje nalazimo
I
. dakle,
.

Razmotrimo nehomogenu linearnu rekurentnu jednačinu

Neka
je opšte rješenje homogene jednadžbe (1), i
- privatni(specifično) rješenje nehomogena jednačina (3). Zatim sekvenca
formira opće rješenje jednačine (3), te je stoga valjan.

Teorema 2.Opće rješenje nehomogene linearne rekurentne jednačine je predstavljeno kao zbir opšteg rješenja odgovarajuće homogene linearne rekurentne jednačine i nekog posebnog rješenja nehomogene jednačine.

Dakle, na osnovu teoreme 1, zadatak pronalaženja opšteg rješenja rekurentne jednačine (3) svodi se na pronalaženje nekog posebnog rješenja.

U nekim slučajevima postoje opći recepti za pronalaženje zajedničkog rješenja.

Ako
(Gdje ) nije karakterističan korijen, dakle, zamjenski
u (3), takođe dobijamo odavde
, tj. određeno rješenje može se dati formulom
.

Neka
- stepen polinoma r iz varijable n, a broj 1 nije karakterističan korijen. Tada treba tražiti određeno rješenje u formi
. Zamjenom polinoma u formulu (3) dobivamo

Upoređujući koeficijente na lijevoj i desnoj strani posljednje jednakosti, dobijamo omjere brojeva , što omogućava utvrđivanje ovih brojeva.

Primjer. Pronađite rješenje jednačine

(4)

sa početnim stanjem
.

Razmotrimo karakteristični polinom
. Jer
i desnu stranu
jednačina (3) je jednaka n+1, tada ćemo tražiti određeno rješenje u obrascu
. Zamena u jednačinu (4), dobijamo . Izjednačavajući koeficijente na lijevoj i desnoj strani posljednje jednakosti, dobijamo sistem

odakle ga nalazimo?
. Dakle, određeno rješenje jednačine (4) ima oblik
. Prema teoremi 3.1. opšte rešenje homogene jednačine
je data formulom
, i teoremom 3.2. dobijamo opšte rešenje jednačine (4):
. Od početnog stanja
mi nalazimo
, tj. . dakle,
.