Cím: Delta-kommandó, avagy rekurziók és differencia-egyenletek
Szerző(k):  Kós Rita 
Füzet: 2009/május, 260 - 267. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Alapfeladat. A Nagyáruház előtti parkolóban szeretnénk parkolóhelyet találni lehetőleg minél közelebb a bejárathoz úgy, hogy nem tudva, vannak-e még a bejáratig üres helyek, a parkolóhelyek mellett haladva eldönthetjük, hogy beállunk-e az üres helyre vagy továbbmegyünk. Ha továbbmentünk, vissza már nem fordulhatunk. Mindezt a folyamatot a lehető legrövidebb idő alatt akarjuk végrehajtani. Mi a legjobb stratégia?

 

Cikkünkben igyekszünk behatolni abba a szemléletmódba, amikor egy folyamatot adott pillanatokban feljegyzett állapotának változásával/változásaival, vagy néhány, egymást követő állapot egymáshoz való viszonyának segítségével (rekurzió) írjuk le. Például a bankszámlámon tartott pénzem kamatozik, mely kamatot a bank naponta jóváírja: ha ma f0=10000 Ft-om van, a napi kamat 0,02%, akkor holnap f1=f01,0002=10002 Ft-om lesz (rekurzió). Másként megfogalmazva, a pénzem naponta az előző napi összeg 0,0002-szeresével nő: f1-f0=0,0002f0 (differencia-egyenlet). Azaz a kezdeti lépéseket kívánjuk megtenni a felé, hogy a differencia-egyenlettel megadott folyamatok állapotait ki tudjuk számolni egyszerűbb esetekben közvetlenül ‐ az egyenlet megoldásával; példánkban megmondhatjuk, hogy két hét múlva mennyi pénzünk lesz (f13=f01,000213=10026 Ft).
Egy folyamat azonos időközönként mért állapotait jelöljük sk-val (k=0,1,2,...), például jódizotópok számát a megfigyelés kezdetétől eltelt k-adik napon. Legyen a differencia, azaz változás jele Δ: (Δs)k=sk+1-sk. A változás változását, majd azok változását stb. is értelmezhetjük, így n-ed rendű differenciának nevezzük azt az s-ből képzett Δns sorozatot, amelynek k-adik tagja
(Δns)k=(Δn-1s)k+1-(Δn-1s)k.

 
1. Delta 1
 

A legegyszerűbb egyenlet a jó öreg számtani sorozatról szól:
(Δs)k=sk+1-sk=d,(1)
ahol d egy adott szám. Ha d=0, akkor a sorozat konstans-sorozat. Ha d0, akkor az egyenlet megoldása: sk=s0+kd. Általánosíthatjuk is (1)-et például az
αsk+1-βsk=γ
egyenletre, ami picit más alakban írva:
α(sk+1-sk)+(α-β)sk=γ
(α, β, γ adott számok). Ezekben az egyszerű esetekben célszerű a sorozat első néhány tagjának felírásával megsejteni a tetszőleges k-adik tagra vonatkozó képletet.
 
1. feladat. Szeretném a 2 m hosszú, 2 cm vastagra lapított hálózsákomat összegöngyölve belepréselni a zsákjába. Belefér-e, ha a (henger alakú) zsák keresztmetszetének átmérője 22 cm?
 

Amíg az együtthatók adott konstansok és γ=0, a feladatok ebben és a későbbi fejezetekben is megoldhatóak a lineáris rekurzív sorozatok elméletének segítségével (l. a 2.1. fejezetben).
Írjuk föl differenciával az első általánosítást:
Δs=(q-1)s+c,(2)
ahol βα:=q és γα:=c (α0).
A γ=c=0 esetben ismét egy ismerőssel találkozunk:
sk+1=sk+Δsk=qsk=s0qk+1
mértani sorozat ‐ pénzügyi szemmel pedig az, ha a számlánkra betett pénz azonos időközönként mindig ugyanannyival kamatozik.
 
2. feladat. Egy kémcsőnyi víz 131J jódizotóppal szennyeződött be. 4 nappal később a kémcső tartalmának aktivitása 185 Bq volt. Hány gramm 131J került a vízbe? (1 Bq=1 bomlás másodpercenként, 1 g 131J-nak az aktivitása 4,61015 Bq, a felezési idő 8 nap.)
 

Ha c0, akkor sk+1=qsk+c-re azt a gyakorlati példát is mondhatjuk, hogy minden időegység alatt mindig adott összeget vonnak le kezelési költségként/mindig ugyanannyit teszünk be a számlára. Ezért itt már két helyen is van mértani sorozat: az egyik pont az előző, a másik pedig ugyanazon kvóciensű (hányadosú) sorozat tagjainak összege, ahol az első tag c. Így
sk=s0qk+qk-1q-1c,
amiből az exponenciális tagot kiemelve
sk=(cq-1+s0)qk-cq-1.(3)

 
3. feladat. Igazoljuk a képletet! Mi történik az α=0 és az α=β esetekben?
 

