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

Введение.

Глава I. Решение алгебраических систем уравнений и неравенств методом недоопределенных вычислений.

1.1. Метод недоопределенных вычислений (МНВ).

1.2. Сходимость МНВ

1.3. Область применения МНВ.

1.4. Решатель 11шСа1с.

1.5. Интервальная библиотека математических функций.

1.5.1. Общие сведения.

1.5.2. Тригонометрические функции.

1.5.3. Обратные тригонометрические функции.

1.5.4. Степенная функция.

Глава П. Анализ математических моделей и поиск решения

2.1. Локализация решения.

2.1.1. Базовый алгоритм поиска корней.

2.1.2. Выбор направления поиска для базового алгоритма.

2.1.3. Алгоритм локализации е-корня для системы двух уравнений.

2.2. Анализ чувствительности математических моделей.

2.2.1. Постановка задачи.

2.2.2. Разностный метод анализа чувствительности.

2.2.3. Интервальный метод анализа чувствительности.

2.2.4. Сравнительные возможности разностного и интервального методов анализа чувствительности моделей.

2.2.5. Система 8Б-81М.

Глава Ш. Применение МНВ для решения систем обыкновенных дифференциальных уравнений

3.1. Решение краевых задач для систем обыкновенных дифференциальных уравнений (ОДУ) с интервальными параметрами.

3.2. Анализ эффекта раскрутки для динамических систем.

3.3 Алгоритм уточнения интервального решения систем ОДУ.

Глава IV. Решение задач моделирования с применением решателя итСак

4.1. Применение аппарата недоопределенных вычислений для решения экологических проблем.

4.1.1. Особенности моделирования в области экологии.

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

4.2. Решение недоопределенных систем уравнений.

4.2.1. Постановка задачи.

4.2.2. Анализ системы.

4.2.3. Стратегия выбора последовательности переменных при локализации решения.

4.3. Задачи геометрического проектирования. Определение области пересечения пространственных трубок.

4.3.1. Метод уточнения области пересечения.

4.3.2. Описание тестовых примеров и результаты расчетов.

4.4. Обратная задача для линейной системы ОДУ.

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

4.4.2. Численный эксперимент.

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

Переход к сложным незамкнутым моделям с неточными данными потребовал разработки новых подходов к их решению. В вычислительной математике стали интенсивно развиваться интервальные методы [1, 8, 10, 40, 65], а в искусственном интеллекте были созданы различные способы представления и методы обработки неполных и неточных знаний. Одним из направлений в этой области стало развитие методов распространения ограничений, которые первоначально разрабатывались для конечных (дискретных) областей [61, 81]. Базовым элементом в этих методах является понятие метки. Метка - это пара: <х, v>, где х - переменная, v - значение из области переменной х [106]. Ограничение на множестве переменных определяется как объединение множества меток. Для моделей, представленных в виде набора ограничений, ставится задача удовлетворения ограничениям (CSP- Constraint Satisfaction Problem).

Определение (CSF). CSP - это тройка {X, D, С), где Х = {х1Ух2, ., хи)- множество переменных, Z)={DXi, DXi,., Д. } - множество значений переменных X, (xj eDx ), С = {с,, с2,., ст ] - множество ограничений.

Решением CSP называется такой вектор А-{ах, а2,., ая|е£)для которого выполняются все ограничения .

В задачах удовлетворения ограничениям различают глобальную и локальную совместности.

Определение (глобальной совместности). С SP =М= (X, D, С) называется глобально-совместной тогда и только тогда, когда любой вектор А eZ) принадлежит решению М.

Другими словами для глобальной совместности требуется одновременное выполнение всех ограничений на всех возможных наборах значений всех переменных. В отличие от глобальной совместности, для локальной совместности достаточно, чтобы некоторые группы ограничений выполнялись на всех возможных наборах значений переменных, входящих в соответствующую группу. Установление глобальной совместности является NP-полной проблемой [106], тогда как установление частичной или локальной совместности, хоть и не решает проблему полностью, однако позволяет значительно сузить область возможных решений. Важным этапом в развитии методов решения CSP стало введение А. Макворсом (А. Mackworth) понятий совместности по дугам и путям а также создание алгоритма достижения агс-совместности (известного в литературе как алгоритм АС-3), имеющего полиномиальную сложность [81]. Достаточно полное описание методов решения задач удовлетворения ограничениям для конечных областей можно найти в [106].

Позднее были созданы методы распространения ограничений над непрерывными областями, использующие интервальное представление данных [49-51, 58, 66, 75, 77, 78].

E. Davis [58] обобщил алгоритм распространения ограничений над конечными областями на непрерывные области, используя интервальные метки, т.е. метки, в которых значения переменных представлялись в виде интервалов. Ограничения для непрерывных областей более естественно определять в виде уравнений, неравенств, логических выражений.

Для CSP над непрерывными областями определяются свои виды локальной совместности. Наиболее используемыми являются Bound- consistency [77], {Interval, Hull, Box}-consistency [49], weak arc-consistency [50], {2B,3B}- consistency [77, 78].

