szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 11:35 
Użytkownik

Posty: 31
Lokalizacja: Kraków
Wyznacz ciąg U _{n} jeśli:
a)\ U _{0} = 0, U _{1} = 1, U _{n+2} - U _{n+1} - 6U _{n} = n, (n \ge 0) \\
 b)\ U _{0}=2, U _{1}=-6,U _{n+2}+8U _{n+1} - 9U _{n}=8  \cdot  3 ^{n+1}, (n \ge 0) \\
 c)\ U _{n+2} - 6U _{n+1} + 9U _{n}=2 ^{n}+n, (n \ge 0)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 17:34 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
proponuję funkcje tworzące
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 18:06 
Użytkownik

Posty: 31
Lokalizacja: Kraków
Nic mi to Panie Arku nie mówi. Z dyskretnej jestem absolutnie ciemny. Może gdybym zobaczył rozwiązany przykład to coś by mi w głowie zaświtało :/.
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 18:23 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
Przy odrobinie czasu mogę z jedno trzasnąć ale myślę , że mnie ktoś ubiegnie np Premislaw...
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 18:35 
Użytkownik

Posty: 31
Lokalizacja: Kraków
DZIĘKUJĘ! BĘDĘ MEGA, ALE TO MEGA WDZIĘCZNY!

Postaram się rozwiązać resztę przykładów wzorując się na jednym wykonanym przez Pana.
(O ile mi się coś rozjaśni...)
PS.Dyskretna to chyba najgorsze co może być na studiach informatycznych ;>.
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 19:04 
Użytkownik
Avatar użytkownika

Posty: 11865
Lokalizacja: Wrocław
Nie lubię metody przewidywań, więc będzie, jak wyżej postulował arek1357, metodą funkcji tworzących.

a)
U_{n+2}-U_{n+1}-6U_n=n\\ \sum_{n=0}^{ \infty } U_{n+2}x^n- \sum_{n=0}^{ \infty }U_{n+1}x^n-6 \sum_{n=0}^{+\infty}U_n x^n= \sum_{n=0}^{ \infty } nx^n\\
Mnożymy stronami przez x^2 i mamy:
\sum_{n=0}^{ \infty } U_{n+2}x^{n+2}- x\sum_{n=0}^{ \infty }U_{n+1}x^{n+1}-6 x^2\sum_{n=0}^{+\infty}U_n x^n=x^2 \sum_{n=0}^{ \infty } nx^n
Zwijamy \sum_{n=0}^{ \infty } nx^n dla |x|<1:
\sum_{n=0}^{ \infty } nx^n=\sum_{n=1}^{ \infty } nx^n=\\= \sum_{n=1}^{ \infty } \sum_{k=1}^{n}x^n= \sum_{k=1}^{ \infty } \sum_{n=k}^{ \infty }x^n= \sum_{k=1}^{ \infty }\frac{x^k}{1-x}=\frac{x}{(1-x)^2}
Skorzystałem ze wzoru na sumę szeregu geometrycznego (dwa razy) i ze zmiany kolejności sumowania.
Czyli mamy
\sum_{n=0}^{ \infty } U_{n+2}x^{n+2}- x\sum_{n=0}^{ \infty }U_{n+1}x^{n+1}-6 x^2\sum_{n=0}^{+\infty}U_n x^n= \frac{x^3}{(1-x)^2}
Oznaczmy teraz G(x)= \sum_{n=0}^{ \infty } U_n x^n. Mamy z powyższej równości:
G(x)-a_0-a_1x-x(G(x)-a_0)-6x^2G(x)=\frac{x^3}{(1-x)^2}
czyli korzystając z warunków początkowych U_0=0, \ U_1=1:
(1-x-6x^2)G(x)=x+\frac{x^3}{(1-x)^2}\\ G(x)= \frac{x+\frac{x^3}{(1-x)^2}}{1-x-6x^2}=-\frac{2x^3-2x^2+x}{6(1-x)^2(x+\frac 1 2)(x-\frac 1 3)}=\\=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{x+\frac 1 2}+\frac{D}{x-\frac 1 3}
- rozkład na ułamki proste.
Współczynniki A, B, C, D znajdujemy mnożąc przez mianownik lewej strony i rozważając równość wielomianów (współczynniki muszą być równe, to daje układ czterech równań liniowych z czterema niewiadomymi A, B, C, D).
Następnie te ułamki proste rozwijamy w szeregi potęgowe wg:
\frac{1}{1-x} =\sum_{n=0}^{\infty}x^n \\ \frac{1}{(1-x)^2} = \sum_{n=0}^{ \infty }(n+1)x^n, łączymy to w jeden szereg
i mamy
G(x)= \sum_{n=0}^{ \infty } \left(A+B(n+1)+2C(-2)^n -3D \cdot 3^n\right) x^n,
stąd (przy n-tej potędze w G(x) stoi nasze U_n) otrzymujemy, że
U_n=A+B(n+1)+2C(-2)^n -3D \cdot 3^n
Współczynniki A, B, C, D sobie wyznacz. Po zastosowaniu tego z wielomianami i przyrównaniem współczynników otrzymasz, jak wspomniałem, układ równań. Tu możesz sobie sprawdzić wynik tego rozkładu na ułamki proste:
http://www.wolframalpha.com/input/?i=Apart%5B-(2x%5E3-2x%5E2%2Bx)%2F(6(1-x)%5E2(x%2B1%2F2)(x-1%2F3))%5D
b) i c) już mi się nie chce, ale da się podobnie. A dyskretna jest trudna, ale potrzebna, więc jej nie lekceważ.
Góra
Mężczyzna Offline
PostNapisane: 23 lis 2017, o 19:48 
Użytkownik

Posty: 31
Lokalizacja: Kraków
Jej!
Ukłony Premislav w Twoją stronę. DZIĘKUJĘ! WIĘCEJ LUDZI DOBREGO SERCA.
Pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2017, o 20:44 
Użytkownik
Avatar użytkownika

Posty: 6604
Lokalizacja: 53°02'N 18°35'E
Premislav, jak podobałby ci się taki sposób ?

Jednorodne rozwiązujemy przekształcając je w układ równań i stosując metode algebraiczną
wykorzystującą wartości i wektory własne
(zamiast e^{At} liczymy A^n)
Rozwiązanie szczególne równania niejednorodnego znajdujemy uzmienniając stałe
(zamiast Wrońskianu mamy Casoratian a zamiast całkować sumujemy)

Zakres stosowania tej metody jest zbliżony do metody przewidywań
ale jest pozbawiona zgadywania a dodatkowo można doszukać się analogii do równań różniczkowych
Nie ćwiczyłem tej metody dość dobrze ale zdaje się że będzie wymagała nieco więcej obliczeń
ale mimo to bym ją proponował zamiast równania charakterystycznego i zgadywania
jeśli nie mieliśmy wprowadzonych funkcji tworzących
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2017, o 19:34 
Użytkownik
Avatar użytkownika

Posty: 11865
Lokalizacja: Wrocław
mariuszm, nie stosowałem nigdy takiego sposobu, ale brzmi ciekawie. Osobiście bardzo nie lubię zgadywania, dlatego np. wolę metodę uzmienniania stałych w równaniach różniczkowych niż metodę przewidywań. Może spróbuję to sobie przeliczyć, jak będę się nudzić w następny weekend.
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2017, o 20:46 
Użytkownik
Avatar użytkownika

Posty: 6604
Lokalizacja: 53°02'N 18°35'E
Jeśli chodzi o sposób będący analogiem uzmiennienia stałej to opisuje
go koleś z UMK i w sieci jest umieszczony jego pdf

Uzmiennianie stałych dla równań rekurencyjnych masz np w tym pdf

http://www-users.mat.uni.torun.pl/~much ... xi2006.pdf

od strony 13

