автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Твинные арифметики и их применение в методах и алгоритмах двустороннего интервального оценивания

Введение.

Глава 1. Интервальные арифметики и оценка множества значений функции.

1.1. Интервальная арифметика.

1.2. Свойства интервальной арифметики.

1.3. Задача внешней оценки множества значений функции.

1.4. Точность оценки.

1.5. Ограниченность стандартной интервальной арифметики.

1.6. Модификации стандартной интервальной арифметики.

1.6.1. Арифметики с бесконечными интервалами.

1.6.1.1. Арифметика бесконечных внутренних интервалов.

1.6.1.2. Арифметика Кахана.

1.6.2. Обобщения интервальной арифметики для учета монотонности.

1.6.2.1. Арифметика Каухера. Метод

Гарденеса и Трепата.

1.6.2.2. Направленная интервальная арифметика.

1.6.2.3. Арифметика с нестандартными операциями.

1.6.3. Машинная арифметика.

1.6.4. Апостериорный интервальный анализ.

1.7. Некоторые алгебраические вопросы.

1.8. Некоторые вопросы сложности интервальных вычислений.

Глава 2. Обобщенные интервальные арифметики и арифметики твинов.

2.1. Интервальные арифметики и учет монотонности.

2.2. Арифметика твинов.

2.2.1. Обоснование подхода.

2.2.2. Задача внутренней оценки.

2.2.3. Определение твинной арифметики.

2.3. Основные свойства твинной арифметики.

2.4. Дальнейшие обобщения.

2.4.1. Направленные твины.

2.4.1.1. Направленная твинная арифметика.

2.4.1.2. Свойства направленной твинной арифметики.

2.4.1.3. Примеры.

2.4.2. Твинная арифметика с бесконечными твинами.

2.5. Сравнение с другими подходами.

2.6. Твины и глобальная оптимизация.

2.7. Машинная твинная арифметика.

2.8. Алгебраические свойства твинных пространств.

Глава 3. Точность и сложность твинных вычислений.

3.1. Семантика твинных вычислений.

3.2. Постановка задачи и некоторые наблюдения.

3.3. Точность твинных вычислений.

3.4. Алгоритм поиска внутренней оценки, использующий разбиение исходного интервала.

3.5. Новое определение твинной арифметики.

3.6. Сложность твинных вычислений.

Глава 4. Применение твинных вычислений.

4.1. Основные области использования твинов.

4.2. Применение твинов при решении математических задач.

4.3. Твины и задачи искусственного интеллекта.

4.4. Твины и модальная математика.

Глава 5. Реализация твинных арифметик.

5.1. Язык высокого уровня для интервальных и твинных вычислений.

5.2. Язык РазсаГХБС и его окружение.

5.2.1. Общая информация.

5.2.2. Языковые особенности.

5.2.3. Специальные средства.

5.3. Расширение языка РазсаЬ-ХБС.

5.4. Модуль для работы с твинами.

5.5. Модуль для работы с направленными твинами

История развития вычислительной математики уходит корнями в глубокую древность. Вместе с тем особенно бурно развиваться эта область начала вместе с развитием вычислительных машин. Компьютеры позволили реализовать сложные вычислительные алгоритмы. Особая значимость вычислительной математики становится понятной, если принять во внимание те многочисленные практические приложения, в которых она используется.

Вычислительные алгоритмы, где бы и с какой целью они ни применялись, объединяет следующая схема использования. На вход алгоритма подаются входные данные, которые по существу являются целыми или действительными числами. Результатом работы алгоритма является другой (искомый) набор чисел. Ниже нас будут интересовать вычислительные алгоритмы, оперирующие с действительными числами. Практически все такие алгоритмы на выходе выдают не точные решения задачи, а значения, в том или ином смысле близкие к искомым. Отметим несколько причин возникновения погрешностей.

Первая причина - принципиальная неточность алгоритма. В частности, итерационные методы выдают одно за одним значения, приближающие искомое, как правило его не достигая. К примеру, метод Ньютона выдает последовательные приближения корня уравнения.

Вторая причина - невозможность точной реализации алгоритма на цифровой вычислительной машине. Даже если мы имеем точный алгоритм, не всегда можно точно вычислить результат. Пример -вычисление корней квадратного уравнения. Соответствующая формула является абсолютно точной, однако если корни уравнения иррациональны, мы можем их вычислить лишь с некоторой точностью (во всяком случае, используя традиционную арифметику на традиционной ЭВМ). Можно сказать, что источником погрешности является необходимость округления промежуточных и конечных результатов до чисел, представимых на данной машине.

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

Существует множество методов оценки качества полученного решения. Можно вспомнить методы, основанные на оценке константы Липшица для реализуемой функции, методы анализа сходимости последовательных приближений и т. д. Все они, как правило, представляют из себя оценки отличия уже полученного приближения от искомого значения. Такие методы обладают рядом недостатков. Пожалуй, основным является тот недостаток, что не для каждого алгоритма, в принципе, можно оценить погрешность приближения искомого результата. Если же такую оценку можно произвести, то зачастую затраченные вычислительные ресурсы во много раз превышают те, которые были израсходованы на само получение приближения. Вспомним также, что для любой вычислительной машины легко построить алгоритмы, которые только за счет погрешностей округления будут выдавать результат, сколь угодно далеко отстоящий от искомого.

Для того, чтобы можно было строить вычислительные алгоритмы, которые одновременно с получением результата выдают и гарантированную оценку погрешности, была высказана идея интервальных вычислений. По свидетельству некоторых исследователей, эта идея зародилась достаточно давно, но в зрелом виде она оформилась к началу 60-х годов и была высказана в монографии Р. Э. Мура [116] (см. также [88]).

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

