Arytmetyka przedziałów - Interval arithmetic

Interwał arytmetyka (znany również jako przedział matematyki , analizy interwałowej lub przedziału obliczeń ) jest techniką matematyczny stosowany do stawiać granice na zaokrąglanie błędy i błędy pomiarowe w matematycznych . Metody numeryczne wykorzystujące arytmetykę przedziałową mogą gwarantować wiarygodne, matematycznie poprawne wyniki. Zamiast przedstawiać wartość jako pojedynczą liczbę, arytmetyka przedziałowa przedstawia każdą wartość jako zakres możliwości . Na przykład, zamiast szacować wzrost osoby na dokładnie 2,0 metry, używając arytmetyki interwałowej, można mieć pewność, że ta osoba ma od 1,97 do 2,03 metra.

Matematycznie, zamiast pracować z niepewnym rzeczywistym , pracujemy z końcami przedziału, który zawiera . W arytmetyce przedziałowej każda zmienna znajduje się w przedziale domkniętym między a . Funkcja , zastosowana do , daje niepewny wynik; tworzy przedział, który zawiera wszystkie możliwe wartości for all . ${\displaystyle x}$${\displaystyle [a,b]}$${\displaystyle x}$${\displaystyle x}$${\displaystyle a}$${\displaystyle b}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle [c,d]}$${\displaystyle f(x)}$${\displaystyle x\in [a,b]}$

Arytmetyka interwałowa nadaje się do różnych celów. Najczęstszym zastosowaniem jest oprogramowanie do śledzenia błędów zaokrągleń w obliczeniach i niepewności w znajomości dokładnych wartości parametrów fizycznych i technicznych. Te ostatnie często wynikają z błędów pomiarowych i tolerancji komponentów lub z ograniczeń dokładności obliczeniowej. Arytmetyka przedziałowa pomaga również znaleźć gwarantowane rozwiązania równań (takich jak równania różniczkowe ) i problemy optymalizacji .

Wstęp

Głównym celem arytmetyki przedziałowej jest prosty sposób obliczenia górnej i dolnej granicy zakresu funkcji w jednej lub wielu zmiennych. Te punkty końcowe niekoniecznie są prawdziwym najwyższym lub dolnym , ponieważ dokładne obliczenie tych wartości może być trudne lub niemożliwe; granice muszą zawierać tylko zakres funkcji jako podzbiór.

Zabieg ten jest zazwyczaj ograniczony do rzeczywistych interwałów, więc ilości formy

${\ Displaystyle [a, b] = \ {x \ w \ mathbb {R} \, | \ a \ równoważnik x \ równoważnik b \}}$

gdzie i są dozwolone. Przy jednym z , nieskończony, przedział byłby przedziałem nieograniczonym; z obiema nieskończonością, przedział byłby rozszerzoną linią liczb rzeczywistych. Ponieważ liczbę rzeczywistą można interpretować jako przedziały interwałowe, a liczby rzeczywiste można dowolnie łączyć. ${\displaystyle a={-\infty}}$${\displaystyle b={\infty}}$${\displaystyle a}$${\displaystyle b}$${\ Displaystyle r}$${\displaystyle [r,r],}$

Podobnie jak w przypadku tradycyjnych obliczeń na liczbach rzeczywistych, należy najpierw zdefiniować proste operacje arytmetyczne i funkcje na przedziałach elementarnych. Z tych podstawowych elementów można obliczyć bardziej skomplikowane funkcje.

Przykład

Jako przykład rozważ obliczenie wskaźnika masy ciała (BMI) i ocenę, czy dana osoba ma nadwagę. BMI oblicza się jako masę ciała danej osoby w kilogramach podzieloną przez kwadrat jej wzrostu w metrach. Waga łazienkowa może mieć rozdzielczość jednego kilograma. Nie można odróżnić wartości pośrednich — na przykład 79,6 kg i 80,3 kg są nie do odróżnienia — ale rzeczywista waga jest zaokrąglana do najbliższej liczby całkowitej. Jest mało prawdopodobne, że gdy waga wskazuje 80 kg, osoba waży dokładnie 80,0 kg. W normalnym zaokrągleniu do najbliższej wartości waga pokazująca 80 kg oznacza wagę między 79,5 kg a 80,5 kg. Odpowiada to interwałowi . ${\ Displaystyle [79,580,5]}$

Dla mężczyzny o wadze 80 kg i wzroście 1,80 m BMI wynosi około 24,7. Waga 79,5 kg i taka sama wysokość daje ok. 1 kg. 24.537, podczas gdy waga 80,5 kg daje ok. 24.846. Ponieważ funkcja wzrasta monotonicznie, wnioskujemy, że rzeczywisty BMI mieści się w zakresie . Ponieważ cały zakres wynosi mniej niż 25, co stanowi granicę między normalną a nadmierną wagą, wnioskujemy, że mężczyzna ma normalną wagę. ${\ Displaystyle [24.537,24.846]}$

Błąd w tym przypadku nie wpływa na wniosek (normalna waga), ale nie zawsze tak jest. Jeśli mężczyzna był nieco cięższy, zakres BMI może obejmować wartość odcięcia 25. W takim przypadku precyzja skali była niewystarczająca do wyciągnięcia ostatecznego wniosku.

Należy również zauważyć, że zakres przykładów BMI może być przedstawiony jako , ponieważ ten przedział jest nadzbiorem obliczonego przedziału. Przedział nie mógł jednak zostać podany jako , ponieważ obecnie przedział nie zawiera możliwych wartości BMI. ${\ Displaystyle [24,5, 24,9]}$${\ Displaystyle [24,6, 24,8]}$

Arytmetyka interwałowa wyraźnie określa zakres możliwych wyników. Wyniki nie są już podawane jako liczby, ale jako przedziały reprezentujące nieprecyzyjne wartości. Rozmiary przedziałów są podobne do słupków błędów w wyrażaniu zakresu niepewności.

Wiele interwałów

Wzrost i masa ciała wpływają na wartość BMI. Traktowaliśmy już wagę jako pomiar niepewny, ale wzrost również jest obarczony niepewnością. Pomiary wysokości w metrach są zwykle zaokrąglane do najbliższego centymetra: zarejestrowany pomiar 1,79 metra w rzeczywistości oznacza wzrost w przedziale . Teraz należy wziąć pod uwagę wszystkie cztery kombinacje możliwych wartości wzrostu/wagi. Stosując metody interwałowe opisane poniżej, BMI leży w przedziale ${\ Displaystyle [1.785,1.795]}$

${\ Displaystyle {\ Frac {[79,5,80,5]}{[1,785,1,795] ^ {2}}} \ podseteq [24,673,25,266].}$

W takim przypadku mężczyzna może mieć normalną wagę lub mieć nadwagę; pomiary masy ciała i wzrostu nie były wystarczająco precyzyjne, aby wyciągnąć ostateczne wnioski. Pokazuje to zdolność arytmetyki interwałowej do prawidłowego śledzenia i propagowania błędu.

Operatory interwałowe

Operacja binarna na dwóch interwałach, taka jak dodawanie lub mnożenie, jest zdefiniowana przez ${\displaystyle \gwiazda}$

