Üldözési jelenetek

Pihenésképpen nézzünk meg egy közönséges, régi feladványt közelebbről. A probléma eredetileg úgy hangzik, hogy egy egységnyi oldalú szabályos sokszög csúcsaiban ül egy-egy azonos röpképességű sas, és adott jelre mindegyik űzőbe veszi a jobboldali szomszédját. (Hasonló esettel már foglalkoztunk.) Ekkor egy görbe vonalú pályát leírva a sokszög középpontjában találkoznak. Mekkora utat tesznek meg a találkozásig? A kidolgozás hasznos fejszámolás, eredménye

1/(1 + cos α),

ahol α a sokszög oldalai által bezárt szög. A feladatnak abban az általánosításában, melyben a pontok síkbeli elhelyezkedése tetszőleges, de a sebességek továbbra is egyenlő nagyságúak, mutassuk ki, hogy a madarak végül (véges időn belül) egyetlen pontban találkoznak. (Ezzel egyúttal az eredeti feladat homályban hagyott előfeltételezését is igazoljuk.)

ljapunov

Alekszandr Mihajlovics Ljapunov (1857 – 1918)

Alekszandr Mihajlovics Ljapunov  ötlete alapján járunk el. Képzeljük el, hogy egy hegycsúcsról lefelé indulva egyetlen célunk, hogy lejussunk. Ha találunk egy mennyiséget, matematikusi tolvajnyelven függvényt, mely kiválasztott pályánk során úgy változik, hogy abból kikövetkeztethetjük valamilyen úton-módon úticélunk garantált elérését, akkor megnyugodhatunk. Nézzük csak, ez esetben megfelel-e a célnak a tengerszint feletti magasság mint függvény. Sajnálattal állapíthatjuk meg, hogy nem. Ha garantáltan csökken is utunk során a tengerszint feletti magasságunk, megeshet, hogy olyan útra tévedünk, mely egyre kisebb eséssel egyre jobban beolvad egy, a hegyet körbefutó szintvonalba, végtelen hosszúságban. Ekkor a kudarc garantált, pedig magasságunk mindvégig csökkent. Világos tehát, hogy egy ilyen függvény csökkenésének kellően nagy sebességét ki kell kössük a lehetséges pályák mentén. Ez esetben a mennyiséget Ljapunov-függvénynek mondjuk. Jelentősége abban áll, hogy kirándulók, pontok vagy pontrendszerek mozgásának tényleges pályáit nem is kell ismernünk az alapkérdés megválaszolásához egy-egy ilyen Ljapunov-függvény ismeretében. Ilyenképpen mozgások kvalitatív vizsgálatára alkalmas, mondhatni, a kvalitatív vizsgálatok legegyszerűbb típusa egy Ljapunov-függvény szerencsés megtalálása. Anélkül hogy kifinomítanánk a megpendített állítást, a kitűzött feladat megoldása során, szigorúan ebben az esetben, a Ljapunov-függvény viselkedése és haszna világos lesz.

sorrend

üldözési sorrend

Mindenekelőtt vessünk egy pillantást az alapfeladatra négyzet esetén. A pályákat egyszerűen kirajzoltatjuk, és semmi sem tud meggyőzni arról bennünket, hogy Leonhard Euler (1707 – 1783) legegyszerűbb, de számítástechnikai veszélyeket magában hordozó töröttvonal-módszere helyett valami komolyabb, azaz gyorsabb és biztosabb megoldást alkalmazzunk, például Carl David Tolmé Runge (1856 – 1927) és Martin Wilhelm Kutta (1867 – 1944) valamelyik ismert közelítő eljárását.[1] sas

Természetesen előfordulhat, hogy némely sasok hamarabb összefutnak a többinél. Ha ez két olyan sassal történik meg, amelyik közül egyik sem üldözte a másikat, akadálytalanul továbbhaladnak. Ha egyikük üldöző volt, akkor ő elérte célját, a másik hátán folytatja tovább röptét. Ez utóbbi eset egy példáját látjuk:

sas2