Все три источника погрешностей числовых алгоритмов, указанные выше, могут быть учтены с помощью интервального подхода. Вместо приближенных значений, получаемых неинтервальными алгоритмами, их интервальные аналоги на каждом шаге имеют дело с интервалами, гарантированно содержащими точное значение. Погрешности округления также учитываюся - границы интервала округляются в сторону его расширения. Неточные входные данные могут быть заданы соответствующими интервалами.

К сожалению, прямой перевод алгоритмов в интервальную форму редко приводит к удовлетворительным результатам. Можно выделить две группы проблем, возникающих на этом пути. Во-первых, корректный прямой перевод не всегда возможен, например, из-за невсюду определенных интервальных операций (деление на интервал, содержащий ноль). Во-вторых, полученные интервальные алгоритмы часто не обеспечивают необходимую точность, т. е. вычисленные ими интервалы слишком широки. По этим причинам развитие интервальных методов пошло по пути создания специфических алгоритмов, специально ориентированных на работу с интервалами. Часто такие алгоритмы создавались по образу и подобию неинтервальных алгоритмов, но не простой заменой действительных переменных на интервальные переменные и точечных операций на интервальные операции, а более серьезными трансформациями.

Как уже отмечалось, историю развития интервального подхода принято отсчитывать от начала 60-х годов. Сперва наиболее популярным был термин "интервальный анализ". Позже область применения интервальных методов столь расширилась, что вошел в употребление термин "интервальная математика", подчеркивающий универсальность подхода. Пика расцвета рассматриваемая область вычислительной математики достигла, вероятно, к середине 80-х годов. После этого интенсивность исследований стабилизировалась и находится на достаточно высоком уровне.

Развитие интервального подхода наблюдалось и наблюдается в разных направлениях. Очень много сделано для его применения к решению задач линейной алгебры. Большие успехи достигнуты в развитии методов решения нелинейных алгебраических и дифференциальных уравнений. Многое сделано для развития математических основ интервальной математики, для оценки сложностных аспектов получаемых алгоритмов. На русском языке написаны две монографии по основам интервального подхода [9] и [32] и переведена основополагающая книга [1]. Хотя эти книги написаны уже достаточно давно (особенно в сравнении с быстрым развитием описываемой области математики), в них можно найти необходимые начальные сведения по рассматриваемой теме.

В последнее время получил распространение термин "надежные вычисления". Он включает в себя не только интервальные вычисления, но и другие разделы математики, обеспечивающие абсолютную надежность результатов, однако именно интервальные вычисления играют здесь основную роль. Преимуществом интервальных алгоритмов является гарантированность получаемых результатов. Из-за этого всегда особое внимание интервальным методам уделялось в прикладных исследованиях. Интервальные методы получили свое развитие в автоматическом управлении, оптимизации [4], [46], [72], экономике [79], теории экспертных систем [11], других прикладных областях. Хороший обзор приложений дается в сборнике [87] и статьях [55], [96].

Естественно, не могли пройти мимо новой области вычислительной математики и специалисты по созданию программного и даже аппаратного обеспечения [34], [103]. Были созданы специальные языки с интервальными типами данных [47], [48], [50], библиотеки численных методов [69], [70], самое разнообразное математическое и программное обеспечение для реализации интервальных алгоритмов. Были предложены специальные аппаратные средства [150], [151]. Появилось несколько программных систем, в которых интервальные типы данных и интервальные вычисления занимают центральное место [76], [140], [153]. Очень хороший обзор раннего этапа развития интервальных программ дан в работе [34]. Более современный обзор дан в работе [150]. Учебник по одному из языков программирования интервальных алгоритмов был издан недавно в России [10]. Много информации по специализированным библиотекам интервальных вычислений может быть найдено, например, в книгах [69] и [70].

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

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

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

Другой актуальной задачей является построение вычислительных алгоритмов, оперирующих с такими объектами, и позволяющих получать гарантированные оценки решений для различных задач численного анализа.

Методы и алгоритмы, первоначально предназначавшиеся для решения классических задач численного анализа, могут быть перенесены в другие области. Применение интервальных и твинных методов и алгоритмов в других областях знаний, например, в искусственном интеллекте, также является весьма актуальным.

Одновременно с разработкой вычислительных алгоритмов всегда должны рассматриваться методы их компьютерной реализации. Разработка принципов такой реализации а также создание соответствующего программного обеспечения составляют еще одну актуальную задачу.

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

Для достижения поставленной цели в работе решены следующие теоретические и практические задачи:

• введены, исследованы и разработаны теоретические основы обобщенных интервальных и твинных арифметик, для широкого класса задач построены гарантированные алгоритмы, использующие предлагаемые структуры, получены оценки точности и сложности таких алгоритмов;

• разработана методология применения предложенных методов к решению конкретных задач из области вычислительной математики и искусственного интеллекта;

• исследованы вопросы компьютерной реализации твинных алгоритмов и построена программная инструментальная система для этой цели.

Первая глава диссертации носит постановочный характер. Цель первой главы - дать определения, поставить задачи и сформулировать результаты, являющиеся отправной точкой исследований. В отличие от остальных глав, первая глава не содержит новых результатов, полученных автором.

В первых трех параграфах дано определение стандартной интервальной арифметики, приведены ее основные свойства, сформулирована задача внешней оценки множества значений функции. В четвертом параграфе приведены известные результаты, касающиеся точности решения задачи внешней оценки и изложены некоторые идеи, лежащие в основе современных методов глобальной оптимизации.

Далее рассматриваются основные недостатки, присущие стандартной интервальной арифметике. Они могут быть разделены на три категории: незамкнутость интервальной арифметики, неточность получаемых с ее помощью оценок, невозможность работы с бесконечными интервалами. Рассмотрены модификации интервальной арифметики. Описаны обобщения, оперирующие с бесконечными интервалами и обобщения, дающие возможность в некоторых случаях повысить точность оценки множества значений функции путем рассмотрения дополнительной информации, связанной с монотонностью функции. При этом удается принять во внимание взаимозависимость подвыражений выражения, задающего рассматриваемую функцию. В первой главе рассмотрена также машинная арифметика и кратко освещены вопросы компьютерной реализации. Более подробно эти вопросы обсуждены в пятой главе. Кратко излагаются идеи апостериорного интервального анализа Ю. В. Матиясевича.