${\ Displaystyle [x_ {1}, x_ {2}] {\, \ gwiazda \,} [y_ {1}, y_ {2}] = \ {x \ gwiazda y \, | \, x \ w [x_ {1},x_{2}]\,\land \,y\w [y_{1},y_{2}]\}.}$

Innymi słowy, jest to zbiór wszystkich możliwych wartości , gdzie i są w odpowiadających im przedziałach. Jeśli jest monotoniczny w każdym operandzie na interwałach, co ma miejsce w przypadku czterech podstawowych operacji arytmetycznych (z wyjątkiem dzielenia, gdy mianownik zawiera ), wartości ekstremalne występują w punktach końcowych interwałów operandów. Wypisanie wszystkich kombinacji, jednym ze sposobów na stwierdzenie tego jest: ${\displaystyle x\gwiazda y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \gwiazda}$

${\ Displaystyle [x_ {1}, x_ {2}] \ gwiazda [y_ {1}, y_ {2}] = \ lewo [\ min \ {x_ {1} \ gwiazda y_ {1}, x_ {1} \star y_{2},x_{2}\star y_{1},x_{2}\star y_{2}\},\max\{x_{1}\star y_{1},x_{1} \gwiazda y_{2},x_{2}\gwiazda y_{1},x_{2}\gwiazda y_{2}\}\prawo],}$

pod warunkiem, że jest to określone dla wszystkich i . ${\displaystyle x\gwiazda y}$${\displaystyle x\w [x_{1},x_{2}]}$${\ Displaystyle y \ w [y_ {1}, y_ {2}]}$

W przypadku zastosowań praktycznych można to jeszcze bardziej uprościć:

• Dodatek :${\displaystyle [x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]}$
• Odejmowanie :${\displaystyle [x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]}$
• Mnożenie :${\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[\min\{x_{1}y_{1},x_{1}y_{2} ,x_{2}y_{1},x_{2}y_{2}\},\max\{x_{1}y_{1},x_{1}y_{2},x_{2}y_{1 },x_{2}y_{2}\}]}$
• Oddział :

${\displaystyle {\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},}$

gdzie

