Новый подход к анализу статических систем с интервальной неопределенностью в данных

Вычислительные технологии

Том 2, № 1, 1997

НОВЫЙ ПОДХОД К АНАЛИЗУ СТАТИЧЕСКИХ СИСТЕМ С ИНТЕРВАЛЬНОЙ НЕОПРЕДЕЛЁННОСТЬЮ

В ДАННЫХ*

С.П.Шлрый ^ Институт вычислительных технологий Новосибирск, Россия

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

1. Введение

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

Для известных входных и выходных данных системы найти (или как-то оценить) её внутренние состояния.

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

В этой работе мы делаем попытку рассмотрения интервальных статических систем с общей нелинейной зависимостью вход-состояние-выход. Более простые и сильные результаты для линейного случая были получены ранее и изложены, например, в [12, 31, 32].

*© С.П.Шарый

^Статья публикуется в авторской редакции с сохранением авторской орфографии.

2. Задача анализа интервально заданной системы

Пусть внутреннее состояние системы, входное воздействие на нее и выходной отклик системы описываются конечномерными векторами х £ а £ К и Ь £ К5 соответственно. При этом во множестве всех входов системы будем различать возмущения а1, ... , ак, не зависящие от нас и действующие в пределах интервалов а^ ..., аи, и управления ак+1, ... , аг, которые мы можем выбирать по своей воле из интервалов а^+1, ... , аг. Аналогично, во множестве выходов системы мы выделяем компоненты Ь1, Ь2, ... , Ь, которые должны переводиться в каждое значение из заданных интервалов достижимости Ь1, ..., Ь (регулируемые выходы), и компоненты Ьг+1, ..., Ь5, от которых требуется гарантированное попадание в некоторые коридоры значений Ь^+1, ... , Ь5 (стабилизируемые выходы).

Например, регулируемыми выходами являются координаты механической руки — исполнительного органа робота-манипулятора, — от которых требуется гарантированное "накрытие" каждой точки некоторой заданной рабочей области. Но при этом, вообще говоря, механической рукой могут достигаться и некоторые другие положения. Типичным примером стабилизируемого выхода системы может служить температура внутри химического реактора в ряде технологических процессов: она не должна отличаться от номинальной Т больше чем на некоторую величину 8Т, но приемлемо любое ее значение из интервала [Т - 5Т,Т + 5Т].

Предполагаем, что зависимость вход-выход в рассматриваемой системе имеет вид

Г

с некоторой известной функцией Г : К х ^ К5, компоненты которой Г1(а,х), Г2(а,х), ... , Г3(а, х) являются рациональными функциями от а и х, непрерывными всюду в рассматриваемой области изменения переменных. В целом ситуация описывается структурной схемой, изображенной на рисунке.

возмущающие

управляющие

регулируемые

а1, .. •, ак Ь1, •

ВХОДЫ а х Ь ВЫХОДЫ

ак+1, • • •, аг Ьг+1, • •, Ь3

^(а, х) = Ь

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

Для каких состояний системы х при любых возмущениях а1,... ,аи, не выходящих за пределы интервалов а1,... , а^, и при любых значениях Ь1,... из интервалов достижимости Ь1,... , Ь можно подобрать такие управляющие воздействия на систему ак+1 £ ак+1,... ,аг £ аг, что её (2) выходной отклик Г (а, х) будет в точности равен Ь1,... на регулируемых выходах и не выйдет за пределы Ь^+1,... , Ь5 на стабилизируемых выходах?

Некоторые исследователи возражают против использования терминов "управление", "регулирование" и т.п. в ситуациях, подобных вышеописанной. Их аргументы сводятся к тому, что смысл, вкладываемый нами в эти понятия, несколько отличается от того, что принят в классической теории автоматического управления. Это действительно так, но классическая теория управления не является единственной дисциплиной, оперирующей с "управлениями". Напомним, например, повсеместно принятое в исследовании операций определение [1, 6]: операцией называется целенаправленное действие, которое может быть описано в виде

и = / (ад),

где и есть полезность, или значение критерия, характеризующего качество функционирования системы; X — переменные, которыми можно управлять (контролируемые переменные); 1] — переменные (и постоянные), не поддающиеся управлению, но влияющие на и, то есть неуправляемые, или возмущающие (неконтролируемые переменные). Таким образом, смысл, вкладываемый нами в понятие "управления" и ему родственные, хорошо согласуется с терминологией исследования операций.

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

Но вернемся к исходной задаче. Если входы и выходы системы заданы точно, решение задачи (2) сводится к решению относительно х системы уравнений (1). Если же входные и выходные данные системы имеют интервальную неопределенность, то, в соответствии с терминологической традицией интервального анализа, процесс решения задачи (2) мы также будем называть "решением" интервальной системы уравнений

^

где а = (а1, а2,... , аг)т, Ь = (Ь1, Ь2,... , Ь)т, но смысл, вкладываемый в понятие такого "решения", потребует специального разъяснения. Прежде всего определим, что будет пониматься под "множеством решений" интервальной системы (3).

Формально множество состояний х, являющихся решениями задачи (2), описывается в точности следующим образом:

{ х е Ега |

( ^(а, х) = Ь) }.

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

лишь принадлежность некоторым интервалам, логические кванторы всеобщности V и существования 3 выражают принципиальное различие [3, 5] между:

входными воздействиями, которые нашей воле неподвластны и являются внешними неконтролируемыми возмущениями (это соответствует записи Уа^ £ а^), и

входными воздействиями, которые мы можем варьировать в пределах заданных интервалов по своей воле, то есть управлять ими (это соответствует записи 3а ^ £ а^-).

В отношении выходов системы Ьг логические кванторы выражают разграничение между:

коридорами стабилизации системы, в пределах которых требуется обеспечить ее функционирование, каковы бы ни были значения внешних возмущений (это соответствует записи 3Ьг £ Ьг), и

множествами достижимости системы, каждый элемент которых должен быть накрыт в результате подходящего выбора управляющих воздействий (это соответствует записи УЬг £ Ьг).

3. Обобщённые множества решений интервальных уравнений

К необходимости введения общего определения множества решений вида (4) для интервальных уравнений можно подойти и с других позиций, рассматривая, например, некоторые задачи идентификации систем в условиях интервальной неопределенности данных, или даже с совершенно абстрактных позиций. Действительно, интервальная неопределенность изначально может трактоваться двояко, в соответствии с двойственным характером интерпретации самих интервалов. С одной стороны, интервал [х,х ] может представлять собой множество всех вещественных чисел от х до х, а с другой — быть лишь вместилищем, указателем границ для какого-то, хотя бы одного значения между х и х.1 В формальной записи это различие выражается употреблением логических кванторов — либо всеобщности V, либо существования 3: в первом случае мы пишем Ух £ [ х, х ], а во втором — 3х £ [ х, х ]. При этом в соответствующих ситуациях уместно говорить о У-типе (А-типе) неопределённости и 3-типе (Е-типе) неопределённости. Давая строгое определение множеств решений интервальных уравнений и систем, мы должны четко разграничивать эти два типа неопределенности, и именно это сделано в определении (4). Особенно рельефно вышеупомянутое различие между двумя типами интервальной неопределенности проявляется тогда, когда мы имеем дело не с единственным интервалом самим по себе, но когда несколько интервалов описывают различные по природе, нередко конфликтующие друг с другом, воздействия на систему.

Несмотря на большую общность определения (4), оно все же не является самым общим. В принципе, поскольку кванторы V и 3 не коммутируют друг с другом [8], путем комбинирования их сочетаний с коэффициентами уравнения и перестановки порядка можно определять и другие множества решений интервальных уравнений. К примеру, для одного уравнения

а2, а3, а4, х) = Ь

хНа эту двойственность в интерпретации интервала указывает, в частности, Ю. В. Матиясевич в своем предисловии к русскому переводу книги [2].

с четырьмя интервальными параметрами в левой части в качестве множества решений можно рассматривать множество

{ x G Rn | (3«2 G a2)(Vai G ai)(Va4 G a4)(Vb G Ь)(3аэ G аз)( (p(a1,a2,a3,a4,x) = b) },

или

{ x G Rn | (Vai G ai)(Va2 G a2)(3a4 G a4)(Vb G Ь)(3аз G аз)( ^(ab a2, аз, a4, x) = b) }

и т.п. Наиболее общее определение множества решений для интервальной системы уравнений F(a,x) = Ь с a G IRr, Ь G IRs выглядит, следовательно, так:

где

(ci, c2,... , cr+s) = (ai, a2,... , ar, bi, b2,..., bs) — агрегированный вектор параметров

рассматриваемой системы уравнений, (02,... , 0r+s) — некоторая перестановка чисел { 1, 2,... , r + s }, Qi, Q2,... , Qr+s G {V, 3 } — логические кванторы.

Определение 1. Множества вида (5) будем называть обобщёнными множествами решений для интервальной системы уравнений F(a, x) = Ь.

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

Ax < Ь

И. Рон и Я. Креслова в работе [27] изучали, в частности, обобщенное множество решений

(но не выписывали его явно). Введенное ими понятие сильной разрешимости интервальной линейной системы неравенств является не чем иным, как свойством непустоты множества решений (6).

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

Объединённое множество решений (united solution set), образованное решениями всех точечных систем F(a, x) = b с a G a и b G Ь, то есть множество

£33

2По существу, это обычные задачи теории управления динамическими системами, но в интервальной постановке.

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

Допустимое множество решений (tolerable solution set), образованное всеми такими векторами x G что F(a,x) G b для любого a G a, то есть множество

(см., например, [24, 29]). А. Ноймайер [24] и некоторые другие авторы использовали по отношению к (8) малоудачный термин "restricted solution set".3

Управляемое множество решений

образованное всеми такими x G что для любого желаемого b G b можно подобрать соответствующий a G a со свойством F(a, x) = b (см. [28]).

Из определения (5) видно, что обобщенное множество решений интервальной системы уравнений полностью определяется 1) перестановкой компонент агрегированного вектора параметров системы и 2) последовательностью логических кванторов. Другой, более наглядный способ описания множеств решений состоит в том, чтобы пойти от их содержательной интерпретации, данной нами в разделе 2. Для этого расчленим кванторную приставку выделяющего предиката множества решений на АЕ-блоки. Каждый такой блок соответствует одному элементарному акту "возмущение-управление", или одному шагу процесса принятия решения (или игры). Таким образом, в целом обобщенное множество решений может быть содержательно проинтерпретировано [5] как решение некоторой игры или многошагового процесса принятия решений в условиях интервальной неопределенности.

Если интервалы неопределенности параметров системы уже известны, то каждый такой шаг полностью задается указанием

элементов, имеющих V-неопределенность на данном шаге, элементов, имеющих 3-неопределенность на данном шаге, элементов, неопределенность которых несущественна на данном шаге.

Далее в этой работе мы не будем рассматривать самый общий случай, а ограничимся только множествами решений интервальных уравнений вида (4), у которых в выделяющем предикате все вхождения квантора всеобщности V предшествуют вхождениям квантора существования 3, или, иными словами, будем рассматривать только те множества решений, для которых выделяющий предикат имеет АЕ-форму.

3В русской научной литературе для обозначения условия принадлежности выходов системы к некоторому a priori заданному множеству режимов давно и широко применяется термин "условие живучести" [3]. Аналогичная дифференциальная задача интенсивно исследовалась Ж.-П. Обэном и его сотрудниками (см., например, [11, 14]). Интересно, что Ж.-П. Обэн использовал тот же самый термин — viability condition, — но переведенный в русских изданиях его книг то как "условие жизненности", то как "условие жизнеспособности". По-видимому, терминология интервального анализа в этом пункте должна быть скорректирована соответствующим образом.

SV3(F, a, b) = { x G Rn | (Va G a)(3 b G b)(F(a,x) = b) }

£3v(F, a, b) = { x G Rn | (Vb G b)(3 a G a)(F(a,x) = b) },

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

а

вг

V, если а3- представляет У-неопределенность,

3, если а3- представляет 3-неопределенность,

V, если Ьг представляет У-неопределенность,

3, если Ьг представляет 3-неопределенность,

