Hidrológiai Közlöny 1994 (74. évfolyam)
3. szám - Gáspár Csaba–Józsa János–Simbierowicz, Pawel: Új szemléletmód a numerikus hidraulikában. I. Egyenlőtlen hálók: generálásuk, első alkalmazások
GÁSPÁR CS. el al.: Új szemléletmód, I. 167 számozzuk meg az egy szülőtől származó cellákat („testvéreket") a 3. ábrán látható rendszer szerint. Nevezzük az 1. és 2. részcellát északi fekvésűnek (a szülő cellán belül), a 3.-at és a 4.-et pedig déli fekvésűnek. Ugyanakkor az 1. és 3. cellát egyúttal nyugati fekvésűnek, a 2.-at és a 4.-et pedig keleti fekvésűnek is hívjuk. Könnyen látható, hogy tetszőleges C cella adott irányú oldal-szomszédjai a következő algoritmussal adhatók meg. Tegyük fel, hogy az északi szomszédo/ka/t keressük (az összes többi eset hasonlóan adódik): (a) Állapítsuk meg, hogy C milyen fekvésű a szülő-cellában. Haladjunk a gráfban a gyökérelem felé (tehát az ősök irányába) mindaddig, amíg valamelyik ős ellenkező, tehát déli fekvésű nem lesz az ő szülő-cellájában. Jelölje ezt az őst C' . Ha ilyen nincs, akkor ez azt jelenti, hogy a C cella az £2 négyzet északi oldalára illeszkedik, így nincs északi szomszédja a QTcel la rendszerben. Jegyezzük meg az út folyamán minden ős fekvését (mind észak-déli, mind kelet-nyugati értelemben). (b) Vegyük az ily módon megtalált C' északi szomszédját, jelölje ezt N': ennek megtalálása triviális, mert mivel C' déli fekvésű, azért C'-nek északi szomszédja egyúttal C' testvére is. (c) Kiindulva N'-ből, haladjunk visszafelé a gráfban, de az idevezető úthoz képest részben ellenkező tájolással, azaz mindig a déli fekvésű gyermekek irányában, de megtartva az idevezető út során feljegyzett keleti és nyugati irányokat. Tegyünk meg ily módon ugyanannyi lépést vissza a gráfban, mint ahányat C-től C'-ig tettünk. Ha az eljárás eközben megakad (mert időközben „gyermektelen" cellához értünk), akkor ez azt jelenti, hogy C-nek egyetlen, éspedig nagyobb méretű északi szomszédja van, és ez a szóbanforgó „gyermektelen" cella. (d) Ellenkező esetben eljutunk egy N cellához, amely C-vel azonos méretű, és szomszédos vele északról. Ha N gyermektelen, akkor ez az egyetlen északi szomszéd. Ha nem, akkor vegyük N-nek a déli fekvésű gyermekeit, majd azoknak is a déli fekvésű gyermekeit, és így tovább, amíg csupa gyermektelen cellához nem jutunk: ezek, és csakis ezek lesznek C északi szomszédai. Miután bármely cella esetében legfeljebb L lépést kell tenni a gráfban a C' ősig, és ugyancsak legfeljebb L lépést vissza, a szomszédkeresés műveletigénye minden egyes C cella esetén legfeljebb O(L). Következésképpen az összes cella összes szomszédjának megtalálása legfeljebb 0(N • L) műveletbe kerül, ami - nagyságrendjét tekintve - nem nagyobb, mint a QT-háló generálásának műveletigénye. Megjegyzés: Ennél jóval erősebb becslés is igazolható: bár néhány C cella esetében valóban L lépést kell tenni a gráfban a C' ősig, az ilyen esetek száma valójában kicsi, és az összes cella összes szomszédainak megtalálásához O(N) művelet is elég. A QT-hálót regulárisnak nevezzük, ha bármely cellához oldalszomszédként legfeljebb kétszer akkora cella csatlakozik. (Ez egyúttal azt is jelenti, hogy az oldalszomszédok legalább feleakkorák mint a szóban forgó cella.) A regularitás lényege, hogy a cellaméretekben hirtelen nagymérvű változás ne történjék. Ez a megoldandó parciális differenciálegyenlet közelítésére alkalmazott differenciasémák pontosságát növeli, ezzel egyidejűleg lényegesen leegyszerűsíti a cellarendszer szerkezetét: reguláris cellarendszer esetén nyilván minden cellának legfeljebb 8 oldalszomszédja létezik, míg a szomszédok száma általános QT-háló esetén ennél jóval nagyobb is lehet. Egy QT háló regularizálása legegyszerűbben pótlólagos cella felbontások útján történhet. Mindazon cellákat, melyeknek vannak feleakkoránál kisebb oldalszomszédai, újra felbontjuk négy részre, pontosabban, megismételjük velük az algoritmus 1. lépését. Ezt mindaddig folytatjuk, míg van újrabontandó cella, azaz míg a QT-háló reguláris nem lesz. A regularizálás általában megnöveli a cellák számát, de a cellaszám növekedésének mértéke az esetek döntő többségében nem jelentős, tehát a cellaszám még mindig jóval kisebb, mintha a legkisebb celláknak megfelelő méretű egyenletes rácsot alkalmaztunk volna. Valóban, ha pl. a QT-hálót egy tartomány peremének pontjai generálják, és M a peremre illeszkedő (tehát legkisebb méretű) cellák száma, akkor könnyen látható, hogy a tartományt lefedő cellák össz-száma 0(M)-mel becsülhető akkor is, ha a QT-háló reguláris: egyenletes cellarendszer esetén ez a szám nyilván 0(M 2). Megjegyzés: Részletek nélkül megemlítjük, hogy a regularitás kritériuma beépíthető magába a rekurzív algoritmusba is, így a generált QT-háló mindjárt reguláris is lesz. Mindenesetre világos, hogy a regularizálás feltételezi azt, hogy bármely cella oldal-szomszédait egyszerűen - kis műveletigénnyel - meg tudjuk határozni: ez ismét rávilágít a szomszédkeresés fontosságára, ahogy azt az előbbiekben már megjegyeztük. A 4. ábrán egy körvonal pontjai által generált QThálót és annak regularizálását mutatjuk be. Itt a maximális felbontási szint 6: az ábra jól illusztrálja a reguláris és nem reguláris QT-hálók közti különbséget, valamint a QT-hálóknak azt a tipikus tulajdonságát, hogy a vezérlő ponthalmaz környezetében besűrűsödnek. Végezetül röviden érintünk egy gyakorlati problémát a hálógenerálásokkal kapcsolatosan. Legyen az eredeti (hidraulikai vagy transzport) probléma egy Q 0 tartományon kitűzve. Legyen Q egy olyan négyzet, mely Q 0-t teljes egészében tartalmazza, és tekintsük az Q-ból kiinduló QT-hálót. Miután Q 0 általában nem egyezik Q-val, a celláknak csak egy része esik belsejébe, egy (esetleg jelentős) része pedig azon kívülre esik. Ha a cellák száma nagy (pl. több ezer), akkor triviális, ám igen fáradságos munka kijelölni ezek közül az Q 0 résztartomány belsejébe eső cellákat. Ez a probléma termrészetesen ekvidisztáns hálók esetében is felléphet. Kívánatos tehát ezt egy alkalmas algoritmus segítségével automatizálni. Az alábbiakban egy ilyen algoritmus (rekurzív) definícióját adjuk meg. (1) Minden cellához rendeljünk egy jelzőszámot, melynek értéke legyen 1, ha a cella Qq peremére illeszkedik, egyébként 0. Ennek a jelzőszámnak a beállítása a QT-háló generálásakor nehézség nélkül elvégezhető. (2) Keressünk egyetlen tetszőleges C cellát, mely Q 0 belsejébe esik. (3) Ha cellához rendelt jelzőszám nem 0, akkor az adott szinten az eljáráshívást befejeztük. Ellenkező esetben lépjünk a (4) pontra.