В последних двух параграфах первой главы рассмотрены алгебраические свойства известных арифметик и сложностные аспекты решения некоторых задач интервальными методами.

Вторая глава содержит основные теоретические результаты, полученные автором. Основная цель главы - построить теорию твинных вычислений. Для ее достижения предложены арифметика твинов и арифметика направленных твинов, исследованы их свойства. Доказана теорема о монотонности по включению естественного твинного расширения рациональных функций. Проведено сравнение с ранее известными твинными структурами. Обоснованы принципы компьютерной реализации твинной арифметики, сохраняющей монотонность по включению.

В первом параграфе получено обобщение результата С. Маркова об оценке множества значений функции средствами интервальной арифметики с нестандартными операциями. Обобщение проведено в двух направлениях: ослаблено условие монотонности и результат доказан для более общего класса функций. Предложен графический формализм, который полезен при работе с конкретными функциями.

Далее дается определение арифметики твинов. Приводится обоснование подхода, состоящее в необходимости механизма двусторонней оценки неизвестных интервалов. Доказывается корректность введенной твинной арифметики и рассматриваются ее свойства. С одной стороны, они обосновывают использование твинов для двусторонней оценки, с другой - создают базу для дальнейшего развития теории и приложений твинной арифметики. После рассмотрения твиной арифметики проводится дальнейшие обобщения твинного подхода. Вводятся направленные твины, которые, в известном смысле, так же соотносятся с обычными твинами, как интервалы Каухера с обычными интервалами. Рассматриваются свойства направленных твинов. Приводятся примеры двусторонней оценки множества значений функции с использованием разных введенных твинных структур. Кратко рассмотрено еще одно обобщение твинной арифметики - твинная арифметика с бесконечными твинами.

Пятый параграф второй главы посвящен сравнению разработанного подхода с известным подходом Гарденеса и Трепата [63], которые также рассматривают твинные структуры. Последние три параграфа второй главы посвящены рассмотрению трех важных моментов, связанных с введенным твинным пространством. Рассмотрено соотношение твинных методов с известными методами глобальной оптимизации, рассмотрены вопросы машинной твинной арифметики, которых мы дополнительно коснемся в пятой главе, доказаны алгебраические свойства введенных твинных пространств.

Цель третьей главы диссертационной работы - исследовать вопросы точности и сложности твинных вычислений. В главе на основе полученного результата о линейной зависимости точности двусторонней оценки от величины интервала, предлагается алгоритм внутренней оценки, основанный на дроблении исходного интервала. Доказывается существование алгоритма с полиномиальным временем выполнения, который получает оценку твинной рациональной функции, причем эта оценка почти всегда точна для достаточно узких входных твинов.

Показано, что вычислительная сложность твинных алгоритмов не превосходит вычислительной сложности их интервальных аналогов.

Глава начинается с рассмотрения некоторых содержательных аспектов твинных вычислений. Далее доказывается теорема о твинных вычислениях функции с однократным вхождением каждой переменной. Доказанная теорема позволяет усовершенствовать алгоритм внутренней оценки, предложенный ранее.

Во втором параграфе третьей главы даются базовые определения точности внутренней и двусторонней оценок. Рассмотрены также точности оценок для базовых твинных операций. Полученные соотношения приводят к выводам относительно областей эффективной применимости твинных вычислений. Получена оценка точности твинных вычислений для функции, удовлетворяющей условию Липшица. Эта оценка позволяет построить эффективный алгоритм внутренней оценки, который описан в виде общей схемы с последующим разъяснением ключевых шагов.

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

В последнем, шестом, параграфе третьей главы рассматривается вычислительная сложность твинных вычислений. Показано, что оценка вычислительной сложности твинных алгоритмов сводится к аналогичной задаче для интервальных алгоритмов.

Четвертая глава посвящена применениям твинных вычислений. Наряду со второй главой она представляет собой основу диссертационной работы. Цель главы - исследовать общие принципы использования твинов и, используя разработанную теорию, указать пути решения ряда конкретных задач. Основным результатом главы является методология использования твинов в некоторых математических задачах и задачах искусственного интеллекта.

В первом параграфе формулируется основной методологический аспект использования твинов как представителей величин, имеющих интервальную природу. Указывается на аналогию с представлением вещественного значения интервалом.

Далее описывается ряд применений твинов для решения чисто математических задач (задачи двусторонней оценки множеств различной природы, двусторонней оценки решения линейной системы интервальных уравнений, задачи анализа статической системы) и задач искусственного интеллекта. Последние представляются нам наиболее перспективной областью использования полученных результатов. Помимо общих принципов использования твинов для представления интервалов сформулирован ряд конкретных задач и разработаны методы их решения. Рассмотрены, в частности, задача о представлении динамики курса акций, задача обработки экспериментальных данных о ядерных взаимодействиях, задача представления геометрии реального мира. Особое внимание уделено использованию твинов при представлении экспертных знаний в экспертных системах.

Короткий заключительный параграф четвертой главы посвящен основам модальной математики. Показано, что основная задача твинных вычислений допускает переформулировку в терминах задачи установления истинности формулы модальной математики. Такая переформулировка дает возможность установить связь между твинными вычислениями и модальным подходом, что обещает привести к взаимному переносу твинных методов в модальную математику и наоборот.

В пятой главе описана разработанная автором компьютерная реализация твинной арифметики и направленной твинной арифметики. Основная цель главы - описать предложенные автором общие принципы реализации твинных вычислений.