Второй способ описания распределения различных типов неопределенности по интервальным элементам системы Г (а, х) = Ь заключается во введении, наряду с кванторными векторами а и в, еще интервальных векторов а7 = (а^) и а3 = (а3) и интервальных векторов Ь7 = (Ь7) и Ь3 = (Ь3) тех же размеров, что а и Ь следующим образом:

7 Г а3-, если аj = V, 3 Г а3-, если аj = 3,

3 \ 0, иначе, j [ 0, иначе,

Ь7 , Ьг, если вг = V, ^ Г Ьг, если вг = 3,

г 0, иначе, г I 0, иначе.

г

Таким образом, векторы а7, а3 и Ь7, Ь3 представляют собой интервалы с однотипной неопределенностью. При этом

а = а7 + а3, Ь = Ь7 + Ь3

и а7 а3 = 0, Ь7 Ь3 = 0 для всех г,^,

то есть векторы а7 и а3, Ь7 и Ь3 образуют дизъюнктные разложения (взаимно-дополнительные разложения) для а и Ь соответственно.

Определение 2. Пусть для интервальной системы уравнений Г (а, х) = Ь тип интервальной неопределенности компонент а и Ь конкретизируется кванторными векторами а и в и соответствующими дизъюнктными разложениями

а = а7 + а3, Ь = Ь7 + Ь3.

Мы будем называть множество

(Г, а, Ь) = { х € Ега | (Уа € а7) (УЬ € Ь7)(3а € а3)(3Ь € Ь3) (Г (а + а, х) = Ь + Ь) }

обобщённым множеством решений типа ав (или ав-обобщенным множеством решений или просто ав-множеством решений) и обозначать через (Г, а, Ь).

4. Постановка математической задачи

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

решений, под которым всюду ниже, исходя из нашей практической интерпретации, будем понимать их внутреннее оценивание некоторыми более простыми подмножествами: ведь только для подмножеств П С а, Ь) ответ на вопрос (2) является положительным

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

Найти интервальный вектор, который содержится во множестве решений а, Ь) интервальной системы уравнений (10) ^ (а, х) = Ь.

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

До сих пор задачи вида (2), (10) решались лишь минимаксными методами математического программирования. Цель настоящей работы — представить новый, алгоритмически эффективный подход к анализу статических систем с интервальной неопределенностью, то есть к решению задачи (10), и ключевым в наших построениях является понятие алгебраического решения интервальной системы уравнений, впервые рассмотренное для одного уравнения в работах [16, 26] и для системы линейных уравнений в комплексной круговой арифметике в работе [25].

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

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

5. Аналитическая характеризация ав-множеств решений

Предложение 1. Пусть отображение ^ таково, что каждый из параметров системы ак+1,... , аг, соответствующих 3-типу неопределённости, входит лишь в одну из компонент ^¿(а,х). Тогда принадлежность х е а, Ь) равносильна следующей системе

неравенств:

min max Fj(a + a,x) > bj,

ä€av ä€a3

max min Fj(a + a,x) < bj,

a€av <i€a3

— для регулируемых выходов, i = 1,... , I,

min max Fj(a + a,x) > b^, aeav asa3

max min Fj(a + a,x) < bj,

a£av «sa3

— для стабилизируемых выходов, i = I + 1,... , s.

Доказательство предложения мы проводим путем эквивалентных преобразований выделяющего предиката множества решений интервальной системы. Положим Ь = (Ь^ Ь2,..

Ь + Ь, Ь, Ь € К5. Тогда

(^ а, Ь) =

{ х € | (Уа € а7)(УЬ € Ь7)(3а € а3)(3Ь € Ь3)(^(а,х) = Ь) } =

( х) = Ь1

& •••

& (а, х) = Ьг

& ^г+1(а,х) € Ь|+1 & •••

& ^

( ^1(а,х) > Ь1 & ^1(а,х) < Ь1 & •••

& ^(а,х) > Ьг & ^г(а,х) < Ьг _

& ^г+1(а,х) > Ьг+1 & ^+1(а,х) < Ьг+1 & ••• _

& ^(а,х) > & ^(а,х) < ) } =

( (3а € а3)(^1(а,х) > Ь1) & (3а € а3)(^1(а,х) < Ь1) & •••

& (3а € а3)(^г(а,х) > Ьг) & (3а € а3)(^(а,х) < Ьг) _

& (3а € а3)(^г+1(а, х) > Ьг+1) & (3а € а3)(^]+1(а, х) < Ьг+1) & ••• _

& (3а € а3)(^5(а,х) > Ь5) & (3а € а3)(^(а,х) < Ьв) ) }.

Последнее равенство является верным в силу того ограничения, которое мы наложили на ^: каждая его компонента имеет лишь единственное вхождение переменных, соответствующих ненулевым элементам в а3, и потому мы можем "проносить" кванторы всеобщности к отдельным членам конъюнкции [8].

Л)

Отметим, что для любой функции f, непрерывной на некотором интервале а, имеют место следующие эквивалентности:

(За G a)( f (а) > b) ^^ max f (а) > b,

asa

(За G a)( f (а) < b) ^^ min f (а) < b.

asa

Поэтому можно продолжить наши выкладки следующим образом: (F, а, b) =

( (maxä€a3 Fi (а, x) > bi) & (minä€a3 Fifa,x) < bi) & •••

& (maxä€a3 F (а, x) > b) & (minäea3 F (а, x) < b) _

& (maxä€a3 F^+i^x) > bi+i) & (minä€a3 F^+i^x) < bi+i) & ••• _

& (maxä€a3 F^x) > bs) & (minä€a3 F^x) < bs) ) }.

Далее,

f (а) > b, f (а) < b,

так что имеем

( (maxaSa3 F1(а,x) > bi) & (minaSa3 F1(а,x) < bi) & ••• _

& (maxä€a3 Fi (а, x) > bz) & (minü€a3 F (а,x) < b) _

& (maxä€a3 F+i^x) > bi+i) & (minä€a3 F+i^x) < bw) & ••• _

& (maxä€a3 F^x) > bs) & (min^3 F^x) < bs) ) }.

Наконец,

min f (а) > b,

asa

max f (а) < b,

