1. óra Intervallum-matematika

A speciálkollégium jellege az előadás és a gyakorlat között lesz. Zárthelyi dolgozatot nem kell írni, de beszámoló (vizsga) lesz. Fontos az órák látogatása és az aktív szereplés. Jegyzet vagy magyar nyelvű irodalom sajnos még nincs. Az órával párhuzamosan készül egy egyszerű oktatási segédlet aminek újabb lapjait ez érintettek alkalmanként megkapják, de a mindenkori aktuális változat el

is érhető a http://www.inf.u-szeged.hu/∼csendes/indexh.html címen. Angol

és német (esetleg orosz) nyelvű bevezető könyveket tudok ajánlani (lásd az irodalomjegyzéket). Ezek ismeretére nincs feltétlenül szükség a speciélkollégiumon elhangzottak megértéséhez. Ami viszont szükséges, az a lineáris algebra és a többváltozós analízis.

A tematika kulcsszavakban:

• intervallum-aritmetika: a 4 alapművelet, a négyzetreemelés, a gyökvonás, a standard függvények kiterjesztése intervallum-argumentumra

• a bit-billentés szerepe számítógépeken

• a naiv-, vagy természetes intervallum-kiterjesztés becslésének minősége, lineáris konvergencia

• a központi alak (centered form), és más befoglaló függvények, négyzetes konvergencia

• numerikus eljárások helyi — ill. globális információra támaszkodva.

• a Moore-Skelboe intervallum-felezési algoritmus, és alkalmazása globális optimalizálásra és érzékenység-vizsgálatra

• intervallumos módszer a szinthalmaz jellemzésére

• az automatikus deriválás és szerepe a befoglaló függvények javításában

• néhány intervallum-aritmetikát támogató programozási nyelv: például a PASCAL-XSC, C-XSC, FORTRAN-XSC, ACRITH, BIAS/PROFIL, ...

A jelenlegi numerikus eljárások szinte kivétel nélkül helyi információn alapulnak: pl. a vizsgált függvényt adott pontban kiértékelő szubrutin megadását kívánják meg. Bár a szóbajövő függvények pontos képletét , vagy legalább annak kiszámítási módját ismerni kell, mégis a legtöbb numerikus módszer csak adott pontbeli függvényértékre épül. Számos feladat és módszer esetén igazolható, hogy csak helyi információra támaszkodva az illető feladat véges sok lépésben nem oldható meg, sőt, ilyen módszer nem is létezhet (vö. Cs. T., Acta Cybernetica, 1988). Az a paradox helyzet áll fenn, hogy valójában az illető függvényről lényegesen többet tudunk, mint amennyit a legtöbb numerikus módszer a megoldáshoz felhasznál. Ezek tehát a fekete doboz elvén működnek.

A doktorandusz hallgatók számára külön követelmény egy 20-30 oldalas esszé írása a speciálkollégium bővebb témaköréből. A választható témák a következők:

• Affin aritmetika (Ronald van Iwaarden doktori dolgozata alapján)

• Back-boxing, illetve ϵ-infláció (Ronald van Iwaarden doktori dolgozata alapján)

• kiterjesztett intervallum aritmetikák, Kaucher-féle intervallum aritmetika (elsősorban a Kearfott könyv alapján)

• intervallumos Newton-iteráció, prekondicionálás (Kearfott könyve alapján)

• lejtő-aritmetika (slope, Dietmar Ratz habilitációs disszertációja alapján)

• változó pontosságú aritmetikák

Feladatok:

• Írjunk egy rövid programot, amely három valós számot összead, majd igazoljuk, hogy van olyan három szám, amelyre a programáltal adott eredmény a ténylegestől legalább 1999-el eltér!

• Módosítsuk a programot úgy, hogy az utóbbi három számra pontos legyen!

• Adjunk meg néhány olyanösszeadó eljárást, amely a fenti problémára megoldást jelenthet!

• Vizsgáljuk meg az egyes algoritmusok műveletigényét!

• Milyen módszer felel meg a pénzügyi számításokhoz, ahol lényegében csak egészszámokkal számolnak, de azért 100.˙3 + 100.˙3 + 100.˙3 = 301?

• Mit lehet ajánlani olyan alkalmazáshoz, ahol minden szóbajövő szám racionális, és szeretnénk azt, ha (xy)/y = x mindig teljesülne?

Házi feladat:

Próbáljuk meg a valós számokra ismert négy alapműveletetáltalánosítani kompakt valós intervallumokra!