Реализация выполнена в среде языка РаэсаГХБС - расширения стандартного Паскаля, специально предназначенного для верифицированных вычислений, в частности включающего в себя все необходимые средства для работы с интервалами.

В начале пятой главы раскрыты преимущества и недостатки высокоуровневой реализации интервальных и твинных арифметик. Сделан вывод о том, в каких случаях предлагаемый путь реализации оказывается эффективным и имеет преимущества перед другими подходами.

Второй параграф главы содержит краткий обзор языка РаэсаГ ХБС, причем основное место уделено тем его средствам, которые представляют для нас особый интерес в рамках настоящей работы. Описаны принципы реализации языка, раскрыты его особенности, которые не имеют места в стандартном Паскале. Далее описываются специальные средства языка РавсаГХЗС, обеспечивающие обработку числовых данных с высокой точностью, и, главное, с верификацией результатов. Эта часть особенно важна для главы в целом. Изложенные в ней средства использованы автором при разработке твинной арифметики.

Отдельный параграф пятой главы посвящен архитектуре расширений языка РавсаГХЭС. В рассмотрение включены стандартные модули для работы с интервалами, поставляемые вместе с транслятором языка, созданные автором модули для расширенных интервальных арифметик, не рассматриваемые в данной работе, и два модуля для работы с твинами и с направленными твинами, являющиеся основным предметом рассмотрения главы. Описываются типы данных, основные группы операций, процедур и функций, включенные в эти два модуля.

В заключении работы сделан вывод по работе и кратко сформулированы основные ее результаты.

В двух приложениях к основному тексту диссертации собраны описания типов и заголовки описаний операций, процедур и функций, реализованных в модулях, поддерживающих работу с твинами и направленными твинами.

Заключение

В диссертации разработаны теоретические основы твинных вычислений, которые в целом представляют собой дальнейшее развитие интервальных методов в вычислительной математике. Теория твинных вычислений служит для создания новых алгоритмов, решающих актуальные вычислительные задачи, в первую очередь, задачи двустороннего интервального оценивания неизвестных числовых множеств.

Разработанная теория, в частности, включает в себя определение твинной и направленной твинной арифметик, доказательство их свойств, разработку базовых алгоритмов интервального оценивания, определение их точности и сложности, изучение возможных приложений и компьютерной реализации.

Положения теории и пути ее применения формируются следующими основными результатами.

1. Предложена твинная арифметика, доказаны ее основные свойства.

2. Исследованы задачи внутренней и двусторонней оценки множества значений функции. Разработаны методы применения твинной арифметики для решения этих задач. Доказана их корректность.

3. Предложена направленная твинная арифметика как обобщение простой твинной арифметики. Доказаны ее свойства. Показано, что применение направленной твинной арифметики позволяет повысить точность полученных оценок путем учета дополнительной информации о монотонности оцениваемых функций.

4. Предложен алгоритм поиска глобальных экстремумов на основе использования твинной арифметики и деления множества определения функции на части.

5. Показана линейная зависимость точности двусторонней оценки от интервала, на котором производится оценка, в случае, если функция удовлетворяет условию Липшица.

6. Доказано, что вычислительная сложность конкретных алгоритмов вычисления двусторонней оценки, реализованных средствами твинных вычислений, эквивалентна вычислительной сложности соответствующих алгоритмов вычисления внешней оценки, реализованных средствами интервальных вычислений. Доказано существование алгоритма с полиномиальным временем выполнения, который для рациональной функции дает почти всегда точную оценку для достаточно узких интервалов.

7. Предложен алгоритм внутренней оценки, использующий разбиение исходного интервала.

8. Исследовано применение аппарата твинных вычислений к задачам вычислительной математики (к задаче оценки решений линейных систем, задаче анализа статической системы).

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

10. Сформулированы и обоснованы основные принципы машинной твинной арифметики. На их основе построено расширение языка РаясаЬХБС, предоставляющее все необходимые средства для программирования твинных вычислений.

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. Мир, М., 1987, 360 с.

2. Ащепков Л. Т. К проблеме увеличения живучести управляемых систем. В кн: Бельтюков Б. А., Булатов В. П. (ред.). Модели и методы исследования операций. Наука, Новосибирск, 1988, с. 6985.

3. Биркгоф Г. Теория решеток. Наука, М., 1984.

4. Вощинин А. П., Сотиров Г. Р. Оптимизация в условиях неопределенности. Моск. энерг. ин-тут, М., Техника, София, 1990, 224 с.

5. Гаганов А. А. О сложности вычисления интервала значений полинома многих переменных. Кибернетика 4 (1995), с. 6-8.

6. Захаров А. В., Шокин Ю. И. Синтез систем управления при интервальной неопределенности параметров их математических моделей. Доклады Академии наук СССР 299 (2) (1988), с. 292295.

7. Зюзин В. С. Теины и методы решения системы твинных уравнений. В кн. Информационно-оперативный материал (интервальный анализ), Препринт N. 6, ВЦ СО АН СССР, Красноярск, 1988, с. 19-21.

8. Йенсен К, Вирт Н. Паскаль: руководство для пользователя. М., Финансы и статистика, 1989.

9. Калмыков С. А., Шокин Ю. И., Юлдашев 3. X. Методы интервального анализа. Наука, Новосибирск, 1986, 222 с.

10. Клатте Р., Кулиш У., Неага М., Рац Д., Улльрих X. Pascal-XSC. Руководство по языку и учебный курс. Теревинф, М., 1997, 336 с.

11. Курош А. Г. Лекции по общей алгебре. Наука, М., 1973.

12. Лакеев А. В., Носков С. И. Описание множества решений линейного уравнения с интервалъно заданным оператором и правой частью. Доклады Академии наук 330 (4) (1993), с. 430-433.

13. Матиясевич Ю. В. Вещественные числа и ЭВМ. В кн. Кибернетика и вычислительная техника, вып. 2. Наука, М., 1986, с. 104133.

