Верхние и нижние оценки множеств решений систем обыкновенных дифференциальных уравнений с интервальными параметрами тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Р Г о С Д

¡а правах рукописи УДК 519.6

РГо О А

РОГАЛЁВ АЛЕКСЕЙ НИКОЛАЕВИЧ

ВЕРХНИЕ И НИЖНИЕ ОЦЕНКИ МНОЖЕСТВ РЕШЕНИЙ

СИСТЕМ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ИНТЕРВАЛЬНЫМИ ПАРАМЕТРАМИ

01.01.07 - вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск 1996

Работа выполнена в Красноярском государственном университете, г. Крас

ярск.

Научный руководитель: академик РАН, профессор Ю.И.Шокпн .

Официальные оппоненты: доктор физико-математических наук, профессор В.В. Шаядуров, кандидат физико-математических наук , доцент В.В. Кобков

Ведущая организация: Институт математики СО РАН (г. Новосибирск)

15 СЮ

Iи часов

Защита состоится "1 * июля 1996г. в

[О часов ^ мин.

на заседании специализированного совета К064.61.01 по защите диссертас на соискание ученой степени кандидата физико-математических наук при Красноярск государственном университете

(660041, Красноярск , проспект Свободный 79)

С диссертацией можно ознакомиться в библиотеке Красноярского госуд. ствеииого университета

Автореферат разослан ^л!-1996г

Ученый секретарь

специализированного совета

К 064.61.01 в Красноярском госуниверситете

кандидат физико-математических наук Е.К.Лейнартас

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Алгоритмы гарантированных вычисле-й приобретают все большее- значение в численном моделировании за-I естествознания, техники, управлений, анализа информации . Это [зано со многими причинами, в том числе с необходимостью учета ве-гности входных параметров задачи, для которых могут быть заданы пь содержащие их множества (оценки), а также с процессом разви-I новой компьютерной техники, позволяющей привлекать все более иные процессоры с большим быстродействием и длиной машинно-слова. Тем самым; наряду с преимуществами, проявляющимися в пении многих сложных практических задач, мы сталкиваемся со все [ьшим влиянием малых ошибок при выполнении машинных операций к называемые ошибки округления).

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

Научная новизна и практическая ценность. Основные ультаты диссертации являются новыми и имеют как теоретиче-ю, так и практическую ценность. Обоснована сходимость лнтер-ъеых оценок к множеству точных решений в хаусдорфовой метрике, : этом определение решения содержит объединенное интервальное □игрение, п доказаны теоремы о покоординатной сходимости этих егок к множеству точных решений. Тем самым, предлагается под, 'позволяющий преодолеть влияние эффекта Мура, проявляющего-зо всех существующих алгоритмах нахождения двусторонних оце-решений систем обыкновенных дифференциальных уравнений. 06: схема этого алгоритма объединяет.нахождение символьных формул шн-функдпп, аппроксимирующих решение по методу коллокагога, и ервальных расширений по этим формулам. Существенным фактом гется то, что в отличие ог большинства символьных методов реше-уравнений здесь используется н разыскивается не точное решение, алитпческая формула для сплапн-функшга, аппроксимирующих репе системы обыкновенных дифференциальных уравнений, в сово-эгостп с интервальной оценкой глобальной ошибки, что позволяет

производить строгое исследование решений системы и получать гар тированные оценки. Предложены различные способы нахождения ; тервальных расширений функций в том числе суперпозиций функц. что позволяет эффективно использовать их для нахождения облас: значений решений систем обыкновенных дифференциальных уравнен Полученные в диссертации результаты использовались для созд;и программных средств, реализующих алгоритмы надежных вычлслы ( язык реализации - Borland Pascal 7.0, Object Windows for Pasc, а также утилит для получения символьных формул сплайн-аппрок мацпй решений ( реализация в системе Marple). В приложения: и 2 приведены символьные формулы и графики решений, найденных разработанному алгоритму.

Апробация работы. Результаты диссертации докладывал] на семинаре кафедры вычислительных методов механики сплошной с ды Новосибирского государственного университета под руководст1 академика Н.Н.Яненко; на семинаре по численному анализу под ру водством академика Ю.И.Шокпна (ИТПМ СО РАН, г. Новосибпрс на семинаре "Проблемы математического и численного моделпровац; (ВЦ СО РАН г. Красноярск); на конференциях молодых ученых ИТ1 СО РАН г.Новосибирск (1981, 1983 гг.); на международном спмпозщ по интервальной математике ( Фряйбург, Германия, 1980 г.); на В российских совещаниях по интервальному анализу ( 1985, 1986, 1988] г. Красноярск, 1992г.- Абрау-Дюрсо); па Всероссийской школе "Вы слктельные методы и математическое моделирование" -Институт п кладной математики им.М.В.Келдыша, Красноярский госуниверсп' (1986г.- Шушенское); на Всероссийской конференции "Актуальные п блемы прикладной математики"- Саратовский госунпверснтет ( 1991 Саратов); на 8-й международной школе- семинаре " Качественная i рия дифференциальных уравнений гидродинамики" -Институт гид динамики им. М.А.Лаврентьева,'Красноярский госуниверситет (199! Красноярск); на международной конференции по численному анал н автоматической верификации результатов - Университет штата тадная Луизиана ( 1993г. - Луизиана, США); на международной к ферешши по компьютерным системам и прикладной математике -Петербургский госунпверснтет (1993г.- С.-Петербург); на междунар нон конференции по интервальным и компьютерно-алгебраическим тодам в науке п инженерии - С.-Петербургский госунпверснтет (199

■Петербург); па Всероссийском совещании по интервальной матема-ке - Институт вычислительных технологий СО РАН. Новосибирск 194,1995 гг. — Новосибирск); па международной конференции по чхт-: иному моделированию в научных исследованиях, компьютерной ариф-гике и гарантированным вычислениям (5СА1^-95)- Университет г. пнерталь, Германия ( 1995г.- Вупперталь, Германия).

Публикации. По теме диссертации опубликовано 14 печатных

ют.

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

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

»' = /(«,»). (1)

ное решение которой равно ?/(<).

Ды хотим вычислить интервальную функцию У(<) = [!!(*) , У(<)], которой у(<) € У(<) при всех I £ */}- Функция У(*) учитывает же гарантированные границы глобальной ошибки решения задачи Этот подход расширяет методику опенки численных решенпй с гом всех типов погрешностей.

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