Приведем определения наиболее распространенных видов совместностей, следуя работе [55] и используя те же обозначения.

Определение (расширения множества). Пусть S - подмножество R. Аппроксимацию S - определим как наименьший интервал I такой, что S cz/. OS - обозначает аппроксимацию S.

Определение (2В-совместности). Пусть (X, D, С) — CSP и с еС - к-арное ограничение для переменных (х,,., хк). Ограничение с 2В-совместно, если V/, DXi = D{v, sDXi 3v, еД,,., 3v,., gDx^, 3

VM G Ati+i' •••' e DXt такое, что c(vxVj.j,v.,vi+1,.,vk) выполняется}.

CSP - 2В-совместно, если все ее ограничения 2В-совместны.

В работе [78] доказано, что замыкание 2В-совместности всегда существует и единственно.

Определение (Вазе-совместности). Пусть (X, D,C) - CSP и с еС - k-арное ограничение для переменных ., х^.). Ограничение с 5ох-совместно, если для всех х; из {xj, х2,., хп j, таких что DXj =[а, выполняются следующие отношения:

1. c(DXi,.,Dx^[a,a+),DXM,.,Dx)

2. c(DXi,.,DXii,(b~,blDXM,.,DXt)

Определение {Bound-совместности). Пусть (X, D, С) - CSP и ceC - к-арное ограничение для переменных (я,,., хк}. Ограничение с Bound-совместно, если для всех хг из (г,, х2,., хи}, таких что Dx =\а, ¿] выполняются следующие отношения:

2. ФВох(с(д.,.,DXi i,(b-, b], DXm ,., ^ )) * P0, где P0 - обозначает пустую CSP, т.е. CSP имеет по крайней мере одну пустую область,

Р) - замыкание системы ограничений Р, вычисленное по алгоритму, устанавливающему совместность este.

В работе [55] сравниваются алгоритмы, устанавливающие определенные выше совместности, и доказывается, что алгоритм, устанавливающий 2В-совместность, сильнее алгоритма, устанавливающего £ох-со в местность, т.е. Ф 2в(Р) вох(Р) • Из приведенных там же результатов следует, что ФВоипа (Р) -< ФВох (Р). Если к системе ограничений Р применить декомпозицию (представить ограничения в виде бинарных и унарных отношений), то

ФВт{Р)<^2в[Р<1еоотР)

Для интервального представления переменных наиболее распространенными становятся алгоритмы установления 2В-совместности, которые в CSP для конечных областей называются алгоритмами совместности по дугам (АС-3). По сути эти алгоритмы совпадают, только применяются для различных типов данных. Ниже приведем описание алгоритма (АС-3), используя введенные выше обозначения.

PROCEDURE AC-3 ((X, D, Q) (Q - очередь)

BEGIN

Q С (все ограничения ставятся в очередь); WHILE }) DO (;пока очередь не пуста)

BEGIN с <— POP Q ; (взять из очереди ограничение с)

D <r~c(D) ;

IF D^D THEN Q<c-Qyj {все ограничения, в которых значение хотя бы одного аргумента изменилось};

END return(X, D, С)

END

В 80-х годах в лаборатории искусственного интеллекта ВЦ СО АН в рамках работ по представлению знаний А.С. Нариньяни был предложен н-метод [24-25], позднее названный методом недоопределенных вычислений (МНВ). Этот подход может рассматриваться как одно из направлений в методах распространения ограничений. В 1986г. выходит статья А.С. Нариньяни [26], в которой дается определение недоопределенных данных и недоопределенных функций, а также вводятся операции над ними. В этой статье описывается метод недоопределенных вычислений и показывается его непротиворечивость.

В вычислительном плане МНВ может рассматриваться как итерационный процесс, последовательно сужающий область, гарантированно содержащую все решения. Каждый шаг итерационного процесса представляет собой вычисление множества интервальных функций интерпретации, устанавливающих прямые и обратные функциональные соответствия между переменными. Построение функций интерпретации осуществляется по уравнениям исходной системы с помощью специального алгоритма [26]. Управление итерационным процессом осуществляется по данным, т.е. для исполнения на очередном шаге выбираются только те функции, аргументы которых были изменены в процессе вычислений на предыдущем шаге. Таким образом получаем вложенную последовательность многомерных параллелепипедов, которая по теореме Брауэра стабилизируется за конечное число шагов. В результате работы алгоритм находит 2В-совместность для декомпозированной системы , т.е. Ф2B(Pdecomp).

Отдельные аспекты метода недоопределенных вычислений исследованы в следующих работах. Д.Ушаков, используя аппарат многосортных алгебраических моделей, доказал независимость результата от порядка вычислений [107]. Е. Петровым [32] получены условия сходимости МНВ для систем линейных алгебраических уравнений (СЛАУ) с точными значениями коэффициентов и правых частей. В совместной работе автора с A.JI. Семеновым [13] для уравнения от одной переменной получен критерий сходимости МНВ к решению, из которого следует, что область сходимости МНВ шире, чем метода последовательных приближений.