${\ Displaystyle {\ zacząć {wyrównany} {\ Frac {1} {[y_ {1}, y_ {2}]}} i = \ lewo [{\ tfrac {1} {y_ {2}}}, {\ tfrac {1}{y_{1}}}\right]&&\mathrm {if} \;0\notin [y_{1},y_{2}]\\{\frac {1}{[y_{1} ,0]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\\{\frac {1}{[0,y_{2}]}}& =\left[{\tfrac {1}{y_{2}}},\infty \right]\\{\frac {1}{[y_{1},y_{2}]}}&=\left[ -\infty ,{\tfrac {1}{y_{1}}}\right]\cup \left[{\tfrac {1}{y_{2}}},\infty \right]\subseteq [-\infty ,\infty ]&&\mathrm {if} \;0\in (y_{1},y_{2})\end{wyrównany}}}$

Ostatni przypadek traci przydatne informacje o wykluczeniu . Dlatego często pracuje się z oddzielnymi interwałami i jako oddzielne interwały. Ogólnie rzecz biorąc, podczas pracy z funkcjami nieciągłymi czasami przydatne jest wykonanie obliczeń z tzw. multiprzedziałami postaci Odpowiednia arytmetyka wieloprzedziałowa zachowuje zestaw (zwykle rozłącznych) przedziałów, a także zapewnia nakładanie się przedziałów w celu zjednoczenia . ${\displaystyle (1/rok_{1},1/rok_{2})}$${\ Displaystyle \ lewo [- \ infty {\ tfrac {1} {y_ {1}}} \ prawo]}$${\ Displaystyle \ lewo [{\ tfrac {1} {y_ {2}}}, \ infty \ prawo]}$${\textstyle \bigcup _{i}\left[a_{i},b_{i}\right].}$

Mnożenie przedziałów często wymaga tylko dwóch mnożeń. Jeśli , są nieujemne, ${\displaystyle x_{1}}$${\displaystyle Y_{1}}$

${\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[x_{1}\cdot y_{1},x_{2}\cdot y_{2} ],\qquad {\text{ if }}x_{1},y_{1}\geq 0.}$

Mnożenie można interpretować jako obszar prostokąta o różnych krawędziach. Przedział wyników obejmuje wszystkie możliwe obszary, od najmniejszego do największego.

Przy pomocy tych definicji, jest to już możliwe, aby obliczyć zakres prostych funkcji, takich jak na przykład, jeśli , i : ${\ Displaystyle f (a, b, x) = a \ cdot x + b.}$${\ Displaystyle a = [1,2]}$${\displaystyle b=[5,7]}$${\displaystyle x=[2,3]}$

${\ Displaystyle f (a, b, x) = ([1,2] \ cdot [2,3]) + [5,7] = [1 \ cdot 2,2 \ cdot 3] + [5,7] =[7,13]}$.

Notacja

Aby zmniejszyć notację interwałów we wzorach, można zastosować nawiasy.

${\displaystyle [x]\equiv [x_{1},x_{2}]}$może służyć do reprezentowania interwału. Zauważ, że w tak zwartej notacji nie należy mylić interwału jednopunktowego z interwałem ogólnym. Dla zbioru wszystkich interwałów możemy użyć ${\displaystyle [x]}$${\displaystyle [x_{1},x_{1}]}$

${\ Displaystyle [\ mathbb {R} ]: = \ lewo \ {\ [x_ {1}, x_ {2}] \ | \ x_ {1} \ leq x_ {2} {\ tekst { i} }x_{1},x_{2}\in \mathbb {R} \cup \{-\infty ,\infty \}\right\}}$

jako skrót. Dla wektora interwałów możemy użyć pogrubionej czcionki: . ${\ Displaystyle \ lewo ([x] _ {1}, \ ldots, [x] _ {n} \ po prawej) \ w [\ mathbb {R}] ^ {n}}$${\displaystyle [\mathbf {x}]}$

Podstawowe funkcje

Można również zdefiniować funkcje interwałowe poza czterema podstawowymi operatorami.

W przypadku funkcji monotonicznych w jednej zmiennej zakres wartości jest łatwy do obliczenia. Jeśli w przedziale jest monotonicznie wzrastający (odpowiednio malejący), to dla wszystkich takich, że (odpowiednio ). ${\ Displaystyle f: \ mathbb {R} \ do \ mathbb {R}}$${\displaystyle [x_{1},x_{2}],}$${\displaystyle y_{1},y_{2}\in [x_{1},x_{2}]}$${\displaystyle y_{1}\leq y_{2},}$ ${\displaystyle f(y_{1})<f(y_{2})}$${\displaystyle f(y_{2})<f(y_{1})}$

Zakres odpowiadający przedziałowi można zatem obliczyć, stosując funkcję do jej punktów końcowych: ${\displaystyle [y_{1},y_{2}]\subseteq [x_{1},x_{2}]}$

${\ Displaystyle f ([y_ {1}, y_ {2}]) = \ lewo [\ min \ lewo \ {f (y_ {1}), f (y_ {2}) \ prawo \} \ max \ lewo\{f(y_{1}),f(y_{2})\prawo\}\prawo].}$

Na tej podstawie można łatwo zdefiniować następujące podstawowe cechy funkcji interwałowych:

• Funkcja wykładnicza : for${\ Displaystyle a ^ {[x_ {1}, x_ {2}]} = [a ^ {x_ {1}}, a ^ {x_ {2}}]}$${\displaystyle a>1,}$
• Logarytm : dla dodatnich przedziałów i${\ Displaystyle \ log _ {a} [x_ {1}, x_ {2}] = [\ log _ {a} {x_ {1}}, \ log _ {a} {x_ {2}}]}$${\displaystyle [x_{1},x_{2}]}$${\displaystyle a>1,}$
• Nieparzyste potęgi: , na nieparzyste${\ Displaystyle [x_ {1}, x_ {2}] ^ {n} = [x_ {1} ^ {n}, x_ {2} ^ {n}]}$${\ Displaystyle n \ w \ mathbb {N}.}$

W przypadku potęg parzystych ważny jest zakres rozważanych wartości i należy się nim zająć przed wykonaniem jakiegokolwiek mnożenia. Na przykład, for powinno wytworzyć przedział, gdy Ale jeśli zostanie wzięty przez powtórzenie mnożenia przedziału postaci, to wynik jest szerszy niż to konieczne. ${\ Displaystyle x ^ {n}}$${\displaystyle x\in [-1,1]}$${\displaystyle [0,1]}$${\displaystyle n=2,4,6,\ldots.}$${\ Displaystyle [-1,1] ^ {n}}$${\ Displaystyle [-1,1] \ cdot [-1,1] \ cdot \ cdots \ cdot [-1, 1]}$${\displaystyle [-1,1],}$

Bardziej ogólnie można powiedzieć, że dla funkcji odcinkowo monotonicznych, wystarczy wziąć pod uwagę punkty końcowe , z przerwą, wraz z tak zwanych punktów krytycznych w przedziale, będąc te punkty gdzie monotoniczności funkcji zmienia kierunek. Dla funkcji sinus i cosinus punkty krytyczne są odpowiednio w lub dla . W związku z tym należy wziąć pod uwagę tylko do pięciu punktów w przedziale, ponieważ przedział wynikowy jest wtedy, gdy przedział zawiera co najmniej dwa ekstrema. W przypadku sinusa i cosinusa tylko punkty końcowe wymagają pełnej oceny, ponieważ punkty krytyczne prowadzą do łatwo obliczonych wartości, a mianowicie -1, 0 i 1. ${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\ Displaystyle \ po lewej ({\ tfrac {1} {2}} + n \ po prawej) \ pi}$${\displaystyle n\pi}$${\ Displaystyle n \ w \ mathbb {Z}}$${\displaystyle [-1,1]}$

Rozszerzenia interwałowe funkcji ogólnych

Ogólnie rzecz biorąc, znalezienie tak prostego opisu interwału wyjściowego dla wielu funkcji może nie być łatwe. Ale nadal może być możliwe rozszerzenie funkcji na arytmetykę przedziałową. Jeśli jest to funkcja z prawdziwego wektora do liczby rzeczywistej, wówczas   nazywa się przerwa przedłużenie o jeśli ${\ Displaystyle f: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}$${\ Displaystyle [f]: [\ mathbb {R}] ^ {n} \ rightarrow [\ mathbb {R}]}$${\displaystyle f}$

${\ Displaystyle [f] ([\ mathbf {x} ]) \ supseteq \ {f (\ mathbf {y}) | \ mathbf {y} \ w [\ mathbf {x}] \}}$.

Ta definicja przedłużenia przedziału nie daje dokładnego wyniku. Na przykład oba i są dopuszczalnymi rozszerzeniami funkcji wykładniczej. Pożądane są ściślejsze rozszerzenia, chociaż należy wziąć pod uwagę względne koszty obliczeń i niedokładności; w takim przypadku należy wybrać, ponieważ daje możliwie najściślejszy wynik. ${\ Displaystyle [f] ([x_ {1}, x_ {2}]) = [e ^ {x_ {1}}, e ^ {x_ {2}}]}$${\ Displaystyle [g] ([x_ {1}, x_ {2}]) = [{-\ infty}, {\ infty}]}$${\displaystyle [f]}$

Biorąc pod uwagę rzeczywiste wyrażenie, jego naturalne rozszerzenie interwału uzyskuje się za pomocą rozszerzeń interwału każdego z jego podwyrażeń, funkcji i operatorów.

Przedział rozbudowa Taylor (stopnia ) to czasy funkcja różniczkowalna zdefiniowane przez ${\displaystyle k}$${\displaystyle k+1}$${\displaystyle f}$

${\ Displaystyle [f] ([\ mathbf {x} ]): = f (\ mathbf {y} ) + \ suma _ {i = 1} ^ {k} {\ Frac {1} {i!}} \ mathrm {D} ^{i}f(\mathbf {y} )\cdot ([\mathbf {x} ]-\mathbf {y} )^{i}+[r]([\mathbf {x} ], [\mathbf {x} ],\mathbf {y} )}$,

dla niektórych , gdzie jest różniczką rzędu th w punkcie i jest rozszerzeniem przedziału reszty Taylora${\ Displaystyle \ mathbf {y} \ w [\ mathbf {x}]}$${\ Displaystyle \ operatorname {D} ^ {i} f (\ mathbf {y})}$${\displaystyle i}$${\displaystyle f}$${\displaystyle \mathbf {y}}$${\displaystyle [r]}$

${\ Displaystyle r (\ mathbf {x} , \ xi , \ mathbf {y} ) = {\ Frac {1} {(k + 1)!}} \ operatorname {D} ^ {k + 1} f (\ xi )\cdot (\mathbf {x} -\mathbf {y} )^{k+1}.}$

Wektorem leży między i ze , jest chroniona . Zwykle wybiera się punkt środkowy interwału i wykorzystuje naturalne rozszerzenie interwału do oceny reszty. ${\displaystyle \xi}$${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {y}}$${\ Displaystyle \ mathbf {x} \ mathbf {y} \ w [\ mathbf {x}]}$${\displaystyle \xi}$${\displaystyle [\mathbf {x}]}$${\displaystyle \mathbf {y}}$

Specjalny przypadek przedziałowego rozszerzenia stopnia Taylora jest również określany jako postać wartości średniej . ${\ Displaystyle k = 0}$

Arytmetyka przedziałów zespolonych

Przedział można również zdefiniować jako zbiór punktów w określonej odległości od środka, a definicję tę można rozszerzyć z liczb rzeczywistych na liczby zespolone . Podobnie jak w przypadku obliczeń na liczbach rzeczywistych, obliczenia na liczbach zespolonych obejmują niepewne dane. Biorąc więc pod uwagę fakt, że liczba przedziałowa jest przedziałem domkniętym, a liczba zespolona jest parą uporządkowaną liczb rzeczywistych , nie ma powodu, aby ograniczać stosowanie arytmetyki przedziałowej do miary niepewności w obliczeniach na liczbach rzeczywistych. Arytmetyka przedziałowa może być zatem rozszerzona o zespolone liczby przedziałowe w celu określenia obszarów niepewności w obliczeniach na liczbach zespolonych.

Podstawowe operacje algebraiczne na liczbach rzeczywistych przedziałów (rzeczywistych przedziałach domkniętych) można rozszerzyć na liczby zespolone. Nie jest zatem zaskakujące, że zespolona arytmetyka przedziałowa jest podobna, ale nie taka sama, jak zwykła zespolona arytmetyka. Można wykazać, że podobnie jak w przypadku arytmetyki przedziałów rzeczywistych, nie ma rozdzielności między dodawaniem i mnożeniem liczb przedziałów zespolonych, z wyjątkiem pewnych szczególnych przypadków, a elementy odwrotne nie zawsze istnieją dla liczb przedziałów zespolonych. Dwie inne użyteczne właściwości zwykłej zespolonej arytmetyki nie mają zastosowania w przypadku zespolonej arytmetyki przedziałowej: addytywne i multiplikatywne właściwości zwykłych zespolonych koniugatów nie mają zastosowania do zespolonych sprzężonych przedziałów.

Arytmetyka przedziałowa może być rozszerzona w analogiczny sposób na inne wielowymiarowe systemy liczbowe, takie jak kwaterniony i oktonony , ale kosztem, który musimy poświęcić innym użytecznym właściwościom zwykłej arytmetyki.

Metody interwałowe

Metod klasycznej analizy numerycznej nie można przenieść jeden do jednego na algorytmy o wartościach przedziałowych, ponieważ zależności między wartościami liczbowymi zwykle nie są brane pod uwagę.

Arytmetyka z zaokrąglonymi przedziałami

Aby efektywnie pracować w rzeczywistej implementacji, interwały muszą być zgodne z obliczeniami zmiennoprzecinkowymi. Wcześniejsze operacje opierały się na arytmetyce dokładnej, ale generalnie metody szybkiego rozwiązywania numerycznego mogą nie być dostępne. Zakres wartości funkcji dla i to na przykład . Tam, gdzie to samo obliczenie jest wykonywane z jednocyfrową precyzją, wynik byłby zwykle . Ale , więc takie podejście byłoby sprzeczne z podstawowymi zasadami arytmetyki przedziałowej, gdyż część dziedziny byłaby stracona. Zamiast tego stosuje się rozwiązanie zaokrąglone na zewnątrz . ${\displaystyle f(x,y)=x+y}$${\displaystyle x\w [0.1,0.8]}$${\ Displaystyle y \ w [0.06,0.08]}$${\ Displaystyle [0.16,0.88]}$${\ Displaystyle [0.2,0.9]}$${\ Displaystyle [0.2,0.9] \ nie \ supseteq [0.16,0.88]}$${\ Displaystyle f ([0,1,0,8],[0,06,0,08])}$${\ Displaystyle [0.1,0.9]}$

Standard IEEE 754 dla binarnej arytmetyki zmiennoprzecinkowej określa również procedury implementacji zaokrąglania. System zgodny z IEEE 754 umożliwia programistom zaokrąglanie do najbliższej liczby zmiennoprzecinkowej; alternatywy to zaokrąglanie w kierunku 0 (obcinanie), zaokrąglanie w kierunku dodatniej nieskończoności (tj. w górę) lub zaokrąglanie w kierunku ujemnej nieskończoności (tj. w dół).

Wymagane zewnętrzne zaokrąglanie dla arytmetyki przedziałowej można zatem osiągnąć poprzez zmianę ustawień zaokrąglania procesora w obliczeniach górnej granicy (w górę) i dolnej granicy (w dół). Alternatywnie można dodać odpowiedni mały odstęp . ${\ Displaystyle [\ varepsilon _ {1}, \ varepsilon _ {2}]}$

Problem zależności

Tak zwany problem zależności jest główną przeszkodą w stosowaniu arytmetyki przedziałowej. Chociaż metody przedziałowe mogą bardzo dokładnie określić zakres elementarnych operacji arytmetycznych i funkcji, nie zawsze jest to prawdą w przypadku bardziej skomplikowanych funkcji. Jeśli przedział występuje kilka razy w obliczeniach przy użyciu parametrów, a każde wystąpienie jest brane niezależnie, może to prowadzić do niepożądanego rozszerzenia wynikowych przedziałów.

Jako ilustrację weź funkcję zdefiniowaną przez Wartości tej funkcji w przedziale są Jako naturalne rozszerzenie przedziału oblicza się jako: ${\displaystyle f}$${\ Displaystyle f (x) = x ^ {2} + x.}$${\displaystyle [-1,1]}$${\ Displaystyle \ lewo [-{\ tfrac {1} {4}}, 2 \ prawo].}$

${\displaystyle [-1,1]^{2}+[-1,1]=[0,1]+[-1,1]=[-1,2],}$

który jest nieco większy; my zamiast obliczył kresy dolny i górny funkcji ponad Jest lepszy wyraz w którym zmienna pojawia się tylko raz, a mianowicie przez przepisywanie jako dodatek i kwadratury w kwadratowej ${\ Displaystyle h (x, y) = x ^ {2} + r}$${\displaystyle x,y\in [-1,1].}$${\displaystyle f}$${\displaystyle x}$${\ Displaystyle f (x) = x ^ {2} + x}$

${\ Displaystyle f (x) = \ lewo (x + {\ Frac {1} {2}} \ prawej) ^ {2} - {\ Frac {1} {4}}.}$

Tak więc odpowiednie obliczenie przedziału to

${\ Displaystyle \ lewo ([-1,1] + {\ Frac {1} {2}} \ prawej) ^ {2} - {\ Frac {1} {4}} = \ lewo [- {\ Frac { 1}{2}},{\frac {3}{2}}\right]^{2}-{\frac {1}{4}}=\left[0,{\frac {9}{4} }\right]-{\frac {1}{4}}=\left[-{\frac {1}{4}},2\right]}$

i podaje prawidłowe wartości.

Ogólnie można wykazać, że można osiągnąć dokładny zakres wartości, jeśli każda zmienna pojawia się tylko raz i jest ciągła wewnątrz ramki. Jednak nie każdą funkcję można przepisać w ten sposób. ${\displaystyle f}$

Zależność problemu powodującego przeszacowanie zakresu wartości może sięgać nawet dużego zakresu, uniemożliwiając bardziej sensowne wnioski.

Dodatkowy wzrost zasięgu wynika z rozwiązania obszarów, które nie przybierają postaci wektora przedziałowego. Zbiór rozwiązań układu liniowego

${\ Displaystyle {\ zacząć {przypadki} x = p \ \ y = p \ koniec {przypadki}} \ qquad p \ w [-1,1]}$

jest dokładnie linią między punktami, a Użycie metod interwałowych daje w wyniku kwadrat jednostkowy. Jest to znane jako efekt zawijania . ${\ Displaystyle (-1,-1)}$${\ Displaystyle (1,1).}$${\displaystyle [-1,1]\razy [-1,1].}$

Liniowe systemy interwałowe

Liniowy system interwałowy składa się z macierzowego rozszerzenia interwału i wektora interwałowego . Chcemy najmniejszy prostopadłościan dla wszystkich wektorów , które znajduje się para z i zaspokajania ${\ Displaystyle [\ mathbf {A}] \ w [\ mathbb {R}] ^ {n \ razy m}}$${\ Displaystyle [\ mathbf {b}] \ w [\ mathbb {R}] ^ {n}}$${\ Displaystyle [\ mathbf {x}] \ w [\ mathbb {R}] ^ {m}}$${\ Displaystyle \ mathbf {x} \ w \ mathbb {R} ^ {m}}$${\ Displaystyle (\ mathbf {A} , \ mathbf {b} )}$${\ Displaystyle \ mathbf {A} \ w [\ mathbf {A}]}$${\ Displaystyle \ mathbf {b} \ w [\ mathbf {b}]}$

${\ Displaystyle \ mathbf {A} \ cdot \ mathbf {x} = \ mathbf {b}}$.

Dla układów kwadratowych – innymi słowy dla – może istnieć taki wektor przedziałowy , który obejmuje wszystkie możliwe rozwiązania, znalezione po prostu metodą przedziałową Gaussa. Zastępuje to operacje numeryczne, ponieważ metoda algebry liniowej znana jako eliminacja Gaussa staje się jego wersją przedziałową. Jednak ponieważ ta metoda używa jednostek interwałowych i wielokrotnie w obliczeniach, może dawać słabe wyniki w przypadku niektórych problemów. Stąd użycie wyniku Gaussa o wartościach przedziałowych dostarcza tylko pierwszych przybliżonych szacunków, ponieważ chociaż zawiera cały zbiór rozwiązań, ma również duży obszar poza nim. ${\displaystyle n=m}$${\displaystyle [\mathbf {x}]}$${\displaystyle [\mathbf {A}]}$${\displaystyle [\mathbf {b}]}$

Zgrubne rozwiązanie można często poprawić, stosując interwałową wersję metody Gaussa-Seidela . Powodem tego jest to, że -ty wiersz przedziałowego rozszerzenia równania liniowego ${\displaystyle [\mathbf {x}]}$${\displaystyle i}$

${\ Displaystyle {\ zacząć {pmatrix} {[a_ {11}]} i \ cdots i {[a_ {1n}]} \ \ \ vdots i \ ddots i \ vdots \ \ {[a_ {n1}]} i \cdots &{[a_{nn}]}\end{pmatrix}}\cdot {\begin{pmatrix}{x_{1}}\\\vdots \\{x_{n}}\end{pmatrix}}= {\begin{pmatrix}{[b_{1}]}\\\vdots \\{[b_{n}]}\end{pmatrix}}}$

może być określona przez zmienną, jeśli dozwolony jest podział . Jest zatem jednocześnie ${\displaystyle x_{i}}$${\ Displaystyle 1/[a_ {ii}]}$

${\ Displaystyle x_ {j} \ w [x_ {j}]}$i .${\ Displaystyle x_ {j} \ w {\ Frac {[b_ {i}] - \ suma \ limity _ {k \ nie = j} [a_ {ik}] \ cdot [x_ {k}]} {[a_ {ii}]}}}$

Więc możemy teraz zastąpić przez ${\ Displaystyle [x_ {j}]}$

${\ Displaystyle [x_ {j}] \ czapka {\ Frac {[b_ {i}] - \ suma \ limity _ {k \ nie = j} [a_ {ik}] \ cdot [x_ {k}]} { [a_{ii}]}}}$,

a więc wektor przez każdy element. Ponieważ procedura jest bardziej efektywna dla macierzy przekątnej dominującej , zamiast układu można często spróbować pomnożyć ją przez odpowiednią macierz wymierną z otrzymanym równaniem macierzowym ${\displaystyle [\mathbf {x}]}$${\ Displaystyle [\ mathbf {A}] \ cdot \ mathbf {x} = [\ mathbf {b}] {\ mbox {}}}$${\ Displaystyle \ mathbf {M} }$

${\ Displaystyle (\ mathbf {M} \ cdot [\ mathbf {A}]) \ cdot \ mathbf {x} = \ mathbf {M} \ cdot [\ mathbf {b}]}$

do rozwiązania. Jeśli wybierze się na przykład macierz centralną , to jest to zewnętrzne rozszerzenie macierzy jednostkowej. ${\ Displaystyle \ mathbf {M} = \ mathbf {A} ^ {-1}}$${\ Displaystyle \ mathbf {A} \ w [\ mathbf {A}]}$${\ Displaystyle \ mathbf {M} \ cdot [\ mathbf {A}]}$

Metody te działają dobrze tylko wtedy, gdy szerokości występujących przedziałów są wystarczająco małe. W przypadku szerszych przedziałów przydatne może być użycie układu przedziałowo-liniowego na skończonych (choć dużych) układach liniowych równoważnych liczbami rzeczywistymi. Jeśli wszystkie macierze są odwracalne, wystarczy wziąć pod uwagę wszystkie możliwe kombinacje (górny i dolny) punktów końcowych występujących w przedziałach. Powstałe problemy można rozwiązać za pomocą konwencjonalnych metod numerycznych. Arytmetyka przedziałowa jest nadal używana do określania błędów zaokrąglania. ${\ Displaystyle \ mathbf {A} \ w [\ mathbf {A}]}$

Jest to odpowiednie tylko dla systemów o mniejszych wymiarach, ponieważ przy całkowicie zajętej macierzy, macierze rzeczywiste muszą być odwrócone, z wektorami po prawej stronie. To podejście zostało opracowane przez Jiri Rohn i nadal jest rozwijane. ${\displaystyle n\razy n}$${\ Displaystyle 2 ^ {n ^ {2}}}$${\ Displaystyle 2 ^ {n}}$

Metoda interwałowa Newtona

Wariant przedziałowy metody Newtona do znajdowania zer w wektorze przedziałowym można wyprowadzić z rozszerzenia wartości średniej. Dla nieznanego wektora zastosowanego do , daje ${\displaystyle [\mathbf {x}]}$${\ Displaystyle \ mathbf {z} \ w [\ mathbf {x}]}$${\ Displaystyle \ mathbf {y} \ w [\ mathbf {x}]}$

${\ Displaystyle f (\ mathbf {z} ) \ w f (\ mathbf {y} ) + [J_ {f}] (\ mathbf {[x]} ) \ cdot (\ mathbf {z} - \ mathbf {y } )}$.

Dla zera , czyli , a zatem musi spełniać ${\displaystyle \mathbf {z}}$${\ Displaystyle f (z) = 0}$

${\ Displaystyle f (\ mathbf {y} ) + [J_ {f}] (\ mathbf {[x]}) \ cdot (\ mathbf {z} - \ mathbf {y}) = 0}$.

Jest to odpowiednik . Zewnętrzne oszacowanie można określić za pomocą metod liniowych. ${\ Displaystyle \ mathbf {z} \ w \ mathbf {y} - [J_ {f}] (\ mathbf {[x]}) ^ {-1} \ cdot f (\ mathbf {y})}$${\ Displaystyle [J_ {f}] (\ mathbf {[x]} ) ^ {-1} \ cdot f (\ mathbf {y} ))}$

W każdym kroku interwałowej metody Newtona przybliżona wartość początkowa jest zastępowana przez, dzięki czemu wynik można iteracyjnie poprawiać. W przeciwieństwie do tradycyjnych metod, metoda interwałowa zbliża się do wyniku zawierając zera. Gwarantuje to, że wynik wygeneruje wszystkie zera w początkowym zakresie. Odwrotnie, dowodzi, że żadne zera z nie znajdowały się w początkowym zakresie, jeśli krok Newtona daje pusty zbiór. ${\ Displaystyle [\ mathbf {x}] \ w [\ mathbb {R}] ^ {n}}$${\ Displaystyle [\ mathbf {x}] \ czapka \ lewo (\ mathbf {y} - [J_ {f}] (\ mathbf {[x]}) ^ {-1} \ cdot f (\ mathbf {y} )\Prawidłowy)}$${\displaystyle f}$${\displaystyle [\mathbf {x}]}$

Metoda zbiega się na wszystkich zerach w regionie początkowym. Dzielenie przez zero może prowadzić do oddzielenia odrębnych zer, chociaż oddzielenie może nie być kompletne; można go uzupełnić metodą bisekcji .

Jako przykład rozważmy funkcję , zakres początkowy i punkt . Następnie mamy i pierwszy krok Newtona daje ${\ Displaystyle f (x) = x ^ {2}-2}$${\displaystyle [x]=[-2,2]}$${\ Displaystyle y = 0}$${\ Displaystyle J_ {f} (x) = 2 \ x}$

${\ Displaystyle [-2, 2] \ czapka \ lewo (0-{\ Frac {1} {2 \ cdot [-2, 2]}} (0-2) \ po prawej) = [-2, 2] \ czapka {\Big (}[{-\infty },{-0.5}]\cup [{0.5},{\infty }]{\Big )}=[{-2},{-0.5}]\cup [ {0.5},{2}]}$.

Więcej stopni Newtona jest używanych oddzielnie na i . Zbiegają się one do dowolnie małych przedziałów wokół i . ${\ Displaystyle x \ w [{-2}, {-0,5}]}$${\ Displaystyle [{0,5}, {2}]}$${\displaystyle -{\sqrt {2}}}$${\displaystyle +{\sqrt {2}}}$

Metoda Interval Newton może być również używana z grubymi funkcjami, takimi jak , które w każdym przypadku miałyby wyniki w przedziale. Wynik daje następnie przedziały zawierające . ${\ Displaystyle g (x) = x ^ {2}-[2,3]}$${\ Displaystyle \ lewo [-{\ sqrt {3}}, - {\ sqrt {2}} \ prawo] \ filiżanka \ lewo [{\ sqrt {2}}, {\ sqrt {3}} \ po prawej]}$

Bisekcje i okładki

Różne metody przedziałowe dają konserwatywne wyniki, ponieważ zależności między rozmiarami różnych rozszerzeń przedziałów nie są brane pod uwagę. Jednak problem zależności staje się mniej istotny dla węższych przedziałów.

Pokrycie wektora przedziałowego przez mniejsze prostokąty, tak aby ${\displaystyle [\mathbf {x}]}$${\ Displaystyle [\ mathbf {x} _ {1}], \ ldots, [\ mathbf {x} _ {k}],}$

${\ Displaystyle [\ mathbf {x}] = \ bigcup _ {i = 1} ^ {k} [\ mathbf {x} _ {i}]}$

obowiązuje wtedy dla zakresu wartości

${\ Displaystyle f ([\ mathbf {x}]) = \ bigcup _ {i = 1} ^ {k} f ([\ mathbf {x} _ {i}]).}$

Tak więc dla rozszerzeń interwałów opisanych powyżej obowiązuje następująca zasada:

${\ Displaystyle [f] ([\ mathbf {x}]) \ supseteq \ bigcup _ {i = 1} ^ {k} [f] ([\ mathbf {x} _ {i}]).}$

Ponieważ często jest to prawdziwy nadzbiór prawej strony, zwykle prowadzi to do lepszego oszacowania. ${\displaystyle [f]([\mathbf {x}])}$

Takie pokrycie można wygenerować metodą bisekcji, np. grube elementy wektora interwałowego , dzieląc w środku na dwa interwały, a jeśli wynik nadal nie jest odpowiedni, możliwy jest dalszy stopniowy podział. Pokrycie przedziałów wynika z podziałów elementów wektorowych, co znacznie zwiększa koszty obliczeń. ${\ Displaystyle [x_ {i1}, x_ {i2}]}$${\ Displaystyle [\ mathbf {x}] = ([x_ {11}, x_ {12}], \ ldots, [x_ {n1}, x_ {n2}])}$${\ Displaystyle \ lewo [x_ {i1}} {\ tfrac {1} {2}} (x_ {i1} + x_ {i2}) \ prawo]}$${\ Displaystyle \ lewo [{\ tfrac {1} {2}} (x_ {i1} + x_ {i2}), x_ {i2} \ prawej].}$${\ Displaystyle 2 ^ {r}}$${\ Displaystyle r}$

