Интервальный анализ: вычисления с гарантированной математической точностью

Катастрофическая потеря значимости чисел с плавающей запятой

Все классические численные алгоритмы, реализуемые на компьютерах, используют формат чисел с плавающей запятой (стандарт IEEE 754). Этот формат неизбежно вносит погрешность округления при каждой арифметической операции. В большинстве инженерных задач эти крошечные ошибки (порядка 10 в минус 16 степени) не имеют значения. Однако в плохо обусловленных задачах, при вычитании близких чисел или в хаотических динамических системах (где малейшее изменение начальных условий ведет к радикальной смене траектории), ошибки округления накапливаются и полностью искажают результат. Компьютер может выдать ответ, который математически не имеет ничего общего с реальностью, и при этом никак не предупредить пользователя об ошибке.

Для управления полетами космических аппаратов, расчета доз облучения в медицинской лучевой терапии и проверки безопасности атомных реакторов такой риск неприемлем. Нам нужен способ не просто получить приближенный ответ, но и получить строгие математические гарантии того, что истинный ответ гарантированно находится внутри определенного диапазона. Эту революционную идею в 1960-х годах воплотил в жизнь американский математик Рамон Мур, создав новую ветвь математики — интервальный анализ.

Замена чисел на множества

В интервальном анализе базовым объектом оперирования является не конкретное число (скаляр), а замкнутый интервал (отрезок) на числовой оси: [a, b]. В этом отрезке a — это строгая нижняя граница, а b — строгая верхняя. Любые исходные данные с погрешностью (например, длина детали 10 мм с погрешностью 0.1 мм) сразу представляются как интервал [9.9, 10.1].

Далее переопределяются все арифметические операции (сложение, вычитание, умножение, деление) и базовые функции (синус, экспонента). Когда компьютер складывает два интервала, он складывает их нижние и верхние границы с особым аппаратным округлением (нижняя граница всегда округляется в меньшую сторону, верхняя — в большую). Это гарантирует, что истинный ответ никогда не выскользнет за пределы вычисленного результирующего интервала. Иными словами, интервальные вычисления предоставляют стопроцентную, математически строгую оценку глобальной погрешности алгоритма. Если в результате расчета орбиты спутника мы получили интервал расстояния до Земли [400 км, 405 км], мы можем быть абсолютно уверены, что спутник не упадет.

Проблема зависимости (эффект переоценки)

Главным препятствием на пути повсеместного внедрения интервальной арифметики является так называемая «проблема зависимости». Если в классической математике x - x всегда равно 0, то в интервальной арифметике, если мы возьмем интервал X = [1, 2] и вычтем его сам из себя, мы получим интервал [-1, 1], а не ноль. Алгоритм «забывает», что интервалы физически связаны (зависят от одной переменной), и рассматривает их как два независимых множества, принимающих наихудшие возможные значения.

Из-за этого эффекта, при прохождении длинного алгоритма, границы результирующего интервала могут раздуваться до абсурдных размеров (например, от минус бесконечности до плюс бесконечности), делая результат бесполезным. Современные исследования в области интервального анализа сфокусированы на создании сложных алгебраических структур (аффинная арифметика, полиномы Тейлора с интервальным остатком), которые отслеживают корреляции между переменными и сдерживают рост интервалов, открывая путь к абсолютно надежным компьютерным доказательствам математических теорем.