Практическое применение МНВ нашел во многих прикладных системах [103]. И.Е. Швецовым в начале 80-х годов была создана прикладная система «Фабрика» [37], которую можно рассматривать как прототип системы NEMO-TEC [38], а затем современной NEMO+ [105].

В 1985г. И.Е. Швецовым, и В.В. Телерманом была разработана макетная версия вычислителя математических задач [37], в котором МНВ был реализован для интервального представления недоопределенных данных. Этот вычислитель послужил прототипом первой версии решателя UniCalc [3, 42].

В настоящее время UniCalc представляет собой кооперативный решатель, в который наряду с алгоритмом МНВ встроены различные методы интервальной математики, компьютерной алгебры и алгоритмы локализации корней [97]. Такая организация вычислителя

UniCalc позволила во многих случаях решать задачи, непосильные для традиционных вычислительных методов [17] и сделать этот решатель коммерческим продуктом, конкурентоспособным на российском и зарубежном рынках.

В качестве вычислительной базы UniCalc используется другими прикладными системами:

• интервальными электронными таблицами [29],

• системой ТАО - технологией активных объектов [39],

• TIME-EX - системой календарного планирования [27].

Интервальная библиотека математических функций UniCalc впоследствии была встроена в прикладные системы NEMO+ и Eclipse.

Опыт практического использования метода недоопределенных вычислений в сочетании с методами интервальной математики во многих программных реализациях подтвердил на практике его применимость для решения широкого спектра задач и показал перспективность интервального подхода в CSP.

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

Первые работы в области интервального анализа были связаны в основном с обобщением существующих вычислительных алгоритмов на интервальное представление данных. Работы P.E. Мура [41, 82], которые были первыми в этой области, показали перспективность использования интервального анализа в вычислительных процессах и обозначили возникающие здесь проблемы (неоправданное расширение оценочной области решения). Первой монографией по интервальному анализу на русском языке была вышедшая в 1981г. книга Ю.И. Шокина [40], в которой рассматривались вопросы интервального анализа и применение интервального подхода к решению дифференциальных уравнений.

Обзор литературы по интервальным методам проведем по трем направлениям:

• решение систем линейных алгебраических уравнений,

• решение систем нелинейных алгебраических уравнений,

• решение систем обыкновенных дифференциальных уравнений.

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

Внешняя интервальная" задача ставится как определение следующего множества

В работах [19-20, 74] показано, что задача вычисления оптимальных покоординатных оценок объединенного множества решений и даже распознавание того, является ли множе

Ах = b,

98, 99]: ство пустым или нет, оказывается NP-полной. Для нахождения оптимального решения "внешней задачи" С.П. Шарым предложен РББ- алгоритм, основанный на методе ветвей и границ, сложность которого пропорциональна 2й [99].

И. Роном предложен алгоритм решения "внешней задачи", сводящий интервальную задачу для системы п уравнений от п переменных к решению не более чем 2" систем уравнений с точными коэффициентами и правыми частями, трудоемкость которого пропорциональна в худшем случае 4" [90].

Задача о внутреннем интервальном оценивании "допустимого множества решений" ставится как нахождение множества ^уз(а, ь)=^]уз = е К"|(\//4 еА)(з/> еЬ)(^х= (в

36] оно называется живучим множеством решений).

3. Румп получает внутреннюю интервальную оценку решения на основе точечного решения, строя расширяющуюся интервальную последовательность [92].

Задачи внутреннего и внешнего оценивания интервальных СЛАУ подробно рассматриваются А. Ноймайером в [87]. В частности, в этой работе исследуется интервальный метод Гаусса-Зейделя и доказывается, что если матрица А размерности пхп не является Н-матрицей, то существуют сколь угодно широкие правильные интервальные векторы, которые не улучшаются интервальным методом Гаусса-Зейделя, примененным для внешнего оценивания объединенного множества решений.

В последнее время получены интересные результаты для интервальных СЛАУ в расширенной интервальной арифметике Каухера. С.П. Шарый [36] показал, что с помощью алгебраических решений в расширенной интервальной арифметике Каухера можно находить внутреннее и внешнее оценивание обобщенных множеств решений интервальных СЛАУ, и предложил субдифференциальный метод Ньютона, позволяющий получать оценки с высокой вычислительной эффективностью. С помощью этого подхода почти всегда можно получить максимальные по включению внутренние интервальные оценки для множеств решений интервальных СЛАУ. А. В. Лакеевым получены условия существования и единственности решения для интервальных матриц постоянных знаков [21].

Переходя к интервальным методам решения нелинейных систем уравнений, отметим, что интервальный метод Ньютона позволяет найти оптимальную внешнюю оценку решения. В вычислительной математике наиболее распространенным методом решения нелинейных систем является метод Ньютона [4], который имеет квадратичную скорость сходимости, если определитель матрицы Якоби пересчитывается на каждом шаге. Метод Ньютона сходится, если якобиан отличен от нуля и нулевое приближение выбрано удачно. Этот метод требует предварительного качественного исследования решения и позволяет находить лишь приближенное, хоть и с высокой точностью, значение корня. Если нам требуется гарантированное значение решения, то применяется интервальный метод Ньютона [1, 82, 86], который определяется следующей итеративной формулой:

1 = [т(хк) ~ {р'(**)) ' Р(гп{хк ))}ГК, к > 0, где х0 - начальный интервал, который должен содержать не более одного корня; -обратное значение интервального расширения матрицы Якоби системы уравнений Г(х) = 0; т(х) - вектор средних значений интервального вектора х.

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

Для решения нелинейных алгебраических систем общего вида нет способов, позволяющих определить число решений в заданной области, и более того, нет даже критерия несовместности системы. В некоторых случаях ответить на вопрос о наличии корней помогает вычисление степеней отображения (topological degree) [108]. В [35] строится символьное решение систем двух полиномиальных уравнений и получен критерий количества решений. В общем же случае задача решения полиномиальных систем является NP-полной проблемой [67]. Таким образом, разработка алгоритмов, не требующих предварительного исследования на наличие корней, является весьма актуальной проблемой.

Для нахождения корней одного уравнения / (х) = 0 Е. Р. Хансеном [62, 64] предложен алгоритм, итерационный процесс которого определяется формулой: [т(хк) - f(m(xk)) / / '(хк )} П хк, к > 0, где х0 - начальный интервал, f - интервальное расширение первой производной, а т(х) -среднее значение интервала х. Этот метод можно рассматривать как модификацию метода Ньютона для случая одной переменной, в котором предполагается использование расширенной интервальной арифметики, что позволяет осуществлять деление на интервал, содержащий ноль. Таким образом, алгоритм Е. Р. Хансена дает возможность находить все корни уравнения без предварительного выделения областей с одним решением.

Для систем алгебраических уравнений Р. Кравчик [72] предлагает модифицированный интервальный метод Ньютона, в котором вычисление обратной интервальной матрицы заменяется ее оцениванием. Улучшением этого алгоритма является алгоритм Хансена-Сенгупты [63], однако в случае большого начального интервала данный алгоритм может не сойтись к корню. Позднее появляются различные улучшения и модификации вышеупомянутых алгоритмов, связанные в основном с более точным оцениванием обратной интервальной матрицы [73, 86, 87, 110]. Модифицированные методы Ньютона в сочетании с би-секцией области позволяют гарантированно находить все решения системы нелинейных алгебраических уравнений в рассматриваемой области, тем не менее, пока остается окончательно не решенной проблема эффективного нахождения кратных корней.

Применение интервальных методов для решения дифференциальных уравнений позволяет получить гарантированные оценки решений. Следует, однако, отметить, что использование прямых пошаговых интервальных методов приводит к неоправданному расхождению границ получаемого интервального решения. Этот эффект (wrapping effect) был замечен P.E. Муром [82] (в литературе на русском языке можно встретить его различные названия - эффект раскрутки Мура, эффект упаковывания, эффект обертывания). Поэтому наибольший интерес представляют алгоритмы, устраняющие эффект расширения интервального решения.

В работе [7] доказано, что для отсутствия интервального эффекта Мура относительно интервального пространства Jo в i = f(x) необходимо и достаточно, чтобы матрицы Якоби отображения / во всех точках множества В, являющегося компактным выпуклым телом из R" , были диссипативны относительно Jo. В частности, для системы y = A{t)y диссипативность А относительно нормы 11| означает в точности следующее: ||еж|| < 1 при всех t>0.

В развитии интервальных методов решения дифференциальных уравнений можно выделить три основных направления:

• разработку интервальных итерационных алгоритмов путем обобщения вещественных итерационных алгоритмов с использованием теоремы включения (итерации Пикара или Ньютона) [48, 70];

• применение интервального аналога конечно-разностных методов с оценкой глобальной ошибки [57, 59, 109];

• использование разложений в ряды Тейлора (следуя P.E. Муру) с оценкой остаточного члена [23, 56, 79, 80, 82].

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

В работах [56, 79, 80] рассматривается модифицированный метод Тейлора для получения гарантированного решения. Интервальные аналоги конечно-разностных методов с оценкой остаточных членов используются в [59, 109]. Р. Лонер [79, 80] использует итерационный алгоритм Пикара и разложения Тейлора, внеся в них некоторые усовершенствования. На основе разработанных им алгоритмов создана программа А\¥А. Достаточно полный обзор работ зарубежных ученых по интервальным подходам к решению ОДУ можно найти в [89]. В работе [85] отражены последние результаты, достигнутые в области развития интервальных алгоритмов решения ОДУ. В частности, в этой работе можно найти описание алгоритма Лонера, различные модификации алгоритмов, основанных на разложении Тейлора, и усовершенствованные интервальные итерационные алгоритмы Пикара.

Как альтернативу пошаговым методам интегрирования можно рассматривать получение двусторонних оценок решения, методика которых появилась раньше интервальных подходов. Для получения двусторонних оценок используют операторные неравенства, оценки остаточных членов, априорные и апостериорные оценки и т.д. К недостаткам этих методов можно отнести то, что 1) они используют, как правило, точные входные данные и 2) некоторые приемы гарантируют включение точного решения только в асимптотике (при стремлении шага сетки к нулю). В работах [8, 60] сделана попытка объединить интервальные подходы с двусторонними методами, в основном с апостериорным анализом.

Одним из перспективных подходов к решению задачи Коши для систем ОДУ является получение аналитического выражения решения [30, 33-34]. Для нахождения символьных формул приближенных решений в [33] изложена методика применения сплайн-коллокаций. В работе [34] предлагается метод, основанный на аппроксимации оператора сдвига вдоль траектории и символьных формулах его представления сплайнами с последующим интервальным оцениванием. Нелинейная правая часть аппроксимируется линейно на каждом шаге интегрирования. Такой подход снимает проблему пошагового интервального расширения, однако не решает всех проблем, связанных с интервальным оцениванием решений, в частности, при решении жестких систем и систем уравнений с осциллирующим решением.

Приведенный обзор работ по интервальным подходам, разрабатываемым в области искусственного интеллекта и интервальной математики, демонстрирует широкий спектр методов исследования незамкнутых математических моделей с неопределенностью в данных и получения их гарантированных решений. Разработанные методы составляют основу кооперативных решателей, разрабатываемых в настоящее время [71, 91, 97].

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

Диссертационная работа состоит из введения, четырех глав и заключения. Общий объем работы - 127 страниц. Работа включает 6 таблиц и 3 рисунка.

Заключение

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

Полученные в диссертации результаты имеют как теоретическую, так и практическую значимость. Разработка методов решения недоопределенных систем выполнялась в рамках договора с компанией Dassault Aviation (Франция). Алгоритм определения области пересечения двух пространственных трубок был разработан в ходе выполнения совместного проекта с компанией Dassault Systèmes (Франция). Необходимость решения обратной дифференциальной задачи возникла, в частности, при уточнении траектории полета спутника. Эта задача решалась в рамках научного сотрудничества с Исследовательским институтом прикладных систем обработки знаний (FAW, г. Ульм, Германия).

В заключение перечислим основные результаты. 1. Исследована сходимость метода недоопределенных вычислений (МНВ). Для уравнения от одной переменной с монотонной левой частью доказана теорема сходимости МНВ. Проведены вычислительные эксперименты на UniCalc, оценивающие точность и область применимости МНВ (совместно с Семеновым А.Л.).

115

2. Разработана библиотека интервальных математических функций, которая встроена в решатель UniCalc. Создан набор тестов для полного тестирования библиотеки (совместно с Семеновым A.JL).

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

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

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

6. На основе МНВ решен ряд сложных практических задач с использованием решателя UniCalc.

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

2. Андреев В.В. Разработка гибких программных средств имитационного моделирования процессов в водных экосистемах // Математические проблемы экологии: Тез. докл. -Новосибирск, ИМ СО РАН. 1992. - С. 42-43.

3. Бабичев А.Б., Кадырова О.Б., Кашеварова Т.П., Семенов А.Л. UniCalc инструмент для решения задач с неточными и недоопределенными данными // Среда программирования: методы и инструменты. - Новосибирск, 1992. - С. 8-11.

4. Бахвалов Н.С., Жидков Н.П., Кобельников Г.М. Численные методы. М.: Наука, 1987. - 600с.

5. Белолипецкий В.М., Шокин Ю.И. Математическое моделирование в задачах охраны окружающей среды. Новосибирск: ИНФОЛИО-пресс, 1997. - 240с.

6. Березин И.С., Жидков Н.П. Методы вычислений. Т. 2. -М.: Физматгиз, 1959. 620 с.

7. Вербицкий В.И., Горбань А.Н., Усюбаев Г.Ш., Шокин Ю.И. Эффект Мура в интервальных пространствах //Докл. АН СССР. 1989. - Т. 304, № 1. - С. 17-22.

8. Добронец Б.С., Шайдуров В.В. Двусторонние численные методы. -Новосибирск: Наука. Сиб. отд-ние, 1990. 208с.

9. Иванов И.С., Кашеварова Т.П. Интервальный метод анализа чувствительности математических моделей // Тр. междунар. конф. «Проблемы управления и моделирования в сложных системах», Самара, 15-17 июня, 1999. Самара, 1999. - С. 291-296.

10. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. -Новосибирск: Наука. Сиб.отд-ние, 1986, -221с.

11. Кашеварова Т.П., Семенов А.Л. Решение недоопределенных задач для систем обыкновенных дифференциальных уравнений первого порядка в системе 11шСа1с // Материалы Всесоюз. научно-техн. конф., Самара, июнь 1991 г. Самара, 1991. - Ч.З. -С. 21-24.

12. Кашеварова Т.П., Семенов А.Л. О решении задач математического моделирования природных явлений методом недоопределенных вычислений // Информатика окружающей среды: введение в проблематику. Москва-Новосибирск: РосНИИ ИИ, 1994. - С. 58-69.

13. Кашеварова Т.П., Семенов А.Л. Некоторые вопросы сходимости метода недоопределенных вычислений // Проблемы представления и обработки не полностью определенных знаний. Москва-Новосибирск: РосНИИ ИИ, 1996. - С. 31-37.

14. Кашеварова Т.П., Семенов А.Л., Швецов И.Е. Моделирование динамических процессов методом недоопределенных вычислений // Тез. докл. III Сибирского конгресса по прикладной и индустриальной математике (ИНПРИМ-98). Новосибирск, 1998. - Т. V. -С. 16.

15. Кашеварова Т.П. Использование метода недоопределенных вычислений для анализа чувствительности математических моделей // Вычислительные технологии. -Новосибирск, 1999. Т. 4, № 4. - С. 24-32.

16. Кашеварова Т.П. Алгоритм уточнения интервального решения систем обыкновенных дифференциальных уравнений // Тр. междунар. конф. «Проблемы управления и моделирования в сложных системах», Самара, 15-17 июня, 1999. Самара, 1999. - С. 281-286.

17. Кашеварова Т.П. Использование системы ОшСа1с для решения задач математического моделирования. Новосибирск, 1999. - 34с. - (Препр. / РАН. ИСИ; № 64).

18. Ладыженская O.A. Краевые задачи математической физики. М.: Наука, 1973. - 407с.

19. Лакеев A.B., Носков С.И. Описание множества решений линейного уравнения с интервально заданными оператором и правой частью // Докл. Академии Наук. 1993. -Т. 330, № 4. - С. 430-433.

20. Лакеев A.B., Носков С.И. О множестве решений линейного уравнения с интервально заданными оператором и правой частью // Сиб. матем. журн. -1994. № 35. - С. 10741084.

21. Лакеев A.B. Существование и единственность алгебраических решений интервальных линейных систем в полной арифметике Каухера // Вычислительные технологии. -Новосибирск, 1999. Т.4, № 4. - С. 33-44.

22. Математическое моделирование. Процессы в сложных экономических и экологических системах / Под ред. Самарского A.A., Моисеева H.H., Петрова A.A. М.: Наука, 1986. -296с.

23. Меньшиков Г. Г. Интервальный анализ и методы вычислений. Конспект лекций. Вып. 9. Элементы локализующего интегрирования дифференциальных уравнений. -СПб, 1998. 98с.

24. Нариньяни A.C. Средства моделирования неполноты знаний в аппарате представления знаний // Представление знаний и моделирование процесса понимания. Новосибирск, 1980.

25. Нариньяни A.C. Недоопределенные модели и операции с недоопределенными значениями. Новосибирск, 1982. - 33 с. - (Препр. / АН СССР СО. ВЦ; № 400).

26. Нариньяни A.C. Недоопределенность в системах представления и обработки знаний // Изв. АН СССР. Техн. Кибернетика. 1986. - №5. - С. 3-28.

27. Нариньяни A.C., Иванов Д.А., Седреев C.B., Фролов С.А. Недоопределенное календарное планирование: новые возможности // Информационные технологии. М. : Машиностроение, 1997. - № 1.

28. Нариньяни A.C., Телерман В.В., Ушаков Д.И., Швецов И.Е. Программирование в ограничениях и недоопределенные модели // Информационные технологии. М.: Машиностроение, 1998. - № 7. - С. 13-22.

29. Нариньяни A.C., Корниенко В.В., Прейс C.B., Швецов И.Е. ФинПлан: новая технология финансово-экономического планирования в условиях неполноты информации // Информационные технологии. М.: Машиностроение, 1998. - № 11. -С. 10-17.

30. Новиков В.А., Рогалев А.Н. Построение сходящихся верхних и нижних оценок решений систем обыкновенных дифференциальных уравнений // Журн. вычисл. матем. и матем физ. 1993. - Т. 33, № 2. - С. 219-231.

31. Оран, Дж. Борис. Численное моделирования реагирующих потоков: Пер. с англ. М.: Мир, 1990.

32. Петров Е.С. Сходимость метода недоопределенных вычислений при решении линейных уравнений // Проблемы представления и обработки не полностью определенных знаний. Москва-Новосибирск: РосНИИИИ, 1996. - С. 41-51.

33. Рогалев А.Н. Нахождение оптимальных гарантированных оценок множеств решений систем ОДУ с интервальными данными // Вычислительные технологии. -Новосибирск, 1995. Т.4, № 13. - С. 58-64.V

34. Рогалев А.Н., Шокин Ю.И. Исследование и оценка решений обыкновенных дифференциальных уравнений интервально-символьными методами // Вычислительные технологии. Новосибирск, 1999. - Т.4, № 4. - С. 51-75.

35. Утешев А.Ю., Черкасов Т.М. Локализация решений систем алгебраических уравнений и неравенств // Докл. АН. 1996. - Т. 347, № 4. - С. 451-453.

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

37. Швецов И.Е. Разработка программных обстановок для недоопределенных иоделей // Конструирование программных средств интеллектуализации / Под ред. Нариньяни А.С., Левина Д.Я. Новосибирск, 1988. - С. 124-136.

38. Швецов И.Е, Дмитриев В.Е., Телерман В.В. Технологический комплекс для разработки интеллектуальных систем на основе недоопределенных моделей // Тез. докл. Всесоюз. конф. по искусственному интеллекту, Переславль-Залесский, 1988. -М., 1988. С. 343347.

39. Швецов И.Е., Нестеренко Т.В., Старовит С.А. ТАО технология активных объектов для разработки многоагентных систем // Информационные технологии и вычислительные системы. - РАН, Москва. - 1998. - № 1. - С. 35-44.

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

41. Asaithambi, Shen Zuhe, R. Moore. On computing the range of values // Computing. 1982. -Vol. 28. - P. 225-237.

42. Babichev, 0. Kadyrova, T. Kashevarova, A. Semenov. UniCalc as a tool for solving problems with inaccurate and subdefinite data // Proc. Conf. Interval'92. Interval Computations. -1992.-Vol. 3(5). - P.13-16.

43. Babichev, T. Kashevarova, A. Semenov. Solving Computational Problems by the Method of Constraint Propagation // SAMS 1995. - Vol. 18-19. - P. 187-190. (Proc. of IMACS-SAS'95).

44. Bauch, H. On the Iterative Inclusion of Solutions in Initial-Value Problems for Ordinary Differential // Computing. 1979. - Vol. 22. - P. 339-354.

45. Benhamou F., McAllester D., Van Hentenryck P. CLP(Intervals) Revisited // Proc. of ILPS'94, Ithaca, NY, USA, 1994. P. 124-138.

46. Benhamou F., Older W. Applying Interval Arithmetic to Real, Integer and Boolean Constraints // Journal of Logic Programming, 1997.

47. Buckle T., Skuppin R. Use of CLP programs for solving satellite attitude control problems. ESPRIT Project #5246 PRINCE, Draft. FAW, Ulm, June 1993.

48. Buckle T., Skuppin R. Estimating Gyro errors by solving an ordinary differential equation boundary value problem. Daimler-Benz Aerospase AG, 1994. - 73p.

49. Collavizza H., Delobel F., Rueher M. A note on partial consistencies over continuous domains //Proc. CP98, Pisa, Italy, October26-30, 1998. -MaherM., Puget. J.-F. (Ed.). -P 147-161.

50. Corliss G., Chng Y. Solving ordinary differential equation using Taylor series // ACM Trans. Math. Software. 1982. - Vol. 8. - No. 2. - P. 114-144.

51. Corliss G. Theory of numerics in ordinary and partial differential equation / W.A. Light, M. Machetta (Eds). Vol. IV. - P. 1-75. - Oxford University Press, 1995.

52. Davis E. Constraint propagation with interval labels // Artificial Intelligence. 1987. - Vol. 32. -P. 99-118.

53. Deville Y., Janssen M., Van Hentenryck P. Consistency techniques in ordinary differential equation // Proc. CP98, Pisa, Italy, October 26-30, 1998. Maher M., Puget. J.-F. (Ed). - P. 162-176.

54. Dobronets B.S. On some two-sided methods for solving systems of ordinary differential equations // Interval Computations. 1992. - № 1. - P. 6-21.

55. Freuder E. Synthesizing Constraint Expression // CACM. 1978. - Vol. 21(11). -P. 958-966.

56. Hansen E.A. A globally convergent interval method for computing and bounding real roots // BIT. 1978. - Vol. 18. - P. 415-424.

57. Hansen E.A., Sengupta S. Bounding solutions of systems of equations using interval analysis // BIT. 1981. - Vol. 21. -P. 203-211.

58. Hansen E.A., Greenberg R.I. An interval Newton method // Appl. Math. Comput. 1983. -Vol. 12. - P. 89-98.

59. Hansen E. Global Optimization Using Interval Analysis. New York: Marcel, Dekker, 1992.

60. E. Hyvonen. Constraint reasoning based on interval arithmetic. The tolerance propagation Approach // Artificial Intelligence. 1992. - Vol. 58. - P. 71-112.

61. Jager C., Ratz D. A combined method for enclosing all solutions of nonlinear systems of polynomial equations // Reliable Computing. 1995. - Vol. 1(1). - P. 41-64.

62. Kashevarova T., Semenov A. Solution of Problems of Mathematical Modeling of Natural Phenomena with the Method of Subdefinite Computations // Proc. of 9th Intern. Symp. On Computer Science for Environmental Protection, Berlin, Germany, 1995. P. 361-369.

63. Kaucher E. Methoden zur Lusung von Ingral-und-Gleichungen // Math. Res. -1989. № 58. -P. 225-238.

64. Kearfott R.B. Rigorous global search: Continuous problems. Kluwer, Dordrecht, 1996.

65. Krawczyk R. Newton-Algorithmen zur Besimmung von Nullstellen mit Fehlerschranken // Computing. 1969. - Vol. 4. - P. 187-201.

66. Krawczyk R. A class of interval Newton operators // Computing. 1986. - Vol. 37. - P. 179183.