4. feladat. Minden újszülött jogosult százezer forintnyi babakötvényre, amit a Magyar Államkincstár állít ki. Egy lelkes fiatal házaspár elhatározza, hogy minden hónapban ötezer forintot tesznek be Emma lányuk számlájára, amíg 18 éves nem lesz. Arra számítanak, hogy évi 10%-os kamat mellett szép summa gyűlik majd össze. Vajon fedezi-e Emma egyetemi tanulmányait az így felhalmozott összeg?
 

A γ=c=0 eset egy lineáris rekurzió (l. a 2.1. fejezetet), a leíró egyenletet pedig homogénnek nevezik. (Egy egyenlet homogén, ha megoldáshalmaza megegyezik tetszőleges λ0-szorosának megoldáshalmazával. Egy f függvény homogén, ha tetszőleges λ0-val
f(x1,x2,...,xn)=λf(x1λ,x2λ,...,xnλ).
Egy koordinátarendszer homogén, ha tetszőleges λ0-ra az (x1,x2,...,xn) és a (λx1,λx2,...,λxn) koordináták ugyanazt a pontot jelölik.) A homogén egyenlet megoldását jelöljük sh-val. Ha c0, akkor az egyenlet már nem homogén, azaz inhomogén. Nem nehéz észrevenni, hogy (ha q1) az s=c1-q konstans sorozat a megoldása a (2) egyenletnek, jelöljük ezt spih-vel1. A q=1 esetről a 4. feladat szólt. Ugyanakkor tetszőleges A valós számmal az
sih=spih+Ash(4)
megoldásokat tudjuk előállítani.
Fontos megjegyezni, hogy ha az {s0,s1,...} sorozat megoldása egy d differencia-egyenletnek, akkor {si,si+1,...}, i=1,2,... is megoldása. Másrészről, ha az egyenletnek több sorozat is eleget tesz, akkor az előzőek értelmében bármely két megoldás-sorozat esetén vagy az egyik tartalmazza a másikat, vagy nincs közös elemük; ezt úgy is szokás mondani, hogy a megoldások nem keresztezik egymást és nem ágaznak el.
 
5. feladat. Bizonyítsuk be a fenti állítást!
 

Általában, ha d egy adott problémát, folyamatot ír le, akkor a feladat tartalmaz konkrét (kontroll) feltételeket, peremfeltételeket (pl. a repülő sebessége, amiből az ejtőernyősök kiugrottak, v0 volt).
Így az iménti megoldás folytatható a peremfeltételhez való igazítással:
A=cq-1+s0,
amivel visszakapjuk a korábbi megoldásban adódott (3) sorozatot.
 
2. Delta 2
 

A Fibonacci-számok (általánosabban pedig a Fibonacci-féle sorozatok2) megadásában három egymást követő sorozat-elem szerepel: fk+fk+1=fk+2, illetve általában αfk+βfk+1=fk+2. Ebben az esetben azt is mondhatjuk, hogy a különbségek különbsége áll az egyenlet egyik oldalán. Ugyanis
(Δ2f)k=(Δf)k+1-(Δf)k=fk+2-2fk+1+fk
jelöléssel a Fibonacci sorozat megadható egy differencia-egyenlet megoldásaként: Δ2f+Δf-f=0. Az egyenlet megoldása ismert:
fk=A(1+52)k+B(1-52)k.
A klasszikus esetben f0=0 és f1=1 a kezdőfeltételek, melyekkel A=-B=55.
 
6. feladat. Az első rész eredményeit felhasználva oldjuk meg a
Δ2f+(1-r)Δf=0
másodrendű egyenletet, ha f1=c+rf0, ahol c a feladathoz adott konstans.
 

 
2.1. Delta n
 

A legegyszerűbb homogén differencia-egyenletek lineáris rekurziók, ezért hasznos, sőt szükséges az ismeretük ‐ gondoljunk csak a (4)-beli elvre.
Az
a0rk+a1rk-1+a2rk-2+...+an-1rk-n+1+anrk-n=0
rekurzió (aiR, i=1,2,...n) megoldásának első lépése az
a0xn+a1xn-1+...+an-1x+an
karakterisztikus polinom felírása. Tegyük fel, hogy ennek az egymástól különböző gyökei q1,q2,...qj, jn. Ha j=n, akkor a sorozat tagjai
rk=A1q1k+...+Anqnk(5)
alakban állnak elő. (Ha valamelyik gyök nem valós komplex szám, akkor az együtthatója is az.)
 