ференциальных уравнений. Подробное описание этого метода и зорную статью академика H.H. Лузина можно найти в сборш трудов С.А.Чашшгпна . Дальнейшее развитие методы построе! двусторонних оценок получили в работах В.Вальтера, В. Лакпп кантама, В.В. Шаидурова, B.C. Добронца и других математиков, ( блиография по двусторонним методам содержится в монографии В Шайдурова, Б.С.Добронца .

Появление интервальных методов привело к реализации нового m хода в оценивании решений систем обыкновенных дифференппалън уравнений, основанного на понятии интервальных величин и hhti вальных операций, впервые предложенного в книге Мура. В даль» шем эти методы развивались в работах К.Никеля, Ф.Крукебер Ю.И.Шокпна, Х.Штеттера, Р.Лонера, Э.Эймса. В.Адамса, Ф.С. 4i яоусько, А.Ф.Филиппова, B.C. Добронца, Р. Скилла и других иссле, вателей.

Постановка этих задач, аналогична постановке задачи (1), отличи том, что задан интервал начальных значений:

у' = у),

У {to) = Уо t € [io,i/], У е R".

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

Чтобы проиллюстрировать отличие, рассмотрим обыкновенное ди ференциальное уравнение

y'(t) = -y, у(0) = [1,2].

Если рассматривать уравнение (2) как дифференциальное интервалы: уравнение, то решение, проходящее через начальную точку (to, Уо) (0,2) может иметь тангенс угла наклона, ограниченный сверху .41 лом —1, решение, проходящее через точку (0,1) может иметь танге угла наклона, ограниченный снизу значением -2.

Оптимальное включение [У(<),У(<)] точного решения у удовлетво-:т системе .

Г = —У, F(o') = 2

У! 4 -Y, Z(o) = 1

едовательно.

y(t) 6 [ШТ(<)] = [(Зе-' - е')/2, (Зе~< + е')/2] ,

'I

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

С другой стороны, если мы рассматриваем уравнение (3) как пара-гризованное семейство, оптимальным включением будет [е~',2е_<] -ершенно другое решение.

В работах, строящих интервальные методы, имеют место оба этих [хода, хотя для концепции, в которой мы сопоставляем системе обык-¡енных дифференциальных уравнений параметризованное семейство, нпкают сложности с нахождением эффективных численных алгорит-5. Например, если в задаче (1) правая часть / зависит от параметров, Лонер считает, что каждый параметр-это дополнительная зависимая >еменная, производная которой равна нулю.

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

Материал данной главы содержит основные вопросы, освещающие ятие совокупности решений систем обыкновенных дифференпиаль-z уравнений и их основных характеристик. Рассматривается случай ого уравнения п системы обыкновенных дифференциальных уравне-понятие сечения совокупности решений систем обыкновенных диф->енцпальных уравнений, метрики Хаусдорфа. Пусть функция f(y)-

непрерывна на некотором открытом интервале в, содержащем ¿о п У влетворяет условию Липшица на замкнутом интервале [¿о, С С. О значим через У4-образ множества в момент времени t в силу систе: (2), то есть

«^{»Шб^}

Множество У(-можно назвать сечением совокупности решений, соотв ствуюпхих значению У0'при фиксированном времени t.

Интервальный вариант метода последовательных приближений ] лезен тем, что обладает свойством сходаыости к интервалу точных шений на всем интервале времени t при выполнении достаточно о видных и необременительных условий. Следует заметить, что мет последовательных приближений в случае систем уравнении не обла; ет свойством близости к интервалу точных решений на всем интерва а лишь на некотором малом подинтервале, хотя включение сохраняет Для описания эволюции множеств решений дифференциальных ур; нений можно решать более общие задачи оценки множества достиа мости решений дифференциальных уравнений, параметры которых : меняются на некоторой совокупности значений. Например, под мно> ством достижимости с начального многообразия Уо понимается все м] жество правых концов у(т) траекторий ¡/(£), Ц <t < т, начинающш на Уо, то есть у(Ц) € Уо-

Методы интервального анализа могут быть эффективно использо] ны для исследования совокупности решений дифференциальных ур; нений. Основным инструментом исследования при этом является щ водимая ниже последовательность определении и утверждений.

Пусть У иУ„ - это интервалы при п — 1,2, — Тогда Уп сходится У при п, стремящимся к бесконечности, если"

1ш1 У_п = У и 1ип У„ = У.

п—«ОС " П—.ОС

Пусть Р- отображение интервалов, задающее метод последовате; ных приближений. Сформулируем следующее утверждение.

Пусть существует интервальная функция Уо такая, что РУо* С Уо- Ч гда последовательные итерации Уп+1 = РУ„ образуют убывающую I следовательность интервально-значных функций и limn_.cc Уп(0 = У( где У(*)- интервальная функция на I. Кроме того, если у- пропзво; ное решение уравнения ру = 0, то у(*) £ У(1) на области существовал решений.

Показано, что метрика Хаусдорфа

h(A, В) — max < sup inf d(a, b). sup inf d(a, h) >, (5)

1ъел 'ей ' tsB °e-4 J

;e Л. В - пекоторые множества в 7?",

d(a, Ь) = max ¡а,- — £>,■

1=1,п

[я интервалов принимающая вид '

h(A, В) = тпах{\а - Ь|, |о - Ь|},

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

есь описан метод построения интервальных оценок, который осно-а на предварительном определении формул приближенных решений в алитическом виде, гарантированной оценке глобальных ошибок и населению интервальных расширений (совместно для формул и глобаль-зс-ошибок). Требование строить формулы прпблпжеяпых решений в >бой точке t области G позволяет бороться с влиянием эффекта Мура, скольку переносит определение интервальных расширений на послед-й этап алгоритма, то есть снимает "пошаговость" оценок множеств лений. При этом применяются кусочно- полиномиальные функции ш сплайн-функции) различных степеней гладкости п дефектов, что уясняется необходимостью эффективно выполнять аналитические вы-1Дки для компьютеров любой производительности и конфигурации, ■летим, что выбор вида сплайн-функций зависит от того, для каких :тем уравнений производятся оценки: для систем уравнений, имею-х лилейную правую часть, пли нелинейную правую часть.

Основные шаги численно-аналитических алгоритмов включают: вг ражепие значения сплайна в любой интересующей нас точке t ннтерв ла [¿о, как функции от начальных значений; линеаризацию данш функции по начальным значениям в некоторой точке оценку нормы ра ности значений сплайна 5(<) и точного решения ¡/(¿) с помощью оцет глобальной ошибки; определение лнтерпальной оценки множества реш ний по каждой компоненте как объединение интерсального расширял сплайн-функции, аппроксимирующей решение исходной системы обы нозепных дифференциальных уравнений" и интервальной оценки гл бальной ошибки.

Будем строить полиномиальную сплайн-функцию степени г 4-1, гла кости 1, аппроксимирующую решение у(1) согласно схе.ме

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

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

Итак, символьные формулы сплайн- функций аппроксимиру]

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

для производных , участвующих п процессе вычисления.

Будем производить линеаризацию зтнх функций на интервале 1

г ^

<"*]» к — 1,... пг.

т •

зляюпгпмся произведением интервалов У® х У21' х . .. х Упр. Используем Формулу Тейлооа

Уг—1 у'1) = • • • ,у'„) ~ ^ (г/? - г/;, -... (к

¡-- и*-кл-н Ш ш+ад - +мй - ?/;))•

в{. 6», е [о, я. г*,г" е у,° х ... х 1;р

Обозначим через тпь^ линейную часть этого разложения

гппк = ,..., ь-;) + ¿; ^ |г. (у? - у;) о

Итак алгоритм заключается в следующем:

в На каждом интервале £,•] представляем выражения как функции, зависящие только от начальных данных

в Затем определяем их ликейкые часта согласно формуле (9)

р Подставляем их в выражения, по которым мы вычисляли компоненты сплайн- йуцкппл

) - + £тпыМ,VI...,ПО)

**(* о) = (11)

к — 1,..., пг, г = 1,..., п

Тогда для" вектора глобальной сишбкп нашего метода, реализуемого гтервально - аналитически получаем опешеу

¡1 Е{=) ||< ехр |! А || Л«'2(1о)ы) , (12)

[йсь Ь\-константа. Неравенство (12) означает сходимость предложение метода сплапн-коллокашш при Л (—» 0, ги(Уо) » 0.

В схеме практической реализации этого алгоритма появление зна-!Штя длины пзтеркала га(Уо) в выписанной выше оценке приводит к

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

Итак, компоненты сплайн-решения могут быть записаны в впде

Sk(t) = Pti(t, %i(<o) + • • -+ Pkn(t,h)yn(t0).

Поэтому объединенное интервальное расширение этой функции сош дает с естественным интервальным расширением, т.е.

Зь(*) = Uwenat(t0,yo,i) = Pki(i. h)Y0д + ... + ft„(i, h)Y0.n. (]

Как мы уже отмечали, практическое применение этого алгорит основывается на нахождении интервальных расширений для получ* пых символьных выражений сплайн-аппроксихищий решений, при эт только от вида этих расширений зависит ширина интервальной он'*н множеств решений. Рассмотрим некоторые аспекты вычислений инт( вальных расширений.

Напомним, что объединенным интервальным расширением функции / мы называем интервально-знатную функцию

№ = \j№ = {f(t)\t6T}.

(6Т

Любое отображение F(T) на множество интервальных чисел ( интер; лов из Я") такое, что

/(Т) € F(T) и f(t) = F(t)jua Vi с X

называется интервальным расширением функции f(t) на X. Если л ;побых двух интервалов 7\ С Ti мы имеем

F(Tt) С F(Tt),

то F(T) называют монотонным по включению интервальным расши] кием. Интересно получить конструктивные оценки, позволяющие : следовать возможность выбора наилучшего по ширине включения i тервальиого расширения функции /. В нашем случае мы производи

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

Для оценки отклонений тгих оценок от границ совокупности всех гоч-1ЫХ решений укачанной задачи вводятся понятия сходимости в хаус-юрфовий метрике объединенного интервального расширения, соответ-;твуюшего построенной в предлагаемом методе интервальной опенке, к ;овокупности точных решений, и неулучшаемой (покоординатной) интервальной оценки.

Сходимость в хаусдорфовой метрик»1 объединенного расширения но-:ит скорее теоретический характер, а неулучшаемость (покоординатная близость) оценок имеет практическое значение, поскольку отражает [>акт параллельности осям координат границ интервалов и близость их ; совокупностям точных решений.

Третья глава состоит из двух параграфов и содержит описание алго-

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

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

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

Итак, общий алгоритм сложения интервальных величин может быть хредстаилен в следующем виде

function add(a,b:interval):interoal; begin

add. inf: ~a. inf+ low(b. inf); if overflow then error;

if underflow then if add.inf > 0 then udd.iv.f:~Q else add.inf:—small: add. sup:=a. sup+vp(b. sup J; if overflow then error; if underflow theii if ad a. sup < 0 then adi.suv:=0. else add.sup:—small

end:

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

При реализации процедур для операции пад граничными точка:: интервалов мы должны обеспечить присутствие утилит, получающим ближайших к заданному машинному числу величин, к обозначаемы succ (v) и prcd(v).

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

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

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

Каждый шаг алгоритма, обозначенный памп V, состоит из (разы ••о-хапия и модификации графа, за которой следует фаза исключения за-пснмости среди переменных, используемых а шагах .... Г^'К

На фазе создлнпя графа выделяется несколько анализируемых слу-аев, зависящих от того является ли У определена и использована и ыражешга на данном шаге алгоритма

а фазе исключеппя зависимостей можно определить шаги проверки: ) Существует ли пара (А',,X,), такая, что Х[(1'Х^

T/i

Тогда

) Xi 'sued Xj влечет, что Xj заменяется па свое определение в У*.

Например,

Xi = 2Х, Yi = Х,Х2

Хг = 2Х-2 Y{ = 2ХД'2

b) Xi 'ptcom' Xj злечет, что как Xj так и Xj заменяется на свое хределение в У.

Х\ = Z | Г = Z

х2 -3 Z => J = 3 Z

= X, - X! 1 * = 2 Z

Например,

2) Существует Yj, такое, что i 'sued Yj and (ЗД {Хк 'sued Yi) and (Xk 'sued Yj). В этом случае реализуется последовательная замена сверху впиз пе-«мепшлх, применяемых в Yj, Yj, на их определения.

Например,

( Yj - У/ + Хп ( Yj = Y,+ X„ f Yy = Xl

{ Y, =Y; ^¿Y, Xn { Y, = -Yi - Xn

[ Y = Xi - Xn ( Y = Xi - A'n { Yi = Xt -

Циклы в этом направленном графе будут соответствовать использу-тым ( used), но не типщпализпрованиым переменным, что позволяет

попутно выявить семантические ошибки в программе.

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

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

Для системы Мура ■

... У' = АУ, (1

где у— вектор размерности два, А— матрица коэффициентов

с интервальными начальными данными у1 <Е [—0.1,0.1], у'2 G [0.9,1.1 которую использовали в качестве тестовой авторы всех интервал ных методов, получены практически точные по каждой координате ве тора решений оценки. На фазовой плоскости множество решений сист мы представляет движущийся по концентрическим окружностям кв драт и поворачивающийся относительно координатных осей. Для бол шинства методов, гарантирующих точное включение множества реш епй, сторона этого квадрата л'величпвается после к— оборотов в с2 раз, то есть после первого оборота почти в 600 раз. После первого mai получаем для компонент вектора решений формулы, зависящие толы от начальных значений j/q, у*:

ЧА- '4. 'A h2y'° y'hi 4- h*yi + hSy>

1(,\ , , , *2y,f .¿vl, s! h* h5y'

У \4 = So - h Ус--7Г~ + T~ + '

6 16 180

После второго шага - формулы:

2hiy'o , О «г i 4hby' 31 h*y'e

15 3 360

h'vl , 13 fcV+A»»l J h^vi

45 2880 1440 14400

4А5^ , 2 у* Л4 , 4л\' , 15 АУ , ¿4'

^ 28 я'Ч

45 180 13460

После третьего шага-формулы: П2у< .27

—— + У о + —

Э^Л3 121 Л6 ^ 17 V у* , 49 Л8 у^

У (ч ---~ + Уо+ —д— + 3 Уо А + 40

2 120 40 320

Ч' , 409 ЬЧ' Л14^ , Л'Ч* . ,

—- Н—^гтт:--, -г^А™ ~ , , + , лот +

3200 8640 1728000 115200 12800

181 к12у'0 361 И10 у' 345600 28800

= - у° + у° - % + Уа +

7 ^ ' л 115200 17280С0 12300 3200

181 Ь12у„ 81 />5Уэ 27 у-Л4 9/>3у^

345600 40 8 2

ЭЛУ , 49 Л8у* 409 А9

2 У" 320 8640

121 К6 у' 361 к10у>0

40 120 28800

На. рисунке 1 по оси абсцисс отложена у3, по оси ординат у2.

Рисунок 1

тов в фазовом пространстве занимает 30 минут для ПК ЮМ PC 486 SX и менее 8 мнвут для ПК IBM PC 486 - DX4.

На рисунке 2 показаны оценки решений системы

х = ху — х 4- R,

I ч

У = -х* - у.

Если (xq, ¡/о) -начальная точка., то решение содержится в сфере радиуса г = пгах[й, + Уо)1/2], где R > 0. Легко показать, что эта систем ма имеет всегда только одно стационарное решение, которое устойчиво Результаты интервального оценивания решений, полученные по другкъ: методам при различных значениях R, демонстрируют экспоненциальный рост границ этих оценок. Полученные в нашем методе оценки решений этой системы при начальном интервале х € [4.9,5.1], у € [4.4,4.6 сходятся в одну точку, что легко увидеть на рисунке .

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

Pu с J

На рисунке 4 показаны оценки решений системы Ван-дер-Поля

еу' = у- (1/3)уг - х, здесь £ > О малый параметр.

Известно, что в ней устанавливается периодический режим- релаксаш онные колебания, характерной чертой которых является наличие учас: ков, где траектория резко меняет направление-релаксационыых учас: ков. Для того, чтобы чпсленно определить релаксационные участк траектории .• необходимо интегрировать систем}' с шагом много меньше. Поведение интервальных оценок, полученных по нашему алгоритму пр е = 0.5 приведены па рисунке 4. Время расчетов составило 20 секунд не зависит от 'вычисления оценок производились при значениях £ о 0.5 до 0.001.

Рас. 4

В заключения перечислены основные результаты диссертации,

оторые сводятся к следующему:

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

2. Доказаны теоремы сходимости интервальных оценок, полученных по указанным схемам.

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

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

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

Основное содержание диссертации отражено в работах:

[гггература

1] Яленко H.H., Шокин Ю.И., Рогалез А.Н. О принципах построения пакета интервальных операций // Сб. Численные методы механики сплошной среды.- Новосибирск.- 1980, т.11, 5,- С.147-153.

2] Шохин Ю. И., Рогалев А.Н. Пакет интервальных операций для ЭВМ БЭСЫ-6 // Препринт ИТПМ СО РАН 24-81.- Новоснбирск.-1981.- 22 с.

3] Шокин Ю.И., Рогалев А.Н., Юлдашев 3-Х. Использование методов интервального анализа в проблеме транспортабельности программ // Прикладная математика я мехаяпка.- Ташкент, 1981.- 670.- С.91-97.

4] Новиков В.А., Рогалев А.Н. Об одном методе решения обыкновенных дифференциальных уравнений с начальными дадяъшд в виде

интервала // Информационно-оперативный материал (интервал ный анализ). Препринт ВЦ СО РАН.- Красноярск, 1989.- 9.- С.2 30.,

[5] Новиков В.А., Рогалев А.Н. Исследование интервального метода и следовательных приближений / / Информационно-оперативный м териал (интервальный анализ). Препринт ВЦ СО РАН.- Краен ярск, 1989.- 9.- С.28-29.

[6] Новиков В.А., Рогалев А.Н. Влияние эффекта "раскрутки" на п лучение верхних и нижних оценок решений систем обыкновеннь дифференциальных уравнении // Ж. выч. мат. п мат. физ.- 199С т.29, 10.- С.1593-1595.

[7] Рогалев АШ. Построение сходящихся верхних и нижних опенс решений систем обыкновенных дифференциальных уравнений / Материалы Всесоюзной конференции "Актуальные проблемы npi кладной математики",- Саратов, 1991.- С. 136-140.

[8] Рогалев А.Н. Двусторонние численно-аналитические методы ощч кп решений систем ОДУ с интервальными данными // Восьми международная школа-семинар "Качественная теория дифферент альыых уравнений гидродинамики (институт гидродинамики, Hi восибпрск - Красноярский госунпверсптет)".- Красноярск, 1992 С.22-24.

[9] Rogaiev A.N. Numerical Methods for Enclosing Solutions of Ordinal Differential Equations with Interval Data //Abstracts for an Intern; tioual Conference on Numerical Analysis with Automatic Result Ve: ification. Mathematics, Applications and Software. February 25-Mac 1, 1993. University of South Western Louisiana. USA.- P.75-77.

[10] Rogaiev A.N. Outer and inner estimates for sets of solutions of ODE with interval data // International Congress on Computer Systems an Applied Mathematics.- St.Peterburg State University, Russian Loc; ACM Chapter (St. Peterburg) - 1993.- P.99-100.

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

] Rogalev A.N. Optimal upper and lower bounds for sets of solutions of ODE's with interval data // International Congress on Interval and Computer- Algebraic methods in Science and Engineering.-St.Peterburg State University, International Journal " Interval Computations", 1994,- P.203-204.

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

] Rogalev Alexei N. Solving Systems of Ordinary Differential Equation, with Interval Data: Rigorous and Optimal Bounds.// IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Sept. 26-29,1995.- Bergische Universität Gesamthochschulle Wuppertal , Fachbereich Mathematic und Institut für Angewandte Informatic (Germany) , - p.113-114.

Соискатель :

Усл. net. л. v г Уч-нзд. л.

Тираж 4iO Ъхга59У Цене,

Усл-печ-л.

Подписано я печать Бумага тип. .

Формат 6Q*S<f//£ Печать офятошц

Радакци0!П1о-издатеяьао1Й цедар Красноярского государственного унивс 660041 Красноярск, пр. Свободой, 79.