67. Kreinovich V., Lakeev A. V., Noskov S.I. Optimal solution of interval linear systems is intractable (NP-hard) // Interval Computations. 1993. - No. 1. - P. 6-14.

68. V. Kumar. Algorithms for constraint-satisfaction problems: a survey // AI Magazine. Spring, 1992.-Vol.13.-P. 32-44.

69. Loenko M. Solving systems of nonlinear equations with methods using interval constraint propagation// SCAN-98, Budapest, Hungary, 1998. P. 98-99.

70. Lhomme 0. Consistency Tecniques for Numeric CSP's // Proc. of the 13th IJCAI, 1993 / R. Bajcsy (Ed). IEEE Computer Society Press, 1993. - 232-238.

71. Lhomme O. Contribution a la resolution de contraintes sur les reels par propagation d'intervalles: PhD Thesis. University of Nice Sophia Antipolis, France, 1994.

72. Lohner R. J. Enclosing the solution of ordinary initial and boundary value problems // Kaucher E., Kulisch U., Ullrich Ch. (Eds.): Computer arithmetic: Scientific Computation and Programming Languages. Stuttgart: B.G. Teubner, 1987. - P. 255-286.

73. Lohner R. J. On step size and order control in the verified solution of ordinary initial value problems // SCAN-93, Vienna, 1993.

74. Macworth. Consistency in Networks of Relations // Artificial Intelligence. 1977. - Vol. 8(1). - P.99-118.

75. Moore R.E. Interval analysis. -Englewood Cliffs, N.-J.: Prentice Hall, 1966.

76. Nedialkov N.S., Jackson K.R., Corliss G.F. Validated solutions of initial value problems for ordinary differential equation // Submitted to SIAM Review, February 1997. 40p.

77. Neumaier A. Interval iterations for zeros of systems of equations // BIT. 1985. - No. 25. - P. 256-273.

78. Neumaier A. Interval methods for systems of equation. Cambridge University Press, 1990.

79. Petunin D., Semenov A. The Use of Multi-Intervals in the UniCalc Solver // Scientific Computing and Validated Numerics / G. Alefeld, A. Frommer and B. Lang (Eds). Berlin: Akademie Verlag, 1996. - P. 91-97.

80. Rihm R. Interval methods for initial value problems in ODEs // Topics in Validated Computations / J. Herzberger (Ed.). Elsevier Science B.V., 1994. - P. 173-207.

81. Rohn J. Systems of linear equations // Linear Algebra Appl. 1989. - Vol. 126. - P. 39-78.

82. Rueher M. An Architecture for Cooperating Constraint Solvers // Constraint Programming: Basic and Trends / A. Podelski (Ed.). Lecture Notes in Computer Science. - SpringerVerlag, 1995. - Vol. 910. - P. 231-250.

83. Rump S.M. Solution of linear and nonlinear algebraic problems with sharp guaranteed bounds // Computing Suppl. 1984. - Vol. 5. - P. 147-168.

84. Semenov A. Solving Integer/Real Nonlinear Equations by Constraint Propagation. // Technical Report No. 12, Institute of Mathematical Modelling, The Technical University of Denmark. -Lyngby, Denmark, 1994. 22 p.

85. Semenov A.L., Leshchenko A.S. Interval and Symbolic Computations in the UniCalc Solver // Intern. Conf. on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL-94), St-Petersburg, Russia, March, 1994 (Abstracts). P. 206-208.

86. Shary S.P. A new class of algorithms for optimal solution of interval linear systems // Interval Computations. 1992. - Vol. 2, No. 4. - P. 11-22.

87. Shary S.P. On optimal solution of interval linear equation // SIAM J. Numer. Anal. 1995. -Vol. 32. - P. 610-630.

88. Sloan S.W. An algorithm for profile and wavefront reduction of sparse matrices// Intern, journal for numerical methods in engineering. 1986. - Vol. 23. - P. 239-251.lOl.Strohm J. Population Model, Draft. -FAW, Ulm, 1997.

89. Stroud A.H., Secrest D. Gaussian Quadrature Formulas. Prentice-Hall, Inc., N.Y., 1966.

90. Shvetsov I., Semenov A., Telerman V. Application of Subdefinite Models in engineering // Artificial Intelligence in Engineering. 1997. - Vol. 11(1). - P. 15-24.

91. Tsang E. Foundation of Constraint Satisfaction. London: Academic Press Ltd., 1993.

92. Ushakov D. Some Formal Aspects of Subdefinite Models. Novosibirsk, 1998. - 23 p. -(Prepr. / Siberian Division of Russian Acad. Sci. IIS; No. 49).

93. Vrahatis M.N. Solving systems of nonlinear equations using the nonzero value of the topological degree // ACM TOMS. 1988. - Vol. 14. - P. 312-329.

94. Wayne H. Enright. Analysis of Error Control Strategies for Continuous Runge-Kutta Methods // SIAM J. Numerical Analysis. June, 1989. - Vol. 26. - P. 588-599.

95. Wolfe M.A. A modification of Krawczyk's algorithm // SIAM Journal on Numerical Analysis. -1980.-Vol. 17.-P. 376-379.