asa

и мы получаем

äeav «sa3 ä€av asa3

& ••• _

&

asav «sa3 asav «sa3 _

&

asav asa3

asav asa3

a sav asa3

что совпадает с системой (11).

& ••• _

& ( min max Fj^x) > bs) & ( max min Fj^x) < bs) ) },

a sav «sa3

6. Полная интервальная арифметика

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

Как известно, классическая интервальная арифметика — это алгебраическая система (Ш, +, —, •, /), носитель которой образован интервалами вещественной оси [х, X], х < X, а операции сложения, вычитания, умножения и деления таковы, что фундаментальное свойство — определение операций над множествами через операции над их представителями

х * у = { х*у | х € х, у € у }

— оказывается выполненным для всех интервалов х, у, таких что (х*у), * € { +, —, •, / }, имеет смысл для любых х € х, у € у [2, 7, 23, 24]. Развернутое определение интервальных арифметических операций таково:

х + у = [х + У, х + у] , х — у = [х — У, х — у] ,

х • у = [шт{ху, ху, ху, ху}, тах{ху, ху, ху, ху}] , х/у = х • [1/у, 1/у] для у ^ 0.

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

х Л у = [тах{х, у}, тт{х, у} ] — взятие инфимума относительно С, х V у = [тт{х, у}, тах{х, у} ] — взятие супремума относительно С,

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

"Неполнота" как алгебраической, так и порядковой структур Ж естественно стимулировала попытки "достроить" классическую интервальную арифметику, создать на ее основе "более совершенную" интервальную арифметику. Такая достройка Ш была осуществлена в работах Э. Каухера (см. [18, 19] и имеющиеся там ссылки), который называл получившуюся алгебраическую систему "интервальной арифметикой Ж". Мы будем придерживаться термина "полная интервальная арифметика", иногда используя также термин "интервальная арифметика Каухера". Впоследствии ею занимались также Е. Гарденес и А. Трепат

[17], установившие ряд полезных свойств и важных приложений. Подробное описание интервальной арифметики Ж можно найти в работах [17, 19], а здесь мы опишем лишь те ее свойства, которые понадобятся нам в дальнейшем изложении.

Элементами Ж являются вещественные пары [ х, х ], не обязательно связанные соотношением х < х. Таким образом, Ж получается присоединением неправильных интервалов [х,х ], х > х, к множеству правильных интервалов и вещественных чисел Ш = { [ х,х ] | х,х £ К, х < х }. Элементы полной интервальной арифметики и составленные из них объекты мы будем обозначать, как и обычные интервалы, буквами жирного шрифта.

Правильные и неправильные интервалы, две половинки Ж, меняются местами в результате отображения дуализации

dual : IR

переворачивающего концы интервала, то есть такого что

dual x = [x,x]. Как и в классической интервальной арифметике,

def ^ _ _

x Q y ^^ x > У и x < y,

но, в отличие от Ш, интервальная арифметика Ж является относительно такого порядка по включению условно полной решеткой [4].

Сложение и умножение на вещественные числа определяются на Ж следующим образом:

x + У := Л  x :=

[x + ^x + y] ,

[ Л x, Л x], если Л > 0, [ Л x, Л x ], иначе.

Очевидно, что каждый элемент х из Ж имеет единственный противоположный элемент [ —х, —X ], и относительно сложения полная интервальная арифметика Ж является коммутативной группой, изоморфной аддитивной группе стандартного линейного пространства К2.

Для того, чтобы выписать явные формулы для умножения, выделим в Ж следующие подмножества:

P Z -P

dual Z

{ x 6 IR | (x > 0) & (x > 0) }, — положительные интервалы, { x 6 IR | x < 0 < x}, {x 6 IR | -x 6 P}, {x 6 IR | dual x 6 Z},

нульсодержащие интервалы, отрицательные интервалы, интервалы, содержащиеся в нуле.

В целом IR = PUZU-PU dual Z. Тогда умножение в полной интервальной арифметике может быть описано следующей таблицей [19]:

—>

Умножение в Ж у € Р у € Я у € —Р у € ёиа1 Я

х € Р [ хуху ] [ху ху ] [ Xy, ху ] [ xy, ху ]

х € 2 [ ху,ху ] [шт{ху, ху}, тах{ху, ху} ] [ Xy, ху ] 0

х € —Р [ху, ху ] [ xy, ху ] [ xy, ху ] [ xy, ху ]

х € ёиа1 Я [ху, ху ] 0 [ xy, ху ] [шах{ху, ху}, шт{ху, ху} ]

Как видим, умножение в полной арифметике допускает нетривиальные делители нуля. Например, [ —1, 2] • [5, -3] = 0. Интервальное умножение в Ж является коммутативным и ассоциативным, как и его прародитель из Ш, но мультипликативную группу в Ж образуют лишь интервалы х с хх > 0 (т.е. множество Р и —Р), поскольку закон сокращения не выполняется ни на каком более широком подмножестве Ж [18].

Определения интервальных вычитания и деления в арифметике Ж аналогичны соответствующим определениям для обычной арифметики Ш:

х — У = х + (—1) • У, х /у = х • [1/у, 1/у] для уу > 0.

Важно отметить, что в полной арифметике свойство монотонности по включению также остается справедливым:

х С х', у С у' х * у С х' * у'

для * € { + , — , • ,/ } и любых х, х', у, у' € Ж. Подобно обычной интервальной арифметике полная интервальная арифметика не обладает свойством дистрибутивности умножения по сложению [17, 19]. Кроме того, не имеет места и дистрибутивность умножения относительно решеточных операций V и Л.

Заметим, что с помощью операции взятия супремума относительно порядка по включению определение (12) можно переписать в следующем эквивалентном виде

х * у =У\/

ж€х у€у

Наиболее удивительным фактом, относящимся к полной интервальной арифметике, является то, что в ней, построенной чисто алгебраическими средствами, выполнено тем не менее представление, обобщающее (12) и (14). Именно, для каждой интервальной арифметической операции * в Ж имеет место

х * у = ИХ ИУ (х*у),

ж€рго х у€рго у

где

Их ==

Y, если x правильный, Д, иначе,