Jelöljük a madarak helyzetét leíró helyvektort ri-vel (i = 1…n most és a továbbiakban). Ekkor az általuk kifeszített, esetleg önmagát metsző vagy bármely egyéb módon elfajuló sokszög kerülete alkalmas Ljapunov-függvény lesz. Legyen ugyanis

k1

ahol az összegzőjel alatti O a körkörös összegzést írja elő. Mivel a vi sebességvektorok egységnyiek,

k2

Ennek megfelelően a kerület (V) időbeli alakulása (felhasználva, hogy vektor hossza a négyzetéből vont gyök):

k3

Ha a vi és a vi+1 egységvektorok által bezárt szöget φi-vel jelöljük (ciklikusan, azaz a vn+1 = v1 hátsó gondolattal), akkor

k4

Állapítsuk meg az összeg lehetséges legnagyobb értékét! (Maguknak a szögeknek az előjeles összege 2π egész számú többszöröse.) Két vektor szöge nem lehet homorú (azaz π-nél nem lehet nagyobb). Ebben a tartományban a koszinuszfüggvény csökkenő. Ha a sebességvektorokat közös pontból felrajzoljuk, egy húrsokszöget kapunk úgy, hogy az egységkör kerületén a végpontok sorrendje minden változatban előfordulhat. Az első vektorból a második felé elindulva végig a körön kialakul egy egymásra közvetlen szomszédként következő sorrend. Az egymás utáni (tehát feltehetőleg nem a valóságos sorrendnek megfelelő) kerületi pontokhoz tartozó középponti szögeket jelöljük αi-vel. A tényleges sorrendnek megfelelő középponti szögek ezek közül némely egymás után következőnek az összege.
Mutassuk meg, hogy a valóságos szögeknek kölcsönösen egyértelműen megfeleltethető az αi-k közül olyan, amelyik az összeadandói között van. (Nem olyan gyermekded, mint első pillanatra látszik.) A megfeleltetéshez induljunk el v1 végpontjától a kerületen v2 felé. A köztük levő szögnek feleltessük meg az αi-k közül az elsőt, amelyen áthaladunk. Ezt a szöget azonban értelemszerűen ki kell zárjuk az elkövetkező megfeleltetésekből. A továbbiakban az úton mindig az első olyan α-t választjuk, amely még nem foglalt. Be kell bizonyítanunk, hogy ez lehetséges. Nevezzük régiónak a körívnek azt a részét, melyet a kiindulástól kezdődően már érintettünk. Ha egy pillanatban kiugrunk a régióból, az abból a pontból (bármerre is) induló út első lépése még érintetlen, tehát ilyen pont esetén nem fordulhat elő, hogy már nem tudjuk elvégezni a hozzárendelést. Következésképpen csak az fordulhat elő, hogy egy régión belüli ponthoz érkezve onnan egy szintén régióbeli pont az erre következő, de a köztük levő minden középponti szög már szerepelt korábban hozzárendelésben. Azt az utat, amelyet ez a pont a következő lépésben megtenne a köríven, egészítsük ki olyan ívvé, melyben nincs már ki nem választott középponti szög. Ennek a szegmensnek a kiválasztásai nem keletkezhettek olyan módon, hogy egy szegmensen kívüli pont átlépett a szegmensen, hiszen akkor más, a szegmensen kívüli középponti szöget kellett volna kiválasztani a szabálynak megfelelően. Tehát a szegmensen belül minden középponti szög kiválasztásában egy szegmenshez tartozó pont mint kiinduló- és végpont is hozzájárult. Ez azonban azt jelenti, hogy a szóban forgó lépés nem lehetséges, hiszen éppen annyi szöget választottunk már ki, amennyi pontja a szegmensnek van (az aktuális kiindulópontot leszámítjuk), vagyis a célállomás egyszer már szerepelt, ami lehetetlen. Ha tehát minden valóságos sorrendnek megfelelő szöget kölcsönösen egyértelműen meg tudjuk feleltetni egy összeadandójának, akkor az azt jelenti (a koszinuszfüggvény adott szögtartománybeli csökkenése miatt), hogy a valóságos szögek koszinuszainak összege kisebb vagy egyenlő, mint az α-ké. Ábránkon n = 5-re látunk példát, az α-k szögtartományaiba bejelölve azt a lépést, melynek során a lépéshez tartozó középponti szöghöz éppen azt az α-t rendeltük a valóságos szög összeadandói közül. plA kerület időbeli változásának képletében szereplő összeg tehát legfeljebb

