UP VIZ M v z AMET E„S VN GEODETS TomažAmbrožič, mag. Goran Turk FNT-Oddelek za montanistiko, FAGG-(Jddelek za gradbeništvo, Ljubljana Prispelo za objavo: 29.6.1993 Izvleček V članku je prikazana metoda„skyline", kije ena izmed metod za učinkovito shranjevanje matrik sistemov linearnih enačb, ki med drugim omogoča reševanje velikih sistemov linearnih enačb. Pregledno je opisan način shranjevanja elementov matrike normalnih enačb, kar je bistvo te metode. Podan je način izračuna vektorja neznank Primerjave med „klasičnimi" metodami in metodo „skyline" kažejo na njene prednosti in večjo učinkovitost. Ključne besede: geodetske mreže, izravnanje, metoda „skyline", primer, sistem linearnih enačb Abstract The use of„skyline" method in surveying is presented in the paper. Large systems of linear equations can be solved by „skyline" method which uses an effective type of storage of matrices. The essential idea of the method is described in detail. The modifted Cholesky method is used to salve the system of line ar equations. The comparison among the „classic" methods and „skyline" type methods shows advantages and greater efficiency of the latter. Keywords: adjustment, example, ,,skyline" method, surveying networks, system of line ar equations UVOD UDK (UDC) 528.1 INE" H Pomembna faza dela na mnogih inženirskih področjih je reševanje sistemov linearnih enačb. To velja tudi v geodeziji. Toko imenovane normalne enačbe sestavimo iz enačb popravkov opazovanj po metodi najmanjših kvadratov. Rešitev teh enačb pa nam predstavlja izravnane neznanke. Metode za reševanje sistemov linearnih enačb Ax = b delimo v dve skupini (Bohte 1985): direktne in iterativne. Pri direktnih metodah izračunamo rešitev, če obstaja, s končnim številom aritmetičnih operacij. Med te prištevamo Kramerjevo pravilo, Gaussovo eliminacijo, trikotno razstavitev, metodo Choleskega in druge. Pri iterativnih metodah pa tvorimo zaporedje približkov, ki konvergira k rešitvi, če ta obstaja. lteriramo, dokler natančnost ne ustreza zahtevani oziroma željeni. Mednje prištevamo Jacobijevo iteracijo, Seidlovo iteracijo in druge. Geodetski vestnik 37 (1993) 2 a voljo imamo kar nekaj metod za reševanje sistemov linearnih enačb. Vendar so pri reševanju velikih sistemov linearnih enačb težave, saj nam zmanjka računalniškega pomnilnika pri shranjevanju koeficientov leve strani enačb, elementov matrike A. Pomagamo si na različne načine. Najbolj enostavno je upoštevanje simetričnosti matrike A. Preprosta metoda je tista, ki upošteva pasovnost matrike A. Pomanjkljivost te metode pa je, da je širina pasu določena s številom elementov od diagonale pa do najbolj oddaljenega od nič različnega člena. To pomeni, da element, ki je daleč od diagonale in različen od nič, zelo razširi pas matrike in s tem zmanjša učinkovitost metode. Za izredno velike sisteme linearnih enačb z relativno ozkim pasom je najuspešnejša tako imenovana frontalna metoda (Irons 1970). Njeno bistvo je v tem, da rešuje sistem v fronti. Hkrati je v računalniškem pomnilniku le majhen del celotne matrike, ostanek matrike pa je shranjen na disku. To je sicer vzrok za relativno neučinkovitost te metode, saj je branje z diska in zapisovanje na disk bistveno počasnejše kot operacije v hitrem pomnilniku. Ugotovili smo, da je za shranjevanje elementov matrike normalnih enačb pri izravnavi geodetskih mrež najbolj učinkovita metoda „skylilie". Ker večine elementov, ki so enaki nič, ne shranimo, zmanjšamo zasedenost pomnilnika. Zato lahko v razpoložljiv pomnilnik shranimo velik sistem linearnih enačb. Naslednja velika prednost tako shranjenih elementov je, da izvajamo računske operacije z mnogo manj elementi, zato je metoda učinkovitejša. REŠITEV SISTEMA LINEARNIH ENAČB d sredine petdesetih let tega stoletja prevladujejo tehnike direktne eliminacije za izračun rešitev sistema linearnih enačb Ax = b. (1) V enačbi (1) je: A - simetrična regularna matrika ( det A :;t: O) leve strani enačb ( dimenzije n x n ), x - vektor neznank (dimenzije n), b - vektor desne strani enačb (dimenzije n) in n - število linearnih enačb = število neznank. ešitev sistema linearnih enačb (1) lahko izračunamo po modificirani metodi Choleskega (Felippa 1975, Wilson et al. 1974). Matriko A najprej razcepimo: A = LDLT (2) in nato izračunamo vektor neznank v naslednji korakih: Lz = b, Dy=zin LTx = y. V enačbah (2), (3), (4) in (5) pomeni: L - spodnja trikotna matrika (dimenzije n x n), D - diagonalna matrika (dimenzije n x n) in z, y - pomožna vektorja (dimenzije n). (3) (4) (5) Geodetski vestnik 37 (1993) 2 NAČIN SHRANJEVANJA ELEMENTOV MATRIKE V METODI „SKYLINE" ačin shranjevanja elementov matrike A najlažje pokažemo s primerom (Felippa 1975). Simetrično matriko a11 a13 a16 a22 o a24 o A= a33 a34 ·O a44 a46 (6) ass as6 sim. a66 shranimo kot vektor a z elementi: a = [ an a22 a13 O a33 a24 a34 a44 ass a16 O O a46 as6 a66 J . (7) Pike predstavljajo vrednosti nič, ki ne zasedajo pomnilnika, če za shranjevanje matrike A uporabimo metodo „skyline". Poleg vrednosti elementov moramo shraniti še njihovo lego (položaj posameznega elementa v sistemu). Najenostavnejši in najboljši način določitve lege je uvedba kazalca diagonalnih členov. Oglejmo si ta kazalec na našem primeru. Zaporedje elementov matrike A je naslednje: 1 · 3 · 10 2 4 6 · 11 5 7 · 12 8 · 13 9 14 15 Toko ima vektor, ki vsebuje kazalce na diagonalne člene, naslednje elemente: kazalec = [ 1 2 5 8 9 15 ] . (8) (9) Vektor s kazalci ima toliko elementov, kolikor imamo linearnih enačb oziroma neznank. Število elementov vektorja a je odvisno od razporeda (lege) neznank. Pri tej metodi shranimo v posameznem stolpcu matrike Avse elemente od prvega, ki je različen od nič, pa vse do diagonalnega. S prerazporejanjem enačb (neznank) pridemo do minimalnega števila elementov vektorja a. To pa pomeni, da lahko pri isti velikosti pomnilnika izračunamo večji sistem linearnih enačb. Na primer, pri izravnavi nivelmanskih mrež zmanjšamo število elementov vektorja a, če podamo približne višine reperjev (s tem določimo lego neznank) tako, kot smo jih označili, torej zaporedno po zankah. PRIMER UPORABE METODE „SKYLINE" etodo „skyline" smo uporabili pri izdelavi programa za izravnavo geodetskih mrež v ravnini in programa za izravnavo nivelmanskih mrež. Za prikaz uspešnosti obravnavane metode smo izbrali program za izravnavo nivelmanskih mrež, imenovan ViM. Zaradi primerljivosti so torej vsi navedeni rezultati primeri nivelmanske mreže in vsi so izračunani na istem računalniku. Uporabili smo PC 80386, 20 MHz, z vgrajenim matematičnim koprocesorjem. Geodetski vestnik 37 (1993) 2 Preglednica 1: Primerjava zasedenosti pomnilnika z elementi normalnih enačb in potrebnega časa za izravnavo nivelmanske mreže. Število enačb n 100 197 300 399 496 Zasedenost pomnilnika (v kByte): Polna matrika A 80,0 310,5 720,0 1273,6 1968,1 Simetrična matrika A 40,4 156,0 361,2 638,4 986,0 MatrikaA 6,9 64,4 122,9 139,7 157,7 Metoda skyline Vektor Kazalec 0,2 0,4 0,6 0,8 1,0 Skupaj 7,1 64,8 123,5 140,5 158,7 Čas izravnave (v minutah in sekundah) Polna matrikaA 006 035 159 436 845 MatrikaA- ,,skyline" 003 035 135 222 318 Pri oceni zasedenosti pomnilnika smo upoštevali, da en element matrike oziroma vektorja zasede 8 bytov računalniškega pomnilnika ( dvojna natančnost) in en element vektorja kazalcev na diagonalne člene 2 byta. Iz preglednice lepo vidimo, kako hitro narašča prednost uporabe metode „skyline" z naraščanjem števila enačb. Pri tem pa se moramo zavedati, da velikih sistemov linearnih enačb (več kot 600) sploh ni možno rešiti na današnjih osebnih računalnikih brez uporabe metod, ki varčujejo z računalniškim pomnilnikom. Povedati moramo, da je uporaba metode „skyline" izrazito primerna za izravnavo nivelmanov, saj je oblika matrike sistema normalnih enačb takšna, da z metodo „skyline" bistveno izboljšamo učinkovitost računanja. Pri izravnavi ravninskih mrež pa ne moremo pričakovati tolikšne prednosti. ZAKLJUČEK ljub hitremu razvoju računalniške tehnologije je velikost računalniškega pomnilnika še vedno omejitev pri reševanju sistemov linearnih enačb. Zato celotne matrike ne moremo shraniti v računalniškem pomnilniku, kar pomeni, da sistema linearnih enačb ne moremo izračunati. V geodeziji imamo simetrični sistem normalnih enačb, v katerem so elementi matrike A, ki so različni od nič, največkrat blizu diagonale. Metoda „skyline" upošteva obe lastnosti. Zato se je izkazala kot primerna za shranjevanje normalnih enačb. Z uporabo metode „skyline" pa skrajšamo čas, ki je potreben za izračun rešitev sistema linearnih enačb, saj je shranjenih veliko manj elementov matrike, zaradi česar je potrebnih manj operacij za izračun rešitev. Vi.ri: Bohte, Z., 1985, Numerične metode, Društvo matematikov, fizikov in astronomov SRS, Zveza za tehnično kulturo Slovenije, Ljubljana. Felippa, C. A., 1975, Solution of Linear Equations With „Skyline"-Stored Symmetric Matri:x, Computers & Structures, 5, 13-29. Geodetski vestnik 37 (1993) 2 Irons, B.M, 1970, Afronta! solution program for finiteelement analysis, International Journal for Numerical Methods in Engineering, 2, 5-32. Wilson, E. L., Bathe, K. J., Doherty, W. P., 1974, Direct Solution of Large System of Linear Equations, Computers & Structures, 4, 363-372. Recenzija: Marjan Jenko profdr. Ranko Todorovic Geodetski vestnik 37 (1993)