условная операция взятия экстремума по включению,

pro x:

x,

dual x,

если x правильный, иначе,

правильная — проекция интервала.

Оно выражает связь между интервальным результатом интервальной операции x * y и результатами отдельных точечных операций x * y для x G pro x и y G pro y.

Какое отношение имеет полная интервальная арифметика к рассматриваемым нами задачам? Как следует из представления (15), полная интервальная арифметика и является искомой минимаксной интервальной арифметикой! Действительно, формула (15) отражает, в частности, тот факт, что в полной арифметике концы результирующего интервала являются минимаксом и максимином результатов арифметических операций между точками правильных проекций интервалов-операндов, если один из операндов — правильный интервал, а другой — неправильный.

Векторные и матричные операции в полной арифметике Каухера определяются точно так же, как и для IR (см., например, [2, 24]), а порядок по включению на множествах интервальных векторов и матриц является прямым произведением [4] порядков по включению на отдельных компонентах. Аналогично, действие операции дуализации "dual" на интервальные векторы и матрицы и взятие их правильной проекции "pro" будем понимать покомпонентно.

Из (15) по индукции нетрудно заключить, что если рациональное выражение f (x, y) = f (xi,... , xp, yi,... , yq) имеет лишь по одному вхождению каждой переменной в первой степени, то для любых правильных интервальных векторов x G IRp, y G IRq имеет место равенство

min max f

_ x€x y€y x€x y€y J

Более сложный случай, который также может быть обоснован математической индукцией: если рациональное выражение f (x, y) = f (xi,... , xp, yi,... , yq) имеет лишь по одному вхождению переменных y^ в первой степени, то для любых правильных интервальных векторов x G IRp, y G IRq справедливо включение

min max f (x,y), max min f (x,y) С f (x, dual y).

_ x€x y£y x€x y&y J

Интервалы левой и правой частей соотношений (16) и (17) могут быть, вообще говоря, неправильными.

7. Алгебраический подход

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

Предложение 2. Пусть отображение ^ таково, что каждая из переменных ак+1, ..., аг, имеющих 3-неопределённость, входит не более одного раза в первой степени

в единственное из компонентных выражений выполнено включение

У i „з ~ n г- uv i u3

Fs. Если для вектора x G

F(aV + dual a3, X) С dual bV + b3 то X G (F, a, b).

Если каждая из переменных a1, a2,   , ar встречается не более одного раза в первой степени в единственном из компонентных выражений F1; F2, . .., Fs, то верно и обратное утверждение, то есть принадлежность x G (F, a, b) эквивалентна включению (18).

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

min max Fj

L a€av a€a3 a,€av a,€a3

С dual bi,

i = 1, 2,

min max F^a + a, x), max min F^a + a, x)

a€av a€a3 a€av a€a3

С bi

l + 1,...,s,

или, в единообразной форме,

min max Fi

- a,€av a€a3

a€av a€ad

С (dual bV + b3)i, i = 1,..., s.

Если для некоторой точки x выполнено (18), то, комбинируя с (17), получим (19), то есть согласно Предложению 1 x G (F, a, b).

Второе утверждение Предложения 2 непосредственно следует из равенства (16).

Предложение 3. Пусть отображение F таково, что каждая из переменных ak+1, ..., ar, имеющих 3-тип неопределённости, входит лишь не более одного раза в первой степени в единственное из компонентных выражений F1,F2, ...,Fs. Если правильный интервальный вектор x является алгебраическим решением уравнения

F

то x С (F, a, b), иными словами интервальный вектор x является решением задачи (10).

Определение 4. Для интервальной системы F(a, x) = b мы будем называть систему уравнений (20) уравнением в дуализациях, соответствующим ее множеству ав-решений.

Доказательство. Пусть правильный интервальный вектор x является алгебраическим решением уравнения в дуализациях (20) и x G x. Принимая во внимание свойство монотонности по включению арифметических операций в IR, имеем

F(aV + dual a3, x) С F(aV + dual a3, x) = dual bV + b3.

Таким образом, x G (F, a, b) в силу Предложения 2. Поскольку эта принадлежность верна для любого x G x, то x С (F, a, b), что и требовалось.

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

l

Пусть отображение F таково, что каждая из переменных ai, a2, ..., ar входит лишь один раз в первой степени в единственное из компонентных выражений F1, F2, ... , Fs. Если правильный интервальный вектор x является алгебраическим решением уравнения

F(dual a, x) = b,

то x С S^F, a, b), т.е. x является внутренней интервальной оценкой объединенного множества решений системы F(a, x) = b. Этот результат применим, в частности, к интервальным линейным системам (см. [20, 30]).

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

F(a, x) = b,

то x С Svb(F, a, b), т.е. x является внутренней интервальной оценкой для допустимого множества решений системы F(a, x) = b (или, иначе, по терминологии А. Ной-майера [24] и работы [29], решением соответствующей задачи о допусках).

Пусть отображение F таково, что каждая из переменных a1, a2, ... , ar входит лишь один раз в первой степени в единственное из компонентных выражений F1, F2, ... , Fs. Если правильный интервальный вектор x является алгебраическим решением уравнения

F(dual a, x) = dual b,

то x С S^v(F, a, b), т.е. x является внутренней интервальной оценкой управляемого множества решений системы F(a, x) = b.

Наконец, рассмотрим вопрос о качестве интервального решения задачи (10), которое может быть получено с использованием алгебраического подхода, или, иначе, вопрос о размерах интервальной оценки множеств решений (F, a, b). Наиболее сильным из известных на настоящий момент результатов в этом направлении является

Предложение 4. Если все компоненты Fj(a,x) — билинейные функции a и x (т.е. Fj(a,x) = j k ajxk с некоторыми £ R) и каждый aj входит лишь в одно из выражений Fi; то максимальное по включению алгебраическое решение уравнения в дуа-лизациях (20) является максимальной по включению внутренней интервальной оценкой для обобщённого множества решений , или, иначе, максимальным по включению 'решением задачи (10).

Доказательство можно найти, например, в [32].

8. Что дальше?

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

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