ncos(2π/n),

vagyis határozottan kisebb n-nél.

Ugyanis a maximális értéket akkor kapjuk, ha a vektorok végpontjai sorban következnek, azaz az α-k egyben a valóságos szögek. Minimum pedig nem képzelhető el másképpen, mint a szögek egyenlőségének esetén. Minden egyes vektornak feleznie kell a két szomszédja által bezárt szöget, amint az geometriai megfontolásokból vagy a cos x + cos (α – x) függvény deriválásából közvetlenül adódik. És mivel van maximum, ez csak a szögek egyenlőségének esetén állhat fenn.

Maga az időbeli változás tehát határozottan negatív, és ez azt eredményezi, hogy a példa sasmadarai véges hosszúságú idő alatt utolérik egymást. Máskülönben az általuk kifeszített sokszög kerülete nem válhatna 0-vá. Felvethető, hogy megzavarja a képet a végső találkozások előtti esetleges találkozások sora, ugyanis ezzel n értéke csökken. Ám n = 5 esetén a csökkenés sebessége mintegy -0,9549, és n további csökkenése esetén a kisebbítendő egészen n = 1 eléréséig nempozitív. Ám n = 1 esetén vége a dalnak.


[1] http://mathworld.wolfram.com/Runge-KuttaMethod.html

Reklámok

5 responses to “Üldözési jelenetek

  1. Gyönyörű! Felmerülnek itt azonban nehéz általánosítási kérdések:

    1. Mi van akkor, ha az üldözési leképezés nem ciklikus?

    2. Mi van 2-nél magasabb dimenziókban?

    Kedvelik 1 személy

    • Köszönöm, szerintem már három dimenzióban is megzavarja a képet, hogy az egymás után következő szögek a sebességvektorok között semmilyen értelemben nem additívok, de ezzel nem akarom elhárítani a kérdést 🙂
      Nemciklikus esetben szerintem tipikusan végtelen repülésre számítsunk…

      Kedvelik 1 személy

      • “Nemciklikus esetben szerintem tipikusan végtelen repülésre számítsunk…”

        Tisztelettel ellent kell mondjak. Tekintsük a madarak {1,2,…,n}=M halmazának azt az f: M—->M leképezését önmagába, amire az igaz, hogy minden i értékre az i madár az f(i) madár irányába repül egységnyi sebességgel. Az f tehát fixpontmentes leképezés. Ezt a leképezést iterálva minden i belefut egy végső ciklusba. Az ilyen végciklusokban levő madarak persze véges időn belül egyesülnek egy ponttá a t. blogszerző gondolatai alapján. Az a baj, hogy azt nem tudjuk, ez az egyesített pont a ciklus végső egyesülése után hogyan mozog, mert nincs természetes definiciója a mozgását leíró differenciálegyenletnek. Ezt pedig fontos lenne tudni, mivel ez a pont még magához vonzhat olyan madarakat, amiknek az indexe az f iterálásánál a vizsgált végcklusba fut bele.

        Kedvelés

  2. “Az a baj, hogy azt nem tudjuk, ez az egyesített pont a ciklus végső egyesülése után hogyan mozog, mert nincs természetes definiciója a mozgását leíró differenciálegyenletnek. ”

    Corrigendum: Amikor a végciklus pontjai egy ponttá olvadnak össze, akkor utolsó lépésben két pont rohan egymás irányába egységnyi sebességgel, nulla összimpulzussal, tehát természetes dolog azt venni, hogy az eggyé összeolvadt pont végül állva marad és azután úgy szippantja magába azokat a további esetleges pontokat, amik az f iterálásánal ebbe a végciklusba való futásra vannad predesztinálva, de eddig még nem olvadtak bele a végciklusba.

    Kedvelés

  3. Köszönöm, én értettem félre. Úgy értettem, valamelyik madár csak úgy szálldogál.

    Kedvelik 1 személy

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s