szukanie zaawansowane
 [ Posty: 20 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 gru 2014, o 19:21 
Użytkownik

Posty: 42
Witam, mam tutaj garść problemów związanych z rekurencją

1) Jakie jest rozwiązanie, zależne od n, poniższej rekurencji?
a_0=\sqrt{2},a_1=\frac{1}{\sqrt{2}+1}
oraz dla n \geq 1
a_{2n}=2a_n+\sqrt{2}
a_{2n+1}=2a_n+\frac{1}{\sqrt{2}-1}

2) Niech b_0=1, b_1=3, b_2=4, b_3=0, b_4=2
oraz dla n\geq 1
b_{5n}=21b_n+1
b_{5n+1}=21b_n+3
b_{5n+2}=21b_n+4
b_{5n+3}=21b_n
b_{5n+4}=21b_n+2
Czy powyższy ciąg jest różnowartościowy? (Jeśli tak, to uzasadnić.)

3) Niech c_0=0, c_1=2, c_2=1
oraz dla n \geq 1
c_{3n}=2c_n
c_{3n+1}=2c_n+2
c_{3n+2}=2c_n+1

Czy powyższy ciąg przyjmuje wartości postaci 2^k, jeśli tak to wyznaczyć (z uzasadnieniem) wszystkie argumenty, dla których one są osiągane.

4) Podać rozwiązanie rekurencji:
d_0=1,d_1=-1,d_2=1,d_3=-1
oraz dla n \geq 1
d_{4n}=d_n
d_{4n+1}=-d_n
d_{4n+2}=d_n
d_{4n+3}=-d_n

Nie będę ukrywać, że pomocny może być mój blog. :) Ale ciekawią mnie też, a może nawet bardziej niezależne pomysły.
Góra
Mężczyzna Online
PostNapisane: 24 gru 2014, o 11:43 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
W zadaniu np czwartym jak dodasz strony lewe i prawe otrzymasz:

d_{4n+3}+d_{4n+2}+d_{4n+1}+d_{4n}=0

równanie charakterystyczne:

r^3+r^2+r+1=0

pierwiastki:

-1, i ,-i

czyli przewidujesz rozwiązanie w postaci:

d_{n}=a(-1)^n+bi^n+c(-i)^n

a warunki brzegowe?

i teraz coś mi się nie bardzo widzi z tym całym początkiem jak masz w definicji ciągu:

dla: n>2

to pierwszy wyraz , który otrzymasz to d_{4 \cdot 3}=d_{12}=d_{3}=-1
A gdzie pozostałe?

i w ogóle te warunki początkowe w tych zadaniach są dla mnie nie za bardzo spójne!
W zadaniu np 1 nie wyznaczysz a_{2} ,
itd...

W zadaniu pierwszym np układ spełnia zależność niejednorodną:

a_{2n+1}=a_{2n}+1
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 15:32 
Użytkownik

Posty: 42
Przepraszam, rzeczywiście źle to napisałem. Już poprawiłem. Chodziło oczywiście o to, że pewną ilość wyrazów początkowych osobno definiuję, a pozostałe wg podanej zależności.

-- 25 gru 2014, o 15:29 --

arek1357 napisał(a):
d_{n}=a(-1)^n+bi^n+c(-i)^n
Jedno jest pewne. Rozwiązaniem tej rekurencji jest -1 do czegoś zależnego od n, ale to nie może mieć takiej reprezentacji. Bo wtedy
-1=d_1=d_4=a+b+c
1=-d_1=d_{4+1}=-a+bi-ci stąd b=c
-1=d_1=d_{4+2}=a-b-c=a-2b
1=-d_1=d_{4+3}=-a-bi+ci=-a stąd a=-1
to np. z 3. równania b=c=0 co implikuje, że d_n=-(-1)^n, ale np. -1=d_{4\cdot5}=d_5=d_{4+1}=-d_1=1 - sprzeczność.
Góra
Mężczyzna Online
PostNapisane: 25 gru 2014, o 17:02 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
Można by się pokusić o ciut inne rozwiązanie np:

d_{4n+1}+ d_{4n+2}+ d_{4n+3} +d_{4n+4}=(-1)^n \cdot 2

Bo rzeczywiście ten ciąg łamie się dopiero na granicy 4n,4n+1 - na przemian jedynki lub minus jedynki
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 18:10 
Użytkownik

Posty: 42
To też nie. Wiemy, że d_n \in \{-1,1\}. Zatem równość
d_{n+1}-d_n=-d_n+d_n-d_n+d_{n+1}=d_{4n+1}+d_{4n+2}+d_{4n+3}+d_{4n+4}=2(-1)^n
Oznacza, że d_{n+1}\neq d_n, a więc d_{n+1}=-d_n a to by oznaczało d_n=(-1)^n, co z pewnością nie jest prawdziwe dla np. n=7.

Nie wspomniałem o tym, ale moje rozwiązanie jest postaci -1 do pewnej funkcji, której nie da się za bardzo wyrazić przy pomocy funkcji elementarnych. Oczywiście, nie oznacza to, że nie dałoby się znaleźć funkcji elementarnej, która przystaje do niej modulo 2, ale znając rozwiązanie wątpię, aby dało sie coś takiego zrobić.

Generalnie, tylko w pierwszym zadaniu da się znaleźć rozwiązanie wyrażone przez elementarne operacje (i część całkowitą).
Góra
Mężczyzna Online
PostNapisane: 25 gru 2014, o 18:37 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
mam tam to tylko tak sobie głośno myślałem masz racje
i jak rozwiązałem to równanie niejednorodne to nic dobrego z tego nie wyszło!

ale zauważyłem , że to równanie można ładnie zwijać:
posiada okres:

1,1,-1,1,-1,-1,1,-1, ===  ,1,1

dziewiąty wyraz się już powtarza i wszystko idzie tak samo od nowa a więc równanie rekurencyjne powinno wyglądać tak:

d_{n+8}=d_{n}

a więc równanie charakterystyczne powinno wyglądać tak:

r^8=1

z warunkami brzegowymi:

d_{1}=1,d_{2}=1,d_{3}=-1,d_{4}=1,d_{5}=-1,d_{6}=-1,d_{7}=1,d_{8}=-1

pomijając już jak to się zaczyna czy od jeden czy od minus jeden i dlatego uprościłem żeby ujednolicić


I zamiast od - d_{0} zacząłem od - d_{1}


Ale szukanie pierwiastków stopnia osiem z jedynki potem znajdywanie współczynników raczej nie należy
to do rzeczy łatwych i przyjemnych.Może w wolframie da się to zrobić.


Zauważyłem jeszcze coś mianowicie:

d_{n}=-d_{n+4}

co by uprościło nasz układ.
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 19:25 
Użytkownik

Posty: 42
Powinienem powiedzieć jeszcze jedną rzecz, ja nie znam żadnych standardowych metod rozwiązywania równań rekurencyjnych. Jednak mimo tego, wymyśliłem metodę (wzór na rozwiązanie)
dla tego typu równań jak te, które są zaprezentowane w zadaniach. Właśnie z powodu tej niewiedzy chciałem zobaczyć jak standardowe metody sobie radzą z takimi równaniami. Dlatego potrzebny mi jest wynik, który bedę mógł sobie już jakoś zweryfilkować.

Poniżej zamieszczam odpowiedź do zadania 4., jeśli nie masz ochoty więcej się z tym bawić. Tak czy owak dzięki za zainteresowanie.
Ukryta treść:    
Góra
Mężczyzna Online
PostNapisane: 25 gru 2014, o 19:30 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
No ciekawe ale chyba nasze metody są w tym wypadku równoważne
Dla mnie w tym momencie zadanie się rozświetliło jak zobaczyłem, że w końcu liczby zaczynają się powtarzać! A moja metoda to metoda równania charakterystycznego dla ciągu jednorodnego.


Tylko nie rozumiem co masz na myśli przez sumę cyfr liczby zespolonej w postaci czwórkowej?

rozwiązujesz równanie postaci:

r^4=-1

i przewidujesz ciąg postaci:

d_{n}=ar_{1}^n+br_{2}^n+cr_{3}^n+dr_{4}^n

gdzie a,b,c,d - wyznaczasz z warunków początkowych a r_{i}

to pierwiastki czwartego stopnia z minus jedynki co nie należy do przyjemności ich liczenie
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 19:50 
Użytkownik

Posty: 42
Napisałem "przedstawionej", a nie "zespolonej". Chodziło o zwykłe rozwinięcie w systemie czwórkowym. :) Nie do końca jeszcze widzę jak dochodzisz do tego samego rozwiązania jak ja.
Góra
Mężczyzna Online
PostNapisane: 25 gru 2014, o 19:54 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
Nie o to chodzi że ja tak samo rozwiązałem jak ty tylko, że nasze rozwiązania powinny być równoważne!
Ale rozumiem idee twojego rozumowania sorki w twoim zapisie i wziąłem jako zespolone i dlatego to zamieszanie nie popatrzyłem dobrze.
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 20:02 
Gość Specjalny
Avatar użytkownika

Posty: 12737
Lokalizacja: Kraków
arek1357 napisał(a):
d_{4n+3}+d_{4n+2}+d_{4n+1}+d_{4n}=0

równanie charakterystyczne:

r^3+r^2+r+1=0

Nie można stosować metody równań charakterystycznych w takim przypadku.


arek1357 napisał(a):
ale zauważyłem , że to równanie można ładnie zwijać:
posiada okres:

1,1,-1,1,-1,-1,1,-1, ===  ,1,1

dziewiąty wyraz się już powtarza i wszystko idzie tak samo od nowa a więc równanie rekurencyjne powinno wyglądać tak:

d_{n+8}=d_{n}

Zauważyłeś, czy udowodniłeś? To są dwie różne rzeczy. Jeżeli tego nie dowiodłeś, to dalsze rachunki są bezzasadne.


arek1357 napisał(a):
Tylko nie rozumiem co masz na myśli przez sumę cyfr liczby zespolonej w postaci czwórkowej?

Nie jest to pytanie do mnie, ale jego zadanie świadczy o pewnym niezrozumieniu. Rekurencje rzeczywiste mogą mieć bazowe rozwiązania zespolone, ale jawna postać dowolnego wyrazu ciągu odczytana z ogólnego rozwiązania rekurencji zawsze będzie liczbą rzeczywistą nawet jeżeli wzór ogólny zawiera człony zespolone.

arek1357 napisał(a):
to pierwiastki czwartego stopnia z minus jedynki co nie należy do przyjemności ich liczenie

Hmm to są pierwiastki czwartego stopnia z 1 razy e^{i\frac{\pi}{4}}. Proste, jeżeli spojrzy się na to geometrycznie.

arek1357, widzę dużo "machania rękami", niestety.

Cutlass napisał(a):
Poniżej zamieszczam odpowiedź do zadania 4., jeśli nie masz ochoty więcej się z tym bawić. Tak czy owak dzięki za zainteresowanie.
Ukryta treść:    

Czy to jest wynik, który uzyskałeś sam z obliczeń, czy przepisałeś znane Ci ze źródła rozwiązanie? Jeżeli to pierwsze, chętnie zobaczyłbym sposób.
Góra
Mężczyzna Online
PostNapisane: 25 gru 2014, o 20:07 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
Co do pierwszego cytatu sprawa jest zamknięta. tu się zgadzam i mój błąd!

Ale że równanie od dziewiątego miejsca się powtarza to już nie jest machanie rękami i sprawa jest oczywista!
Pewne rzeczy się udowadnia a pewne wystarczy zaobserwować oczywiście, że na początku machałem rękami i z tym się zgodzę jednak tę zależność można nawet udowodnić indukcyjnie i po sprawie nie sądzę że muszę udowadniać rzeczy oczywistych i wszystkich swoich przemyśleń!


Cytuj:
Cyt Yorgina:
Nie jest to pytanie do mnie, ale jego zadanie świadczy o pewnym niezrozumieniu. Rekurencje rzeczywiste mogą mieć bazowe rozwiązania zespolone, ale jawna postać dowolnego wyrazu ciągu odczytana z ogólnego rozwiązania rekurencji zawsze będzie liczbą rzeczywistą nawet jeżeli wzór ogólny zawiera człony zespolone.


A co ty myślisz, że ja o tym nie wiem a ty się wymądrzasz trzeba było napisać rozwiązanie a nie
grać rolę mędrca.Jakbyś czytał ze zrozumieniem co pisałem, to miałem zupełnie co inne na myśli.