7. feladat. Igazoljuk az állítást.
 

Abban az esetben, ha pl. q1 többszörös gyök, azaz (x-q1) osztója a karakterisztikus polinomnak (2n-j+1), akkor az (5)-beli összegben  darab tagot az A1q1k+A2kq1k+...+Ak-1q1k összeg helyettesít. Így az általános megoldás (5)-nél bonyolultabb:
iai(k)qik,
ahol ai egy olyan polinom, amelynek a foka kisebb, mint a qi gyöknek a multiplicitása.
 

Speciálisan a másodrendű esetben (azaz ha n=2) a karakterisztikus polinom gyökeiként kaphatunk két különböző valós számot (mint például a Fibonacci-sorozat esetében is), és skh=A1q1k+A2q2k. Előfordulhat, hogy a karakterisztikus polinom ,,teljes négyzet'', azaz egy gyöke van (ami kétszeres). Ebben az esetben
skh=A1qk+A2kqk.

 
8. feladat. Mutassuk meg, hogy a karakterisztikus polinom
a) egyik gyöke pontosan akkor 1, ha a differencia-egyenlet visszavezethető egy elsőrendű egyenletre;
b) pontosan akkor ,,teljes négyzet'', ha a differencia-egyenlet is az.
 
Harmadik esetként, ha a karakterisztikus polinomnak két (egymással konjugált) nem valós komplex gyöke van, akkor az A1 és A2 együtthatók olyan komplex számok, amelyek egymás konjugáltjai.
Az elméletet azonban óvatosan kell alkalmazni a gyakorlatban!
 
1. példa. Régen a magasfeszültséget szállító vezetékek mellett porcelántárcsákat használtak szigetelésnek. Ezt úgy kellett megtervezni, hogy sehol se üssön át.
 

 

Ezt az áramkört sematikusan egy létraszerű nagyon-nagyon hosszú kondenzátorsorral lehet szemléltetni:
 
 

A k-adik csomópontban a feltétel szerint Q=0, így felírható a
C1Uk+1-(2C1-C2)Uk+C1Uk-1=0
rekurzió. A karakterisztikus polinom szerint van megoldás, ha C24C1, ám a tapasztalatok szerint Uk=U0qk alakú (ahol q a nagyobbik gyök).
 
1. gyakorlat. A C24C1 esetben számítsuk ki q értékét.
 

3. Delta 1 ‐ P kód
 

Modellezzük az Alapfeladatot a lehető legegyszerűbb esetre. A parkolóhelyek egymás után vannak sorban, az áruháztól való távolságuk növekvő sorrendjében számozva. Csak az éppen mellettünk levő parkolóról látjuk, hogy foglalt-e vagy sem ‐ meg persze a már mögöttünk levőkről. Legyen p annak a valószínűsége, hogy egy hely szabad, q=1-p pedig annak, hogy foglalt; minderről pl. a bejáratnál levő számláló tájékoztathat, és ez a parkolás ideje alatt nem változik.
 
 

3.1. P1
 

A feladatbeli feltételeket modellezhetjük azzal, hogy a kevésbé jó parkolást büntetjük. A parkolásért annyit kelljen fizetni, amilyen messze van a hely (k), de ha nem állunk meg, és az áruház elé érünk (0. hely), akkor igen magas összegre rúgó büntetést kapunk (C). Ezzel az átfogalmazással a lehető legkisebb díjat keressük. A következő kérdésre kell tehát válaszolni: mikor döntünk úgy, hogy a következő szabad helyre beállunk?
A k-adik helynél állva azt mérlegeljük: ha szabad, akkor leparkolunk, és a fizetendő díj k, vagy előre megyünk eggyel. Azt választjuk, ami jobban megéri: k és Vk-1 közül melyik a kisebb, ha általában Vn-nel jelöljük a várhatóan fizetendő összeget az n-edik helyen. Ha foglalt a hely, akkor muszáj továbbállni. Ezért
Vk=pmin{k,Vk-1}+qVk-1.(6)

Ez a várható tarifa az áruház felé haladva sajnos nem csökken (különben gondolkodás nélkül előrehajtanánk). A rekurzió felírásakor természetesnek vettük, hogy a (k-1)-edik helyen is ugyanezt a stratégiát fogjuk követni. Ez egy nagyon fontos elv az optimalizációs és kontroll folyamatok vizsgálatánál: a legjobb stratégia meghatározásához (pl. optimális gazdasági növekedés, befektetések, monetáris és fiskális politika), amit Bellmann-elvként/egyenletként3 ismernek. A lényege: az optimális stratégia minden lépése optimális.
 
9. feladat. Mutassuk meg, hogy Vk nemnövő sorozat.
 
 

Tehát amíg kVk-1, addig haladunk előre, és Vk=Vk-1. Abban a pillanatban, amikor kVk-1, azaz Vk=pk+qVk-1 a várható díj ‐ a legelső szabad helyre beállunk. Ahogy az első részben, itt is egy lehetséges megoldás V0,V1,V2,... felírásával megsejteni Vk alakját és indukcióval bizonyítani. Ehelyett azonban nézzük a megoldandó differencia-egyenletet:
ΔV+pV=pk+p.(7)
Általánosabban, vizsgáljuk a
ΔV=μV+νk+ω(8)
differencia-egyenletet. Tudjuk, hogy a speciális ν=0 és ω=0 (homogén) esetben a (3) szerint Vkh=V0h(μ+1)k.
 
10. feladat. Mi a megoldása a ΔV=2k+1 egyenletnek? És a ΔV=νk+ω-nak?
 

A (4) szerint keressünk a (8) kérdésre egy konkrét Vk* megoldást, mert akkor a Vk=AVkh+Vk*-ként előállított is jó (A tetszőleges szám). Márpedig
Vk*=-νμk-νμ2-ωμ,(μ0),illetveVk*=ν2k2+(ω-ν2)k,(μ=0),
ezt visszahelyettesítve egyenlőséget kapunk! Így a megoldás, természetesen igazítva az adott sorozathoz:
Vk=V0+νμ2+ωμV0h(μ+1)k-νμk-νμ2-ωμ,illetveVk=ν2k2+(ω-ν2)k+V0.

Alkalmazzuk μ=-p, ν=p, ω=p és V0=C-re, hogy megkapjuk a várható parkolási díj nagyságát:
Vk=(C+qp)qk+k-qp.

Némi számolás után kiderül, hogy a kritikus hely k0=[1-logq(pC+q)]+1 ([x]=n, ahol nx<n+1, nN). Ha valóban alkalmazni szeretnénk ezt a stratégiát, akkor C megválasztásával tudjuk biztosítani, hogy elég nagy valószínűséggel valóban le tudjunk parkolni, de ne kelljen túl messze megállni csak azért, mert ,,biztosra'' akarunk menni.
 
11. feladat. Mi annak a valószínűsége, hogy a kiszámolt k0-adik parkolóhely után mégsem lesz szabad hely?
 
12. feladat. Hogyan válasszuk meg C-t, ha legalább 90%-os eséllyel szeretnénk üres helyet találni?
 
3.2. P2
 

Befejezésül néhány megjegyzés a feladat modelljének egy kissé módosított változatáról. Annak a valószínűsége, hogy a k-adik hely foglalt, legyen a hely függvénye q:N(0,1), például q(k)=qk. Ekkor a megoldandó egyenlet
ΔV+1-qkqkV=1-qkqkk,(9)
ennek megoldásához a korábban megbeszéltekből két dolog használható. Elmondható ugyanis, hogy ha van megoldás, akkor adott V0 kezdőfeltétel esetén ez egyértelmű. Másrészről ha Vkh megoldása a
ΔV+1-qkqkV=0(10)
homogén egyenletnek, Vk* pedig egy konkrét (általános) megoldás, akkor Vk=AVkh+Vk* is megoldása (9)-nek. Látjuk, hogy (10) már nem lineáris, nem használhatjuk azt, ami idáig jól működött. Célunk ugyanakkor a módosított probléma megoldása, azaz a Vkk egyenlőtlenség küszöbindexének megtalálása: a legelső jó k, amit nevezzünk k0-nak. Adott C és q mellett ez persze megállapítható, általános megoldáshoz pedig használhatunk egy Vk-t közelítő megoldást:
Vk˜=(C+1)qk22+k-1,
aminek segítségével
k0=logqC.
(x=[x]+1, az x felső egészrésze.)
 
13. feladat. Mutassuk meg, hogy a Vk˜ közelítő megoldás minimumhelye k0 és |V˜k0-k0|<1.
 

Ez lesz a munkamódszere a differenciál-egyenletek megoldásának is (pl. mi történik a villany felkapcsolásakor, miért kering ellipszis pályán a Föld). A történet pedig ott folytatódik.
 
Felhasznált irodalom
 


[1]http://www.math.bme.hu/jofri/JOFRI/OKTAT/pmmar.pdf
[2]http://wikipedia.org/wiki/Richard_E._Bellmann
[3]http://wikipedia.org/wiki/Bellmann_equation

1p, mint partikuláris, azaz részleges

2A téma nagyon érdekes feldolgozása olvasható Énekes Béla ‐ Kós Géza: Néhány érdekesség a Fibonacci- és a Fibonacci-típusú sorozatokról I.‐II. (KöMaL, 2000/12. és 2001/1.) cikkekben.

3Richard E. Bellmann (1920‐1986), a dinamikus programozás atyja