Interval aritmetik

Intervalaritmetik  er en matematisk struktur , der for reelle intervaller definerer operationer svarende til almindelig aritmetik. Dette område af matematik kaldes også intervalanalyse eller intervalberegning . Denne matematiske model er praktisk til at studere forskellige anvendte objekter [1] :

• Mængder, hvis værdier kun kendes tilnærmelsesvis , det vil sige, der er defineret et begrænset interval, hvori disse værdier er indeholdt.
• Mængder, hvis værdier er forvrænget af afrundingsfejl under beregninger .
• tilfældige variable .

Intervalaritmetikkens objekter og operationer kan ses som en generalisering af den reelle talmodel, hvorfor intervaller kaldes intervaltal i en række kilder . Den praktiske betydning af denne model skyldes, at resultaterne af målinger og beregninger næsten altid har nogle fejl, som skal tages i betragtning og vurderes.

Baggrund

Intervalregning er ikke et helt nyt fænomen i matematikken; hun har optrådt flere gange i historien under forskellige navne. For eksempel Arkimedes i det III århundrede f.Kr. e.. beregnet de nedre og øvre grænser for tallet :

Selvom intervalberegninger ikke var så populære som andre numeriske metoder, blev de ikke helt glemt.

Intervalberegningens nye historie begynder i 1931 med Rosalind Cecily Youngs arbejde [2] , hvor regler for beregning med intervaller og andre delmængder af reelle tal blev givet. I 1951 udkom Paul S. Dwyers lærebog om lineær algebra , hvor dette emne blev overvejet ud fra et synspunkt om at forbedre pålideligheden af ​​digitale systemer - intervaller blev brugt til at estimere afrundingsfejl forbundet med flydende kommatal [3] . I 1958 udgav Teruo Sunaga et detaljeret papir om anvendelsen af ​​intervalalgebra til numerisk analyse [4] .

I anden halvdel af det 20. århundrede forårsagede computercomputernes behov den hurtige udvikling af intervalanalyse næsten samtidigt og uafhængigt i Sovjetunionen, USA, Japan og Polen. I 1966 udkom den amerikanske matematiker Ramon Moores bog "Interval Analysis" [ 5 ] . Fordelen ved dette arbejde var, at det ud fra et simpelt princip gav en generel metode til automatisk at analysere fejl, og ikke kun fejl som følge af afrunding.

I de næste to årtier blev vigtig forskning i intervalanalyse og dens anvendelser udført i Tyskland af Karl Nickel og hans studerende ved universitetet i Freiburg, i grupperne Ulrich Kulisch og Götz Ahlefeld ved universitetet i Karlsruhe [6] ] [7] og andre.

I 1960'erne udvidede Eldon R. Hansen intervaltilgangen til lineære ligningssystemer og gav derefter vigtige bidrag til global optimering , herunder hvad der nu er kendt som Hansen-metoden, måske den mest udbredte intervalalgoritme [8] . Klassiske metoder i dette problem har ofte et problem med at bestemme den største (eller mindste) globale værdi (de kan kun finde et lokalt optimum og kan ikke finde de bedste værdier); Helmut Rachek og John George Rockne udviklede en variation af branch and bound-metoden , som indtil da kun var blevet anvendt på heltalsværdier.

I 1988 udviklede Rudolf Lohner Fortran - baseret software til at bevise Cauchy-problemet for systemer med almindelige differentialligninger [9] .

Siden 1990'erne begyndte udgivelsen af ​​det internationale tidsskrift "Interval Computing" - "Interval Computations", som i 1995 blev omdøbt til "Reliable Computing" ("Reliable Computing"). Tidsskriftets hovedemner er evidensbaserede beregninger, metoder til intervalanalyse og dets anvendelser.

I Rusland og USSR har V. M. Bradis været aktivt involveret i intervaltemaer siden 1920'erne . I 1962 udgav en af ​​de første udgaver af Siberian Mathematical Journal en artikel af Leonid Vitalievich Kantorovich , som faktisk skitserede grundlaget for intervalanalyse i delvist ordnede rum og anvendelsen af ​​nye teknikker. I hans artikel blev dette emne udpeget som en prioritet for vores beregningsvidenskab [10] . I efterkrigstiden var en af ​​de første bogen af ​​Yu. I. Shokin "Interval Analysis" [11] . Året efter udkom en lærebog af T.I. Nazarenko og L.V. Marchenko "Introduktion til intervalmetoder for beregningsmatematik" [12] , og i 1986 - en monografi af S. A. Kalmykov, Yu. I. Shokin og Z. Kh. Yuldashev "Methods of interval analysis" [13] .

Operationer på intervaller

Vi vil overveje alle mulige endelige reelle intervaller . Operationer på dem er defineret som følger:

• Tilføjelse: [ a , b ] + [ c , d ] = [ a + c , b + d ]
• Subtraktion: [ a , b ] − [ c , d ] = [ a − d , b − c ]
• Multiplikation: [ a , b ] × [ c , d ] = [min ( ac , ad , bc , bd ), max ( ac , ad , bc , bd )]
• Division: [ a , b ] / [ c , d ] = [min ( a/c , a/d , b/c , b/d ), max ( a/c , a/d , b/c , b/ d )]

Det kan ses af definitionen, at sum-intervallet indeholder alle mulige summer af tal fra summand-intervallerne og bestemmer grænserne for mængden af ​​sådanne summer. Andre handlinger behandles på samme måde. Bemærk, at divisionsoperationen kun defineres, hvis divisorintervallet ikke indeholder nul.

Degenererede intervaller, hvis begyndelse og slutning falder sammen, kan identificeres med almindelige reelle tal. For dem falder ovenstående definitioner sammen med de klassiske aritmetiske operationer.

Operationsegenskaber

Addition og multiplikation af intervaller er både kommutative og associative . Men i stedet for den fuldgyldige fordeling af multiplikation ved addition, finder den såkaldte underfordeling sted:

Varianter og udvidelser af intervalaritmetik

IEEE 1788

IEEE 1788-2015 computerimplementeringsstandarden for intervalaritmetik blev vedtaget i juni 2015. [14] Under udviklingen af ​​standarden og i de efterfølgende år blev der udarbejdet adskillige frit distribuerede referenceimplementeringer: [15] C++-biblioteket libieeep1788 [ 16] -biblioteket til C++, JInterval-biblioteket til Java-sproget og en pakke, der implementerer interval beregninger for gratis matematisk software GNU Octave [17] .

Minimumsundergruppen af ​​standarden, designet til at forenkle og fremskynde dens implementering - IEEE Std 1788.1-2017, blev vedtaget i december 2017 og offentliggjort i februar 2018. [18]

Software

Der er mange implementeringer af interval-aritmetik i forskellige softwarepakker [19] . Ofte er de designet som specialiserede biblioteker. En række Fortran og C++ compilere inkluderer understøttelse af intervalværdier som en speciel datatype.

Se også

• Tilnærmede beregninger
• IEEE 754

Noter

1. ↑ Shary, 2019 , s. atten.
2. ↑ Young, Rosalind Cicely (1931). mængden af ​​mange værdifulde mængder. Mathematische Annalen, 104(1), 260-290. (Dette er hendes afhandling ved University of Cambridge ).
3. ↑ Dwyer, Paul Sumner (1951). Lineære beregninger. Oxford, England: Wiley. (University of Michigan)
4. ↑ Teori om intervalalgebra og dens anvendelse på numerisk analyse  //  RAAG Memoirs: journal. - 1958. - Nej. 2 . - S. 29-46 .
5. ↑ Intervalanalyse  . _ - Englewood Cliff, New Jersey, USA: Prentice Hall , 1966. - ISBN 0-13-476853-1 .
6. ↑ Grundzüge der Intervallrechnung // Jahrbuch Überblicke Mathematik  (tysk) / Laugwitz, Detlef. - Mannheim, Tyskland: Bibliographisches Institut , 1969. - Bd. 2. - S. 51-98.
7. ↑ Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung  (tysk) . - Wiesbaden: Springer Vieweg Verlag , 1989. - ISBN 3-528-08943-1 .
8. ↑ Global optimering ved hjælp af  intervalanalyse . — 2. - New York, USA: Marcel Dekker , 2004. - ISBN 0-8247-4059-9 .
9. ↑ Grænser for almindelige differentialligninger af Rudolf Lohner Arkiveret 11. maj 2018. (på tysk)
10. ↑ Historiske noter .
11. ↑ Shokin, 1981 .
12. ↑ T. I. Nazarenko, L. V. Marchenko. Introduktion til intervalmetoder for beregningsmatematik "Textbook. Irkutsk: Publishing House of Irkutsk University, 1982. - 108 s.
13. ↑ S. A. Kalmykov, Yu. I. Shokin, Z. Kh. Yuldashev Metoder til intervalanalyse. - Novosibirsk: Nauka, 1986, 224 s.
14. ↑ IEEE-standard for intervalaritmetik . Hentet 7. februar 2022. Arkiveret fra originalen 7. februar 2022. (ubestemt)
15. ↑ Revol, Nathalie (2015). Den (nærmeste) fremtidige IEEE 1788-standard for intervalaritmetik. 8. lille workshop om intervalmetoder. Slides (PDF) Arkiveret 2. juni 2016 på Wayback Machine
16. ↑ C++ implementering af den foreløbige IEEE P1788 standard for interval aritmetik . Hentet 31. juli 2018. Arkiveret fra originalen 10. juni 2018. (ubestemt)
17. ↑ GNU Octave interval-pakke . Hentet 31. juli 2018. Arkiveret fra originalen 9. november 2016. (ubestemt)
18. ↑ IEEE Std 1788.1-2017 - IEEE Standard for Interval Aritmetic (Simplified) . IEEE SA . IEEE Standards Association. Hentet 6. februar 2018. Arkiveret fra originalen 7. februar 2022. (ubestemt)
19. ↑ Software til intervalberegninger Arkiveret 2. marts 2006 på Wayback Machine indsamlet af Vladik Kreinovich , University of Texas i El Paso

Litteratur

• Alefeld G., Herzberger J. . En introduktion til intervalberegning . M.: Mir, 1987. 356 s.
• Dobronets B. S. Intervalmatematik . Krasnoyarsk: KSU Publishing House, 2004.
• Shary S. P. Finitdimensional intervalanalyse . - Novosibirsk: XYZ, 2019. - 635 s.
• Shokin Yu. I. Intervalanalyse . - Novosibirsk: Sibirisk afdeling af Nauka-forlaget, 1981.

Links

• Intervalanalyse og dens anvendelser .
  • Historiske Noter .
• Intervalregning hos  Mathworld .