14. Нариньяни А. С. Недоопределенные множества новый тип данных для представления знаний. Препринт N. 232, ВЦ СО АН СССР, Новосибирск, 1980.

15. Нариньяни А. С. Средства моделирования неполноты данных в аппарате представления знаний. В кн. Нариньяни А. С. (ред.) Представление знаний и моделирование процессов понимания. ВЦ СО АН СССР, Новосибирск, 1980.

16. Нестеров В. М. Автоматическое доказательство символьных неравенств в системе синтеза программ. В кн.: Проблемы совершенствования синтеза, тестирования, верификации и отладки программ. Т. И. Рига, 1986, с. 48-49.

17. Нестеров В. М. Автоматическое символьное решение уравнений. Дисс. канд. ф.-м. н., ЛИИАН, 1988, 144 с.

18. Нестеров В. М. Об одном обобщении интервальной арифметики. В кн.: Информационно-оперативный материал (интервальный анализ), Препринт N. 6. Красноярск, 1988, с. 31-33.

19. Нестеров В. М. Установление истинности логических выражений, составленных из неравенств. В кн.: Материалы первого Сов.-Болг. семинара по числовой обработке, 19-23 окт. 1988. Переславль-Залесский, 1988, с. 10-15.

20. Нестеров В. М. Об интервальных расширениях функций R — {true,false}. В кн.: Конференция "Интервальная математика". Саратов, 1989, с. 40-42.

21. Нестеров В. М. Интервальное вычисление логических выражений, составленных из неравенств. В кн.: Информационно-оперативный материал (интервальный анализ), Препринт N. 9. Красноярск, 1989, с. 24-26.

22. Нестеров В. М. Оценка вычислительной сложности алгоритма Мура. В кн.: Информационно-оперативный материал (интервальный анализ), Препринт N. 9. Красноярск, 1989, с. 26-28.

23. Нестеров В. М. Об одном обобщении интервального анализа и его применении для оценки множества значений функции. В кн. Математические методы построения и анализа алгоритмов. Ленинград, 1990, с. 109-124.

24. Нестеров В. М. Вычисление интервальных расширений функций с использованием обобщенных интервальных арифметик. В кн. Международная конференция по интервальным и стохастическим методам в науке и технике. Москва, 1992, с. 119-120.

25. Нестеров В. М. Интервальные арифметики и оценка множества значений функции. В кн. Р. М. Юсупов (ред.) Теоретические основы и прикладные задачи интеллектуальных информационных технологий. Санкт-Петербург, 1998, с. 280-289.

26. Никольский С. М. Курс математического анализа, Т. 1. Наука, М., 1983, 464 с.

27. Фомин Ю. Т., Шокин Ю. И. Введение в машинную интервальную арифметику. Сиб. отд. ИТМП, Новосибирск, 1983, 34 с.

28. Шарый С. П. Новый подход к анализу статических систем с интервальной неопределенностью в данных. Вычислительные технологии 2 (1) (1997), с. 71-83.

29. Шарый С. П. Алгебраический подход к анализу линейных статических систем с интервальной неопределенностью. Известия Академии наук. Теория и системы управления (3) (1997), с. 51-61.

30. Шокин Ю. И. Интервальный анализ. Наука, Новосибирск, 1981, 112 с.

31. Шокин Ю. И. Об интервальных задачах, интервальных алгоритмах и их трудоемкости. Вычислительные технологии 1 (1) (1996), с. 98-115.

32. Яковлев А. Г. Интервальные вычисления на ЭВМ. Обзор. В кн.: 1., с. 336-352.

33. Яковлев А. Г. Локусы и локализационные вычисления. В кн.: Конференция "Интервальная математика". Саратов, 1989, с. 5456.

34. Яковлев А. Г. Мультиаспектность в программировании лока-лизационных (интервальных) вычислений. В кн.: Конференция "Интервальная математика". Саратов, 1990, с. 113-120.

35. Abstracts for a workshop on interval methods in artificial intelligence. In: Abstracts for an International Conference on Numerical Analysis with Automatic Result Verification. Lafayette, LA, 1993, part 2, p. 136.

36. Adams E., Kulisch U. (eds) Scientific computing with automatic result verification. Academic Press, N. Y., 1993.

37. Alefeld G., Frommer A., Lang B. (eds) Scientific computing and validated numerics. Academie Verlag, Berlin, 1996.

38. Alefeld G., Trejo R. A. (eds) Interval computations and its applications to reasoning under uncertainty, knowledge representation and control theory. Mexico City, 1998.

39. Apostolatos N., Kulisch U. Grundlagen einer Maschmenintervallar-ithmetik. Computing 2 (2) (1967), p. 89-104.

40. Apostolatos N., Kulisch U. Approximation der erweiterten Intervallarithmetik durch die einfache Maschinenintervallarithmetik. Computing 2 (3) (1967), p. 181-194.

41. Asaithambi N. S., Shen Zuhe, Moore R. E. On computing the range of values. Computing 28 (3) (1982), p. 225-237.

42. Barth W., Nuding E. Optimale Lösung von IntervaügleichungsSystemen. Computing 12 (1974), p. 117-125.

43. Baur W., Strassen V. The complexity of partial derivatives. Theoretical Computer Science 22 (3) (1983), p. 317-330.

44. Berner S. A parallel method for verified global optimization. In: 39], p. 200-206.

45. Bleher J. H., Röder A. E., Rump S. ACRITH: High accuracy arithmetic an advanced tool for numerical computation. In: Proceedings of 7th Symposium on Computer Arithmetic, 1985, p. 318-321.

46. Bleher J. H., Rump S. M., Kulisch U., Metzger M., Ullrich Ch., Walter W. FORTRAN-SC: A study of a FORTRAN extension for engineering/scientific computation with access to ACRITH. Computing 39 (1987), p. 93-110.