Отметим, что даже для интервальной системы линейных уравнений А. В. Лакеев недавно доказал NP-трудность задачи нахождения алгебраического решения в полной арифметике Каухера [21]. Тем не менее, несмотря на этот неблагоприятный факт, для интервальных линейных систем с "не очень широкими" интервалами имеется ряд эффективных численных методов, быстро вычисляющих алгебраическое решение [13, 30]. Таковыми являются субдифференциальный метод Ньютона [30] (превращающийся для некоторых случаев в квазидифференциальный метод Ньютона) и различные модификации одношаговых стационарных итерационных методов [13]. В целом можно считать, что для линейного случая проблема нахождения алгебраического решения интервальных уравнений решается более или менее успешно.

Для общих нелинейных систем конструирование численных методов для решения уравнения в дуализациях является большой интересной открытой проблемой. При развитии подходов к ней главную роль должны, по-видимому, играть конкретные потребности практики, хотя и в общем случае ситуация здесь отнюдь не безнадежная. Несмотря на то, что мы оказываемся лишенными таких эффективных инструментов, как субдифференциальный метод Ньютона и его обобщения, всегда имеется возможность попытаться использовать универсальную схему стационарных итерационных процессов вида x(fc+1) = G( и ее многочисленные модификации: если G имеет сжимающий оператор Липшица, то последовательность сходится к требуемому решению. Другая привлекательная возможность решения уравнений в дуализациях состоит в том, чтобы прибегнуть к помощи какого-либо из пакетов-решателей нелинейных систем, основанных на технике "распространения ограничений" ("constraint propagation"), интенсивно развивающейся в последние годы. Конкретно мы рекомендуем очень мощный решатель UniCalc [15], разработанный в Новосибирском филиале РосНИИ Искусственного Интеллекта и в настоящее время доступный на рынке программных продуктов.

Автор благодарен Хун Хонгу за незабываемые дискуссии по поводу представленных в этой работе результатов.

Список литературы

[1] Акофф Р., САСИЕНИ М. Основы исследования операций. Мир, М., 1971.

[2] АЛЕФЕЛЬД Г., ХЕРЦБЕРГЕР Ю. Введение в интервальные вычисления. Мир, М., 1987.

[3] АщЕпков Л. Т. К проблеме повышения живучести управляемых систем. В:"Модели и методы исследования операций" Наука, Новосибирск, 1988, 69-85.

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

[5] Ватолин А. А. О задачах линейного программирования с интервальными коэффициентами. ЖВМ и МФ 24, №11, 1984, 1629-1637.

[6] ГЕРМЕйЕР Ю. Б. Введение в теорию исследования операций. Наука, М., 1971.

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

[8] Клини С. Математическая логика. Мир, М., 1973.

[9] ЛАКЕЕВ А. В., Носков С. И. О множестве решений линейного уравнения с интер-вально заданными оператором и правой частью. Сиб. матем. журн. 35, №5, 1994, 1074-1084.

[10] МЕСАРович М., ТАКАХАРА Я. Общая теория систем: математические основы. Мир, М., 1978.

[11] Овэн Ж.-П. Нелинейный анализ и его экономические приложения. Мир, М., 1988.

[12] ШАРЫй С. П. Линейные статические системы с интервальной неопределенностью: эффективные алгоритмы для решения задач управления и стабилизации. Вычислительные технологии, ИВТ СО РАН, Новосибирск, 4, у 13, 1995, 64-80.

[13] ШАРЫй С. П. Численное нахождение алгебраического решения интервальных линейных систем. В "Дискретная математика", КГТУ, Красноярск, 1996, 129-145.

[14] AuBIN J.-P. Viability theory. Birkhauser, Boston, 1991.

[15] BABICHEV A. B., KADYROVA O.B., KASHEVAROVA T.P., LESHCHENKO A. S. AND SEMENOV A. L. UniCalc, a novel approach to solving systems of algebraic equations. Interval Computations №2, 1993, 29-47.

[16] BERTI S. The solution of an interval equation. Mathematica 11, №2, 1969, 189-194.

[17] GardeNes E., TREPAT A. Fundamentals of SIGLA, an interval computing system over the completed set of intervals. Computing 24, 1980, 161-179.

[18] KAUCHER E. Algebraische Erweiterungen der Intervallrechnung unter Erhaltung Ordnungs- und Verbandsstrukturen. Computing Suppl. 1, 1977, 65-79.

[19] KAUCHER E. Interval analysis in the extended interval space IR. Ibid 2, 1980, 33-49.

[20] KuPRIYAnOVA L. Inner estimation of the united solution set of interval linear algebraic system. Reliable Computing 1, №1, 1995, 15-31.

[21] LAKEYEV A. V. On the computational complexity of the solution of linear systems with moduli. Ibid 2, №2, 1996, 125-131.

[22] LAKEYEV A. V., Shary S.P., Rohn J. On characterization and complexity of generalized solution sets to interval linear systems. Reliable Computing в печати.

[23] MOORE R. E. In "Methods and Applications of Interval Analysis". SIAM, Philadelphia, 1979.

[24] NEUMAIER A. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, 1990.

102

C. n. ttapbiH

[25] Nickel K. Die Auflösbarkeit linearer Kreisscheiben- und Intervall-Gleichungssystemen. Linear Algebra Appl. 44, 1982, 19-40.

[26] Ratschek H., Sauer W. Linear interval equations. Computing 28, 1982, 105-115.

[27] Röhn J., Kreslova Ja. Linear interval inequalities. Linear and Multilinear Algebra 38, 1994, 41-43.

[28] Shary S. P. On controlled solution set of interval algebraic systems. Interval Computations 2, №6, 1992, 66-75.

[29] Shary S. P. Solving the linear interval tolerance problem. Mathematics and Computers in Simulation 39, 1995, 53-85.

[30] 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, 3-33.

[31] Shary S. P. Algebraic approach to the analysis of linear static system with interval uncrtainty. Rus. J. Numer. Anal. Math. Modelling 11, №3, 1996, 259-274.

[32] Shary S. P. Algebraic solutions to interval linear equations and their applications. In "Numer. Methods and Error Bounds". G. Alefeld and J. Herzberger, eds., Akademie-Verlag, Berlin, 1996, 224-233.

Правила для Авторов

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

1.1. Два экземпляра рукописи, отпечатанных на одной стороне листа стандартного формата A4 (297x210 мм) + файлы рукописи в формате LTEX или AmS-LTEX + файлы рисунков на дискете;

1.2. Два экземпляра рукописи, отпечатанных на одной стороне листа стандартного формата A4 (297x210 мм) + электронная версия рукописи, набранная в текстовом формате Microsoft Word (RTF) + файлы рисунков на дискете.

Время прохождения издательского цикла для рукописей, представленных в форме 1.1, минимально, а для рукописей в форме 1.2 — максимально.

2. Все файлы предоставляются на дискете 3.5" формата 1440 Кбайт. Возможна пересылка файлов по электронной почте jct@ict.nsc.ru в виде *.zip архива. Текстовые файлы и файлы TX представляются в кодировке CP866 (MS-DOS).

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

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

5. Для каждого автора должна быть представлена (на русском и английском языках) в виде отдельного файла следующая информация:

о Фамилия, имя, отчество о место работы и должность о почтовый адрес о ученая степень и звание о год рождения

о телефоны с кодом города

6. Рекомендации по оформлению статьи в LaTeX.

Оформление статьи в LTEX 2.09 Оформление статьи в LTEX 2е

7. Все материалы следует направлять по адресу: редакция журнала "Вычислительные технологии", Институт вычислительных технологий СО РАН, проспект Ак. Лаврентьева 6, 630090, Новосибирск, 90, Россия, Пестунову Игорю Алексеевичу (отв. секретарь) — тел.: +7(3832)343785, Митиной Галине Григорьевне (зав. РИО).

Оформление статьи в LT^X 2.09

Стиль журнала jctart.sty.

Для представления статей на английском языке используйте стиль jctart-e.sty.

Структура файла формата LaTeX должна быть следующей: \documentstyle{jctart}

\setlength{\textwidth}{170mm}\setlength{\textheight}{240mm}

\begin{document}

\pagestyle{myheadings}

\markboth{<^ О. Фамилия автора(ов)>}{<КРАТКОЕ НАЗВАНИЕ СТАТЬИ (ДО 40 СИМВОЛОВ)>} ^^^{<НАЗВАНИЕ CTАТЬИ>\footnote{<Ссылка на поддержку (факультативно)>.}} \author{\sc{<^ О. Фамилия первого автора>}\\

\^{<Место работы первого автора>}\\[2mm] \sc{<^ О. Фамилия второго автора>}\\ \^{<Место работы второго автора>}\\[2mm] ...} \maketitle \begin{abstract} <Текст аннотации> \end{abstract} <Текст статьи> \begin{thebibliography} <Библиография (\item-список)> \end{thebibliography} \end{document}

<Перевод названия статьи на английский язык (или на русский, если статья на английском)> <аннотации на английский язык (или на русский, если статья на английском)>

Список литературы составляется по ходу упоминания работы в тексте и оформляется по образцу:

[1] Иванов И. И., Иванова И. И. К вопросу о вычислительных технологиях // Вычислительные технологии. 1999. Т. 11, №11. С. 1123-1135.

[2] Иванов И. И. Что такое вычислительные технологии? Новосибирск: Наука, 1995.

[3] Ivanov 1.1. Problems in computational techologies // Intern. Conf. Comput. Techs. Novosibirsk, 1988. P. 225-229.

Следует учитывать, что иллюстрации будут воспроизводиться в масштабе 1:1 с разрешением 300 dpi. Наиболее предпочтительной формой представления иллюстраций являются файлы черно-белых растровых рисунков в форматах .pcx, .bmp, .tif или векторном формате PostScript (.eps). Иллюстрации вставляются в текст статьи с помощью следующих команд:

\begin{figure}[htbp]

\hspace*{<сдвиг рисунка по горизонтали в мм>шш} \special{em:graph <имя файла рисунка>} \vspace*{<BbicoTa рисунка в мм>шш} \caption{<Подрисуночная подпись>} \end{figure}

Оформление статьи в ЖГеХ 2е

Для представления статей на английском языке используйте опцию english: \documentclassEenglishKjctart}.