W przypadku bardzo szerokich interwałów pomocne może być podzielenie wszystkich interwałów na kilka podinterwałów o stałej (i mniejszej) szerokości, co jest metodą znaną jako mielenie . W ten sposób unika się obliczeń dla pośrednich kroków bisekcji. Obie metody są odpowiednie tylko dla problemów o małym wymiarze.

Podanie

Arytmetyka interwałowa może być stosowana w różnych obszarach (takich jak odwracanie zbiorów , planowanie ruchu , szacowanie zbiorów lub analiza stabilności) do przetwarzania oszacowań bez dokładnej wartości liczbowej.

Analiza błędów zaokrągleń

Arytmetyka przedziałowa jest używana z analizą błędów, aby kontrolować błędy zaokrąglania wynikające z każdego obliczenia. Zaletą arytmetyki przedziałowej jest to, że po każdej operacji występuje przedział, który niezawodnie zawiera prawdziwy wynik. Odległość między granicami przedziału daje bezpośrednio bieżące obliczenia błędów zaokrągleń:

Błąd = dla podanego przedziału .${\ Displaystyle \ operatorname {abs} (ab)}$${\displaystyle [a,b]}$

Analiza interwałowa dodaje, zamiast zastępować tradycyjne metody redukcji błędów, takie jak obracanie .

Analiza tolerancji

Podczas symulacji procesów technicznych i fizycznych często powstają parametry, dla których nie można przyporządkować dokładnych liczb. Proces produkcji komponentów technicznych dopuszcza pewne tolerancje, dlatego niektóre parametry wahają się w odstępach czasu. Ponadto wiele podstawowych stałych nie jest dokładnie znanych.

Jeżeli zachowanie takiego systemu, na który wpływ mają tolerancje, spełnia np. , dla i nieznane, to zestaw możliwych rozwiązań ${\ Displaystyle f (\ mathbf {x} , \ mathbf {p} ) = 0}$${\ Displaystyle \ mathbf {p} \ w [\ mathbf {p}]}$${\displaystyle \mathbf {x}}$

${\ Displaystyle \ {\ mathbf {x} \, | \, \ istnieje \ mathbf {p} \ w [\ mathbf {p}], f (\ mathbf {x}, \ mathbf {p}) = 0 \} }$,

można znaleźć metodami interwałowymi. Stanowi to alternatywę dla tradycyjnej propagacji analizy błędów . W przeciwieństwie do metod punktowych, takich jak symulacja Monte Carlo , metodologia arytmetyki przedziałowej zapewnia, że ​​żadna część obszaru rozwiązania nie może zostać pominięta. Jednak wynik jest zawsze analizą najgorszego przypadku dla rozkładu błędu, ponieważ inne rozkłady oparte na prawdopodobieństwie nie są brane pod uwagę.

Arytmetyka przedziałów rozmytych

Arytmetyka interwałowa może być również używana z funkcjami afiliacji dla wielkości rozmytych, ponieważ są one używane w logice rozmytej . Oprócz instrukcji ścisłych i , możliwe są również wartości pośrednie, do których przypisane są liczby rzeczywiste . odpowiada członkostwu określonemu, podczas gdy nie jest członkostwem. Funkcja rozkładu przypisuje niepewność, którą można rozumieć jako kolejny przedział. ${\displaystyle x\w [x]}$${\ Displaystyle x \ nie \ w [x]}$${\ Displaystyle \ mu \ w [0,1]}$${\ Displaystyle \ mu = 1}$${\ Displaystyle \ mu = 0}$

W przypadku arytmetyki rozmytej uwzględniana jest tylko skończona liczba dyskretnych etapów przynależności . Postać takiego rozkładu dla niewyraźnej wartości może być następnie reprezentowana przez ciąg przedziałów ${\ Displaystyle \ mu _ {i} \ w [0,1]}$

${\ Displaystyle \ lewo [x ^ {(1)}} \ po prawej] \ zdenerwowany \ po lewej [x ^ { (2)} \ po prawej] \ zdenerwowany \ cdots \ przerażony \ po lewej [x ^ {(k)} \ po prawej] .}$

Interwał odpowiada dokładnie zakresowi wahań dla etapu${\ Displaystyle \ lewo [x ^ {(i)} \ prawo]}$${\ Displaystyle \ mu _ {i}.}$

Właściwy rozkład dla funkcji dotyczącej wartości nieodróżnialnych i odpowiadających im ciągów ${\ Displaystyle f (x_ {1}, \ ldots, x_ {n})}$${\displaystyle x_{1},\ldots,x_{n}}$

${\ Displaystyle \ lewo [x_ {1} ^ {(1)}} \ prawo] \ supset \ cdots \ supset \ lewo [x_ {1} ^ {(k)} \ prawo] \ ldots \ lewo [x_ { n}^{(1)}\right]\supset \cdots \supset \left[x_{n}^{(k)}\right]}$

można aproksymować ciągiem

${\ Displaystyle \ lewo [y ^ {(1)}} \ prawo] \ zdenerwowany \ cdots \ niespokojny \ lewo [y ^ {(k)} \ prawej]}$

gdzie

${\ Displaystyle \ lewo [y ^ {(i)} \ prawo] = f \ lewo (\ lewo [x_ {1} ^ {(i)} \ prawo] \ ldots \ lewo [x_ {n} ^ {( i)}\prawo]\prawo)}$

i można je obliczyć metodami interwałowymi. Wartość odpowiada wynikowi obliczenia przedziału. ${\ Displaystyle \ lewo [y ^ {(1)}} \ prawo]}$

Dowód wspomagany komputerowo

Warwick Tucker zastosował arytmetykę przedziałową, aby rozwiązać 14 z problemów Smale'a , czyli pokazać, że atraktor Lorenza jest dziwnym atraktorem . Thomas Hales użył arytmetyki przedziałowej w celu rozwiązania hipotezy Keplera .

Historia

Arytmetyka przedziałowa nie jest zupełnie nowym zjawiskiem w matematyce; pojawiał się kilkakrotnie pod różnymi nazwami na przestrzeni dziejów. Na przykład Archimedes obliczył dolne i górne granice 223/71 < π < 22/7 w III wieku p.n.e. Faktyczne obliczenia z interwałami nie były ani tak popularne jak inne techniki numeryczne, ani nie zostały całkowicie zapomniane.

Zasady obliczania z przedziałami i innymi podzbiorami liczb rzeczywistych zostały opublikowane w pracy Rosalind Cicely Young z 1931 roku. Prace arytmetyczne nad liczbami rozstępów w celu poprawy niezawodności systemów cyfrowych zostały następnie opublikowane w 1951 roku w podręczniku algebry liniowej autorstwa Paula S. Dwyera  [ de ] ; interwały wykorzystano do pomiaru błędów zaokrągleń związanych z liczbami zmiennoprzecinkowymi. Obszerną pracę na temat algebry przedziałowej w analizie numerycznej opublikował Teruo Sunaga (1958).

Narodziny nowoczesnej arytmetyki interwałowej został oznaczony przez pojawienie się książki Interval Analysis przez Ramon E. Moore w 1966 roku wpadł na pomysł, na wiosnę 1958 roku, a rok później ukazał się artykuł na temat komputera arytmetyki przedziałowej. Jego zaletą było to, że wychodząc od prostej zasady dostarczał ogólnej metody automatycznej analizy błędów, a nie tylko błędów wynikających z zaokrągleń.

Niezależnie w 1956 r. Mieczysław Warmus zaproponował wzory do obliczeń z przedziałami, choć Moore znalazł pierwsze nietrywialne zastosowania.

W ciągu następnych dwudziestu lat niemieckie grupy badaczy prowadziły pionierskie prace wokół Ulricha W. Kulischa i Götza Alefelda  [ de ] na Uniwersytecie w Karlsruhe, a później także na Uniwersytecie Bergische w Wuppertalu . Na przykład, Karl Nickel  [ de ] zbadał bardziej efektywne implementacje, podczas gdy ulepszone procedury przechowawcze dla zbioru rozwiązań układów równań były zasługą m.in. Arnolda Neumaiera. W latach sześćdziesiątych Eldon R. Hansen zajmował się wydłużaniem przedziałów dla równań liniowych, a następnie wniósł istotny wkład w globalną optymalizację, w tym metodę znaną obecnie jako metoda Hansena, być może najczęściej używany algorytm przedziałowy. Klasyczne metody w tym zakresie często mają problem z określeniem największej (lub najmniejszej) wartości globalnej, ale potrafiły znaleźć tylko lokalne optimum i nie mogły znaleźć lepszych wartości; Helmut Ratschek i Jon George Rokne opracowali metody gałęzi i wiązań , które do tej pory stosowały się tylko do wartości całkowitych, wykorzystując interwały w celu zapewnienia zastosowań dla wartości ciągłych.

W 1988 roku Rudolf Lohner opracował oprogramowanie oparte na Fortranie do niezawodnych rozwiązań problemów z wartością początkową przy użyciu równań różniczkowych zwyczajnych .

Czasopismo Reliable Computing (pierwotnie Interval Computations ) ukazuje się od lat 90. XX wieku i poświęcony jest niezawodności obliczeń wspomaganych komputerowo. Jako redaktor prowadzący, R. Baker Kearfott, oprócz pracy nad globalną optymalizacją, znacząco przyczynił się do ujednolicenia notacji i terminologii stosowanej w arytmetyce przedziałowej.

W ostatnich latach prace koncentrowały się w szczególności na estymacji wstępnych obrazów sparametryzowanych funkcji i solidnej teorii sterowania przez grupę roboczą COPRIN INRIA w Sophia Antipolis we Francji.

Realizacje

Istnieje wiele pakietów oprogramowania, które umożliwiają tworzenie aplikacji numerycznych przy użyciu arytmetyki przedziałowej. Są one zwykle dostarczane w postaci bibliotek programów. Istnieją również kompilatory C++ i Fortran, które obsługują interwałowe typy danych i odpowiednie operacje jako rozszerzenie języka, więc arytmetyka interwałowa jest obsługiwana bezpośrednio.

Od 1967 roku na Uniwersytecie w Karlsruhe opracowywano rozszerzenia do obliczeń naukowych (XSC) dla różnych języków programowania , takich jak C++, Fortran i Pascal . Pierwszą platformą była Zuse Z23 , dla której udostępniono nowy interwałowy typ danych z odpowiednimi operatorami elementarnymi. W 1976 roku pojawił się Pascal-SC , wariant Pascala na Zilog Z80, który umożliwił tworzenie szybkich, skomplikowanych procedur do automatycznej weryfikacji wyników. Następnie pojawił się oparty na Fortran 77 ACRITH-XSC dla architektury System/370 (FORTRAN-SC), który później został dostarczony przez IBM. Począwszy od 1991 roku można było tworzyć kod dla kompilatorów C za pomocą Pascal-XSC ; rok później biblioteka klas C++ obsługiwała C-XSC na wielu różnych systemach komputerowych. W 1997 roku wszystkie warianty XSC zostały udostępnione na licencji GNU General Public License . Na początku 2000 roku C-XSC 2.0 został wydany pod kierownictwem grupy roboczej ds. obliczeń naukowych na Uniwersytecie Bergische w Wuppertalu, aby odpowiadał ulepszonemu standardowi C++.

Kolejna biblioteka klasy C++ została stworzona w 1993 roku na Politechnice w Hamburgu o nazwie Profil/BIAS (Programmer's Runtime Optimized Fast Interval Library, Basic Interval Arithmetic), dzięki czemu zwykłe operacje interwałowe stały się bardziej przyjazne dla użytkownika. Podkreślono efektywne wykorzystanie sprzętu, przenośność i niezależność określonej prezentacji interwałów.

Kolekcja doładowania bibliotek C ++ zawiera klasę szablonu dla przedziałów. Jego autorzy dążą do posiadania arytmetyki przedziałowej w standardowym języku C++.

Język programowania Frink ma implementację arytmetyki przedziałowej, która obsługuje liczby o dowolnej precyzji . Programy napisane w Frink mogą używać interwałów bez przepisywania lub ponownej kompilacji.

Gaol to kolejna biblioteka arytmetyczna przedziałów C++, która jest wyjątkowa, ponieważ oferuje relacyjne operatory przedziałów używane w programowaniu ograniczeń przedziałów .

Biblioteka Moore to wydajna implementacja arytmetyki przedziałowej w C++. Zapewnia interwały z punktami końcowymi o dowolnej precyzji i opiera się na funkcji „koncepcji” C++.

Język programowania Julia ma implementację arytmetyki przedziałowej wraz z funkcjami wysokiego poziomu, takimi jak wyszukiwanie pierwiastków (zarówno dla funkcji o wartościach rzeczywistych, jak i złożonych) oraz programowanie z ograniczeniami przedziałowymi za pośrednictwem pakietu ValidatedNumerics.jl.

Ponadto systemy algebry komputerowej, takie jak FriCAS , Mathematica , Maple , Maxima (oprogramowanie) i MuPAD , mogą obsługiwać interwały. Matlab przedłużenie Intlab buduje na Blas rutyny, a B4M Toolbox umożliwia interfejs Profil / stronniczości. Ponadto Software Euler Math Toolbox zawiera arytmetykę interwałową.

Biblioteka dla języka funkcjonalnego OCaml została napisana w języku asemblera i C.

Standard IEEE 1788

Standard arytmetyki przedziałowej, IEEE Std 1788-2015, został zatwierdzony w czerwcu 2015 roku. Dwie implementacje referencyjne są dostępne bezpłatnie. Zostały one opracowane przez członków grupy roboczej standardu: biblioteka libieeep1788 dla C++ i pakiet interwałowy dla GNU Octave .

Minimalny podzbiór standardu, IEEE Std 1788,1-2017, został zatwierdzony w grudniu 2017 r. i opublikowany w lutym 2018 r. Powinien być łatwiejszy do wdrożenia i może przyspieszyć produkcję wdrożeń.

Konferencje i warsztaty

Na świecie co roku odbywa się kilka międzynarodowych konferencji lub warsztatów. Główną konferencją jest prawdopodobnie SCAN (International Symposium on Scientific Computing, Computer Arithmetic, and Verified Numerical Computation), ale jest też SWIM (Small Workshop on Interval Methods), PPAM (International Conference on Parallel Processing and Applied Mathematics), REC (International Warsztaty na temat niezawodnych obliczeń inżynierskich).

Zobacz też

• Arytmetyka afiniczna
• INTLAB (Laboratorium Interwałowe)
• Automatyczne różnicowanie
• Metoda wielosiatkowa
• Symulacja Monte Carlo
• Interwałowy element skończony
• Liczba rozmyta
• Znaczące liczby
• Dokładna arytmetyka w Karlsruhe (KAA)
• Unum

Bibliografia

Dalsza lektura

• Hayes, Brian (listopad-grudzień 2003). „Świadomy interwał” (PDF) . Amerykański naukowiec . Sigma Xi. 91 (6): 484–488. doi : 10.1511/2003.6.484 .
• Tucker, Warwick (2011). Zatwierdzona numeracja: krótkie wprowadzenie do rygorystycznych obliczeń . Wydawnictwo Uniwersytetu Princeton .
• Wippermann, Hans-Wilm (1968) [15.06.1967, 1966]. „Definicja Schrankenzahlena w Triplex-ALGOL”. Informatyka (w języku niemieckim). Karlsruhe, Niemcy: Springer. 3 (2): 99–109. doi : 10.1007/BF02277452 . ISSN  0010-485X . S2CID  36685400 .(11 stron) (Uwaga: o Triplex-ALGOL Karlsruhe , implementacji ALGOL 60 (1963) z obsługą liczb triplex.)

Zewnętrzne linki

• Arytmetyka interwałowa (Wolfram Mathworld)
• Zatwierdzone dane liczbowe dla pieszych
• Metody interwałowe Arnolda Neumaiera , Uniwersytet Wiedeński
• SWIM (Letnie Warsztaty Metod Interwałowych)
• Międzynarodowa Konferencja Przetwarzania Równoległego i Matematyki Stosowanej
• INTLAB, Instytut Niezawodnej Informatyki , Politechnika w Hamburgu
• Arytmetyka kulowa – Joris van der Hoeven
• kv - biblioteka C++ do zweryfikowanych obliczeń numerycznych
  • kv na GitHub
• Arb — biblioteka C do arytmetyki kulkowej z arbitralną precyzją
  • arb na GitHub
• JuliaIntervals na GitHub