Alapötlet: a valós számokra végzett műveleteket ki lehet terjeszteni intervallumokra is,és ha valamely mennyiségről nem egy konkrét valós számmal való egyenlőségét, hanem egy intervallumba való tartozását ismerjük, akkor az intervallumokra végrehajtott műveletek célirányosnak tűnnek.

Halmazelméleti definíció: A ∘ B := {a ∘ b : a ∈ A, b ∈ B}; A, B ∈ I, ahol I a valós kompakt intervallumok halmaza (azaz olyan (i, j) pároké, amelyekre i, j ∈ IR, és i ≤ j).

Aritmetikai definíció:

[a, b] + [c, d] = [a + c, b + d] [a, b] − [c, d] = [a − d, b − c] [a, b] ∗ [c, d] = [min(ac, ad, bc, bd), max(ac, ad, bc, bd)] [a, b]/[c, d] = [a, b] ∗ [1/d, 1/c], ha 0 ∉ [c, d].

Megjegyzés: az osztás definiálásánál a 0 ∉ [c, d] feltétel gyakran előforduló megszorításnak tűnik, de a tapasztalatok szerint nem az.

Állítás: az aritmetikai definíció megfelel a halmazelméletinek, és viszont. Tehát az intervallum-aritmetika ebben az értelemben pontos.

Az intervallum-aritmetika algebrai tulajdonságai:

• a + és a −, illetve a ∗ és a / nem inverzei egymásnak, ha intervallumokra alkalmazzuk őket. Például [0, 1] − [0, 1] = [−1, 1], és [1, 2]/[1, 2] = [1/2, 2]. Valamint [0, 0] + [0, 1] − [0, 1] = [−1, 1] és az eredmény nem [0, 0].

• érvényes az ún. szubdisztribúciós törvény, azaz A(B + C) ⊆ AB + AC. Például [0, 1]([1, 1] − [1, 1]) = [0, 0] ⊂ [0, 1][1, 1] − [0, 1][1, 1] = [−1, 1]. Másrészt viszont az a ∈ IR konstansra a(B + C) = aB + aC.

• érvényes az az általános szabály is, hogy a 0-szélességű intervallumokra (amelyekre w(A) = 0, ahol w(A) = b − a, ha A = [a, b]) az intervallumműveletek megegyeznek a valós számokon szokásos műveletekkel.

• azösszeadásés a szorzás kommutatívés asszociatív. Az egyetlen egységelem az [1., 1.], az egyetlen zéruselem a [0., 0.].

• érvényes az intervallum-műveletek befoglalási izotonitása (inclusion isotonity): A ⊆ B, C ⊆ D -ből következik, hogy A ∘ C ⊆ B ∘ D. (Persze csak akkor, ha az illető műveletek definiáltak.)

• definiáljuk az n-dimenziós A ∈ I^{n} intervallum szélességét a kordinátánkénti intervallumok szélességének maximumaként: w(A) := max_{i=1,...,n} w(A_{i}), ha A = (A_{1}, A_{2}, …, A_{n}) ∈ I^{n}. Ekkor teljesülnek a következők:

1. ha A ⊆ B, akkor w(A) ≤ w(B)

2. w(C + D) = w(C) + w(D)

3. w(aB) = |a|w(B)

• Definiáljuk az A intervallum m(A) középpontját a következőek szerint:

m(A) = (a + b)/2,

ha A ∈ I, és m(A) = (m(A_{1}), m(A_{2}), …, m(A_{n})), ha A ∈ I^{n}. Ekkor m(A ± B) = m(A) ± m(B), ha A, B ∈ I^{n}.

Kérdések:

1. Az intervallumokra definiált műveletek pontosak, de pontosak-e az ezekkel felépített függvények? Mutassunk példát!

2. Milyen függvények intervallumon vett értékkészlete számítható pusztán az intervallum végpontjaiban felvett függvényértékekkel?

3. Mit mondhatunk a konvex, és a konkáv függvények befoglaló-függvényei-ről?

3. óra: Intervallum-felosztási algoritmus Intervallum-matematika

Az intervallum-felosztási (interval subdivision, Moore-Skelboe) algoritmus adott nemlineáris függvény valamely intervallumon vett globális minimumának alsóés felsőbecslését adja meg. A kezdeti X intervallumban egy olyan X′-t keres meg, hogy F (X′) tartalmazza a globális minimum értékét, és az F (X′) intervallum szélessége kisebb legyen, mint egy előre adott ε pozitív konstans. Az algoritmus a következő:

1. Legyen Y := X és y := min F (X). Inicializáljuk az L = ((Y, y)) listát.

2. Válasszunk egy olyan k koordinátát, amellyel párhuzamosan az Y = Y_{1} × ⋯ × Y_{n} -nek maximális hosszúságú éle van.

3. Vágjuk ketté Y -t a k irány mentén: így olyan V_{1} és V_{2} boxokat kapunk, amelyekre Y = V_{1} ∪ V_{2}.

4. Számítsuk ki F (V_{1})-et és F (V_{2})-t, és legyen v_{i} = min F (V_{i}) i = 1, 2-re.

5. Töröljük (Y, y)-t az L listából.

(a) Monotonitási-vizsgálat: töröljük a (V_{i}, v_{i}) párt, ha 0 ∉ F′_{j}(V_{i}) valamely j (1 ≤ j ≤ n)-re és i = 1, 2-re.

(b) Kivágási-vizsgálat: töröljük a (V_{i}, v_{i}) párt, ha v_{i} > δ (ahol δ adott eljárásparaméter) és i = 1, 2.

6. Tegyük a (V_{1}, v_{1}) és (V_{2}, v_{2}) párokból a megmaradtakat a listába. Ha a lista üres, akkor STOP.

7. Jelöljük a lista azon párját, amelynek második eleme a legkisebb, (Y, y)-al.

8. Ha F (Y) szélessége kisebb, mint ε, akkor nyomtassuk ki F (Y) és Y értékét, és STOP.

9. Folytassuk az algoritmust a 2. lépésnél.

Az 5a pontbeli monotonitási teszt akkor töröl valamely intervallumot, ha azon az f(x) függvény szigorúan monoton. Ilyen esetben az adott intervallum nem tartalmazhat a belsejében minimumpontot. Ha az algoritmus azzal áll le, hogy üres lett a lista, akkor meg kell vizsgálni, hogy nem lehetett-e minimumpont az eredeti X intervallum határán (például úgy, hogy az algoritmust újraindítjuk egy X̂ ⊃ X intervallummal. Másik megoldás lehet, ha az 5a lépésben a törlés helyett az aktuális intervallumot helyettesítjük a megfelelő lapjával. Ekkor nincs szükség az X̂ intervallummal való ellenőrzésre.

Az 5b pontbeli kivágási teszt olyan részintervallumokat dob el, amelyekre az f(x) függvény lehetséges legkisebb értéke is nagyobb, mint δ. A δ értékét megválaszthatjuk a feladatra vonatkozó előzetes információink alapján, de adaptív módon is: kezdetben legyen δ = max F (X), majd minden vágásnál δ = min(δ, max F (V_{1}), max F (V_{2})). Algoritmusunk 5b lépése az utóbbi eljárással biztos nem dob ki olyan részintervallumot, amelyben globális minimumpont van. Teszteredmények az 5a, 5b lépések nélkül, illetve az 5a lépéssel:

S5 S7 S10  H3^{†}  H6^{†}  GP^{†} RB SHCB RCOS
STU 0.4 0.7 1.4 244.3 249.8 199.5 0.1 142.7  0.1
NFE 90 186 204 11453 11319 10499 56 9024  98
NDE – – – – – – – – –
LLI 48 137 166 5000 5000 5000 28 5000  47
EFF 0.3 0.6 0.5 97.5 49.0 52.8 0.3 77.5  0.8

S5 S7 S10 H3 H6  GP RB SHCB RCOS
STU 1.2 1.7 2.5 9.5 75.2 746.8 0.1  0.9  0.4
NFE 86 92 94 722 2288 34850 56  384  98
NDE 205 219 227 1158 8141 46355 63  540  149
LLI  3  5 10 361 1238 5000 9  194  29
EFF 1.0 1.0 0.9 16.0 45.1 408.1 0.6  7.9  2.1

4. óra: Automatikus differenciálás Intervallum-matematika

A numerikus algoritmusok gyakran támaszkodnak valamely függvény deriváltjára. A deriváltfüggvények előállítására az alkalmazás gyakoriságának megfelelő sorrendben a következő eljárásokat szokás használni:

1. Az illető függvény ”kézzel”, papiron való deriválása, majd a megfelelő szubrutin megírása.

2. Numerikus deriválás: amikor a felhasználó vagy a számítógépes program maga ad egy numerikus közelítést ( a differencia-hányadost) a derivált aktuális pontbeli értékére. Ha lehet választani, akkor az algoritmusba beépített közelítést válasszuk!

3. A vizsgált függvény szimbolikus deriválása valamely számítógépes algebra rendszerben (DERIVE, REDUCE, MATHEMATICA, MAPLE, ...).

4. Az alább részletezendő automatikus differenciálás.

Ha egy f(x) függvény képlettel megadható, illetve rendelkezésreáll azőt kiszámító szubrutin, akkor a következő eljárással egyszerűen lehet a derivált értékét (nem numerikus becsléssel) meghatározni. A függvény minden változója helyett használjunk olyan adat-szerkezetet, amely két valós számból áll. Az első felel meg a korábbi változó-értéknek, a második pedig egy derivált-értéknek. Minden változóra ez a második valós legyen a szubrutin hívásakor egy. Minden, a függvény kiszámításához használt konstans új adat-szerkezetében a második érték legyen nulla. Ezután csak olyan segéd-rutin készletre van szükség, amely minden műveletre elvégzi a megfelelő operációt az első tagon, és a deriválási szabályoknak megfelelő lépést a második tagon. Például, ha f(x) = x_{1} ∗ x_{2}, akkor a szokásos programsor F = X(1) ∗ X(2) lenne. Az automatikus differenciálás megfelelő művelete ezzel szemben

F (1) = X(1, 1) ∗ X(2, 1),

és

F (2) = X(1, 1) ∗ X(2, 2) + X(2, 1) ∗ X(1, 2)

lesz. A többi, számítógépen szokásos művelethez is könnyű megadni a megfelelő új aritmetikát. Az automatikus differenciálás jól használható olyan optimalizálási feladatok megoldásához, amikor a célfüggvényt kiszámító szubrutin rendelkezésre áll, de a deriváltak analitikus kiszámítása bonyolult vagy lehetetlen lenne.

Vegyükészre, hogy a deriváltértékének kiszámítása során sehol se jelenik meg a deriváltfüggvény képlete.

Ellenőrző kérdések és feladatok:

• Igazoljuk, hogy a vázolt eljárás kerekítés nélküli aritmetika esetén pontosan a derivált értékét adja.

• Adjunk becslést arra, hogy az automatikus differenciálás és az analitikusan megadott derivált műveletigénye hogyan viszonyul egymáshoz!

• Hogyan működik a belsőfüggvény deriválása esetünkben?

• Hogyan lehet eljárásunkat többváltozós függvények parciális deriválására kiterjeszteni? (Mit kell konstansnak, és mit változónak tekinteni?)

• Határozzuk meg a másodrendű deriváltak előállításához szükséges aritmetikát!

• Vizsgáljuk meg annak lehetőségét, hogy az automatikus differenciáláshoz hasonlóan felépíthető (?) optimalizálási aritmetikát milyen feladatokra lehet alkalmazni!

Ajánlott irodalom: Rall könyve (az irodalomjegyzékben megadtuk a pontos bibliográfiai adatokat),és főleg Csendes Tibor: Automatikus differenciálás című cikke a Polygon folyóirat 1996. júliusi számában.

Programozási feladat: Írjuk meg az automatikus differenciálás szubrutinjait, és teszteljük néhány függvényen!

Ellenőrző kérdések:

1. Ki lehet-e terjeszteni a négy alapmüveletet valós számokról intervallumokra?

2. Igaz-e, hogy két intervallumösszege pontosan azokat a pontokat tartalmazza, amelyek előállnak a két argumentum-intervallumbeli pontok összegeként?

3. Milyen információra támaszkodik a monotonitási teszt?

4. Mi okozza a befoglaló függvények durva becslését?

5. Mi az a kifelé-kerekítés?

6. Hány féle kerekítést enged meg az IEEE processzor-szabvány?

7. Igaz-e, hogy egy szigorúan monoton függvény deriváltjának befoglaló függvénye nem tartalmazza a nullát?

8. Igaz-e, hogy az intervallumos befoglaló függvény számítása mindig tovább tart, mint az eredeti valós függvényé?

9. Melyik eljárással kapjuk a legjobb befoglaló függvényt az X*X-X függvényre a [-1.,1.] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a gyorsabb eljárás a jobb)

10. Melyik eljárással kapjuk a legrosszabb befoglaló függvényt az X*X-X függvényre a [-1.,1.] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a lassabb eljárás a rosszabb)

11. Melyik eljárással kapjuk a legjobb befoglaló függvényt az X*X-X függvényre a [1.,10.] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a gyorsabb eljárás a jobb)

12. Melyik eljárással kapjuk a legrosszabb befoglaló függvényt az X*X-X függvényre a [1.,10.] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a lassabb eljárás a rosszabb)

13. Melyik eljárással kapjuk a legjobb befoglaló függvényt az X*X-X függvényre a [0.4,0.6] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a gyorsabb eljárás a jobb)

14. Melyik eljárással kapjuk a legrosszabb befoglaló függvényt az X*X-X függvényre a [0.4,0.6] intervallumra? (X*X nem négyzetreemelés, azonos pontosság esetén a lassabb eljárás a rosszabb)

15. Mi az a szubdisztribuciós szabály?

16. Invertálható-e az intervallumos összeadás?

17. Azonos-e az X intervallum négyzete X * X -el?

18. Reprezentálhatóak-e mindig a valós müveletek intervallum-müveletekkel?

19. Igaz-e, hogy ha X része Y-nak, akkor minden befoglaló függvényre F(X) is része F(Y)-nak?

20. Milyen programozási nyelvek alkalmasak intervallum aritmetikával való számolásra?

Irodalomjegyzék

1. G. Alefeld, J. Herzberger: Einführung in die Intervallrechnung, Bibliographises Institut AG, Mannheim, 1974.

2. G. Alefeld, J. Herzberger: Introduction to Interval Computations, Academic Press, New York, 1983.

3. S. Berner: Ein paralleles Verfahren zur verifizierten globalen Optimierung (németül), PhD Thesis, University of Wuppertal, Germany, 1995.

4. R. Hammer, M. Hocks, U. Kulisch, D. Ratz: Numerical Toolbox for Verified Computing I., Basic Numerical Problems. Springer-Verlag, Berlin, 1993.

5. E. Hansen: Global Optimization using Interval Analysis. Marcel Dekker, New York, 1992.

6. S.A. Kalmikov, Yu.I. Sokin, Z.H. Yuldashev: Az intervallum-analízis módszerei (oroszul), Nauka, Moszkva, 1986.

7. R. Baker Kearfott: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht, 1996.

8. R. Klatte, U. Kulisch, C. Lawo, M. Rauch, A. Wiethoff: C-XSC — A C++ Class Library for Extended Scientific Computing. Springer-Verlag, berlin, 1993.

9. R. Klatte, U. Kulisch, M. Neaga, D. Ratz, Ch. Ullrich: PASCAL-XSC, Language Reference with Examples. Springer-Verlag, Berlin, 1992.

10. R. Klatte, U. Kulisch, M. Neaga, D. Ratz, Ch. Ullrich: PASCAL-XSC. (oroszul) televinf, Moszkva, 1997.

11. O. Knüppel: BIAS — basic interval arithmetic subroutines. Technical Report 93.3, University of Hamburg, 1993.

12. L.B. Rall: Automatic Differentiation — Techniques and Applications, Lecture Notes in Computer Science Vol. 120, Springer-Verlag, Berlin, 1981.

13. H. Ratschek, J. Rokne: Computer Methods for the Range of Functions, Ellis Horwood Ltd., Chichester, 1984.

14. H. Ratschek, J. Rokne: New Computer Methods for Global Optimization, Ellis Horwood Ltd., Chichester, 1988.

15. D. Ratz: Automatische Ergebnisverifikation bei globalen Optimierungsproblemen. Dissertation, Universität Karlsruhe, 1992.

16. D. Ratz: Automatic Slope Computation and its Application in Nonsmooth Global Optimization. Shaker Verlag, Aachen, 1998.

Ezek mind elérhetők vagy közvetlenül az Informatikai Intézet könyvtárában, vagy az előadónál.

Postscript file-ként rendelkezésre álló doktori dolgozatok, illetve kéziratok:

1. S.L.P. Ferguson: Sphere Packings (a Kepler feladat megoldásának részletei)

2. R.J. Van Iwaarden: An improved unconstrained global optimization algorithm, Denver, 1996.

3. F. Messine: Méthodes d’Optimisation Globale basées sur l’Analyse d’Intervalle pour la Résolution de Problèmes avec Contraintes. Toulouse, 1997.

4. A. Wiethoff: Verifizierte globale Optimierung auf Parallelrechnern. Karlsruhe, 1997.

Hasznos olvasmány még a legutóbbi SCAN konferencia teljes anyaga, amely elérhető a

                 http://www.inf.u-szeged.hu/∼scan98

címen.