I jeszcze jedno skoro jak słusznie zauważyłeś że pytanie było nie do Ciebie to łaskawie mogłeś nie
zajmować "wątpliwego" stanowiska!
Chyba że chciałeś nas maluczkich forumowiczów oświecić swoją elokwencją i wiedzą!

Cytuj:
Hmm to są pierwiastki czwartego stopnia z 1 razy e^{i\frac{\pi}{4}}. Proste, jeżeli spojrzy się na to geometrycznie.


Tyle to też wiem ale miałem na myśli postać typu a+bi

Też kolejna próba mędrkowania.

A po trzecie forum jest miejscem wymiany myśli i pewnych doświadczeń więc skoro jak piszesz
że machałem rękami(głośno może myślałem ...może i na początku błędnie)!
to masz racje bo czasem nim coś rozwiążę to sporo się namacham ponieważ nie należę do grona mędrców jak np Ty.
Z poważaniem!

Jeden post z gatunku: "Machając rękami i nogami" prawie usunąłem, drugi tzn. pierwszy raportowałem bo jego wartość merytoryczna jest do bani ja słusznie zresztą zauważył Yorgin!
Góra
Mężczyzna Offline
PostNapisane: 25 gru 2014, o 21:23 
Gość Specjalny
Avatar użytkownika

Posty: 12737
Lokalizacja: Kraków
arek1357 napisał(a):
Ale że równanie od dziewiątego miejsca się powtarza to już nie jest machanie rękami i sprawa jest oczywista!
Pewne rzeczy się udowadnia a pewne wystarczy zaobserwować oczywiście, (...) nie sądzę że muszę udowadniać rzeczy oczywistych i wszystkich swoich przemyśleń!

Fakty nawet oczywiste wymagają formalnego uzasadnienia. Rzecz oczywista dla Ciebie nie musi być oczywista dla kogoś innego.

arek1357 napisał(a):
A co ty myślisz, że ja o tym nie wiem a ty się wymądrzasz trzeba było napisać rozwiązanie a nie
grać rolę mędrca.Jakbyś czytał ze zrozumieniem co pisałem, to miałem zupełnie co inne na myśli.

Czytałem i znalazłem sumowanie cyfr liczby zespolonej.

arek1357 napisał(a):
I jeszcze jedno skoro jak słusznie zauważyłeś że pytanie było nie do Ciebie to łaskawie mogłeś nie
zajmować "wątpliwego" stanowiska!
Chyba że chciałeś nas maluczkich forumowiczów oświecić swoją elokwencją i wiedzą!

Ja nie odpowiadałem na pytanie, tylko komentowałem sam fakt jego zadania. Jak widać z Twojego komentarza, nie doceniłem Twojej wiedzy, której nie wyeksponowałeś wystarczająco. Mea culpa.

arek1357 napisał(a):
Tyle to też wiem ale miałem na myśli postać typu a+bi

Ja nie widzę problemu - wzory są, wystarczy podstawić i żadnych trudnych obliczeń nie widzę.

arek1357 napisał(a):
A po trzecie forum jest miejscem wymiany myśli i pewnych doświadczeń więc skoro jak piszesz
że machałem rękami(głośno może myślałem ...może i na początku błędnie)!
to masz racje bo czasem nim coś rozwiążę to sporo się namacham ponieważ nie należę do grona mędrców jak np Ty.

Ja nie tytułuję się mędrcem ani nikim podobnym.

Wymiana myśli ok, ale i ja również chciałem wymienić swoje spostrzeżenia z tego tematu, w szczególności zwrócić uwagę na Twoje wypowiedzi, które nie są do końca jasne i szczegółowe. Przynajmniej nie są dla mnie i może przy okazji chciałem wyjaśnić swoje wątpliwości.

arek1357 napisał(a):
Jeden post z gatunku: "Machając rękami i nogami" prawie usunąłem, drugi tzn. pierwszy raportowałem bo jego wartość merytoryczna jest do bani ja słusznie zresztą zauważył Yorgin!

Raportowanie swoich postów jest "dziwne", a usuwanie zawartości co niektórych jest zabronione.
Góra
Mężczyzna Online
PostNapisane: 26 gru 2014, o 02:12 
Użytkownik
Avatar użytkownika

Posty: 3486
Lokalizacja: blisko
Cytuj:
Raportowanie swoich postów jest "dziwne", a usuwanie zawartości co niektórych jest zabronione.


Co w tym dziwnego , że raportowałem coś co obydwoje uznaliśmy za niedorzeczność ,kilka razy już na forum raportowałem niektóre posty , które uznałem za głupie a mój nie miał wielkiej wartości dydaktycznej

A usuwanie zawartości "co niektórych" jak piszesz jest zabronione. I teraz wnioskuję z tego, że mój post
należał do tych "co niektórych" choć jasno tego nie sprecyzowałeś, i wnioskuję dalej, że pewnie za to, że mój post należał do tych "co niektórych" dostałem ostrzeżenie co raczej jest żałosne!
Moja rada na przyszłość najpierw doprecyzuj pojęcie "co niektórych" a potem banuj lub wstawiaj ostrzeżenie bo jak na Ciebie to mało profesjonalne stać Cię na więcej...
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2014, o 11:45 
Użytkownik

Posty: 42
yorgin napisał(a):
Czy to jest wynik, który uzyskałeś sam z obliczeń, czy przepisałeś znane Ci ze źródła rozwiązanie? Jeżeli to pierwsze, chętnie zobaczyłbym sposób.
Zadania wymyśliłem specjalnie pod wzór, który prezentuję na swoim blogu (i do którego doszedłem samodzielnie).
Powiedzmy, żeby nie zepsuć zabawy z pozostałymi zadaniami, udowodnię wzór obejmujący tylko nieco ogólniejszą sytuację z zadania 4.
Rozważmy równanie
d_{4n+r}=\alpha(r)d_n dla n>0, r=0,1,2,3 z dowolnymi d_r, \alpha(r)\neq 0.
Wtedy dla dowolnego n=\sum_{i=0}^N c_i 4^i=c_N\dots c_1 c_0, gdzie c_i \in \{0,1,2,3\} oraz gdzie potęga N jest minimalną, potrzebną do zapisania n w systemie czwórkowym,
zachodzi:
d_{c_N\dots c_1 c_0}n=d_{c_N}\prod_{j=0}^{N-1}\alpha(c_j)
Dowód.
Oznaczmy przez z kandydata na rozwiązanie z tezy. Zauważmy, że z(c_0)=d_{c_0} \prod_{j=0}^{-1}\alpha(c_j)=d_{c_0} \prod_{j\in \emptyset} \alpha_{c_j}=d_{c_0}.
Zatem zgadzają się wyrazy początkowe. To teraz wystarczy pokazać, że z definiuje ta sama zależność rekurencyjna. Weźmy dowolne 4n+r=\sum_{i=0}^N c_i 4^i. Wtedy r=c_0 oraz n=\sum_{i=1}^N c_i 4^{i-1}=\sum_{j=0} ^{N-1}c_{j+1}4^j,
co daje, że
z(n)=z(c_{(N-1)+1})\prod_{j=0}^{N-2}c_{j+1}=z(c_N)\prod_{i=1}^{N-1}\alpha(c_i)
a także
z(4n+r)=z(c_N)\prod_{j=0}^{N-1} \alpha(c_j)=\alpha(r) z(c_N)\prod_{j=1}^{N-1} \alpha(c_j)=\alpha(r)z(n).
Koniec dowodu.

Teraz wystarczy tylko zauważyć, że dla d zdefiniowanego w zadaniu 4. zachodzi d_r=\alpha_r=(-1)^r.
A więc stosując wzór dla n=\sum_{i=0}^Nc_i4^i zachodzi
d_n=\prod_{j=0}^N (-1)^{c_j}=(-1)^{\displaystyle \sum_{i=0}^Nc_i}.

Generalnie, idea jest taka, żeby szukać rozwiązania zależnego od rozwinięć w systemie pozycyjnym o odpowiedniej podstawie. Jeśli we wzorze schodzimy z m=Ln+rdo n itd. to de facto obliczając wartości ciągu, po drodze wyznaczamy rozwinięcie wyjściowego m przy podstawie L.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 20 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiazywanie rownania z uzyciem wzoru Newtona  birdy1986  7
 m dyskretna - Ile jest całkowitych rozwiązań równania .  torbol  1
 Równanie rekurencyjne liniowe niejednorodne  freeze2  1
 Kombinatoryka (rozwiąż równania)  allexx  3
 Jak kombinatorycznie dowieść poprawność równania??  tupatek  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl