szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 13:07 
Użytkownik

Posty: 462
Lokalizacja: Warszawa
Cześć :)
Rozważmy takie równanie rekurencyjne:
a_n = Aa_{n-1} + Ba_{n-2}
I dla równania takiego typu istnieje ( ponoć :D ) równanie charakterystyczne:
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?
Góra
PostNapisane: 29 gru 2014, o 13:10 
Użytkownik
http://pl.wikipedia.org/wiki/Równanie_rekurencyjne

na wiki wszystko masz
Góra
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 13:10 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
Dla tej rekurencji spróbuj poszukać rozwiązań postaci a_n=x^n. Jaką zależność spełnia x?
Góra
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 14:00 
Użytkownik

Posty: 462
Lokalizacja: Warszawa
Dzięki Zordon.
Nie rozumiem jednak, skąd możemy mieć pewność, że rozwiązanie będze postaci x^n, czyli że szereg x^1, x^2, ..., x^ n rozwiazuje tą rekurencję.
Góra
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 15:19 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
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 x_1, x_2. Wtedy mamy rozwiązanie a_n=x_1^n oraz a_n=x_2^n, oraz można udowodnić, że każde rozwiązanie tej rekurencji jest postaci a_n=\alpha x_1^n + \beta x_2^n dla pewnych \alpha, \beta
Góra
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 18:21 
Użytkownik

Posty: 462
Lokalizacja: Warszawa
dobrze, ale popatrz się, że żeby mówić o równaniu charakterystycznym musimy popatrzeć na taką równość:
a_n=x^n
Więc nie bardzo rozumiem w jaki sposób mogłoby być udowodnione, że będą wszystkie postaci:
a_n=\alpha x_1^n + \beta x_2^n skoro i tak zakładamy, że rozwiązaniem będzie x^n
Wyjaśnij mi proszę, bo już odchodzę od zmysłów nad tym :D
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:
a_n = x^n

-- 29 gru 2014, o 17:44 --

1.
Cytuj:
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
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.
Góra
Mężczyzna Offline
PostNapisane: 29 gru 2014, o 21:24 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
Rozważamy przestrzeń liniową ciągów V=\{(a_n)_{n\in \NN}: \forall n\in \NN (a_{n+2}=Aa_{n+1}+Ba_n)\}\subseteq \RR^\NN.
Element przestrzeni V jest określony jednoznacznie przez wartości a_0 i a_1. Zatem przestrzeń ma wymiar 2. Jeśli znajdziemy jej bazę, tzn. dwa liniowo niezależne ciągi (x_n), (y_n) \in V, to bedziemy mogli stwierdzić, że każdy element V jest postaci 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 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 a_n=x^n i szukam 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.
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2014, o 00:33 
Użytkownik

Posty: 462
Lokalizacja: Warszawa
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
x^n skoro definicja wg wikipedii takiego ciągu brzmi: a_1 x^{n-1}
pozdrawiam :)
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2014, o 13:16 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
matematyka464 napisał(a):
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
x^n skoro definicja wg wikipedii takiego ciągu brzmi: a_1 x^{n-1}
pozdrawiam :)

1. Której przestrzeni? Sposobów wyboru bazy jest zawsze wiele.
2. zauważ, że ciągi x^n i ax^n są wzajemnie swoimi krotnościami, więc niewiele się różnią jako elementy naszej przestrzeni liniowej. Jeśli x^n\in V to ax^n\in V dla każdego a\in \RR
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2014, o 13:57 
Użytkownik

Posty: 462
Lokalizacja: Warszawa
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 x_0 jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
x_0^n I to jest dla mnie jasne.
oraz:
nx_0^n i to juz nie wiem skąd się bierze?
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2014, o 15:19 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
"funkcja generująca" to jakieś niezbyt udane tłumaczenie z angielszczyzny

Jak masz równanie postaci

a_{n}=Aa_{n-1}+Ba_{n-2}

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

Wstaw to sobie do równania , wyznacz funkcję A\left( x\right),
rozbij ją na sumę ułamków postaci \frac{A_{j}}{\left( 1-\lambda_{j}x\right)^{k} }
\lambda_{j} \in \mathbb{C}
Ułamek \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
Góra
Mężczyzna Offline
PostNapisane: 31 gru 2014, o 19:09 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
matematyka464 napisał(a):
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 x_0 jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
x_0^n I to jest dla mnie jasne.
oraz:
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 :)
Góra
Mężczyzna Offline
PostNapisane: 1 sty 2015, o 00:47 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
Cytuj:
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 napisał(a):
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 x_0 jest rzeczonym pierwiastkiem, to następujące ciągi stanowią rozwiązanie równania rekurencyjnego:
x_0^n I to jest dla mnie jasne.
oraz:
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 \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 \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 \epsilon
Policz granicę z przewidywanej postaci rozwiązania (dla różnych pierwiastków) przy \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ą
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 funkcja generująca  iwazach  0
 Funkcja generująca - zadanie 2  lukabesoin  3
 Mały problem z funkcją tworzącą  kogutto  1
 Ile jest liczb...; funkcja tworząca; wzór jawny.  marta81  1
 Dwa zadania: metoda wlaczen i wylaczen oraz funkcja tworzaca  Zajec  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl