Intervalová aritmetika

Intervalová aritmetika  je matematická struktura , která pro reálné intervaly definuje operace podobné běžné aritmetice. Tato oblast matematiky se také nazývá intervalová analýza nebo intervalové počítání . Tento matematický model je vhodný pro studium různých aplikovaných objektů [1] :

• Veličiny, jejichž hodnoty jsou známy pouze přibližně , to znamená, že je definován konečný interval, ve kterém jsou tyto hodnoty obsaženy.
• Veličiny, jejichž hodnoty jsou zkresleny chybami zaokrouhlování během výpočtů .
• náhodné proměnné .

Na objekty a operace intervalové aritmetiky lze pohlížet jako na zobecnění modelu reálných čísel, proto se intervaly v řadě zdrojů nazývají intervalová čísla . Praktický význam tohoto modelu je dán tím, že výsledky měření a výpočtů mají téměř vždy nějakou chybu, se kterou je nutné počítat a vyhodnocovat ji.

Pozadí

Intervalová aritmetika není v matematice zcela novým fenoménem; v historii se objevila několikrát pod různými jmény. Například Archimedes ve III století před naším letopočtem. e.. vypočítal dolní a horní hranici pro číslo :

I když intervalové výpočty nebyly tak populární jako jiné numerické metody, nebyly zcela zapomenuty.

Nová historie intervalového počítání začíná v roce 1931 prací Rosalind Cecily Young [2] , kde byla uvedena pravidla pro počítání s intervaly a dalšími podmnožinami reálných čísel. V roce 1951 se objevila učebnice lineární algebry Paula S. Dwyera , ve které bylo toto téma zvažováno z hlediska zlepšení spolehlivosti číslicových systémů - intervaly byly použity k odhadu zaokrouhlovacích chyb spojených s čísly s plovoucí desetinnou čárkou [3] . V roce 1958 Teruo Sunaga publikoval podrobný článek o aplikaci intervalové algebry na numerickou analýzu [4] .

V druhé polovině 20. století způsobily potřeby počítačových výpočtů rychlý rozvoj intervalové analýzy téměř současně a nezávisle v Sovětském svazu, USA, Japonsku a Polsku. V roce 1966 vyšla kniha amerického matematika Ramona Moora „Interval Analysis“ [ 5 ] . Předností této práce bylo, že na základě jednoduchého principu poskytla obecnou metodu pro automatickou analýzu chyb, a nikoli pouze chyb vyplývajících ze zaokrouhlování.

V následujících dvou desetiletích prováděl v Německu významný výzkum intervalové analýzy a jejích aplikací Karl Nickel a jeho studenti na univerzitě ve Freiburgu ve skupinách Ulricha Kulische a Götze Ahlefelda na univerzitě v Karlsruhe [6 ] [7] a další.

V 60. letech rozšířil Eldon R. Hansen intervalový přístup na systémy lineárních rovnic a poté významně přispěl ke globální optimalizaci , včetně toho, co je dnes známé jako Hansenova metoda, možná nejrozšířenější intervalový algoritmus [8] . Klasické metody v této úloze mají často problém s určením největší (či nejmenší) globální hodnoty (umí najít pouze lokální optimum a neumí najít nejlepší hodnoty); Helmut Rachek a John George Rockne vyvinuli variaci na metodu větvení a vazby , která se do té doby používala pouze na celočíselné hodnoty.

V roce 1988 Rudolf Lohner vyvinul software založený na Fortranu pro dokazování Cauchyho problému pro systémy obyčejných diferenciálních rovnic [9] .

Od 90. let začalo vydávání mezinárodního časopisu "Interval Computing" - "Interval Computations", který byl v roce 1995 přejmenován na "Reliable Computing" ("Reliable Computing"). Hlavními tématy časopisu jsou výpočty založené na důkazech, metody intervalové analýzy a její aplikace.

V Rusku a SSSR se V. M. Bradis aktivně věnuje intervalovým tématům od 20. let 20. století . V roce 1962 jedno z prvních čísel Siberian Mathematical Journal publikovalo článek Leonida Vitalieviče Kantoroviče , který ve skutečnosti nastínil základy intervalové analýzy v částečně uspořádaných prostorech a aplikace nových technik. Ve svém článku bylo toto téma označeno za prioritu naší výpočetní vědy [10] . V poválečném období byla jednou z prvních kniha Yu. I. Shokina „Intervalová analýza“ [11] . Následující rok vyšla učebnice T.I. Nazarenko a L.V. Marčenko "Úvod do intervalových metod výpočetní matematiky" [12] a v roce 1986 - monografie S. A. Kalmykova, Yu. I. Shokina a Z. Kh. Yuldasheva "Metody intervalové analýzy" [13] .

Operace s intervaly

Budeme uvažovat všechny možné konečné reálné intervaly . Operace na nich jsou definovány takto:

• Sčítání: [ a , b ] + [ c , d ] = [ a + c , b + d ]
• Odečítání: [ a , b ] − [ c , d ] = [ a − d , b − c ]
• Násobení: [ a , b ] × [ c , d ] = [min ( ac , ad , bc , bd ), max ( ac , ad , bc , bd )]
• Dělení: [ a , b ] / [ c , d ] = [min ( a/c , a/d , b/c , b/d ), max ( a/c , a/d , b/c , b/ d )]

Z definice je vidět, že součet-interval obsahuje všechny možné součty čísel ze sčítacích intervalů a určuje hranice množiny takových součtů. Ostatní akce jsou řešeny podobně. Všimněte si, že operace dělení je definována pouze v případě, že interval dělitele neobsahuje nulu.

Degenerované intervaly, jejichž začátek a konec se shodují s běžnými reálnými čísly. U nich se výše uvedené definice shodují s klasickými aritmetickými operacemi.

Vlastnosti operace

Sčítání a násobení intervalů jsou komutativní i asociativní . Ale místo plnohodnotné distributivity násobení sčítáním dochází k tzv. subdistributivitě:

Varianty a rozšíření intervalové aritmetiky

IEEE 1788

V červnu 2015 byl přijat počítačový implementační standard IEEE 1788-2015 pro intervalovou aritmetiku. [14] Během vývoje standardu a v následujících letech bylo připraveno několik volně distribuovaných referenčních implementací: [15] knihovna C++ libieeep1788 [ 16] knihovna pro C++, knihovna JInterval pro jazyk Java a balíček implementující interval výpočty pro bezplatný matematický software GNU Octave [17] .

Minimální podmnožina standardu, navržená pro zjednodušení a urychlení jeho implementace – IEEE Std 1788.1-2017, byla přijata v prosinci 2017 a zveřejněna v únoru 2018. [18]

Software

Existuje mnoho implementací intervalové aritmetiky v různých softwarových balíčcích [19] . Často jsou navrženy jako specializované knihovny. Řada kompilátorů Fortran a C++ obsahuje podporu pro intervalové hodnoty jako speciální datový typ.

Viz také

• Přibližné výpočty
• IEEE 754

Poznámky

1. ↑ Shary, 2019 , str. osmnáct.
2. ↑ Young, Rosalind Cicely (1931). množství mnohohodnotných veličin. Mathematische Annalen, 104(1), 260-290. (Toto je její disertační práce na University of Cambridge ).
3. ↑ Dwyer, Paul Sumner (1951). Lineární výpočty. Oxford, Anglie: Wiley. (Michiganská univerzita)
4. ↑ Teorie intervalové algebry a její aplikace na numerickou analýzu  //  RAAG Memoirs: journal. - 1958. - Ne. 2 . - str. 29-46 .
5. ↑ Intervalová  analýza . - Englewood Cliff, New Jersey, USA: Prentice Hall , 1966. - ISBN 0-13-476853-1 .
6. ↑ Grundzüge der Intervallrechnung // Jahrbuch Überblicke Mathematik  (německy) / Laugwitz, Detlef. - Mannheim, Německo: Bibliographisches Institut , 1969. - Bd. 2. - S. 51-98.
7. ↑ Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung  (německy) . - Wiesbaden: Springer Vieweg Verlag , 1989. - ISBN 3-528-08943-1 .
8. ↑ Globální optimalizace pomocí intervalové  analýzy . — 2. - New York, USA: Marcel Dekker , 2004. - ISBN 0-8247-4059-9 .
9. ↑ Meze pro obyčejné diferenciální rovnice Rudolfa Lohnera Archivováno 11. května 2018. (v němčině)
10. ↑ Historické poznámky .
11. ↑ Shokin, 1981 .
12. ↑ T. I. Nazarenko, L. V. Marčenko. Úvod do intervalových metod výpočetní matematiky "Učebnice. Irkutsk: Nakladatelství Irkutské univerzity, 1982. - 108 s.
13. ↑ S. A. Kalmykov, Yu.I. Shokin, Z. Kh. Yuldashev Metody intervalové analýzy. - Novosibirsk: Nauka, 1986, 224 s.
14. ↑ Standard IEEE pro intervalovou aritmetiku . Získáno 7. února 2022. Archivováno z originálu 7. února 2022. (neurčitý)
15. ↑ Revol, Nathalie (2015). (blízko)budoucí standard IEEE 1788 pro intervalovou aritmetiku. 8. malý workshop o intervalových metodách. Slides (PDF) Archivováno 2. června 2016 na Wayback Machine
16. ↑ C++ implementace předběžného standardu IEEE P1788 pro intervalovou aritmetiku . Staženo 31. července 2018. Archivováno z originálu 10. června 2018. (neurčitý)
17. ↑ GNU Octave intervalový balíček . Získáno 31. července 2018. Archivováno z originálu 9. listopadu 2016. (neurčitý)
18. ↑ IEEE Std 1788.1-2017 – standard IEEE pro intervalovou aritmetiku (zjednodušený) . IEEE SA . IEEE Standards Association. Staženo 6. února 2018. Archivováno z originálu 7. února 2022. (neurčitý)
19. ↑ Software pro intervalové výpočty Archivováno 2. března 2006 na Wayback Machine shromážděné Vladikem Kreinovichem z Texaské univerzity v El Pasu

Literatura

• Alefeld G., Herzberger J. . Úvod do intervalového počítání . M.: Mir, 1987. 356 s.
• Dobronets B. S. Intervalová matematika . Krasnojarsk: Nakladatelství KSU, 2004.
• Shary S. P. Analýza konečných rozměrů . - Novosibirsk: XYZ, 2019. - 635 s.
• Shokin Yu. I. Intervalová analýza . - Novosibirsk: Sibiřská pobočka nakladatelství Nauka, 1981.

Odkazy

• Intervalová analýza a její aplikace .
  • Historické poznámky .
• Intervalová aritmetika v Mathworld  .