Проверенные цифры
Проверенные числа , или строгие вычисления , проверенные вычисления , надежные вычисления , численная проверка ( нем . Zuverlässiges Rehnen ) — это числовые значения, включающие математически строгую оценку ошибок (ошибка округления, ошибка усечения, ошибка дискретизации), и это одна из областей численного анализа . Для вычислений используется интервальная арифметика , и все результаты представляются интервалами. Проверенные численные значения были использованы Уорвиком Такером для решения 14-й задачи Смейла . [1] и сегодня он признан мощным инструментом для изучения динамических систем . [2]
Важность [ править ]
Вычисления без проверки могут привести к неудачным результатам. Ниже приведены некоторые примеры.
Пример Рампа [ править ]
В 1980-х годах Рамп привел пример. [3] [4] Он составил сложную функцию и попытался получить ее значение. Результаты одинарной точности, двойной точности и расширенной точности казались правильными, но их знак плюс-минус отличался от истинного значения.
Фантомное решение [ править ]
Брейер-Плам-Маккенна использовал спектральный метод для решения краевой задачи уравнения Эмдена и сообщил, что было получено асимметричное решение. [5] Этот результат исследования противоречил теоретическому исследованию Гидаса-Ни-Ниренберга, в котором утверждалось, что асимметричного решения не существует. [6] Решение, полученное Брейером-Пламом-Маккенной, было фантомным решением, вызванным ошибкой дискретизации. Это редкий случай, но он говорит нам о том, что когда мы хотим строго обсуждать дифференциальные уравнения, численные решения должны быть проверены.
вызванные ошибками Несчастные случаи , числовыми
Следующие примеры известны как несчастные случаи, вызванные числовыми ошибками:
- Неудача перехвата ракет в войне в Персидском заливе (1991 г.) [7]
- Авария ракеты Ариан-5 (1996 г.) [8]
- Ошибки при подсчете результатов выборов [9]
Основные темы [ править ]
Изучение проверенных чисел разделено на следующие области:
- Проверка в числовой линейной алгебре
- Проверка специальных функций :
- Проверка числовой квадратуры [31] [32] [33]
- Проверка нелинейных уравнений ( Теорема Канторовича , [34] Изучены метод Кравчика, интервальный метод Ньютона и метод Дюрана-Кернера-Аберта.)
- Верификация решений ОДУ, УЧП [35] (Для PDE знания функционального анализа . используются [34] )
- Проверка линейного программирования [36]
- Проверка вычислительной геометрии
- Верификация в высокопроизводительной вычислительной среде
Инструменты [ править ]
- Библиотека INTLAB , созданная MATLAB / GNU Octave
- kv Библиотека, созданная на C++ . Эта библиотека может получать несколько точных результатов, используя GNU MPFR .
- Библиотека Arb созданная C. , Он способен строго вычислять различные специальные функции .
- CAPD Коллекция гибких модулей C++, которые в основном предназначены для вычисления гомологии множеств, карт и проверенных числовых значений для динамических систем .
- JuliaIntervals на GitHub (библиотека, созданная Джулией )
- Boost Safe Numerics — библиотека C++, состоящая только из заголовков и содержащая проверенные замены для всех встроенных целочисленных типов .
См. также [ править ]
Ссылки [ править ]
- ^ Такер, Уорик . (1999). «Аттрактор Лоренца существует». Comptes Rendus de l'Académie des Sciences, серия I-Mathematics , 328 (12), 1197–1202.
- ^ Зин Араи, Хироши Кокубу, Павел Пиларчик. Последние разработки в области строгих методов расчета в динамических системах .
- ^ Рамп, Зигфрид М. (1988). «Алгоритмы верифицированных включений: теория и практика». В книге «Надежность вычислений» (стр. 109–126). Академическая пресса.
- ^ Ло, Юджин; Уолстер, Дж. Уильям (2002). Еще раз повторим пример Рампа. Надежные вычисления, 8(3), 245–248.
- ^ Брейер, Б.; Плам, Майкл; Маккенна, Патрик Дж. (2001). «Включения и доказательства существования решения нелинейной краевой задачи спектральными численными методами». В разделах численного анализа (стр. 61–77). Шпрингер, Вена.
- ^ Гидас, Б.; Ни, Вэй-Мин; Ниренберг, Луи (1979). «Симметрия и связанные с ней свойства через принцип максимума». Коммуникации в математической физике , 68(3), 209–243.
- ^ «Провал ракеты Патриот» .
- ^ Авария рейса 501 ARIANE 5, http://sunnyday.mit.edu/nasa-class/Ariane5-report.html
- ^ Ошибка округления меняет состав парламента.
- ^ Ямамото, Т. (1984). Границы погрешности приближенных решений систем уравнений. Японский журнал прикладной математики, 1 (1), 157.
- ^ Оиси, С., и Рамп, С.М. (2002). Быстрая проверка решений матричных уравнений. Числовая математика, 90 (4), 755–773.
- ^ Ямамото, Т. (1980). Границы ошибок для вычисленных собственных значений и собственных векторов. Численная математика, 34 (2), 189–199.
- ^ Ямамото, Т. (1982). Границы ошибок для вычисленных собственных значений и собственных векторов. II. Численная математика, 40 (2), 201–206.
- ^ Майер, Г. (1994). Проверка результатов для собственных векторов и собственных значений. Темы проверенных вычислений, Elsevier, Амстердам, 209–276.
- ^ Огита, Т. (2008). Проверенный численный расчет определителя матрицы. SCAN'2008 Эль-Пасо, Техас, 29 сентября – 3 октября 2008 г., стр. 86.
- ^ Шинья Миядзима, Проверенные вычисления для эрмитова положительно определенного решения сопряженного алгебраического уравнения Риккати в дискретном времени, Журнал вычислительной и прикладной математики, том 350, страницы 80-86, апрель 2019 г.
- ^ Шинья Миядзима, Быстрое проверенное вычисление минимального неотрицательного решения несимметричного алгебраического уравнения Риккати, Вычислительная и прикладная математика, том 37, выпуск 4, страницы 4599-4610, сентябрь 2018 г.
- ^ Шинья Миядзима, Быстро проверенные вычисления для решения уравнения Т-конгруэнции Сильвестра, Японский журнал промышленной и прикладной математики, том 35, выпуск 2, страницы 541-551, июль 2018 г.
- ^ Шинья Миядзима, Быстро проверенные вычисления для решения квадратного матричного уравнения, Электронный журнал линейной алгебры, том 34, страницы 137-151, март 2018 г.
- ^ Шинья Миядзима, Быстро проверенные вычисления для решений алгебраических уравнений Риккати, возникающих в теории переноса, Численная линейная алгебра с приложениями, том 24, выпуск 5, страницы 1–12, октябрь 2017 г.
- ^ Шинья Миядзима, Быстрые проверенные вычисления для стабилизации решений алгебраических уравнений Риккати в дискретном времени, Журнал вычислительной и прикладной математики, том 319, страницы 352-364, август 2017 г.
- ^ Шинья Миядзима, Быстрые проверенные вычисления для решений алгебраических уравнений Риккати в непрерывном времени, Японский журнал промышленной и прикладной математики, том 32, выпуск 2, страницы 529–544, июль 2015 г.
- ^ Рамп, Зигфрид М. (2014). Проверены четкие границы реальной гамма-функции во всем диапазоне чисел с плавающей запятой. Нелинейная теория и ее приложения, IEICE, 5 (3), 339–348.
- ^ Яманака, Наоя; Окаяма, Томоаки; Оиси, Синъити (ноябрь 2015 г.). Проверенные границы ошибки для реальной гамма-функции с использованием формулы двойной экспоненты на полубесконечном интервале. На Международной конференции по математическим аспектам компьютерных и информационных наук (стр. 224-228). Спрингер.
- ^ Йоханссон, Фредрик (2019). Численное вычисление эллиптических функций, эллиптических интегралов и модульных форм. В книге «Эллиптические интегралы, эллиптические функции и модульные формы в квантовой теории поля» (стр. 269–293). Спрингер, Чам.
- ^ Йоханссон, Фредрик (2019). Строгое вычисление гипергеометрических функций. Транзакции ACM в математическом программном обеспечении (TOMS), 45 (3), 30.
- ^ Йоханссон, Фредрик (2015). Строгое высокоточное вычисление дзета-функции Гурвица и ее производных. Численные алгоритмы, 69 (2), 253–270.
- ^ Миядзима, С. (2018). Быстрое проверенное вычисление главного корня матрицы pth. ru:Журнал вычислительной и прикладной математики , 330, 276–288.
- ^ Миядзима, С. (2019). Проверено вычисление главного логарифма матрицы. Линейная алгебра и ее приложения, 569, 38–61.
- ^ Миядзима, С. (2019). Проверено вычисление матричной экспоненты. Достижения в области вычислительной математики, 45 (1), 137–152.
- ^ Йоханссон, Фредрик (2017). Arb: эффективная арифметика интервалов средней точки и радиуса произвольной точности. Транзакции IEEE на компьютерах, 66 (8), 1281–1292.
- ^ Йоханссон, Фредрик (2018, июль). Численное интегрирование в шаровой арифметике произвольной точности. На Международном конгрессе по математическому программному обеспечению (стр. 255–263). Спрингер, Чам.
- ^ Йоханссон, Фредрик; Меззаробба, Марк (2018). Быстрое и строгое вычисление с произвольной точностью квадратурных узлов и весов Гаусса-Лежандра. Журнал SIAM по научным вычислениям , 40(6), C726-C747.
- ^ Перейти обратно: а б Эберхард Зейдлер , Нелинейный функциональный анализ и его приложения IV. Springer Science & Business Media .
- ^ Мицухиро Т. Накао, Майкл Плам, Ёситака Ватанабэ (2019) Методы численной проверки и компьютерные доказательства уравнений в частных производных (серия Спрингера по вычислительной математике).
- ^ Оиси, Синъити; Танабэ, Кунио (2009). Численное включение оптимальной точки для линейного программирования. Письма JSIAM, 1, 5-8.
Дальнейшее чтение [ править ]
- Такер, Уорик (2011). Проверенные числовые значения: краткое введение в строгие вычисления. Издательство Принстонского университета .
- Мур, Рамон Эдгар , Кирфотт, Р. Бейкер, Клауд, Майкл Дж. (2009). Введение в интервальный анализ. Общество промышленной и прикладной математики .
- Рамп, Зигфрид М. (2010). Методы проверки: строгие результаты с использованием арифметики с плавающей запятой. Acta Numerica , 19, 287–449.
Внешние ссылки [ править ]
- Проверенные цифры для пешеходов
- Reliable Computing . Открытый электронный журнал, посвященный численным вычислениям с гарантированной точностью, ограничению диапазонов, математическим доказательствам, основанным на арифметике с плавающей запятой, а также другой теории и приложениям интервальной арифметики и направленного округления.