Wyznacz ciąg \(\displaystyle{ U _{n}}\) jeśli:
\(\displaystyle{ 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)}\)
Wyznaczanie ciągu Un
-
Eko140
- Użytkownik
- Posty: 25
- Rejestracja: 8 mar 2016, o 19:27
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 5 razy
Wyznaczanie ciągu Un
Ostatnio zmieniony 23 lis 2017, o 14:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
Eko140
- Użytkownik
- Posty: 25
- Rejestracja: 8 mar 2016, o 19:27
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 5 razy
Re: Wyznaczanie ciągu Un
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 :/.
-
Eko140
- Użytkownik
- Posty: 25
- Rejestracja: 8 mar 2016, o 19:27
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 5 razy
Re: Wyznaczanie ciągu Un
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 ;>.
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 ;>.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Wyznaczanie ciągu Un
Nie lubię metody przewidywań, więc będzie, jak wyżej postulował arek1357, metodą funkcji tworzących.
a)
\(\displaystyle{ 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 \(\displaystyle{ x^2}\) i mamy:
\(\displaystyle{ \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 \(\displaystyle{ \sum_{n=0}^{ \infty } nx^n}\) dla \(\displaystyle{ |x|<1}\):
\(\displaystyle{ \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
\(\displaystyle{ \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 \(\displaystyle{ G(x)= \sum_{n=0}^{ \infty } U_n x^n}\). Mamy z powyższej równości:
\(\displaystyle{ 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 \(\displaystyle{ U_0=0, \ U_1=1}\):
\(\displaystyle{ (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 \(\displaystyle{ 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 \(\displaystyle{ A, B, C, D}\)).
Następnie te ułamki proste rozwijamy w szeregi potęgowe wg:
\(\displaystyle{ \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
\(\displaystyle{ 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 \(\displaystyle{ G(x)}\) stoi nasze \(\displaystyle{ U_n}\)) otrzymujemy, że
\(\displaystyle{ U_n=A+B(n+1)+2C(-2)^n -3D \cdot 3^n}\)
Współczynniki \(\displaystyle{ 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:
b) i c) już mi się nie chce, ale da się podobnie. A dyskretna jest trudna, ale potrzebna, więc jej nie lekceważ.
a)
\(\displaystyle{ 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 \(\displaystyle{ x^2}\) i mamy:
\(\displaystyle{ \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 \(\displaystyle{ \sum_{n=0}^{ \infty } nx^n}\) dla \(\displaystyle{ |x|<1}\):
\(\displaystyle{ \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
\(\displaystyle{ \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 \(\displaystyle{ G(x)= \sum_{n=0}^{ \infty } U_n x^n}\). Mamy z powyższej równości:
\(\displaystyle{ 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 \(\displaystyle{ U_0=0, \ U_1=1}\):
\(\displaystyle{ (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 \(\displaystyle{ 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 \(\displaystyle{ A, B, C, D}\)).
Następnie te ułamki proste rozwijamy w szeregi potęgowe wg:
\(\displaystyle{ \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
\(\displaystyle{ 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 \(\displaystyle{ G(x)}\) stoi nasze \(\displaystyle{ U_n}\)) otrzymujemy, że
\(\displaystyle{ U_n=A+B(n+1)+2C(-2)^n -3D \cdot 3^n}\)
Współczynniki \(\displaystyle{ 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:
b) i c) już mi się nie chce, ale da się podobnie. A dyskretna jest trudna, ale potrzebna, więc jej nie lekceważ.
-
Eko140
- Użytkownik
- Posty: 25
- Rejestracja: 8 mar 2016, o 19:27
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 5 razy
Re: Wyznaczanie ciągu Un
Jej!
Ukłony Premislav w Twoją stronę. DZIĘKUJĘ! WIĘCEJ LUDZI DOBREGO SERCA.
Pozdrawiam.
Ukłony Premislav w Twoją stronę. DZIĘKUJĘ! WIĘCEJ LUDZI DOBREGO SERCA.
Pozdrawiam.
-
Mariusz M
- Użytkownik
- Posty: 6908
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Re: Wyznaczanie ciągu Un
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 \(\displaystyle{ e^{At}}\) liczymy \(\displaystyle{ 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
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 \(\displaystyle{ e^{At}}\) liczymy \(\displaystyle{ 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
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Wyznaczanie ciągu Un
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.
-
Mariusz M
- Użytkownik
- Posty: 6908
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Re: Wyznaczanie ciągu Un
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
... 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
\(\displaystyle{ 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ń
\(\displaystyle{ 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
\(\displaystyle{ \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 \(\displaystyle{ \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
\(\displaystyle{ 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
go koleś z UMK i w sieci jest umieszczony jego pdf
Uzmiennianie stałych dla równań rekurencyjnych masz np w tym pdf
... 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
\(\displaystyle{ 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ń
\(\displaystyle{ 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
\(\displaystyle{ \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 \(\displaystyle{ \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
\(\displaystyle{ 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