Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica MATEMATIČKA ANALIZA NIZOVI I REDOVI

Linearni homogeni rekurentni nizovi

[inlmath]a_1,\:a_2,\:...\:a_{n-1},\:a_n[/inlmath]

Linearni homogeni rekurentni nizovi

Postod Subject » Utorak, 19. Jun 2018, 13:03

Za kvadratnu jednacinu tj neko [inlmath]N=2[/inlmath] LHRN su
[dispmath]a_n=C_1P_1^n+C_2P_2^n[/dispmath] i
[dispmath]a_n=C_1P_1^n+nC_2P_2^n[/dispmath] ako je [inlmath]P_1=P_2[/inlmath]. Sad me interesuje kako je za LHRN za visi red?

Sta ako imamo jednacinu cija su resenja: [inlmath]P_1[/inlmath] i npr. [inlmath]P_2=P_3=P_4[/inlmath], ili vise razlicitih resenja?
"All we have to decide is what to do with the time that is given to us." - J.R.R.Tolkien
"Zivot nije vazniji od obraza." - Milorad Golijan
Korisnikov avatar
Subject  OFFLINE
 
Postovi: 59
Zahvalio se: 38 puta
Pohvaljen: 25 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Linearni homogeni rekurentni nizovi

Postod ubavic » Utorak, 19. Jun 2018, 21:49

Pretpostavimo da želimo da nađemo funkciju [inlmath]f:\mathbb N \rightarrow \mathbb R[/inlmath] koja za svako prirodno [inlmath]n[/inlmath] zadovoljava [inlmath]f(n+k) = c_{k}f(n+k-1) + c_{k-1}f(n+k-2) + \dots + c_{1}f(n)[/inlmath] gde su [inlmath]c_1, \cdots, c_{k}[/inlmath] fiksirani realni brojevi. Gornju linearnu funkcionalnu jednačinu (zajedno sa još [inlmath]k-1[/inlmath] trivijalnom jednačinom) možemo predstaviti kao

[dispmath]\vec u_{n+1} = \left[\begin{matrix} f(n+k) \\ f(n+k-1) \\ \vdots\\f(n+2) \\ f(n+1) \end{matrix}\right] = \left[\begin{matrix} c_k && c_{k-1} && \dots && c_2 && c_1 \\ 1 && 0 && \cdots && 0 && 0 \\ 0 && 1 && \cdots && 0 && 0 \\ \vdots && \vdots && \ddots && \vdots && \vdots \\ 0 && 0 && \dots && 1 && 0\end{matrix}\right] \left[\begin{matrix} f(n+k-1) \\ f(n+k-2) \\ \vdots \\ f(n+1)\\ f(n)\end{matrix}\right] = A \vec u_{n}[/dispmath]

Primetimo da sva rešenja ovog sistema čine vektorski prostor (ovo možeš da dokažeš), kao i da je ovaj vektorski prostor dimenzije [inlmath]k[/inlmath] (naime svaka funkcija koja zadovoljava ovakav sistem je u potpunosti određena sa prvih [inlmath]k[/inlmath] vrednosti). Ostaje još da se odredi jedna baza ovog prostora, a zatim da se neka određena funkcija izrazi u toj bazi (do sada uopšte nismo koristili prvih [inlmath]k[/inlmath] vrednosti niza, kada njih izaberemo imaćemo tačno određen niz). Biranje ove baza zavisi od toga kakav je operator [inlmath]A[/inlmath] tj. kakve su njegove sopstvene vrednosti. Karakteristični polinom operatora [inlmath]A[/inlmath] je [inlmath]\pm(-\lambda^k+c_k\lambda^{k-1}+\dots+c_2\lambda+c_1)[/inlmath], što možeš lako videti razvijanjem determinante [inlmath]\det(A-\lambda I)[/inlmath] po poslednjoj koloni.

Ako su svi koreni ovog polinoma realni i različiti tada operator ima [inlmath]k[/inlmath] sopstvenih vektora [inlmath]e_1, \dots, e_k[/inlmath]. U ovom slučaju možemo dijagonalizovati matricu i ovom slučaju je lako izračunati [inlmath]f(n)[/inlmath] preko sopstvenih vektora, koji su oblika [inlmath]\left[\lambda_i^{k-1} \; \dots \; \lambda_i \;1\right][/inlmath]. U opštem slučaju, možemo naći Žordanovu formu matrice i preko nje izračunati [inlmath]A^n[/inlmath]. Kada znamo [inlmath]A^n[/inlmath] lako možemo naći [inlmath]\vec u_{n+1}[/inlmath] jer je [inlmath]\vec u_{n+1} = A \vec u_{n} = \dots = A^{n-k+1} \vec u_{k}[/inlmath].

Ovo je jedan od načina da se dođe do rešenja (jedini za koji ja znam). Verovatno postoji još tehnika.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Re: Linearni homogeni rekurentni nizovi

Postod Subject » Sreda, 20. Jun 2018, 06:27

Hvala ubavic, ali ja ovo nista ne razumem...

Jedno sto sam nasao je sledece : Ako imam 4 razlicita resenja onda vazi rekurenta relacija:

[dispmath]a_n=C_1P_1^{n}+C_2P_2^{n}+C_3P_3^{n}+C_4P_4^{n}[/dispmath]

gde su [inlmath]P[/inlmath]-ovi resenja, a [inlmath]C[/inlmath]-ovi konstante.

Kako je za 2 razlicita resenja imamo samo 2 clana, jasno je da za [inlmath]n[/inlmath] resenja bice [inlmath]n[/inlmath] clanova kao proizvod neke konstante i resenja.

Ono sto mene interesuje, je sta sad ako imamo 4 jednaka resenja, znaci [inlmath]P_1=P_2=P_3=P_4[/inlmath] kako ce sada da glasi rekurentna relacija?

Sve sam radio pod predpostavkom da [inlmath]C,P\in\mathbb{R}[/inlmath].

Slucaj kada su kompleksna resenja za [inlmath]P[/inlmath] jos nisam razmatrao...
"All we have to decide is what to do with the time that is given to us." - J.R.R.Tolkien
"Zivot nije vazniji od obraza." - Milorad Golijan
Korisnikov avatar
Subject  OFFLINE
 
Postovi: 59
Zahvalio se: 38 puta
Pohvaljen: 25 puta

  • +1

Re: Linearni homogeni rekurentni nizovi

Postod ubavic » Sreda, 20. Jun 2018, 16:53

Ja sam mislio da si ti na faksu. Ovo je osnovna linearna algebra koja se nauči na prvoj godini, tako da se možeš vratititi na moj prethodni post kad stekneš malo znanja. U suštini tu je objašnjeno zašto možemo tražiti rešenja onako kao trežimo (preko karakterističnog polinoma).

Ako imaš neku nulu [inlmath]\lambda[/inlmath] višestrukosti [inlmath]s[/inlmath], tada se koriste funkcije [inlmath]\lambda^{n}, n \lambda^n , \dots, n^{s-1}\lambda^n[/inlmath]. Ovo važi i za kompleksne nule (obrati pažnju da ćeš uvek imati paran broj kompleksnih nula tj. imaćeš konjugovane parove).

Na primer opšte rešenje rekurentne jednačine [inlmath]f_{n+3} + a_2 f_{n+2} + a_1 f_{n+1} + a_0 f_{n} = 0[/inlmath] može imati sledeća četiri oblika u zavisnosti od nula [inlmath]\lambda_1 , \lambda_2, \lambda_3[/inlmath]:

1. Ako su sve nule realne i različite, opšte rešenje je [inlmath]f_n = C_1 \lambda_1^n + C_2 \lambda_2^n + C_3 \lambda_3^n[/inlmath].
2. Ako su nule realne i važi [inlmath]\lambda_1 \ne \lambda_2 = \lambda_3[/inlmath] opšte rešenje je [inlmath]f_n = C_1 \lambda_1^n + C_2 \lambda_2^n + nC_3\lambda_2^n[/inlmath].
3. Ako su nule realne i važi [inlmath]\lambda_1 = \lambda_2 = \lambda_3[/inlmath] opšte rešenje je [inlmath]f_n = C_1 \lambda_1^n + n C_2 \lambda_1^n + n^2 C_3 \lambda_1^n[/inlmath].
4. Ako je [inlmath]\lambda_1[/inlmath] kompleksna, tada je [inlmath]\lambda_2 = \overline \lambda_1[/inlmath] takođe kompleksna nula, i [inlmath]\lambda_3[/inlmath] je realna nula. Opšte rešenje je tada dato sa [inlmath]f_n = C_1 \lambda_1^n + C_2 \lambda_2^n + C_3 \lambda_3^n[/inlmath], gde [inlmath]C_1[/inlmath] i [inlmath]C_2[/inlmath] su kompleksne konstante. Međutim, ovaj izraz se da srediti korišćenjem trigonometrijskog oblika kompleksnog broja, tako da se na kraju dobije realan niz.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Re: Linearni homogeni rekurentni nizovi

Postod Subject » Sreda, 20. Jun 2018, 17:22

Hahaha...Da, ja jesam na faksu, ali smo "napamet" ucili te formule samo do stepena 2, niko nam nije uopste pokazao neko izvodjenje(ako jeste, onda tad sigurno nisam bio na predavanje, ali sumnjam.)... I uvek smo koristili dakle ove 2 formule, a retko za kompleksne brojeve, al nema veze.

Tu linearnu algebru sam ja proso i ne zelim da se vracam na nju uopste, dok sam je znao, znao sam je, ali sad hocu da je zaboravim jer mi treba mesto u glavu za druge stvari(jer ja nisam matematicar pa da to stalno obnavljam), a sad sam presao na diskretnu matematiku.

Sto se tice ovog primera, dobar je, razumeo sam ga sad. Cak i sad lakse razumem nacin razvijanja ovih "jednacina" ako tako mogu da se nazovu.

Recimo konkretno za primer 3, ako bi imali jos neko [inlmath]\lambda_4[/inlmath] koje je jednako ostalim [inlmath]\lambda[/inlmath]-ma, onda bi dodali jos jedan stepen tj [inlmath]n^4C_4\lambda_4^n[/inlmath] sto je naravno [inlmath]\lambda_4=\lambda_1[/inlmath].
"All we have to decide is what to do with the time that is given to us." - J.R.R.Tolkien
"Zivot nije vazniji od obraza." - Milorad Golijan
Korisnikov avatar
Subject  OFFLINE
 
Postovi: 59
Zahvalio se: 38 puta
Pohvaljen: 25 puta

  • +1

Re: Linearni homogeni rekurentni nizovi

Postod ubavic » Sreda, 20. Jun 2018, 21:46

Subject je napisao:Hahaha...Da, ja jesam na faksu, ali smo "napamet" ucili te formule samo do stepena 2, niko nam nije uopste pokazao neko izvodjenje(ako jeste, onda tad sigurno nisam bio na predavanje, ali sumnjam.)...

Dobro, ako si imao linearnu algebru onda ipak nešto razumeš. Znam da ste to učili "napamet" jer se to obično tako radi na fakultetima (najviše zbog toga što ima i bitnijih stvari od ovih rekurentnih jednačina).

Subject je napisao:Recimo konkretno za primer 3, ako bi imali jos neko [inlmath]\lambda_4[/inlmath] koje je jednako ostalim [inlmath]\lambda[/inlmath]-ma, onda bi dodali jos jedan stepen tj [inlmath]n^4C_4\lambda_4^n[/inlmath] sto je naravno [inlmath]\lambda_4=\lambda_1[/inlmath].

Ovo nisam baš razumeo. Broj korena zavisi naravno od stepena karakteristične jednačine koji zavisi od stepena rekurentne jednačine.
Ako bi baš imali rekurentni niz četvrtog stepena, dakle i polinom četvrtog stepena, za koji su sve nule jednake, tada bi opšte rešenje bilo dato sa [inlmath]f_n = C_1 \lambda_1^n + n C_2 \lambda_1^n + n^2 C_3 \lambda_1^n + n^{\color{red}3} C_4 \lambda_1^n[/inlmath] a ne [inlmath]f_n = C_1 \lambda_1^n + n C_2 \lambda_1^n + n^2 C_3 \lambda_1^n + n^{\color{red}4} C_4 \lambda_1^n[/inlmath].



Da ne bi bilo da sam iz etra izvadio funkcije [inlmath]\lambda^{n}, n \lambda^n , \dots, n^{s-1}\lambda^n[/inlmath] pojasniću malo zašto se one javljaju.
Ako matricu [inlmath]A[/inlmath] ne možemo da dijagonalizujemo, tada barem možemo da nađemo njenu Žordanovu normalnu formu [inlmath]J[/inlmath]. Ako je matrica [inlmath]J[/inlmath] sačinjena od Žordanovih blokova [inlmath]J_{m_1}(\lambda_1), \dots, J_{m_k}(\lambda_k)[/inlmath], tada je matrica [inlmath]J^n[/inlmath] sačinjena od blokova [inlmath]J_{m_1}(\lambda_1)^n, \dots, J_{m_k}(\lambda_k)^n[/inlmath] gde je proivoljan blok [inlmath]J_{ m_i}(\lambda_i)^n[/inlmath] oblika
[dispmath]J_{m_i}(\lambda_i)^n = \begin{bmatrix}
\lambda_i^n & {{n}\choose{1}}\lambda_i^{n-1} & {{n}\choose{2}}\lambda_i^{n-2} & \cdots & \cdots & {{n}\choose{m_i-1}}\lambda_i^{n-m_i+1} \\
& \lambda_i^n & {{n}\choose{1}}\lambda_i^{n-1} & \cdots & \cdots & {{n}\choose{m_i-2}}\lambda_i^{n-m_i+2} \\
& & \ddots & \ddots & \vdots & \vdots\\
& & & \ddots & \ddots & \vdots\\
& & & & \lambda_i^n & {{n}\choose{1}}\lambda_i^{n-1}\\
& & & & & \lambda_i^n
\end{bmatrix}[/dispmath]
Ovo se može zaključiti iz
[dispmath]J_{m_i}(\lambda_i)^n=(\lambda_i I+N)^n=\sum_{r=0}^n {n \choose r} \lambda_i^{n-r} N^r=\sum_{r=0}^{\min(n,m_i-1)} {n \choose r}\lambda_i^{n-r} N^r.[/dispmath]
Primetimo sada da se elementi bloka [inlmath]J_{m_i}(\lambda_i)^n[/inlmath] nalaze u prostoru [inlmath]\text{Span}\left\{\lambda_i^n, {{n}\choose{1}}\lambda_i^{n-1}, \dots, {{n}\choose{m_i-1}}\lambda_i^{n-m_i+1} \right\}[/inlmath]. Ali, očigledno je da ovaj potprostor pripada potprostoru [inlmath]\text{Span}\left\{\lambda_i^n, n\lambda_i^{n-1}, \dots, n^{d_i-1}\lambda_i^{n-d_i+1} \right\}[/inlmath] gde je [inlmath]d_i[/inlmath] višestrukost nule [inlmath]\lambda_i[/inlmath]. Ovo važi za proizvoljan blok, pa zaključujemo da se elementi matrice [inlmath]J[/inlmath] nalaze u prostoru
[dispmath]\text{Span}\left\{\lambda_1^n, n\lambda_i^{n-1}, \dots, n^{d_i-1}\lambda_1^{n-d_1+1}, \lambda_2^n, \dots, n^{d_2-1}\lambda_2^{n-d_2+1}, \dots, n^{d_k-1}\lambda_k^{n-d_k+1} \right\}.[/dispmath]
Neka je [inlmath]A = P J P^{-1}[/inlmath]. Matrice [inlmath]P[/inlmath] i [inlmath]P^{-1}[/inlmath] su konstantne matrice, pa i elementi matrice [inlmath]A^n = PJ^nP^{-1}[/inlmath] pripada gore navedenom potprostoru. Odavde sledi da je opšti član traženog niza moguće predstaviti u obliku
[dispmath]f_n = \sum_{i=1}^k \sum_{j=0}^{d_i-1} c_{ij}n^{j}\lambda_i^n[/dispmath]
za neke [inlmath]c_{ij}\in\mathbb{C}[/inlmath] koje je moguće odrediti korišćenjem početnih vrednosti niza.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Re: Linearni homogeni rekurentni nizovi

Postod Subject » Četvrtak, 21. Jun 2018, 05:15

Moja greska...Treba ovako: [inlmath]n^3C_4\lambda_1^n[/inlmath], tako da sam taj deo razumeo sigurno bez obzira na ovaj mali lapsus.

Ovo ostalo stvarno ne mogu da komentarisem.
"All we have to decide is what to do with the time that is given to us." - J.R.R.Tolkien
"Zivot nije vazniji od obraza." - Milorad Golijan
Korisnikov avatar
Subject  OFFLINE
 
Postovi: 59
Zahvalio se: 38 puta
Pohvaljen: 25 puta


Povratak na NIZOVI I REDOVI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 45 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 17:56 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs