Rekursioprobleeman ratkaisutapoja

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Mixerin aikaisempi kirjoitus sisälsi seuraavanlaisen rekursioprobleeman, joka pyrittiin todistamaan induktiolla.

Olkoon a[size=70:1s5hgsag]1[/size:1s5hgsag] = a[size=70:1s5hgsag]2[/size:1s5hgsag] = 5 ja a[size=70:1s5hgsag]n+1[/size:1s5hgsag] = a[size=70:1s5hgsag]n[/size:1s5hgsag] + 6a[size=70:1s5hgsag]n-1[/size:1s5hgsag] . Todista induktiolla, että a[size=70:1s5hgsag]n[/size:1s5hgsag] = 3^n - ((-2)^n), kun n on kokonaisluku.

Induktiollahan tämä onnistuu, mutta rupesin miettimään, mitä muita ratkaisutapoja ongelmaan voisi soveltaa. Yhden osasin jo etukäteen:

Oletetaan, että ratkaisu on muotoa r^n. Sijoitetaan yhtälöön ja jaetaan r^(n-1):llä. Saadaan toisen asteen yhtälö

r^2 - r - 6 = 0,

jonka ratkaisut ovat 3 ja -2. Yleinen ratkaisu probleemalle on siis muotoa a[size=70:1s5hgsag]n[/size:1s5hgsag] = A ∙ 3^n + B ∙ (-2)^n. Alkuehdoista muodostetun yhtälöparin nojalla A = 1 ja B = -1, ja näin ratkaisu on löytynyt.

Samaa en kuitenkaan osaisi tehdä epähomogeeniselle probleemalle (esim. a[size=70:1s5hgsag]n+1[/size:1s5hgsag]=a[size=70:1s5hgsag]n[/size:1s5hgsag]+6a[size=70:1s5hgsag]n-1[/size:1s5hgsag] + n).

Z-muunnostakin voi ilmeisesti soveltaa näihin, mutta silloin yhtälöistä tulee aika raskaita ja hommaan menee enemmän aikaa. Mutta löytyykö muita keinoja näiden kolmen lisäksi?

Kommentit (8)

Vierailija

Ratkaisu esittämääsi tehtävään on tuossa:
http://www.wolframalpha.com/input/?i=a%28n%2B1%29%3Da%28n%29%2B6a%28n-1%...

Rekursioyhtälöthän ovat luonteeltaan samankaltaisia kuin diffisyhtälöt (paitsi diskreettejä). Lineaaristen, epähomogeenisten yhtälöiden ratkaisuun ei ole mitään yleispätevää menetelmää, mutta eräs tapa on käyttää sopivaa yritettä. Lisäksi jos y[size=70:3sc6fdmz]n[/size:3sc6fdmz] on kertalukua k olevan lineaarisen yhtälön jokin ratkaisu ja alkuehdot x[size=70:3sc6fdmz]1[/size:3sc6fdmz], ..., x[size=70:3sc6fdmz]k[/size:3sc6fdmz] on annettu, niin yhtälöllä on yksiselitteinen ratkaisu y[size=70:3sc6fdmz]n[/size:3sc6fdmz]+x[size=70:3sc6fdmz]n[/size:3sc6fdmz], missä x[size=70:3sc6fdmz]n[/size:3sc6fdmz] on vastaavan homogeenisen yhtälön ratkaisu näillä alkuehdoilla.

Tuossa jotain juttua aiheesta (yleisistä lineaarisista rekursioyhtälöistä kohdasta 2.15 alkaen):
http://users.jyu.fi/~tuilmann/jodima/jodima.pdf

Ja tuossa myös jotain:
http://en.wikipedia.org/wiki/Recurrence_relation#Solving

Stratonovich
Seuraa 
Viestejä358
Liittynyt14.6.2009
Kuuba-Pete
Rekursioyhtälöthän ovat luonteeltaan samankaltaisia kuin diffisyhtälöt (paitsi diskreettejä). Lineaaristen, epähomogeenisten yhtälöiden ratkaisuun ei ole mitään yleispätevää menetelmää, mutta eräs tapa on käyttää sopivaa yritettä. Lisäksi jos y[size=70:1u82olk4]n[/size:1u82olk4] on kertalukua k olevan lineaarisen yhtälön jokin ratkaisu ja alkuehdot x[size=70:1u82olk4]1[/size:1u82olk4], ..., x[size=70:1u82olk4]k[/size:1u82olk4] on annettu, niin yhtälöllä on yksiselitteinen ratkaisu y[size=70:1u82olk4]n[/size:1u82olk4]+x[size=70:1u82olk4]n[/size:1u82olk4], missä x[size=70:1u82olk4]n[/size:1u82olk4] on vastaavan homogeenisen yhtälön ratkaisu näillä alkuehdoilla.

Lineaarisilla epähomogeenisilla differentiaaliyhtälöillähän on ihan yleinen ratkaisutapa. Tarkoitan siis sitä mikä opetetaan usemmissa säätötekniikan kirjoissa eli lasketaan fundamentaaliratkaisu ja sitä kautta epähomogeenisen yhtälön ratkaisu käyttämällä sitä integroitavana tekijänä.

Eikö voisi kuvitella, että ihan analoginen geneerinen ratkaisutapa toimisi myös lineaarisiin epähomogeenisiin differenssiyhtälöihin?

Vierailija
Stratonovich
Kuuba-Pete
Rekursioyhtälöthän ovat luonteeltaan samankaltaisia kuin diffisyhtälöt (paitsi diskreettejä). Lineaaristen, epähomogeenisten yhtälöiden ratkaisuun ei ole mitään yleispätevää menetelmää, mutta eräs tapa on käyttää sopivaa yritettä. Lisäksi jos y[size=70:2bsf3e8u]n[/size:2bsf3e8u] on kertalukua k olevan lineaarisen yhtälön jokin ratkaisu ja alkuehdot x[size=70:2bsf3e8u]1[/size:2bsf3e8u], ..., x[size=70:2bsf3e8u]k[/size:2bsf3e8u] on annettu, niin yhtälöllä on yksiselitteinen ratkaisu y[size=70:2bsf3e8u]n[/size:2bsf3e8u]+x[size=70:2bsf3e8u]n[/size:2bsf3e8u], missä x[size=70:2bsf3e8u]n[/size:2bsf3e8u] on vastaavan homogeenisen yhtälön ratkaisu näillä alkuehdoilla.

Lineaarisilla epähomogeenisilla differentiaaliyhtälöillähän on ihan yleinen ratkaisutapa. Tarkoitan siis sitä mikä opetetaan usemmissa säätötekniikan kirjoissa eli lasketaan fundamentaaliratkaisu ja sitä kautta epähomogeenisen yhtälön ratkaisu käyttämällä sitä integroitavana tekijänä.

Tarkoitatko nyt kenties 1. kertaluvun lineaarista differentiaaliyhtälöä, jossa siis esiintyy vain termejä f'(x), f(x) ja jokin epähomogeenitermi g(x)? Ainakin sellaisessa yhtälössä ratkaisut voidaan esittää fundamentaaliratkaisun avulla, tuossa lyhyt esitys siitä:
http://www.sal.tkk.fi/Opinnot/Mat-2.148/K2008/liitteet.pdf

Lineaarinen differentiaaliyhtälöhän on yleisessä tapauksessa muotoa

missä

Tällainen yhtälö voidaan ratkaista ainakin Greenin funktion avulla. En kyllä itse ainakaan muista/osaa sanoa, onko Greenin funktio -menetelmä täysin yleispätevä tai miten se eroaa fundamentaaliratkaisusta? Kaipa se on jonkinlainen yleistys tuohon fundamentaaliratkaisuun (tai sitten toisinpäin)? Ei voi muistaa näitä juttuja enää...

Stratonovich
Eikö voisi kuvitella, että ihan analoginen geneerinen ratkaisutapa toimisi myös lineaarisiin epähomogeenisiin differenssiyhtälöihin?

Jaa'a, kyllä luulisi, että samankaltaiset menetelmät voisivat toimia differenssiyhtälöilläkin. En tosin itse ainakaan muista törmänneeni esim. Greenin funktioiden diskreetteihin versioihin, mutta mikäpä niitä estäisi diskretoimasta?

Stratonovich
Seuraa 
Viestejä358
Liittynyt14.6.2009
Kuuba-Pete
Tällainen yhtälö voidaan ratkaista ainakin Greenin funktion avulla. En kyllä itse ainakaan muista/osaa sanoa, onko Greenin funktio -menetelmä täysin yleispätevä tai miten se eroaa fundamentaaliratkaisusta? Kaipa se on jonkinlainen yleistys tuohon fundamentaaliratkaisuun (tai sitten toisinpäin)? Ei voi muistaa näitä juttuja enää...

Fundamentaaliratkaisu on oikeastaan tässä yhteydessä evoluutio-operaattori tai propagaattori eli eräänlainen operaattorin eksponenttifunktio eikä Greenin funktio, joka on taas eräänlainen operaattorin inverssi. Voi olla kyllä, että terminologia hieman vaihtelee, koska tuolla Wikipediasivulla oli hieman eri määritelmä.

Vierailija
Stratonovich
Kuuba-Pete
Tällainen yhtälö voidaan ratkaista ainakin Greenin funktion avulla. En kyllä itse ainakaan muista/osaa sanoa, onko Greenin funktio -menetelmä täysin yleispätevä tai miten se eroaa fundamentaaliratkaisusta? Kaipa se on jonkinlainen yleistys tuohon fundamentaaliratkaisuun (tai sitten toisinpäin)? Ei voi muistaa näitä juttuja enää...

Fundamentaaliratkaisu on oikeastaan tässä yhteydessä evoluutio-operaattori tai propagaattori eli eräänlainen operaattorin eksponenttifunktio eikä Greenin funktio, joka on taas eräänlainen operaattorin inverssi. Voi olla kyllä, että terminologia hieman vaihtelee, koska tuolla Wikipediasivulla oli hieman eri määritelmä.

Eikös Greenin funktio nimenomaan ole sama asia kuin propagaattori? Ainakin kvanttimekaniikassa propagaattorilla tarkoitetaan juuri Greenin funktiota. Esim. G(x[size=70:3rpo8cm4]f[/size:3rpo8cm4],t[size=70:3rpo8cm4]f[/size:3rpo8cm4];x[size=70:3rpo8cm4]i[/size:3rpo8cm4],t[size=70:3rpo8cm4]i[/size:3rpo8cm4]) voisi olla propagaattori, joka siirtää systeemin pisteestä (x[size=70:3rpo8cm4]i[/size:3rpo8cm4],t[size=70:3rpo8cm4]i[/size:3rpo8cm4]) pisteeseen (x[size=70:3rpo8cm4]f[/size:3rpo8cm4],t[size=70:3rpo8cm4]f[/size:3rpo8cm4]), jolloin ψ(x[size=70:3rpo8cm4]f[/size:3rpo8cm4],t[size=70:3rpo8cm4]f[/size:3rpo8cm4])=∫G(x[size=70:3rpo8cm4]f[/size:3rpo8cm4],t[size=70:3rpo8cm4]f[/size:3rpo8cm4];x[size=70:3rpo8cm4]i[/size:3rpo8cm4],t[size=70:3rpo8cm4]i[/size:3rpo8cm4])ψ(x[size=70:3rpo8cm4]i[/size:3rpo8cm4],t[size=70:3rpo8cm4]i[/size:3rpo8cm4])dx[size=70:3rpo8cm4]i[/size:3rpo8cm4].

Mielestäni tuo fundamentaaliratkaisu vaikuttaa oleellisesti ihan samalta asialta kuin Greenin funktio, mutta hommaa on lähestytty enemmän jostain distribuutioteorian näkökulmasta...

E: Tuosta löytyy jonkinlaista selvitystä, mitä eroa noilla on (elliptisen PDE:n tapauksessa):
http://books.google.fi/books?.... Greenin funktio voidaan nähtävästi ilmoittaa fundamentaaliratkaisun sekä jonkin sileän funktion erotuksena. Ota tuosta nyt sitten selvää...

Stratonovich
Seuraa 
Viestejä358
Liittynyt14.6.2009
Kuuba-Pete
Eikös Greenin funktio nimenomaan ole sama asia kuin propagaattori?