47. Bohlender G. What do we need beyond IEEE arithmetic? In: 161], p. 1-32.

48. Bohlender G., Rail L., Ullrich Ch., Wolff von Gudenberg J. PASCAL-SC: A computer language for scientific computation. Academic Press, New York, 1987.

49. Caprani O., Madsen K. Mean value forms in interval analysis Computing 25 (2) (1980), p. 147-154.

50. Caprani O., Madsen K., Rail L.B. Integration of interval functions. SIAM J. of Math. Anal. 12 (3) (1981), p. 321-341.

51. Carter T. M. Cascade: Hardware for high/variable precision arithmetic. In: Proceedings of the 9th Symposium on Computer Arithmetic, 1989, p. 184-191.

52. Cohen M. S., Hull T. E., Hamacher V. C. CADAC: A controlled precision decimal arithmetic unit. IEEE Transactions oil Computers C-32 (1983), p. 370-377.

53. Corliss G. F. Industrial applications of interval techniques. In: 161], p. 91-113.

54. Dimitrova N., Markov S. M., Popova E. Extended interval arithmetics: New results and applications. In: Atanassova L., Herzberger J. (eds) Computer Arithmetic and Enclosure Methods, North-Holland, Amsterdam, 1992, p. 225-232.

55. Fagin R., Halpern J. Y., Megiddo N. A. Logic for reasoning about probabilities. In: Proceedings of 3th IEEE Symposium on Logic and Computer Science, 1988.

56. Falcö Korn C., König S., Gutzwiller S. MODULA-SC: A precompiler to Modula-2. In: 162], p. 371-384.

57. Floudas A., Pardalos P. (eds) Recent advances in global optimization. Princeton Univ. Press, Princeton, 1992.

58. Gardenes E., Mielgo H., Trepat A. Modal intervals: reason and ground semantics. In: Nickel K. (ed.) Interval Mathematics 1985, (Lecture Notes in Computer Science 212), Springer Verlag, Berlin etc., 1986, p. 27-35.

59. Gardenes E., Trepat A. The interval computing system SIGLA-PL/1(0). Freiburger Intervall-Berichte 8 (1979), 55 p.

60. Gardenes E., Trepat A. Fundamentals of SIGLA, an interval computing system over the completed set of intervals. Computing 24 (1980), p. 161-179.

61. Gardenes E., Trepat A., Janer J.M. SIGLA-PL/1: Development and applications. In: Nickel K. (ed.) Interval Mathematics, 1980, Academic Press, N.Y., 1980, p. 301-315.

62. Gardenes E., Trepat A., Janer J. M. Approaches to simulation and to the linear problem in the Sigla system. Freiburger Intervall-Berichte 8 (1981), p. 1-28.

63. Gardenes E., Trepat A., Mielgo H. Present perspective of the SIGLA interval system. Freiburger Intervall-Berichte 9 (1982), 57 p.

64. Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco, 1979.

65. Good D. I., London R. L. Computer interval arithmetic: Definition and proof of correct implementation. J. of ACM 17 (1970), p. 603612.

66. Gorodetski V. I., Nesterov V. M. Interval probabilities and knowledge engineering. In: 40], p. 15-20.

67. Hammer R., Hocks M., Kulisch U., Ratz D. Numerical toolbox for verified computing I. Basic numerical problems. Springer, Berlin etc, 1991.

68. Hammer R., Hocks M., Kulisch U., Ratz D. C+ + toolbox for verified computing. Basic numerical problems. Springer, Berlin etc, 1996.

69. Hansen E. A generalized interval arithmetic. In: Nickel K. (ed.) Interval Mathematics (Lecture Notes in Computer Science 29), Springer, Berlin, 1975, p. 7-18.

70. Hansen E. Global optimization using interval analysis. Marcel Dekker, New York, 1992.

71. Heintz J., Roy M.-F., Solerno P. On the theoretical and practical complexity of the existential theory of reals. The Computer Journal 36 (5) (1993).

72. Hung T. Nguyen, Kreinovich V., Nesterov V., Nakamura M. On hardware support for interval computations and for soft computing: theorems. IEEE Transactions on Fuzzy Systems 5 (1) (1997), p. 108-127.

73. Hyvonen E., De Pascale S. C++ library family for interval computations. In: 97], p. 85-90.

74. Hyvonen E., De Pascale S. Interval computations on the spreadsheet. In: 87], p. 169-209.

75. IEEE standard 754 for binary floating point arithmetic. American National Standards Institute, 1985.

76. Jansson C. On self-validating methods for optimization problems. In: Herzberger J. (ed.) Topics in Validated Computations, North-Holland, Amsterdam, 1994, p. 381-439.

77. Jerrell M. E. Applications of interval computations to regional economic input-output models. In: 87], p. 133-143.

78. Kahan W. P. Interval arithmetic options in the proposed IEEE floating point arithmetic standard. In: 139], p. 99-128.

79. Kaminsky T. E. Interval rounding off latice. In: International Congress on Computer Systems and Applied Mathematics. St. Petersburg, 1993, p. 90-91.

80. Kaminsky T. E. On semigroup of interval roundings. In: International Conference on Interval and Computer-Algebraic Methods in Science and Engineering. St. Petersburg, 1994, p. 129-130.

81. Kaucher E. Interval analysis in the extended interval space IR. Computing, Suppl. 2 (1980), p. 33-49.

82. Kearfott R. B., Novoa M. INTBIS, a portable interval Newton bisection package. ACM Transactions on Mathematical Software 16 (1990), p. 152-157.

83. Kearfott R. B., Dawande M., Du K., Hu C. A portable FORTRAN 77 elementary function library. Interval Computations 3 (6) (1992), p. 96-105.

84. Kearfott R. B., Dawande M., Du K., Hu C. Algorithm 737: INTLIB: A portable FORTRAN 77 interval standard function library. ACM Transactions on Mathematical Software 20 (1994), p. 447-459.

85. Kearfott R. B., Kreinovich V. (eds) Applications of interval computations. Kluwer Academic Publishers, Dordrecht etc., 1996, XIII+428 p.

86. Kearfott R. B., Kreinovich V. Applications of interval computations: An introduction. In: 87], p. 1-22.

87. Kearfott R. B. A review of techniques in the verified solution of constrained global optimization problem. In: 87], p. 23-59.

88. Keiper J. B. Interval arithmetic in Mathematica. Interval Computations 3 (1993), p. 76-87.

89. Knöfel A. Hardware kernel for scientific/engineering computations. In: 38], p. 549-570.

90. Knöfel A. Fast hardware units for the computation for accurate dot products. In: Proceedings of the 10th Symposium on Computer Arithmetic, 1991, p. 70-75.

91. Knüppel O. PROFIL/BIAS A fast interval library. Computing 53 (1994), p. 277-288.

92. Kohout L. J., Anderson J., Bandler W. Knowledge-based systems for multiple environments. Ashgate Publ. (Gover), Aldershot, 1992.

93. Kohout L. J., Stabile I. Interval-valued inference in medical knowledge-based system CLINAID. Interval Computations (3) (1993), p. 88-115.

94. Kreinovich V. Data processing beyond traditional statistics: Applications of interval computations. A brief introduction. In: 97], p. 13-21.

95. Kreinovich V. (ed.) APIC'95 international workshop on applications of interval computations. El Paso, TX, 1995.

96. Kreinovich V., Lakeyev A., Noskov S. Optimal solution of interval linear systems is intractable (NP-hard). Interval Computations 1 (1993), p. 6-14.

97. Kreinovich V., Lakeyev A., Noskov S. Approximate linear algebra is intractable. Linear Algebra and Its Applications 232 (1) (1996), p. 45-54.

98. Kreinovich V., Lakeyev A., Rohn J. Computational complexity of interval algebraic problems: some are feasible and some are computationally intractable a survey. In: 39], p. 293-306.

99. Kreinovich V., Lakeyev A., Rohn J., Kahl P., Computational complexity and feasibility of data processing and interval computations. Kluwer, Dordrecht, 1998.

100. Kreinovich V., Nesterov V. M., Zheludeva N. A. Interval methods that are guaranteed to underestimate (and the resulting new justification of Kaucher arithmetic). Reliable Computing 2 (2) (1996), p. 119— 124.

101. Kulisch U., Miranker W. L. Computer arithmetic in theory and practice. Academic Press, New York, 1981, XIII+252 p.

102. Kulisch U., Stetter H. J. (eds) Scientific computing with automatic result verification, Computing Supplementum 6, Springer-Verlag, Vienna, 1989.

103. Lakeyev A., Kreinovich V. If input intervals are small enough, then interval computations are almost always easy. In: 97], p. 134-139.

104. Laveuve S. E. Definition einer Kahan-Arithmetik und ihre Implementierung. In: Nickel K. (ed.) Interval mathematics. (Lecture Notes in Computer Science 29), Springer Verlag, Berlin etc., 1975, p. 236-245.

105. Lea R. N., Kreinovich V., Trejo R. Optimal interval enclosures for fractionally-linear functions, and their application to intelligent control. Reliable Computing 2 (3) (1996), p. 265-285.

106. Lerch M., Wolff von Gudenberg J. Multiaspect interval types. In: SCAN'98, IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, September 22-25, 1998, Budapest, Hungary. Budapest, 1998, p. 97.

107. Lohner R. J. Interval arithmetic in staggered correction format. In: 38], p. 301-321.

108. Markov S. M. Extended interval arithmetic involving infinite intervals. Mathematica Balkanica 6 (1992), p. 269-304.

109. Markov, S. On the presentation of ranges of monotone functions using interval arithmetic. Interval Computations 4 (6) (1992), p. 19-31.

110. Markov, S. On directed interval arithmetic and its applications. J. UCS 2 (7) (1995), p. 510-521.

111. Markov, S. On the foundations of interval arithmetic. In: 39], p. 307313.

112. Markov, S. Isomorphic embeddings of abstract interval systems. Reliable Computing 3 (3) (1997), p. 199-207.

113. Mints G. A short introduction to modal logic. CSLI, Stanford University, Stanford, 1992.

114. Moore R. E. Interval analysis. Prentice Hall, Inglewood Cliffs, 1966, 145 p.

115. Moore R. E. Methods and applications of interval analysis. SIAM, Philadelphia, 1979, XI+190 p.

116. Moore R. E. Reliability in computing: The role of interval methods in scientific computations. Academic Press, N. Y., 1988.

117. Nava P., Traylor J. M. Speaker independent voice recognition with a fuzzy neural network. In: Proceedings of the Fifth IEEE International Conference on Fuzzy Systems FUZZ-IEEE'96. New Orleans, September 8-11, 1996, v. 3, p. 2049-2052.

118. Nesterov V. M. Estimating a range of values of functions using extended interval arithmetics. Interval Computations 4 (6) (1992), p. 48-53.

119. Nesterov V. M. How to use monotonicity-type information to get better estimates of the range of real-valued functions. Interval Computations 4 (1993), p. 3-12.

120. Nesterov V. M. On some generalizations of interval arithmetic. In: Abstracts for an International Conference on Numerical Analysis with Automatic Result Verification. Lafayette, 1993, p. 70.

121. Nesterov V. M. Interval arithmetic of the weakly monotone functions. In: International Congress on Computer Systems and Applied Mathematics. St.-Petersburg, 1993, p. 98.

122. Nesterov V. M. Interval analogues of Hilbert's 13th problem. In: International Conference on Interval and Computer-Algebraic Methods. St.-Petersburg, 1994, p. 185-186.

123. Nesterov V. M. Implementation of generalized interval arithmetics. In: International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics. Wuppertal, 1995, p. 97.

124. Nesterov V. M. Directed twin arithmetic. In: II Workshop on Computer arithmetic, Interval and Symbolic Computation. Recife, 1996, p. 61-63.

125. Nesterov V. M., Kreinovich V. The worse, the better: A survey of paradoxical computational complexity of interval computations. In: II Workshop on Computer arithmetic, Interval and Symbolic Computation. Recife, 1996, p. 61a-63a.

126. Nesterov V. M. Interval and twin arithmetics. In: International Conference on Interval Methods and Computer Aided Proofs in Science and Engineering. Wuerzburg, 1996, p. 89-90.

127. Nesterov V. M. On accuracy of estimation in twin arithmetic. In: SCAN'97, GAMM/IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics. Lyon, 1997, p. XII-5 XII-7.

128. Nesterov V. M. Interval and twin arithmetics. Reliable Computing 3 (4) (1997), p. 369-380.

129. Nesterov V. Algebraic properties of twin spaces. In: SCAN'98, IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, September 22-25, 1998, Budapest, Hungary. Budapest, 1998, p. 121-122.

130. Nesterov V. M., Gorodetski V. I. Interval algorithm for checking the consistency of the algebraic Bayes net. In: 40], p. 28-29.

131. Nesterov V., Verchinine K. Implementation of generalized Interval Arithmetics. Technical Report. Université Paris XII, IUT, Department Informatique de Fontainebleau, 1995.

132. Neumaier A. Tolerance analysis with interval arithmetic. Freiburger Intervall-Berichte 86 (9) (1979), p. 5-19.

133. Neumaier A. Interval methods for systems of equations. Cambridge University Press, Cambridge, 1990.

134. Nguyen H. T., Kreinovich V. Nested intervals and sets: Concepts, relations to fuzzy sets, and applications. In: 87], p. 227-244.

135. Nickel K. (ed.) Interval mathematics. Academic Press, New York etc., 1980, 227 p.

136. Petunin D., Semenov A. The use of multiintervals in the Unicalc solver. In: 39], p. 91-97.

137. Rail L. B. Mean value and Taylor forms in interval analysis. SIAM J. of Math. Anal. 14 (2) (1983), p. 223-238.

138. Ratschek H., Schroder G. Centered forms for functions in several variables. J. of Math. Anal, and Applic. 82 (2) (1981), p. 543-552.

139. Ratschek H., Rokne J. New computer methods for global optimization. Wiley, New York, 1988.

140. Reyes S., Clarke M. Logic for computer science. Addison-Wesley, Wokingham, 1990.

141. Rocha L. M., Kreinovich V., Kearfott R. B. Computing uncertainty in interval based sets. In: 87], p. 337-380.

142. Rohn J. NP-hardness results for some linear and quadratic problems. Technical Report No. 619, Institute of Computer science, Academy of Sciencies of the Czech Republic, Prague, 1995, lip.

143. Rohn J. Linear interval equations: Computing enclosures with bounded relative overestimation is NP-Hard. In: 87], p. 81-89.

144. Rohn J., Kreinovich V. Computing exact componentwise bounds on solutions of linear systems with interval data is NP-hard. SIAM Journal on Matrix Analysis and Applications 16 (1995), p. 415-420.

145. Schulte M. J., Swartzlander E. E. Jr. A software interface and hardware design for variable precision interval arithmetic. Reliable Computing 1 (4) (1995), p. 324-342.

146. Schulte M. J., Swartzlander E. E. Jr. Software and hardware techniques for accurate self-validating arithmetic. In: 87], p. 381-404.

147. Schulte M. J., Swartzlander E. E. Jr. Variable-precision, interval arithmetic coprocessors. Reliable Computing 2 (1) (1996), p. 47-62.

148. Schulte M. J., Swartzlander E. E. Jr. A processor for accurate, self-validating computing. In: 39], p. 25-31.

149. Semenov A. L. Solving optimization problems with help of the Unicalc solver. In: 87], p. 211-225.

150. Shary S. P. Algebraic approach to the interval linear static identification, tolerance, and control problems, or One more application of Kaucher arithmetic. Reliable Computing 2 (1) (1996), p. 3-33.

151. Shary S. P. A new approach to the analysis of static systems under interval uncertainty. In: 39], p. 118-132.

152. Shary S. P. Algebraic solutions to interval linear equations and their applications. In: Alefeld G., Herzberger J. (eds) Numerical Methods and Error Bounds. Akademie Yerlag, Berlin, 1996, p. 224-233.

153. Shary S. P. Algebraic approach in the outer problem for interval linear equations. Reliable Computing 3 (2) (1997), p. 103-135.

154. Shokin Yu. I. On interval problems, interval algorithms and their computational complexity. In: 39], p. 314-328.

155. Skelboe S. Computation of rational interval functions. BIT 14 (1974), p. 87-95.

156. Smith D. M. Algorithm 693: A FORTRAN package for floating-point multiple-precision arithmetic. ACM Transactions on Mathematical Software 17 (1991), p. 273-283.

157. Ullrich Ch. (ed.) Computer arithmetic and self-validating numerical methods. Academic Press, New York etc, 1990.

158. Ullrich Ch. (ed.) Contributions to computer arithmetic and self-validating numerical methods. J. C. Baltzer, 1990.

159. Wolff von Gudenberg J. PASCAL-SC: A Pascal extension for scientific computation. In: Proceedings of the 10th IMACS World Congress on System Simulation and Scientific Computation. 1982, p. 402-482.

160. Wyatt W. T., Lozier D. W., Orser D. J. A portable extended precision arithmetic package and library with FORTRAN precompiler. ACM Transactions on Mathematical Software 2 (1976), p. 209-231.