Jednorodne proponowałbym przekształcić w układ równań głównie dlatego
aby uniknąć zgadywania w przypadku wielokrotnych pierwiastków
Tutaj jeśli po sprowadzeniu do układu równań dostaniemy macierz diagonalizowalną
to mamy stosunkowo łatwy do rozwiązania układ równań
Obliczenia nieco się skomplikują gdy macierz układu nie będzie diagonalizowalna

Ten sposób proponowałbym tym którzy jeszcze nie mieli funkcji tworzących
a nie lubią zgadywać

Ogólny szkic tego sposobu

Mamy równanie

a\left( n+k\right) +p_{1}a\left(n+k-1\right)+\ldots+p_{k}a\left( n\right) =f\left( n\right)\\

Równanie jednorodne rozwiązujemy sprowadzając do układu równań

a\left( n+k\right) +p_{1}a\left(n+k-1\right)+\ldots+p_{k}a\left( n\right) =0\\
\vec{a\left( n+1\right) }=A\vec{a\left( n\right) }\\
\vec{a\left( n\right) }=A^n\vec{a\left( 0\right) }\\

Potęgę macierzy znajdujemy metodami znanymi z algebry liniowej
najlepiej wykorzystując jakiś rozkład macierzy
Wartości i wektory własne mogą być tutaj przydatne

Jeśli znamy rozwiązanie ogólne równania jednorodnego to
rozwiązanie szczególne równania niejednorodnego znajdziemy w ten sposób

\varphi_{s}\left( n\right)=c_{1}\left( n\right)\varphi_{1}\left( n\right)+c_{2}\left( n\right)\varphi_{2}\left( n\right)+\ldots+c_{k}\left( n\right)\varphi_{k}\left( n\right)\\
 \begin{bmatrix}\varphi_{1}\left( n+1\right) & \varphi_{2}\left( n+1\right) &\ldots &  \varphi_{k}\left( n+1\right) \\ \varphi_{1}\left( n+2\right) & \varphi_{2}\left( n+2\right) &\ldots &  \varphi_{k}\left( n+2\right)\\\vdots&\vdots &\ddots&\vdots\\\varphi_{1}\left( n+k\right) & \varphi_{2}\left( n+k\right) &\ldots &  \varphi_{k}\left( n+k\right) \end{bmatrix} \cdot  \begin{bmatrix} \\\Delta c_{1}\left( n\right)  \\ \Delta c_{2}\left( n\right)\\\vdots\\\Delta c_{k}\left( n\right) \end{bmatrix}= \begin{bmatrix} 0 \\ 0\\\vdots\\f\left( n\right)  \end{bmatrix}
gdzie \Delta c\left( n\right)=c\left( n+1\right)-c\left( n\right)
więc wystarczy zsumować to co dostaniemy z rozwiązania wyżej wymienionego
układu równań i wstawić do wzorku

Co do obliczania potęgi macierzy A to dla macierzy diagonalizowalnej wystarczy rozkład
A=PDP^{-1}

gdzie P to macierz której kolumny są wektorami własnymi macierzy A
a D to macierz diagonalna z wartościami własnymi na głównej przekątnej

Jeśli liczba liniowo niezależnych wektorów własnych jest równa stopniowi macierzy A
to taki rozkład istnieje i stosunkowo łatwo go otrzymać

Jeśli taki rozkład nie istnieje to obliczenia się komplikują
Jak pytałem o ten przypadek na innym forum kolesia który chwalił się że kiedyś wykładał
to nie umiał mi tego porządnie wytłumaczyć
Jedyne co stwierdził to że wystarczy dokonać
rozkładu na sumę macierzy diagonalizowalnej i nilpotentnej
Zresztą dziwne to jest forum co nawet texa porządnego nie mają

Przykład c) może być ciekawszy jak ktoś chce sprawdzić ten sposób w praktyce
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zamiana ciagu rekurencyjnego na ogolny  eoor  1
 Udowodnić sume ciągu  mostostalek  7
 Postac rekurencyjna ciagu 2,2,-4-4,8,8,-16,-16,32,32....  jesionekl  1
 Znajdz funkcje tworzaca ciagu  brasco  0
 definicja rekurencyjna ciągu  Demon  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl