Введение 4
1. Постановка задачи 6
2. Обзор 7
2.1. Интервальный анализ 7
2.2. Оптимальная оценка ошибки 9
2.3. Апостериорный интервальный анализ 10
3. Реализация 14
3.1. Традиционный интервальный анализ 14
3.2. Динамический апостериорно-интервальный анализ ... 15
4. Статические методы 19
4.1. Общая схема статических методов 19
4.2. Compute и InverseCompute для определителя 22
4.3. Compute и InverseCompute для решения линейных систем 24
5. Сравнения подходов 26
5.1. Генерирование случайных матриц 26
5.2. Определители 26
5.3. Линейные системы 28
Заключение 31
Список литературы 32
Величины с плавающей точкой являются одним из основных типов данных при математических вычислениях. Однако, они не всегда хорошо справляются с возложенной на них задачей быть аналогом вещественных чисел. Ошибка может быстро накапливаться и вычисленное значение может быть сколь угодно удаленным от правильного результата. Таким образом, необходима возможность автоматизации контроля за погрешностью при расчетах на компьютере.
Рассмотрим причины появления неточностей. Традиционно принято их делить на три класса:
1. погрешности в начальных данных;
2. погрешности метода;
3. погрешности округления.
Мы не можем автоматически контролировать погрешности метода, этим занимается отдельный раздел математики — вычислительные методы. В массовых языках обычно возможности указывать направление округления. Также они не позволяют учитывать погрешности в данных.
Интервальные методы применяются еще со времен Архимеда. Начало развития современного интервального анализа связывается с выходом книги ’’Interval Analysis” [7] Мура в 1966 году. Интервальное число представляет собой интервал, в котором гарантированно находится истинное значение. Далее определяются операции, результат которых также является гарантированным.
Таким образом интервалы позволяют одновременно представлять приближенное значение и его погрешность, а с проблемами округления можно бороться с помощью направленных округлений.
Раньше развитие интервального анализа затормаживалось из-за необходимости изучать спецификации конкретных машин, так как не существовало стандартов на вещественные числа. С появлением в 1985 году IEEE 754 [3] стандарта и различных библиотек для работы с числами с произвольной точностью эта проблема сошла на нет.
Интервальные библиотеки в том или ином виде существуют почти для всех популярных языков программирования (INTLAB, Boost interval, libieeep1788, C-XSC, Pascal-XSC, Arb и многие другие). В таких системах компьютерной алгебры как Maple, Mathematica, MuPAD интервалы являются встроенными типами. Недавно вышел IEEE 1788 [4] стандарт на интервальные вычисления. В основном реализации интервальной арифметики предоставляют собой набор стандартных операций и функций без специальных методов улучшения оценки значения ошибки (таких как, например, обобщенный интервальный или апостериорно-интервальный анализ). Это связано с тем, что такие методы значительно увеличивают трудоемкость вычисления.
В данной работе рассматривается применимость апостериорно-интервального метода к таким задачам линейной алгебры как вычисление определителя и решение линейных систем. Также приводится описание реализации библиотеки для апостериорно-интервальных вычислений в произвольных программах.
В результате данной работы были решены следующие задачи:
• исследованы подходы к работе с интервальными величинами, рассмотрены способы уточнения оценки итоговой ошибки;
• реализованы основные операции интервального анализа поверх библиотеки Arb;
• реализованы динамический и статический подход к апостериорному уточнению ошибки в задачах нахождения определителя и решения линейных систем;
• динамический подход реализован в качестве библиотеки и может быть легко использован в других приложениях;
• проведено теоретическое и экспериментальное сравнение подходов, показавшее, что, несмотря на большие затраты по сравнению с традиционным интервальным анализом, апостериорный метод может быть эффективно использован в задачах линейной алгебры.
Дальнейшее развитие может происходить в нескольких направлениях.
Во первых, необходим более тщательный анализ и оптимальная реализация динамического метода. Это может на порядки сократить накладные расходы на использование управляющего устройства.
Во вторых, можно построить больше статических методов. Также полезна была бы возможность эффективно комбинировать динамический и статический методы.
Наконец, важной задаче является исследование возможности построения интервального языка с возможностью автоматической генерации статического этапа.
