Интервалы и Интервальный анализ
Интервал – это замкнутый числовой промежуток. Например, интервал между 2 и 3 содержит все вещественные числа между 2 и 3, включая их самих, и обозначается как [2, 3]. Соответственно, интервальная неопределённость – это состояние неполного (частичного) знания об интересующей нас величине, когда мы можем лишь указать её принадлежность данному интервалу. Иными словами, мы можем предъявить только границы возможных значений этой величины (либо пределы её изменения), и ширина получающегося интервала является естественной мерой нашей неопределённости (неоднозначности). Математическая дисциплина, которая изучает задачи с интервальными неопределённостями и неоднозначностями в данных и методы их решения называется интервальным анализом.
Выполнение арифметических операций над величинами, имеющими интервальную неопределённость, приводит к интервальной неопределённости в ответе, и интервал результата должен содержать все возможные результаты выполнения операции над представителями исходных интервалов. Например, [1,2] + [2,3] = [3,5], если в пределах интервалов [1,2] и [2,3] соответствующие величины могут принимать значения «независимо» друг от друга. Аналогичным образом обстоит дело и с большинством других интервальных операций, так что в результате интервальных вычислений получающийся интервал гарантированно содержит множество всевозможных ответов «точечных» задач, данные к которым содержались в исходных интервалах. В целом, идея интервальных вычислений – это использование интервалов, представляющих числовые промежутки, как основного объекта данных.
Где может быть полезен интервальный анализ?
Имеются три основных сферы успешного применения интервального анализа и интервальных методов:
- Решение практических задач, имеющих интервальную или, более общо, ограниченную неопределённость в данных.
- Строгий учёт ошибок округления при вычислениях с числами с плавающей точкой на цифровых ЭВМ.
- Новые подходы к решению традиционных математических задач (таких, к примеру, как задача глобальной оптимизации, глобальное доказательное решение систем нелинейных уравнений и т.п.)
Рассмотрим подробнее каждый из этих пунктов.
Задачи с интервальными неопределённостями и неоднозначностями
Задачи этого типа являются важнейшей сферой приложений интервального анализа, а само интервальное описание неопределённости – одним из наиболее популярных, наряду с нечётким (размытым) и вероятностным (стохастическим) описаниями. При этом может показаться, что интервальное описание неопределённости явлется наименее информативным среди других, наиболее «скупым» на детали, поскольку учитывет лишь границы возможных значений неизвестной величины. Но эта же «скупость» оборачивается «экономностью» интервальных моделей и большей развитостью математического аппрата для их исследования. К примеру, ни в теории нечётких множеств, ни в теории вероятностей не достигнуто той развитости методов решения систем уравнений с неопределённостями, как это имеет место для интервальных систем уравнений.
Большое разнообразие постановок задач с интервалами на входе доставляет идентификация в условиях неопределённости, когда данные об объекте, получаемые в результате измерений, либо каким-нибудь другим способом, не известны точно, но нам всё равно требуется найти или как-то оценить параметры объекта.
Вплоть до конца прошлого века модели неопределённости, используемые при оценке параметров и идентификации, имели, главным образом, стохастический или вероятностный характер, основываясь на известных распределениях рассматриваемых величин и т.п. Но во многих практических ситуациях недостаточно информации для того, чтобы считать неопределённые факторы подчиняющимися какой-либо вероятностной модели (к примеру, отсутствует статистическая однородность результатов испытаний), либо эти факторы могут не удовлетворять тем или иным (часто весьма обременительным) условиям, которые на них налагает вероятностная модель неопределённости. Таковыми являются требования независимости исходных величин или специальный вид их распределений и т.п.
В настоящее время интервальное представление факторов неопределённости привлекает всё большее внимание инженеров, как наименее ограничительное и наиболее адекватное многим практическим постановкам задач. Подробное обсуждение этого круга вопросов на примере задач идентификации и робототехники можно найти, к примеру, в книге
- L. Julin, M. Kieffer, O. Didrit and E. Walter, Applied Interval Analysis, Springer-Verlag, Berlin-Heidelberg, 2001,
Строгий учёт ошибок округлений на цифровых ЭВМ
Числа с плавающей точкой (floating point numbers), которые являются основой современных цифровых ЭВМ, оказываются не вполне адекватными как реальному физическому миру, так и его математическим моделям, в частности, математическому понятию вещественного (действительного) числа. Основные недостатки чисел с плавающей точкой, как хорошо известно, заключаются в следующем:
- Большинство чисел вещественной оси не могут быть представлены точно числами с плавающей точкой, имеющими конечную длину мантиссы.
- Свойства арифметических операций над числами с плавающей точкой отличаются (из-за неизбежных округлений) от свойств идеальных математических операций над вещественными числами.
- Число в формате с плавающей точкой не несёт никакой информации о точности той величины, которую оно представляет.
Получается, что существующая модель вычислений с плавающей точкой не предназначена ни для представления, ни для отслеживания вычислительных ошибок, и потому большинство расчётов с ней и не дают никакого анализа точности результатов. В той мере, в какой подобные вычислительные результаты используются для принятия критических решений, неучтённые ошибки вычислений означат повышенный риск. И чем сильнее эта зависимость от вычисляемых результатов, чем более важной является их корректность, тем больше допускаемый риск. Катастрофа с американской зенитной ракетой «Пэтриот» 25 февраля 1991 года в Дхаране (Саудовская Аравия) во время натовской военной операции «Буря в пустыне» против Ирака показывает, что может произойти, если существующие вычисления с плавающей точкой будут и далее некритично применяться к новым задачам.
В тот день батарея ракет «Пэтриот», развёрнутая для защиты американских военных объектов в Дхаране, не смогла перехватить иракскую ракету «Скад», причиной чего было официально названо неадекватное вычисление в формате с плавающей точкой. Система управления ракеты «Пэтриот» имеет внутренние системные часы, отсчитывающие время в десятых долях секунды. Для перевода подобного времени в формат с целыми секундами компьютер просто умножает данные на 1/10. С идеальной математической точки зрения эта операция безошибочна, но в вычислительном отношении на современных цифровых ЭВМ с двоичной системой счисления она сопровождается погрешностью, так как дробь 1/10 не имеет точного внутреннего представления на подобных компьютерах и должна быть приближена подходящей двоичной дробью. В качестве такого приближения американские разработчики взяли 24-битное двоичное число 0.00011001100110011001100, которое меньше, чем 1/10, примерно на одну миллионную. Это кажется исчезающее малым, но ведь подобная погрешность постепенно накапливается! После четырёх дней непрерывной работы расхождение системного времени с точным достигло трети секунды, что в комбинации с другими особенностями программного обеспечения «Пэтриотов» привело к ошибке наведения в 700 метров. В результате ракета, выпущенная на перехват «Скада», промахнулась, а «Скад» успешно поразил барак с американскими военнослужащими, убив 28 человек.
Взрыв французской космической ракеты «Ариан-5» сразу после старта 4 июня 1996 года в Гвиане имел ту же самую причину – ошибку в вычислениях с плавающей точкой.
Существуют и обратные примеры, демонстрирующие силу интервальных методов и, в частности, интервальной машинной арифметики. Варвик Тукер (Warwick Tucker) из Университета Упсалы (Швеция) дал строгое доказательство существования так называемого аттрактора Лоренца в известной модельной динамической системе для значений параметров, указанных самим её автором Лоренцем. Задача долго стояла вызовом сообществу специалистов, занимающихся динамическими системами и была включена известным американским математиком Стивеном Смейлом в его список проблем для нового тысячелетия. Доказательство В. Тукера использует компьютерные оценки со строгими гарантированными границами, полученными с помощью многомерной интервальной арифметики. Детали этого решения можно увидеть на http://www.math.kth.se/4ecm/prizes.ecm.html
Новые подходы к решению традиционных задач
Задача оптимизации состоит, как известно, в нахождении наилучшего значения некоторой целевой функции на допустимом множестве, задаваемом обычно системой ограничений (уравнений и/или неравенств). Для решения задачи оптимизации в последние десятилетия было предложено большое количество подходов, каждый из которых имеет свои преимущества и недостатки. Тем не менее, общими чертами большинства из них являются
- локальный характер, и, как следствие, неспособность находить гарантированно глобальный оптимум целевой функции,
- гарантированные оценки точности полученных решений либо находятся подобными методами с большим трудом, либо не находятся вообще.
Методы глобальной оптимизации, основанные на применении интервального анализа, свободны от этих недостатков, так как способны исследовать целые куски области определения целевой функции, имеющие ненулевую меру. Более того, интервальные методы не теряют решений-оптимумов! Подробнее об этом см., к примеру, презентацию лекции «Интервальные методы для решения задач глобального поиска», находящуюся на нашем сайте.
Неудивительно, что интервальный анализ был взят в качестве основного инструмента в научно-исследовательском проекте COCONUT, нацеленном на разработку эффективных вычислительных алгоритмов глобального решения систем нелинейных уравнений и задач непрерывной оптимизации и выполнявшемся в Европейском Союзе в 2001-2004 годах. Подробную информацию по проекту COCONUT и его итоги можно увидеть на http://www.mat.univie.ac.at/~neum/glopt/coconut/.
Другие примеры успешного применения интервальных методов
Выше уже упоминались примеры того, как интервальные методы помогают решать труднейшие задачи естествознания и математического моделирования. Нельзя не упомянуть ещё о двух эффектных приложениях. Первое из них касается применения интервальных вычислений к точному измерению гравитационной константы G, а второе – успешной навигации робота.
Мартовский номер за 1996 год популярного научного журнала «Discover» (США) в список важнейших научных результатов поставил работу по измерению гравитационной константы G (напомним, что согласно закону всемирного тяготения сила притяжения между двумя телами с массами M и m на расстоянии R равна GMm/R2). Поскольку на Земле гравитационное взаимодействие между телами гораздо слабее любых других взаимодействий, значение этой константы известно хуже всех остальных фундаментальных физических констант. Более того, различные измерения для G дают плохо согласующиеся друг с другом результаты: имеется несколько результатов измерений с оценками их точности, так что ими даются интервалы возможных значений для G, точное значение которой должно лежать в каждом из них, но … эти интервалы не пересекаются! Физики и математики-прикладники из Университета Вупперталя (Германия), возглавляемые проф. Х. Мейером (физика) и проф. Б. Лангом (математика), проанализировали ситуацию и обнаружили, что кажущееся противоречие вызвано отчасти пренебрежением некоторыми физическими источниками ошибок, но, главным образом, использованием приближённых оценок ошибки в алгоритмах обработки данных: соответствующая стандартная методика, как правило, выдаёт заниженную общую оценку погрешности. Для исправления этой ошибки немецкие исследователи предложили применять доказательные вычисления с автоматической проверкой корректности результата, основанные, в частности, на методах интервального анализа. Развёрнутое изложение методики немецких исследователей содержит статья O.Holzmann, B. Lang, H. Schütt «Newton's constant of gravitation and verified numerical quadrature» // Reliable Computing. – 1996. – № 2(3). – P. 229-239.
Интервальные методы навигации помогли роботу, разработанному командой из Университета Техаса в Эль-Пасо занять престижное третье место во всемирном соревновании роботов, прошедшем во время конференции Американской Ассоциации Искусственного Интеллекта в Портленде (США), 6-7 августа 1996 года. А на следующий год модифицированная версия «интервального» робота «Диабло», созданного в Университете Техаса в Эль-Пасо, заняла первое место на международных соревнованиях роботов AAAI-97, которое проводилось в 1997 году в Провиденсе (США). Оно предполагало уборку роботом помещения с помощью пылесоса, см. http://www.cs.utep.edu/interval-comp/robot97.html
Интересный обзор интервальных методов решения разнообразных инженерных задач можно найти в статье E.P. Hofer, A. Rauh «Applications of interval algorithms in engineering», опубликованной в электронных трудах симпозиума SCAN-2006 (12th GAMM-IMACS Symposium on Scientific Computing, Computer Arithmetics and Validated Numerics – SCAN-2006, September 26-29, 2006, Duisburg, Germany. Conference Post-Proceedings. – IEEE Computer Sosiety, 2006).
Реализация интервальных вычислений на ЭВМ
Интервальный тип данных и интервальная арифметика реализуются на современных ЭВМ, например, представлением интервала как пары чисел – одного для левого конца интервала, а другого для правого. При этом существующее аппаратное обеспечение, в частности, арифметика чисел с плавающей точкой, используются без каких-либо изменений, так как корректность получающейся интервальной арифметики может быть обеспечена так называемыми направленными округлениями. Например, там, где в задачах внешнего интервального оценивания в процессе вычислений требуется округление результата, нижняя граница интервала должна округляться вниз, а верхняя граница интервала – вверх. Таким образом даже неизбежные ошибки округления при вычислениях с плавающей точкой будут строго и систематически учитываются в процессе выполенния интервальной программы.
В настоящее время существует немало программного обеспечения для низкоуровневой поддержки интервальных типов данных, а также отношений и операций с ним. Оно реализовано для самых разнообразных платформ, причём значительная его часть распространяется свободно (см. материалы нашего сайта). Первым коммерческим языком высокого уровня, поддерживающим интервальный тип данных и интервальную арифметику, стал FORTE Fortran 95 американской Sun Microsystems Inc., выпущенный в мае 2000 года. Интересно, что львиная доля работ по созданию компилятора для FORTE Fortran 95 была выполнена в Новосибирске в компании «УниПро» (в 1997-2002 годах, под руководством А.В. Кулибабы). Этот интервальный Фортран имел богатую библиотеку встроенных функций и большое количество опций подготовки программ, а его версия для операционной системы Solaris распространялась свободно. Потом Sun Microsystems была куплена другой крупной корпорацией – Oracle, но работы по интервальной тематике некоторое время продолжались, как и продажи соответствующего программного обеспечения.
Общая методология интервального компилятора FORTE Fortran 95, его стиль и проектные особенности повлияли почти на все интервальные библиотеки и пакеты интервальной арифметики, созданные в мире после 2000 года. В частности, многие идеи из FORTE Fortran 95 вошли в стандарт IEEE-1788 на интервальные вычисления на ЭВМ, принятый уже в 2015 году. И всё же Sun Microsystems не сделала следующий логичный шаг: в дополнение к низкоуровневой языковой поддержке интервальных вычислений должен быть реализован пакет специфических интервальных алгоритмов для решения задач, часто встречающихся в практике математического моделирования. В 2005-2006 годах такой пакет интервальных алгоритмов был создан корпорацией Intel, как часть известной математической библиотеки Intel MKL версий 8.X и 9.X (и эти работы также были выполнены в Новосибирске). Но потом «рыночная логика» и пассивность службы маркетинга корпорации Intel привели к сворачиванию этих работ, а интервальные части библиотеки MKL были полностью удалены из неё — чтобы не вызывать лишних вопросов у пользователей.
В 2015 году Институтом инженеров электротехники и электроники (широко известным по аббревиатуре IEEE) был принят стандарт на интервальные вычисления на ЭВМ – IEEE 1788-2015. В нём, в частности, наряду с классической интервальной арифметикой большое внимание уделяется полной интервальной арифметиуке Каухера. В целом, текст стандарта довольно внушителен по объёму (90 страниц) и не является лёгким для освоения и реализации. По этой причине вскоре был выработан и принят более простой стандарт IEEE 1788.1-2017.