Eikös propagaattori liity Cauchy-tyyppisten ongelmien ratkaisuun eli tällaisiin:

∂f(r,t)/∂t = H f(r,t),

jossa H on joku r-muuttujan suhteen operoiva operaattori. Propagaattori on sitten formaalisti

Φ(r,t) = exp(H t)

Sen sijaan H:n Greenin funktio G(r,r') on tämän yhtälön ratkaisu:

H f(r) = δ(r-r')

eli vähän niin kuin H^-1:ta vastaava integrointiydin.

Vierailija
Stratonovich
Kuuba-Pete
Eikös Greenin funktio nimenomaan ole sama asia kuin propagaattori?

Eikös propagaattori liity Cauchy-tyyppisten ongelmien ratkaisuun eli tällaisiin:

∂f(r,t)/∂t = H f(r,t),

jossa H on joku r-muuttujan suhteen operoiva operaattori. Propagaattori on sitten formaalisti

Φ(r,t) = exp(H t)

Sen sijaan H:n Greenin funktio G(r,r') on tämän yhtälön ratkaisu:

H f(r) = δ(r-r')

eli vähän niin kuin H^-1:ta vastaava integrointiydin.


Nimitykset ilmeisesti vaihtelee vähän teoriasta riippuen. Itse olen tottunut nimittämään tuota ylempää (kvanttimekaniikan yhteydessä) aikakehitysoperaattoriksi, joka on siis muotoa U=exp(-i/h ∫Hdt), missä H on Hamiltonin operaattori (joka yleisessä tapauksessa voi riippua myös ajasta). Se siirtää tilassa ψ(x,t[size=70:2jr67tvz]i[/size:2jr67tvz]) hetkellä t[size=70:2jr67tvz]i[/size:2jr67tvz] olevan systeemin tilaan ψ(x,t[size=70:2jr67tvz]f[/size:2jr67tvz]) hetkellä t[size=70:2jr67tvz]f[/size:2jr67tvz] ts. ψ(x,t[size=70:2jr67tvz]f[/size:2jr67tvz])=Uψ(x,t[size=70:2jr67tvz]i[/size:2jr67tvz]). Kyllä tuota propagaattoriksikin kutsutaan esim. Wikipediassa: "It is the time evolution operator, or propagator, of a closed quantum system."
http://en.wikipedia.org/wiki/Hamiltonian_%28quantum_mechanics%29#Schr.C3...

Mutta yleensä propagaattoreilla tarkoitetaan kvanttimekaniikassa esim. Schrödingerin yhtälön tai muun liikeyhtälön Greenin funktiota. Tarkoittaen siis sitä, että esim. Schröde kirjoitetaan muodossa (H[size=70:2jr67tvz]x[/size:2jr67tvz]-ih∂/∂t)ψ=0, jolloin ko. yhtälön (tai lineaarioperaattorin) Greenin funktio eli propagaattori K(x,t;x',t') toteuttaa ehdon (H[size=70:2jr67tvz]x[/size:2jr67tvz]-ih∂/∂t)K(x,t;x',t')=-ihδ(x-x')δ(t-t'). Tällöin systeemin tilafunktio voidaan kirjoittaa muodossa ψ(x,t)=∫ψ(x',t')K(x,t;x',t')dx'.
http://en.wikipedia.org/wiki/Propagator

Stratonovich
Seuraa 
Viestejä358
Liittynyt14.6.2009
Stratonovich
Kuuba-Pete
Eikös Greenin funktio nimenomaan ole sama asia kuin propagaattori?

Eikös propagaattori liity Cauchy-tyyppisten ongelmien ratkaisuun eli tällaisiin:

∂f(r,t)/∂t = H f(r,t),

jossa H on joku r-muuttujan suhteen operoiva operaattori. Propagaattori on sitten formaalisti

Φ(r,t) = exp(H t)


Propagaattori on käytännössä sama asia kuin tämän yhtälön Greenin funktio:

(∂/∂t - H) f = δ(r-r') δ(t-t')

joten siinä mielessä propagaattori on kuin onkin Greenin funktio sekin.

edit: kerkisit vastata suurin piirtein saman asian.

Uusimmat

Suosituimmat