funkcja generująca

matematyka464 · Post autor: **matematyka464** » 29 gru 2014, o 12:07

Cześć
Rozważmy takie równanie rekurencyjne:
\(\displaystyle{ a_n = Aa_{n-1} + Ba_{n-2}}\)
I dla równania takiego typu istnieje ( ponoć ) równanie charakterystyczne:
\(\displaystyle{ x^2 = Ax + B}\)
Co oznacza, że to równanie jest charakterystyczne? Takie równanie istnieje dla każdej zależności rekurencyjnej czy tylko dla takiej postaci jak powyżej? Co ono w ogóle nam mówi?

miodzio1988 · Post autor: **miodzio1988** » 29 gru 2014, o 12:10

na wiki wszystko masz

Zordon · Post autor: **Zordon** » 29 gru 2014, o 12:10

Dla tej rekurencji spróbuj poszukać rozwiązań postaci \(\displaystyle{ a_n=x^n}\). Jaką zależność spełnia \(\displaystyle{ x}\)?

matematyka464 · Post autor: **matematyka464** » 29 gru 2014, o 13:00

Dzięki Zordon.
Nie rozumiem jednak, skąd możemy mieć pewność, że rozwiązanie będze postaci \(\displaystyle{ x^n}\), czyli że szereg \(\displaystyle{ x^1, x^2, ..., x^ n}\) rozwiazuje tą rekurencję.

Zordon · Post autor: **Zordon** » 29 gru 2014, o 14:19

No cóż, nie mamy pewności, że każde rozwiązanie jest takiej postaci. Ale dzięki tej metodzie można uzyskać, że takie nietrywialne rozwiązania istnieją. Dokładniej, załóżmy np. że równanie charakterystyczne ma dwa różne rozwiązania \(\displaystyle{ x_1, x_2}\). Wtedy mamy rozwiązanie \(\displaystyle{ a_n=x_1^n}\) oraz \(\displaystyle{ a_n=x_2^n}\), oraz można udowodnić, że każde rozwiązanie tej rekurencji jest postaci \(\displaystyle{ a_n=\alpha x_1^n + \beta x_2^n}\) dla pewnych \(\displaystyle{ \alpha, \beta}\)

matematyka464 · Post autor: **matematyka464** » 29 gru 2014, o 17:21

dobrze, ale popatrz się, że żeby mówić o równaniu charakterystycznym musimy popatrzeć na taką równość:
\(\displaystyle{ a_n=x^n}\)
Więc nie bardzo rozumiem w jaki sposób mogłoby być udowodnione, że będą wszystkie postaci:
\(\displaystyle{ a_n=\alpha x_1^n + \beta x_2^n}\) skoro i tak zakładamy, że rozwiązaniem będzie \(\displaystyle{ x^n}\)
Wyjaśnij mi proszę, bo już odchodzę od zmysłów nad tym
EDIT:
Żeby nie było, że jestem bardziej ciemny niż jestem:
Widzę, że gdzieś tutaj przeplata się kombinacja liniowa, że prawdopodobnie baza jest dwuelementowa ( są to te dwa ciągi), stałe są ustalone przez bazę rekurencji itd.
Potrzebuję tylko jakiegoś uporządkowania. Noi tego, że dalej mam problem z tym, że na początku zakładamy:
\(\displaystyle{ a_n = x^n}\)-- 29 gru 2014, o 17:44 --1.

No cóż, nie mamy pewności, że każde rozwiązanie jest takiej postaci. Ale dzięki tej metodzie można uzyskać, że takie nietrywialne rozwiązania istnieją.

Przeczytałem dokładniej to i mam pytanie:
A mianowicie:
Rozumiem, że podchodząc do rozwiązania liniowej rekurencji zakładając, że
\(\displaystyle{ x^n = a^n}\). Potem przechodzimy na równanie charakterystyczne i dalej sobie rozwiązujemy. Ale wtedy otrzymujemy rozwiązania będące kombinacja szeregów i żadne inne. Zatem może istnieją inne rozwiązania, których nie poznaliśmy! Zatem znamy nie wszystkie rozwiązania.

2. W takim razie jak wygląda sytuacja jeżeli chodzi o ciąg Fibbonaciego. Mamy zadaną rekurencję i chemy otrzymać ciąg będący rozwiązaniem. Czyli chcemy znaleźć coś, co opisze nam ten wzór w sposób "sensowny". Zatem wzór zwarty. I znajdujemy rzeczywiście postępując tą metodą. Zatem jesteśmy zadowoleni, bo mamy wzór zwarty. Ale w takim razie to znaczy, że być może istnieje inny, może w jakiś sposób lepszy?*

*Oczywiście być może udowodniono, że nie ma innnego rozwiązania, ale NASZA metoda daje nam wzór, ale nie gwararntuje, że jest to jedyne rozwiiązanie.

Zordon · Post autor: **Zordon** » 29 gru 2014, o 20:24

Rozważamy przestrzeń liniową ciągów \(\displaystyle{ V=\{(a_n)_{n\in \NN}: \forall n\in \NN (a_{n+2}=Aa_{n+1}+Ba_n)\}\subseteq \RR^\NN}\).
Element przestrzeni \(\displaystyle{ V}\) jest określony jednoznacznie przez wartości \(\displaystyle{ a_0}\) i \(\displaystyle{ a_1}\). Zatem przestrzeń ma wymiar \(\displaystyle{ 2}\). Jeśli znajdziemy jej bazę, tzn. dwa liniowo niezależne ciągi \(\displaystyle{ (x_n), (y_n) \in V}\), to bedziemy mogli stwierdzić, że każdy element \(\displaystyle{ V}\) jest postaci \(\displaystyle{ a_n=\alpha x_n + \beta y_n}\). Skąd wziąć te elementy? To nie jest oczywiste. Trzeba jakoś zgadnąć dwa nietrywialne elementy, istotnie różne od siebie (np. ciąg zerowy należy do \(\displaystyle{ V}\) ale oczywiście jest bezużyteczny). No i jak się trochę pokombinuje, to można dojść do wniosku, że warto szukać tej bazy wśród ciągów geometrycznych (które błędnie nazywasz szeregami). Dlatego podstawiam \(\displaystyle{ a_n=x^n}\) i szukam \(\displaystyle{ x}\). W ten sposób znajduje bazę. Schody zaczynają się, gdy delta równania charakterystycznego nie jest dodatnia... Ale to już kwestia techniczna, obliczeniowa, nie dotyczy idei.
Cała metoda sprowadza się do zgadnięcia bazy.

matematyka464 · Post autor: **matematyka464** » 29 gru 2014, o 23:33

Bardzo Ci dziękuję. Teraz jest zdecydowanie jaśniej
Chciałbym dopytać dwie rzeczy:
1. W naszym wypadku baza ma rozmiar dwa, mamy pewną podprzestrzeń ciągów. Jak wygląda w takim razie baza przestrzeni?
2. Szukamy ciągów geometrycznych, które są rozwiązaniami. Nie rozumiem dlaczego podstawiamy
\(\displaystyle{ x^n}\) skoro definicja wg wikipedii takiego ciągu brzmi: \(\displaystyle{ a_1 x^{n-1}}\)
pozdrawiam

Zordon · Post autor: **Zordon** » 30 gru 2014, o 12:16

matematyka464 pisze:Bardzo Ci dziękuję. Teraz jest zdecydowanie jaśniej
Chciałbym dopytać dwie rzeczy:
1. W naszym wypadku baza ma rozmiar dwa, mamy pewną podprzestrzeń ciągów. Jak wygląda w takim razie baza przestrzeni?
2. Szukamy ciągów geometrycznych, które są rozwiązaniami. Nie rozumiem dlaczego podstawiamy
\(\displaystyle{ x^n}\) skoro definicja wg wikipedii takiego ciągu brzmi: \(\displaystyle{ a_1 x^{n-1}}\)
pozdrawiam

1. Której przestrzeni? Sposobów wyboru bazy jest zawsze wiele.
2. zauważ, że ciągi \(\displaystyle{ x^n}\) i \(\displaystyle{ ax^n}\) są wzajemnie swoimi krotnościami, więc niewiele się różnią jako elementy naszej przestrzeni liniowej. Jeśli \(\displaystyle{ x^n\in V}\) to \(\displaystyle{ ax^n\in V}\) dla każdego \(\displaystyle{ a\in \RR}\)

matematyka464 · Post autor: **matematyka464** » 30 gru 2014, o 12:57

Ok, faktycznie.
Teraz jeszcze ostatnie:
Jeżeli r,ozwiązując równanie charakterysytyczne mam dwa pierwiastki to sprawa jest dla mnie jasna. Jeżeli pojawia się tylko jeden podwójny pierwiastek to o dziwo się komplikuje. Mianowicie, wtedy jeżeli \(\displaystyle{ x_0}\) jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
\(\displaystyle{ x_0^n}\) I to jest dla mnie jasne.
oraz:
\(\displaystyle{ nx_0^n}\) i to juz nie wiem skąd się bierze?

Mariusz M · Post autor: **Mariusz M** » 30 gru 2014, o 14:19

"funkcja generująca" to jakieś niezbyt udane tłumaczenie z angielszczyzny

Jak masz równanie postaci

\(\displaystyle{ a_{n}=Aa_{n-1}+Ba_{n-2}}\)

to zdefiniuj sobie funkcje \(\displaystyle{ A\left( x\right)= \sum_{n=0}^{ \infty }{a_{n}x^n}}\)

Wstaw to sobie do równania , wyznacz funkcję \(\displaystyle{ A\left( x\right)}\),
rozbij ją na sumę ułamków postaci \(\displaystyle{ \frac{A_{j}}{\left( 1-\lambda_{j}x\right)^{k} }}\)
\(\displaystyle{ \lambda_{j} \in \mathbb{C}}\)
Ułamek \(\displaystyle{ \frac{A_{j}}{\left( 1-\lambda_{j}x\right)^{k} }}\) rozwijasz w szereg
korzystając z szeregu geometrycznego i jego pochodnych albo z dwumianu Newtona

Zordon · Post autor: **Zordon** » 31 gru 2014, o 18:09

matematyka464 pisze:Ok, faktycznie.
Teraz jeszcze ostatnie:
Jeżeli r,ozwiązując równanie charakterysytyczne mam dwa pierwiastki to sprawa jest dla mnie jasna. Jeżeli pojawia się tylko jeden podwójny pierwiastek to o dziwo się komplikuje. Mianowicie, wtedy jeżeli \(\displaystyle{ x_0}\) jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
\(\displaystyle{ x_0^n}\) I to jest dla mnie jasne.
oraz:
\(\displaystyle{ nx_0^n}\) i to juz nie wiem skąd się bierze?

Nie ma żadnego prostego wytłumaczenia dla tego faktu. Po prostu jak podstawisz to działa

Mariusz M · Post autor: **Mariusz M** » 31 gru 2014, o 23:47

No i jak się trochę pokombinuje, to można dojść do wniosku, że warto szukać tej bazy wśród ciągów geometrycznych (które błędnie nazywasz szeregami).

W tytule wątku dał "funkcja generująca" i owa funkcja jest już sumą szeregów geometrycznych
i ich pochodnych

matematyka464 pisze:Ok, faktycznie.
Teraz jeszcze ostatnie:
Jeżeli r,ozwiązując równanie charakterysytyczne mam dwa pierwiastki to sprawa jest dla mnie jasna. Jeżeli pojawia się tylko jeden podwójny pierwiastek to o dziwo się komplikuje. Mianowicie, wtedy jeżeli \(\displaystyle{ x_0}\) jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
\(\displaystyle{ x_0^n}\) I to jest dla mnie jasne.
oraz:
\(\displaystyle{ nx_0^n}\) i to juz nie wiem skąd się bierze?

Jak masz pierwiastek podwójny to wyznaczając funkcję tworzącą dostaniesz po rozkładzie na ułamki
dostaniesz składnik \(\displaystyle{ \frac{A_{j}}{\left( 1-\lambda_{j}x\right)^2 }}\)
Jeśli zróżniczkujesz szereg geometryczny to z jednej strony otrzymasz powyższy składnik
z drugiej zaś szereg \(\displaystyle{ \sum_{n=0}^{ \infty }{\left( n+1\right)\lambda_{j}^{n}x^{n} }}\)

Inne podejście

Załóż że pierwiastki są różne
Oznacz ich różnicę jako np \(\displaystyle{ \epsilon}\)
Policz granicę z przewidywanej postaci rozwiązania (dla różnych pierwiastków) przy \(\displaystyle{ \epsilon}\) dążącym do zera

Jak dla mnie sposób z równaniem charakterystycznym jest zbyt ograniczony
poza tym nie chodziło ci o funkcję tworzącą