Intervall aritmetik

Intervallaritmetik  är en matematisk struktur som, för verkliga intervall , definierar operationer som liknar vanlig aritmetik. Detta område av matematik kallas också intervallanalys eller intervallberäkning . Denna matematiska modell är bekväm för att studera olika tillämpade objekt [1] :

• Kvantiteter vars värden är kända endast ungefär , det vill säga ett ändligt intervall definieras i vilket dessa värden finns.
• Kvantiteter vars värden förvrängs av avrundningsfel under beräkningar .
• slumpmässiga variabler .

Intervallaritmetikens objekt och operationer kan ses som en generalisering av den reella talmodellen, varför intervall kallas intervalltal i ett antal källor . Den praktiska betydelsen av denna modell beror på att resultaten av mätningar och beräkningar nästan alltid har något fel, som måste beaktas och utvärderas.

Bakgrund

Intervallaritmetik är inte ett helt nytt fenomen inom matematiken; hon har förekommit flera gånger i historien under olika namn. Till exempel Arkimedes på III-talet f.Kr. e .. beräknat de nedre och övre gränserna för talet :

Även om intervallberäkningar inte var lika populära som andra numeriska metoder, glömdes de inte helt bort.

Intervallberäkningens nya historia börjar 1931 med Rosalind Cecily Youngs arbete [2] , där regler för beräkning med intervall och andra delmängder av reella tal gavs. År 1951 kom Paul S. Dwyers lärobok om linjär algebra , där detta ämne övervägdes ur synvinkeln att förbättra tillförlitligheten hos digitala system - intervall användes för att uppskatta avrundningsfel associerade med flyttal [3] . 1958 publicerade Teruo Sunaga en detaljerad artikel om tillämpningen av intervallalgebra för numerisk analys [4] .

Under andra hälften av 1900-talet orsakade behoven av datoranvändning den snabba utvecklingen av intervallanalys nästan samtidigt och oberoende i Sovjetunionen, USA, Japan och Polen. 1966 kom den amerikanske matematikern Ramon Moores bok "Interval Analysis" [ 5 ] . Förtjänsten med detta arbete var att det, utgående från en enkel princip, gav en generell metod för att automatiskt analysera fel, och inte bara fel som härrör från avrundning.

Under de kommande två decennierna utfördes viktig forskning om intervallanalys och dess tillämpningar i Tyskland av Karl Nickel och hans studenter vid universitetet i Freiburg, i grupperna Ulrich Kulisch och Götz Ahlefeld vid universitetet i Karlsruhe [6] ] [7] , och andra.

På 1960-talet utvidgade Eldon R. Hansen intervallmetoden till linjära ekvationssystem och gav sedan viktiga bidrag till global optimering , inklusive vad som nu är känt som Hansenmetoden, kanske den mest använda intervallalgoritmen [8] . Klassiska metoder i detta problem har ofta problem med att bestämma det största (eller minsta) globala värdet (de kan bara hitta ett lokalt optimum och kan inte hitta de bästa värdena); Helmut Rachek och John George Rockne utvecklade en variant av branch and bound-metoden , som fram till dess bara hade tillämpats på heltalsvärden.

1988 utvecklade Rudolf Lohner Fortran -baserad mjukvara för att bevisa Cauchy-problemet för system med vanliga differentialekvationer [9] .

Sedan 1990-talet började utgivningen av den internationella tidskriften "Interval Computing" - "Interval Computations", som 1995 döptes om till "Reliable Computing" ("Reliable Computing"). Tidskriftens huvudämnen är evidensbaserade beräkningar, metoder för intervallanalys och dess tillämpningar.

I Ryssland och Sovjetunionen har V. M. Bradis varit aktivt involverad i intervallteman sedan 1920 -talet . 1962 publicerade ett av de första numren av Siberian Mathematical Journal en artikel av Leonid Vitalievich Kantorovich , som faktiskt beskrev grunderna för intervallanalys i delvis ordnade utrymmen och tillämpningar av nya tekniker. I hans artikel utsågs detta ämne som en prioritet för vår beräkningsvetenskap [10] . Under efterkrigstiden var en av de första boken av Yu. I. Shokin "Interval Analysis" [11] . Året därpå kom en lärobok av T.I. Nazarenko och L.V. Marchenko "Introduktion till intervallmetoder för beräkningsmatematik" [12] , och 1986 - en monografi av S. A. Kalmykov, Yu. I. Shokin och Z. Kh. Yuldashev "Metoder för intervallanalys" [13] .

Operationer på intervaller

Vi kommer att överväga alla möjliga ändliga reella intervall . Operationer på dem definieras enligt följande:

• Tillägg: [ 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 av definitionen att summaintervallet innehåller alla möjliga summor av tal från summeringsintervallen och bestämmer gränserna för mängden av sådana summor. Andra åtgärder behandlas på liknande sätt. Observera att divisionsoperationen endast definieras om divisorintervallet inte innehåller noll.

Degenererade intervall vars början och slut sammanfaller kan identifieras med vanliga reella tal. För dem sammanfaller ovanstående definitioner med de klassiska aritmetiska operationerna.

Funktionsegenskaper

Addition och multiplikation av intervall är både kommutativa och associativa . Men istället för den fullvärdiga fördelningen av multiplikation genom addition, sker den så kallade subdistributiviteten:

Varianter och förlängningar av intervallaritmetik

IEEE 1788

Datorimplementeringsstandarden IEEE 1788-2015 för intervallaritmetik antogs i juni 2015. [14] Under utvecklingen av standarden och under efterföljande år förbereddes flera fritt distribuerade referensimplementeringar: [15] C++-biblioteket libieeep1788 [ 16] -biblioteket för C++, JInterval-biblioteket för Java-språket och ett paket som implementerar intervall beräkningar för gratis matematisk programvara GNU Octave [17] .

Minsta delmängd av standarden, utformad för att förenkla och påskynda implementeringen - IEEE Std 1788.1-2017, antogs i december 2017 och publicerades i februari 2018. [18]

Programvara

Det finns många implementeringar av intervallaritmetik i olika mjukvarupaket [19] . Ofta är de utformade som specialiserade bibliotek. Ett antal Fortran- och C++-kompilatorer inkluderar stöd för intervallvärden som en speciell datatyp.

Se även

• Ungefärliga beräkningar
• IEEE 754

Anteckningar

1. ↑ Shary, 2019 , sid. arton.
2. ↑ Young, Rosalind Cicely (1931). kvantiteten av många värderade kvantiteter. Mathematische Annalen, 104(1), 260-290. (Detta är hennes avhandling vid University of Cambridge ).
3. ↑ Dwyer, Paul Sumner (1951). Linjära beräkningar. Oxford, England: Wiley. (Michigans universitet)
4. ↑ Teorin om intervallalgebra och dess tillämpning på numerisk analys  //  RAAG Memoirs: journal. - 1958. - Nej . 2 . - S. 29-46 .
5. ↑ Intervallanalys  . _ - Englewood Cliff, New Jersey, USA: Prentice Hall , 1966. - ISBN 0-13-476853-1 .
6. ↑ Grundzüge der Intervallrechnung // Jahrbuch Überblicke Mathematik  (tyska) / Laugwitz, Detlef. - Mannheim, Tyskland: Bibliographisches Institut , 1969. - Bd. 2. - S. 51-98.
7. ↑ Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung  (tyska) . - Wiesbaden: Springer Vieweg Verlag , 1989. - ISBN 3-528-08943-1 .
8. ↑ Global optimering med  intervallanalys . — 2:a. - New York, USA: Marcel Dekker , 2004. - ISBN 0-8247-4059-9 .
9. ↑ Gränser för vanliga differentialekvationer av Rudolf Lohner Arkiverad 11 maj 2018. (på tyska)
10. ↑ Historiska anteckningar .
11. ↑ Shokin, 1981 .
12. ↑ T. I. Nazarenko, L. V. Marchenko. Introduktion till intervallmetoder för beräkningsmatematik "Textbook. Irkutsk: Publishing House of Irkutsk University, 1982. - 108 sid.
13. ↑ S. A. Kalmykov, Yu. I. Shokin, Z. Kh. Yuldashev Metoder för intervallanalys. - Novosibirsk: Nauka, 1986, 224 s.
14. ↑ IEEE-standard för intervallaritmetik . Hämtad 7 februari 2022. Arkiverad från originalet 7 februari 2022. (obestämd)
15. ↑ Revol, Nathalie (2015). Den (nära) framtida IEEE 1788-standarden för intervallaritmetik. 8:e liten workshop om intervallmetoder. Slides (PDF) Arkiverade 2 juni 2016 på Wayback Machine
16. ↑ C++-implementering av den preliminära IEEE P1788-standarden för intervallaritmetik . Hämtad 31 juli 2018. Arkiverad från originalet 10 juni 2018. (obestämd)
17. ↑ GNU Octave intervallpaket . Hämtad 31 juli 2018. Arkiverad från originalet 9 november 2016. (obestämd)
18. ↑ IEEE Std 1788.1-2017 - IEEE-standard för intervallaritmetik (förenklad) . IEEE SA . IEEE Standards Association. Hämtad 6 februari 2018. Arkiverad från originalet 7 februari 2022. (obestämd)
19. ↑ Programvara för intervallberäkningar Arkiverad 2 mars 2006 på Wayback Machine insamlad av Vladik Kreinovich , University of Texas i El Paso

Litteratur

• Alefeld G., Herzberger J .. En introduktion till intervallberäkning . M.: Mir, 1987. 356 sid.
• Dobronets B. S. Intervallmatematik . Krasnoyarsk: KSU Publishing House, 2004.
• Shary S. P. Finitdimensionell intervallanalys . - Novosibirsk: XYZ, 2019. - 635 sid.
• Shokin Yu. I. Intervallanalys . - Novosibirsk: Sibirisk filial av Nauka förlag, 1981.

Länkar

• Intervallanalys och dess tillämpningar .
  • Historiska anteckningar .
• Intervallaritmetik på Mathworld  .