\documentclass{jctart}

\setlength{\textwidth}{170mm}\setlength{\textheight}{240mm} \usepackage{amsmath}

\begin{document} \pagestyle{myheadings}

\markboth{<^ О. Фамилия автора(ов)>}{<КРАТКОЕ НАЗВАНИЕ СТАТЬИ (ДО 40 СИМВОЛОВ)>} \title{<НАЗВАНИЕ СТАТЬИ>\footnote{<Ссылка на поддержку (факультативно)>.}} \author{\sc{<И. О. Фамилия первого автора>}\\

\it{<Место работы первого автора>}\\[2mm] \sc{<И. О. Фамилия второго автора>}\\ \it{<Место работы второго автора>}\\[2mm] ...} \maketitle \begin{abstract} <Текст аннотации> \end{abstract} <Текст статьи> \begin{thebibliography} <Библиография (\iteш-список)> \end{thebibliography} \end{document}

<Перевод названия статьи на английский язык (или на русский, если статья на английском)> <аннотации на английский язык (или на русский, если статья на английском)>

Список литературы составляется по ходу упоминания работы в тексте и оформляется по образцу:

[1] Иванов И. И., Иванова И. И. К вопросу о вычислительных технологиях // Вычислительные технологии. 1999. Т. 11, №11. С. 1123-1135.

[2] Иванов И. И. Что такое вычислительные технологии? Новосибирск: Наука, 1995.

[3] Ivanov 1.1. Problems in computational techologies // Intern. Conf. Comput. Techs. Novosibirsk, 1988. P. 225-229.

Следует учитывать, что иллюстрации будут воспроизводиться в масштабе 1:1 с разрешением 300 dpi. Наиболее предпочтительной формой представления иллюстраций являются файлы черно-белых растровых рисунков в форматах .pcx, .bmp, .tif или векторном формате PostScript (.eps). Иллюстрации вставляются в текст с помощью следующих команд:

\includegraphics{<имя файла рисунка>}

Instructions für Authors

1. The paper may be submitted to the editorial board in one of the following forms:

1.1. As two copies of the manuscript typed on one side of the standard A4 sheet (297x210 mm) + figures on separate sheets + file with electronical manuscript in LTEX or AmSLTeX + files with figures, created in one of the appropriate graphics formats (see below);

1.2. As two copies of the manuscript typed on one side of the standard A4 sheet (297x210 mm) + figures on separate sheets + file with electronical manuscript (saved as RTF-format) with (or without) formules + files with figures, created in one of the appropriate graphics formats (see below).

The duration of the publishing cycle for the manuscripts, submitted in the second form is the longest one and for the manuscript in the forms first - the shortest.

2. All files should be submitted on a 3.5" floppy disc (1440 Kbytes) or sent by e-mail jct@ict.nsc.ru as a *.zip - archive. All text-files and TeX-files in Russian must be submitted in CP866 (MS-DOS) Code Page.

3. The "hard copies"must be typed neatly with a fresh black ribbon. The typing should be double-spaced and lettered as neatly as possible. Any material that cannot be typed such as symbols and formulae should be inked carefully in black meeting the existing standards. The drawings must be printed on a laser or high-quality ink-jet printer or drawn directly in Indian ink on a sheet of a strong (bond) white paper.

4. Each paper must be preceded by an abstract of no more than 300 characters. The title of the paper and its abstract in English should be submitted on a separate sheet accompanied by the list of the key words (not more than 20) in Russian and English as well as the AMS/ZBL classification codes.

5. Authors are required to obtain permission for the publication from the company or institution at which the scientific results presented in the paper had been obtained. The accompanying letter should contain the communicating author, his mail address, telephone number(s), e-mail address.

6. The following information pertinent to every author have to be submitted as a separate file:

o First name, Second name, Last name o Affiliation data: Institution/Organization, Position o Scientific degree, Title o Address

o Telephone numbers, including the area code, Fax number, E-mail address, Homepage URL o Scientific Interests

7. Submission in LaTeX — Case (3). Recommendations.

Using IATEX 2.09 Using IATEX 2e

8. All materials should be mailed to the following address: Journal of Computational Technologies, Institute of Computational Technologies SB RAS, Academician Lavrentyev Ave. 6, Novosibirsk, 630090, Russia, Ph. D. Igor A. Pestunov — Phone +7(3832)343785, Galina G. Mitina.

Writing paper in English in LT^X 2.09

Journal style jctart-e.sty

Writing paper in Russian using L-TX 2.09

Journal style jctart.sty.

In this case LaTeX file structure should look like this: \documentstyle[jctart]

\setlength{\textwidth}{170mm}\setlength{\textheight}{240mm}

\begin{document}

\pagestyle{myheadings}

\markboth{<Name(s) of the author(s)>}{<SHORT TITLE (LESS THAN 40 SYMBOLS)>} \title{<TITLE OF THE PAPER>\footnote{<Name of the supporting institution (optional)>.}} \author{\sc{<Name of the first author>}\\

\it{<Affiliation of the first author>}\\[2mm] \sc{<Name of the second author>}\\

\it{<Affiliation of the second author>}\\[2mm] ...} \maketitle \begin{abstract} <Text of the abstract> \end{abstract} <Body of the paper> \begin{thebibliography} <References(\item-list)> \end{thebibliography} \end{document}

The list of references should only include works that are cited in the text and should be sorted in the order they appear in the text. Here is a short example of the style of references:

[1] Ivanov 1.1., Ivanova 1.1. On computational technologies. Computational technologies // 1989. V. 11, No. 11. P. 1123-1135.

[2] Ivanov 1.1. What is computational technology? Novosibirsk: Nauka, 1995.

[3] Ivanov 1.1. Problems in computational techologies // Intern. Conf. Comput. Techs. Novosibirsk, 1998. P. 225-229.

The preferred representation of figures (along with the hard copy) are the files of black and white or greyscale drawings (resolution = 300 dpi) in the raster formats (.pcx, .bmp, .tif) or as a vector graphics in Encapsulated PostScript format (.ps, .eps). File names for the figures should contain the figure number. Figure captions should be included in the text not in the figure file. The illustrations are inserted into the text by the following commands:

\begin{figure}[htbp]

\hspace*{<horizontal shift of the drawing in mm>mm} \special{em:graph <name of the drawing file>} \vspace*{<height of the drawing in mm>mm} \caption{<caption>} \end{figure}

Writing paper in LT^X 2e

Writing paper in English use the option english: \documentclass[english]{jctart}. \documentclass{jctart}

\setlength{\textwidth}{170mm}\setlength{\textheight}{240mm} \usepackage{amsmath}

\begin{document} \pagestyle{myheadings}

\markboth{<Name(s) of the author(s)>}{<SHORT TITLE(LESS THAN 40 SYMBOLS)>} \title{<TITLE OF THE PAPER>\footnote{<Name of the supporting institution (optional)>.}} \author{\sc{<Name of the first author>}\\

\it{<Affiliation of the first author>}\\[2mm] \sc{<Name of the second author>}\\

\it{<Affiliation of the second author>}\\[2mm] ...} \maketitle \begin{abstract} <Text of the abstract> \end{abstract} <Body of the paper> \begin{thebibliography} <References (\item-list)> \end{thebibliography} \end{document}

<Russian translation of the paper title for papers in Russian> <Abstract in Russian>

The list of references should only include works that are cited in the text and should be sorted in the order they appear in the text. Here is a short example of the style of references:

[1] Ivanov 1.1., Ivanova 1.1. On computational technologies. Computational technologies // 1989. V. 11, No. 11. P. 1123-1135.

[2] Ivanov 1.1. What is computational technology? Novosibirsk: Nauka, 1995.

[3] Ivanov 1.1. Problems in computational techologies // Intern. Conf. Comput. Techs. Novosibirsk, 1998. P. 225-229.

The preferred representation of figures (along with the hard copy) are the files of black and white or greyscale drawings (resolution = 300 dpi) in the raster formats (.pcx, .bmp, .tif) or as a vector graphics in Encapsulated PostScript format (.ps, .eps). File names for the figures should contain the figure number. Figure captions should be included in the text not in the figure file.