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

£9 11

Российская академия наук Уральское отделение Институт Математики и Механики

На ираиах рукописи ШАРЫ И Сергей Петрович

УДК 5!9.0

Решение „внешней" и „внутренней"

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Екатеринбург— 1992

Работа выполнена р» Вычислительном Центре СО РАН н городе Красноярске.

Научпыи руководитель:

доктор физико-математических наук, профессор В. В. Шай-дурои

Официальные оппоненты:

доктор физико-математических наук, профессор В. П. Ильин

кандидат физико-математических наук А. А. Ватолин

Ведущая организация:

Институт Вычислительных Технологий СО РАН (г. Новосибирск)

Защита состоится 24 ноября 1992 года в 15 часов на заседании Специализированного Совета К 002. 07. 01 по присуждению ученой степени кандидата физико-математических наук при Институте Математики и Механики УрО РАН (г. Екатеринбург, ул. Софьи Ковалевской, 16).

С диссертацией можно ознакомиться в библиотеке Института Математики и Механики УрО РАН.

Автореферат разослан 22 октября 1992 года

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

Специализированного совета кандидат физико-математических наук В. Д. Скарин

1 ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Характерная черта тех исследований, где интервальный анализ применяется для автоматического учёта ошибок охруглепнй на ЭВМ с конечной разрядной сеткой, — допущение о малости интервалов изменений "входных" данных, позволяющее во многих случаях осуществлять асимптотический анализ и т.п. Но погрешности вычислений необходимо учитывать при этом во всех без исключения операциях на ЭВМ. Напротив, в тех работах, где интервальный анализ служит средством для изучения ограниченных но амплитуде неопределённостей, размеры "входных" интервалов могут быть сколь угодно валют, по зато предполагается, что все арифметические операции как с точечными величинами, таг н с интервалами выполняются абсолютно точно. В атом же духе выдержана и реферируемая диссертационная работа, посвященная теоретическому анализу н построению численных алгоритмов решенпя двух задач — "внутренней* и 'внешней" — для интервальных линейных алгебраических систем.

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

А г — Ь . (1)

Все они обозначаются обычно одной формальной записью

Аг = Ь. (2)

— "интервальной системой линейных алгебраических уравнений" (ЙСЛАУ) с интервальной т х п-матрицей А Э А и интервальным т-вектором правых частей Ь Э Ь, хотя смысл, вхладываемый при этом в понятие "решения интервальной системы", существенно различен.

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

всевозможных точечных систем (1), содержащихся в (2), — так называемого объедтшёшмго множества решений (ОМР)

А, Ь) = { х 6 К* | (ЗА 6 А)(3 Ъ € Ъ)(Ах = Ь) }. Как правило, её формулируют в следующем виде:

найти интервальный вегтор V, содержащий объединённое множество решений данной ИСЛАУ.

(3)

Если компоненты V имеют наименьшую возможную ширину — совпадают с проекциями Х*(А, Ь) на координатные оси, — то V называют оптимальным, интервальным решением задачи (3), а соответствующие покоординатные оценки Х*(А, Ь) — оптимальными. Часто, имея в виду иыеяно эту задачу, говорят просто о решении интервальной системы линейных алгебраических уравнений, но мы используем для (3) термин онегииал задача для интервальной системы линейных алгебраические уравнений, всё более распространяющийся в последнее время.

Помимо объединённого множества решений важные теоретические и практические приложения обнаруживает в последние годы другое, допустимое множество решений (ДМР) интервальной линейной алгебраической системы

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

Общепризнанное название этой постановка — линейном задача о допусках (ЛЗД), но не менее, часто о ней говорят также как о внутренней задаче для интервальной системы линейных алгебраических уравнений При прочих равных условиях предпочтительней иметь её решением боле« широкий интервальный вектор, но понятие максимального интервалы» го решения ЛЗД не получило пока широкого распространения.

Специфическая особенность линейной задачи о допусках — возможность для ДМР быть пустым даже для "хороших" исходных данных за дачи. В таких ситуациях постановка (4) становится бессмысленной и

Ь) = { « € К* | (УД € А)(3 Ь е Ъ)(А® = Ъ) },

найти интервальный вектор и , содержащийся в допустимом множестве решений данной ИСЛАУ.

(4)

потому говорят о "неразрешимости* ЛЗД. Соответственно, из общей лостановхи лилейной задачи о допусках выделяется более узкая подзадача исследования её разрешимости:

является ли непустым допустимое множество решений данной ИСЛАУ ?

Отметим, что "внутренняя" и "внешнля" задачи для ЙСЛАУ отнюдь эге исчерпывают всего многообразия возможных постановок задач для интервальных систем алгебраических уравнений. Во-первых, имеется большая свобода в определенна того, что следует понимать под множеством решений интервальной системы уравнений. Во-вторых, весьма различавши могут быть способы оценивания множества решений. В рассматриваемых в этой диссертации задачах допустимое множество решений ИСЛАУ приближается "изнутри", а объединённое множество решений — "снаружи". Но существуют и другие популярные постановки, с иными требованиями к оцениванию множеств решений.

"Внешняя задача" для ИСЛАУ — одна из классических задач интервального анализа, находящая многочисленные и разнообразные приложения. За прошедшие три десятилетня методология её решеиия претерпела эволюцию от подражания известным вещественным методам решения СЛАУ до создания самостоятельных "интервальных" концепции и подходов. Среди работ последних лет отметим исследования Б.С. Добронца, Ю. Гарлоффа, Д. Гея, Р.Б. Кирфотта, Г. Манера, А. Ноймайера, К. Нигелл, И. Рока, 3. Руина, X. Шваддта.

Особую ценность и и теории и для практики имеет получение оптимальных решений "внешней задачи", но такая её усиленная постановка оказалась крепким орешком : большинство разработанных до сих пор методов позволяют эффективно находить интервальный вектор V 2 Х*(А,Ъ), но лишь немногие из практических алгоритмов обеспечивают в общем случае его оптимальность, причём все они имеют пассивный переборный характер и чрезвычайно трудоемки. Большинство исследопа-гелей склоняются сейчас к выводу о принципиальной труднорешаемости "внешней задачи" в оптимальной постановке. Одним из основных итогов реферируемой работы является построение целого класса так зазываемых РвБ-алгоритмов для нахождения именно оптимальных или близких к оптимальным решений ЕСЛАУ. Трудоёмкость их выполнения в худшем случае экспоненциальна но размерности, но они являются адаптивными и в среднем демонстрируют высокую эффективность. В диссертации дока-5апа сходимость РБ Б-алгоритмов и рассмотрены некоторые из их обобщений на случай более общих интервальных алгебраических задач.

Подход х решению линейной: задачи о допуска.";:, принятий в настоящей дкссертацаи. развивался ранге в работах II.Л. Хлсбалкна, В.Б. Шайду-рога, А. Есймайера. Его условно мо;:<но назвать "центровым": сначала ищется кгхая-ннбудь точка, удовлетворяющая условиям задачи (т.е. но-ставленная задача исследуется на разрешимость), а затем ун;е> в случае успеха, вокруг нее, как вокруг центра, строятся интервальное решение. Ба основе этого подхода в представляемой диссертационной работе построена полная "технологическая цепочка" решения ЛЗД, позволяющая для задачи практически любой размерности получить приемлемое по ширине решение, лн5о обоснованное заключение о её неразрешимости. Кроме того, с целью более информативного опнеаыхя задачи шл впервкг вводим ряд числовых характеристик ЛЗД, позволяющих точнее судить о степени разрешимости или неразрешимости рассматриваемой задачи, проводить изменение (коррекцию) её входных данных— матрицы и правой части —• б соответствии со смыслом исходной содержателыюй постановки.

Результаты диссертационной работы докладывались на Всесоюзных Совещаниях со интервальной математике в Дпвиогорске (1937 год), в Красноярске (1988 год), в Абакане (1989 год), Ростове-на-Дону (1990 год), Бишкеке (1991 год), на. конференциях "Интервальная математика" (Саратов, 1989 год), "Перспективы к опыт внедрения статистических методов в АСУ ТП" (Тула, 1990 год), "Актуальные проблемы прикладной математики" (Саратов, 1991 год), "Интервальная математика и её приложения" (Абрау-Дюрсо, 1992 год), на Всесибирской Школе молодых ученых ио вычислительной математике (Новосибирск, 1989 год), на семинарах ВЦ СО РАН в г. Красноярске, Института Вычислительных Технологий СО РАН (г. Новосибирск), в Институте Математики СО РАН на семинаре С.К.-Годунова, на семинаре Института Математики и Механики УрО РАН (г. Екатеринбург).

2 СОДЕРЖАНИЕ РАБОТЫ

Структурно диссертация состоит из Введения, указателя основных обозначений, соглашений и аббревиатур, собственно основного текста, разбитого на две Главы (посвященные "внешней" а •'внутренней" задачам для ИСЛАУ, соответственно), Заключения, списка литературы и Приложения. Её общий объём — 213 страниц машинописного текста. Мы предполагаем уке известными читателю основные понятия: и факты интервального анализа, не уделяя их развёрнутому изложению специального места я диссертации. Вместо этого в сцисог основных обозначений

б

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

S, а — правый и левый концы интервала а , соответственно,

med а = (а + а)/2 — середина (медиана) интервала а ,

wid а = (а— а) — пгарнна интервала а ,

|а| = max{|ä|, |а|} — абсолютная величина интервала а ,

, ч Г rain{|ä|, ¡a|}, -геля 0 £ а ,

\а/ = i « — наименьшее из расстоянии

I 0 , иначе г

v ' точек интервала а до нуля.

Первые параграфы обеих Глав основного текста. (§1 и §7) содержат подобное обсуждение постановок решаемых задач и обзор предварительных результатов. Назначение §2 — взестп и всесторонне исследовать гозуго характеризацшо объединённого ьшсетестза решений ЙСЛАУ. Её •лавные достоинства — простота н способность рагличать точки топо-югнчесзон внутренности з границы (ЩР. Кроме того, эта характериза-шя кладется нами а основу удобного критерия разрешимости "внешней здачи" для ЙСЛАУ.

Пусть А ■—интервальная тхп-ндтряца, Ь — нятер: ;лышйгп-вектор, í выражением

Uni (г: А,Ь) = min | i ■wid Ь,- - / med Ь< — Y) fí¡:-s¡ \ \ i<i<™ ¡^ 2 \ ¡-i i )

адается функционал Uni : Ii" —► R. 1Ъгда принадлежность s € í*(A,b) равносильна Uni (a;A,b) > 0, т.е. объединённое множество >ешепий соответствующей НСЛАУ есть лебегово множество {г G R* | Uni (ж;А,Ь) > 0}. Функционал Uni — вогнутый з r-ùsîhou сртанте Г, а если в интервальной матрице А некоторые столбцы — целиком ■ещзстзенпыс, то Uni (ж; Л, Ь) вогнут и на объединениях нескольких ортитов.

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

Бели матрица А имеет I (I < п) вещественных столбцов, то множество Х*{А, Ь) являете« объединением не более чем 2я"' многогранных множеств.

Функционал Uni (s; A, b) достигает конечного максимума на всем R*. Если г — точка топологической внутренности int X*(А,Ь) объединённого множества решений, то Uni (г; А,Ь) > 0. При некоторых дополнительных ограничениях на Л, bus верно и обратное: из принадлежности s € int Х\А,Ъ) слсдузт Uni (г; A,b) > 0.

Далее, в §3, для вычисления точных покоординатных оценок объединён шго множества решений ИСЛАУ мы конструируем, отталкиваюсь от известного в комбинаторной оптимизации "метода ватвай и границ", несложную вычислительную процедуру — простейший PSS-алгоритм. Ис ход пой является следующая эквивалентна! переформулировка "внешне задачи" для ИСЛАУ:

для системы Ах = Ь оценить mm{ х, | х 6 Х*(А, Ь)} снизу и max{a:„ | ® € Х*(А,Ь)} сверху, v = 1,2,...

При этом мы занимаемся вычислением только min{ zv | х € X*(A,b)} для произвольной, но фиксированной компоненты и, поскольку

max{ xv J г € Х*(А,Ь)} = -тт{ », \ ж € ЛГ*(А,-Ъ)},

и предполагаем известным в качестве начального приближения некото рый интервальный вектор V Э Х*(А,Ь). Он может быть легко найден каким-либо из известных алгоритмов для решения "внешней задачи", г его размеры не играют существенной роли.

Обозначим для вектора г - (ri,...,iw,r„+i,...,г»)т через l(r) прямую вй'с параметрическим уравнением

(5]

(у £ R — параметр), параллельную у-ой координатной осн. Пусть также

П(г) = min{ х„ | з € Х'(А,Ъ) П 1(0}

— наименьшее значение f-ой координаты точек из пересечения 1(г) < объединённым множеством решений ИСЛАУ (при этом mm 0 = -boo).

Для всей первой Главы диссертации фундаментальным является фак представления "внешней задачи" для ИСЛАУ как оптимизационной, т.«

зх — fi,

=

г„ = У,

ЗИ-1 Г.

г» Г»

падачи минимизации функции J2(г) на конечномерном компакте: min{ xv I х € J£*(A,b)} = rab{ (J {3y|ieX*(A,b)niM}} (6)

= min{ ft(r) I г e (Vlt...,V*-„Vrtl.....V,)}.

йо неприятной особенностью целевой функции в (б) является отсутствие

нее в общей случае даже непрерывности, что существенно суживает Фуг алгоритмов глобальной оптимизации, применимых к задаче (6).

Тем не менее, в диссертации демонстрируется возможность успешного зешепия "внешней задачи" для ЙСЛАУ в представлении (6) с помощью :>яда алгоритмов, основанных"яа адаптивном дроблении области определения целевой функции. В интервальной математике после пионерской заботы С. Скелбоу методы подобного типа интенсивно разрабатывались P.E. Муром, IJ.Р. Хансеном, X. Рачегам и другими авторами. Нам лишь требуется указать способ нахождения для целевой функции П(г) миноранты ло области (нюяясго конца интервального расширения), т.е. для любого г = (Г),... ..., гя) нужно уметь оценить снизу

min{ ß(r) f г € г } - ию{ xv | х € Х'(А, Ь) Л 1(г)}. (7)

Простейший способ сделать это заключается в следующем. "Подста-злм" параметрическое уравнение (5) в ЙСЛАУ (2), которая превратится ipii этой з систему тп лянсГпшх уравнений с одним единственным неизвестным у н интервальными коэффштепташг: * »

jalj^y

(8)

П

Решением ¿-го уравнения этой системы является множество

f Ь, - £ a^-j / сц„ (9)

-де "/" — знак деления в расширенной интервальной арифметике Ка-саиа, допускающей деление на яульсодержаздке интервалы. Взяв далее тсрессчение всех решеш1й (9) отдельных уравнений системы (8), получим некоторое множество которое, как нетрудно показать, содержит

и,ег{ в„ | а € Х*(А, Ь) П ¡(г)}. Поэтому величина

П(г) = 1шп{ <5 П V,,}

даёт требу е&гую оценку сешзу дда (7). Если же для некоторого г система (8) несовместна (что соответствует Х*(А, Ь) П ¿(г) = 0 для веек г € г), то полагаем П(г) = +сс.

Простейший алгоритм, вычисляющий шп{ яи | г 6 .Х*(А,Ь)}, представляет собой процесс последовательного уточнения оценки для неге снизу, оформленный в соответствии с известной стратегией "метода ветвей к границ", В данном случае "ветви" образуются путём разбиения исходного прямоугольника (VI,.. .. ,У„) па более мелкие

(»—1)-мерные прямоугольники Р, а нахождение "границ" — это вычисление оценок П(Р). Алгоритмом порождается упорядоченный список Ь, образованный парами* (Р, Й(Р)) в порядке возрастания величины Я(Р), так что у первой пары списка (£3,Й(<3)) оценка $2(0.) — наименьшая. Назовем эту пару, а также соответствующие прямоугольник О и оценку Л((2) ведущими, на данном шаге. Перед началом выполнения алгоритма список Ь состоит из единственной пары ((V-!, ..., У„_1, У„+1, ..., "У„), 3&,), а далее запускается шследовательность шагов, на каждом из которых выполняются следующие инструкции:

1. Выбираем в ведущем прямоугольнике компоненту к наибольшей длины, т.е. такую что тяИ (Зь = т&Х!^»

2. Рассехаем ведущий прямоугольник <3 по »-он компоненте пополам на прякоутольннхи-потошеи Q' и такие что

Q' = (<$ь • • -, <3*-1, 1шее! ], СЬ+ь..., д.),

О" = (СЬ,..., Ъь-и [ тес! ..., О»),

3. Вычисляем оценки Й(С}') а Я(С2").

4. Удаллен бывшую ведущей пару (С}, П(С£)) из списка Ь.

5. Новые пары (<}',0(<3')) и (С5",П(<2")} заносим в Ь так , чтобы сохранить его упорядоченность по значению второго элемента.

Результатом работы этого алгоритма является неубывающая последовательность ведущих оценок {Й(<3)}, которая, как показано в Приложении, при некоторых условиях на А, Ь и V сходится к точному значению пиа{ 1»|:6 Х*(А, Ь)}. Выписанный выше алгоритм и другие, ему подобные, предназначенные для решения "внешней задачи" для интервальных систем алгебраических уравнений, н имеющие в своей основе ада-

птивиое дробление множества решений, мы называем PSS-алгоритмами (от adaptive Partitioning of the Solution Set).

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

в после выявления монотонности целевой функции на прямоугольниках списка L по тем или иным переметным уменьшают размерности этих прямоугольников;

• строят для целевой функции более точную миноранту по области ;

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

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

В §4 диссертаций: подробно рассматриваются возможности модификации простейшего PSS-алгоритма с помощью каждого из этих приемов, за исключением самого первого, т.к. рагрьшность целевой функции ft(r) делает обнаружение её монотонности практически неподъёмным.

Обобщения традиционной постановки "внешней задачи" для иптео-вальной линейной системы, которые могут быть успешно решены с помощью некоторых PSS-алгорятиоз, являются предметом §5. Мы рассматриваем, в частности, трудную "внешнюю задачу" для ИСЛАУ со связанными коэффициентами.

Завершает первую Главу §6, содержащий сравнительный анализ численных экспериментов с различными PSS-алгоритмами. Самостоятельным результатом этого параграфа можно считать также предложенное впервые параметрическое семейство ИСЛАУ для тестирована я алгоритмов решения "внешней задача".

Тема второй Главы диссертации — решапне линейной задачи о допусках, т.е. "внутренней задачи" для ИСЛАУ. Посла вводного §7 мы излагаем в §8 простой достаточный признак неразрешимости ЛЗД, предназначенный для предварительного грубого исследования реальных задач. В его основе — введенный X. Рачекои для харахтерязации "относительной узости" ненулевых интервалов фупкциоиал

а/а , если |в| < ¡а|, a/a , иначе.

Пусть в лишенной задаче о допусках с интервальной шхп-иатрнцей А п интервальным rra-вектором правых частей b для некоторого к £ {1,2,... ,т} справедливы условия

(О О0ЬА)

(ii) тах{ x(tty) | 1 < 2 < n, а*;- ф 0 } < x(bt). Тогда данная ЛЗД неразрешима.

Если применение этого признака не позволяет сделать нихакого определенного заключения, следует воспользоваться результатами следующего §9, в котором построен точный критерий разрешимости ЛЗД. Соответствующая теория совершенно аналогична той. что была развита в §2 диссертации, во при этом мы уделнлн больше внимания вопросам коррекции (приведения) ЛЗД к разрешимому виду, определения поры неразрешимости и др., имеющим большое практическое значение.

Пусть А — интервальная mxn-матркца, b — интервальный т-вектор, и выражением

/

Toi (г; A, b) = min

задается функционал Toi : R" —» R. Тогда принадлежность х £ Х,(А,Ъ) равносильна Toi (s; A,b) > 0, т.е. допустимое множество решений соответствующей ИСЛАУ есть лебегово множество { г: G R" | Toi (s; А,Ь) > О }. Кроме того, функционал Toi вогнутый и достигает своего конечного максимума на всем И*. Если интервальная магркда А задачи не имеет нулевых строк, то нз х 6 int X,(A,b) ф 0 следует Toi (х; А, Ь) > 0. Обратно, если Toi (з;А,Ь) > 0, то а; £ int Х,(А,Ь).

Как следствие этих результатов, мы естественно приходим к следующему "конструктивному" критерию разрешимости линейной задачи о допусках:

Решаем задачу безусловной максимизации функционала Tol(x; А, Ь). Пусть шахзе»« Toi (х; A, b) = Т и достигается в точке t, Тогла

-если Т > 0 , то ЛЗД разрешима и i е Х.( A, b), а если Т> 0,

то te int Х.(А, b) ; — если Т < 0 , то рассматриваемая ЛЗД неразрешима.

Для отыскания максимума негладкого вогнутого функционала Toi на К" эффективны широко известные субградиеитные методы.

■wid bi •

med b, - £ >=1

Продемонстрируем теперь, как с помощью функционала Toi можно корректировать входпые данные задачи, делая её разрешимой, или, если исходная ЛЗД имеет решения, очерчивать область вариаций ее входных данных, не выводящих задачу за пределы разрешимого состояния. При неизменных А и med b увеличение ширины всех компонент вектора Ь на одну и ту ке величину 1С > 0 ткет следствием добавлению к функционалу Toi адднтивпой константы С, гак что

при е = ([—1;1],...,[—1;1])т. Поэтому, если исходная задача о допусках была неразрешима и Г = max~eä« Toi (ж; А, Ь) < 0, то путём ушире-ния вектора правых частей на 2Се, С > |Г|, можно при той же матрице А сделать ее разрешимой. При этом найденные ранее точки t € Arg max Toi (x; A, b) будут заведомо принадлежать непустому уже множеству Х,(А, Ь + 2Се). Наоборот, если Т = тахг£в« То) (х; А, Ь) > О, т.о. если исходная задача о допусках разрешима, то она останется таковой даже после уменьшения ширины всех компонент правой части на 2С, С < Т.

Иногда на практике одинаковое уширение всех компонент вектора Ь может быть неприемлемым. Предположим поэтому, что задан положительный вектор (71,72, • - • ,7т), Уi > 0, такой что увеличение ширины Ь,-должно быть пропорциональным 7,-. Далее вычисляем

Если, к прнмеру, линейная задача о допусках с матрицей А и вектором правых частей Ь первоначально не имела решений, то ЛЗД с той же матрицей А и расширенным вектором (Ъ<+ 2С71-[-1;1])£,1 в правой части становится разрешимой при С > |Т7|. Важнейший частный случай рассмотренной конструкции — обеспечение одинаковых относительных (пропорциональных абсолютным значениям) увеличений ширины компонент правой части, когдащ = |Ь;| для ненулевых Ъ,-, г = 1,2,...,т. Абсолютная величина соответствующего Тт может служить мерой неразрешимости данной задачи о допусках, или, напротив, мерой запаса её разрешимости.

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

max Toi (г; A, b + 2Са) = С + шах Toi (г; А, Ь).

Т7 = шах То17(к;А, Ь),

где

допусков для его отдельных компонент задается с помощью вещественного вектора и> — > 0,так что тоё II;/ упй ХТ^ Поскольку путем масштабирования с помощью диагональной матрицы ¿^{гщ,^,. ..,юа} подобные случаи легко сводятся к одному стандартному, когда 10 = (1, 1, ...,1)и вам требуется вписать гиперкуб в соответствующим образом модифицированное множество _Х,(А,Ь), то впредь линейной задачей о допусках — "внутренней задачей" для ИС Л АУ Аг = Ь — можно считать задачу отыскания интервального вектора и с компонентами одинаковой ширины и такого, что {Ах | А е А, я С и} С Ъ.

Основу §10 составляет новый вывод основополагающей формулы для размеров интервала-решения ЛЗД, впервые предложенной В.В. Шайду-ровым:

Если t € Х»(А,Ь) , то при

г = пив mm

!<«<»» Ai А

\ v?i<i bj ■

med bi — ttijij

3" i

El «Vil t=i

(10)

интервальный вектор (i-f re) также целиком содержится в л«(А, Ь).

Такны образом, при известной точке t g Х,(А,Ь) построение интервального решения лилейной задачи о допусках сводится к нахождению величины (10) или же оденет для нее снизу. Поскольку взятие минимума по i е {1,2_____ m} ке представляет трудностей, оснозная тяжесть ложится при этом на вычисление шшлед. Простейший способ его оценивания заключается во взятии для выражения в фигурных скобках в (10) левого Еонца естественного интервального расширения, как это осуществлено s следующем алгоритме:

Для данного t 6 Х,(А,Ь) вычисляем интервалы

-а

wid Б,- —

med hi - £

) 1

i = 1,2,... ,m, и затем полагаем h = mini<,<,n.h». вектор (t + he) является решением ЛЗД.

Интервальный

Оказывается, что получаемые таким способом результаты полностью совпадают с теми, что даёт известный метод А. Наймайера. Оба эти алгоритма просты, легко реализуемы, по ценой значительного огрубления результата.

В следующем §11 попазапо, кол по формуле из §10 размеры инте-рзалъ-)го решения ЛЗД могут быть вычпслочы точно. 3 основа соогзетстзу-щего алгоритма — факт нвазипсгпутости фупхцип з фигурных скоб-IX (10) от аргументов с»,-. По этой причине для каждого i — 1,2,...,п чиимэл ыше значения но Л S А достигаются з Ееряшнгх ннтерваль-?го вектора (a,-i,a¿3,... ,а,ч) и .могут бнть найдены прямым перебором, чего бгрстся мппимуп по г. Трудоёмкость выполнена такого ал-зритма, пропорциональную к • 2", мсжпэ значительно уменьшить, если :::од вершип осуществлять спсцхалтдна-гм образом, переходя на каждом пге к соседней вершине и реххурептпо пергычпелга; суммы med b¡ — M a'-ixj n Яри этом выигрыш а трудоемкости будет тем зка-

зтельней, чем больше размерность задачи, хотя её зхспопепцпалъный ipaxïep всё-тагн не устраняется. Поэтому прахтзчесхое значешгэ пред-iracKbix в §10 алгоритмов исчерпызаетск лишь задачами Ее очень больной размерности.

Построению более сложного, но и более совершенного алгоритма для ачисления размеров интервала-решения ЛЗД посвящен §12. Имея в сво-t основе "метод ветвей и границ", сн занимает промежуточное тгеложе-ае между простейшим алгоритмом §10 и переборными алгоритмами §11. рудоёмкость его реализации в худшем случае тахгяе эвепонекцзальяая ;ак и для всех методов подобного сорта), но, благодаря гибкой зычи-гательпой схеме, он с успехом может быть применён к задачам любой азмерностп.

Накочец, последний §13 призван продемонстрировать нар&ботаинунго во горой Главе диссертации технику в применении ж конкретной прахтп-еской проблеме, в качестве которой мы выбрали экономическую задачу аализа межотраслевого баланса (уравнения Леонтьева) с интерзально еопределёшшмл данными.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

лазные результаты диссертации состоят а следующем:

1. Для объединённого л допустимого множеств решений интервальной линейной алгебраической системы предложены новые харахтернза-иии в виде лебеговых множеств некоторых специальных "распознающих" функционалов. На этой оснозе получены критерии разрешимости "внешней" а "внутренней" задач для ИСЛАУ. Особую практическую значимость эти результаты имеют в отношении "внутренней" задачи для ИСЛАУ (лилейной задачи о допусках).

2. Для отыскания оптимальных решений "внешней" задачи для ЛСЛА2 построен класс PSS-алгоритмов, основанных на идее адантивноп дробления объединённого множества, решений интервальной систе мы. Указаны некоторые возможные обобщения этих алгоритмов, касающиеся, в частности, интервальных линейных алгебраически: систем со связанными коэффициентами.

3. Для "внутренней" задачи для ИСЛАУ (линейной задачи о допус ках) предложен простой признак неразрешимости, использующий сравнение "относительной узости" элементов интервальной матрицы ИСЛАУ и её правой части.

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

4 СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Шайдуров В.В., Шарый С.П. Решение интервальной алгебраическо; задачи о допусках. - Красноярск, 1988. - 27 с. - ( Препринт / ВЦ СО АН СССР ; No. 5 ).

2. Щайдуров В.В., Шарый С.П. Интервальная алгебраическая задача с допусках // Информационно-оперативный материал (интервальный анализ). - Красноярск, 1988. - ( Препринт / ВЦ СО АН СССР ; No. 6 ). - С. 38-40.

3. Шайдуров В.В., Шарый С.П. Интервальное решение алгебраически задачи о допусках // Труда Первого советско-болгарского семина ра по числовой обработке, Переславль-Залесскнй, 18 - 24 октябр; 1987 г. / Институт Программных Систем АН СССР : Переславль-Залесскнй, 1988. - Дед. в ВИНИТИ, No. 2634-В89. - С. 137-140.

4. Шайдуров В.В., Шарый С.Л. Некоторые методы решения линейно! задачи о допусках // Информационно-оперативный материал (интервальный анализ). - Красноярск, 1989. - ( Препринт / ВЦ СО АН СССР ; No. 9 ). - С. 38-41.

5. Шарый С.П. Об одной интерзальной задаче линейной алгебры // Информационно-оперативный материал. - Красноярск, 1987. - (Препринт / ВЦ СО АН СССР; No. 2 ). - С. 45-46.

6. Шарый С.П. О некоторых методах решения линейной задачи о допусках. - Красноярск, 1989. - 45 с. - ( Препринт / ВЦ СО АН СССР ; No. б ).

7. Шарый С.П. Об оптимальном решении интервальных систем линейных алгебраических уравнений. I. - Красноярск, 1989. - 24 с. - Дел. в ВИНИТИ, No. 4180-В89.

8. Шарый С.П. К вопросу разрешимости линейной задачи о допусках. - Красноярск, 1990. - 8 с. - Деп. в ВИНИТИ, No. 3353-В89.

9. Шарый С.П. О характеризацви объединенного множества решений интервальной линейной алгебраической системы. - Красноярск,

1990. - 20 с. - Деп. в ВИНИТИ, No. 726-В91.

.0. Шарый С.П. Оптимальное решение интервальных систем линейных алгебраических уравнений / J Информационно-оперативный материал. Часть 1 (интервальный анализ). - Красноярск, 1990. - ( Препринт / ВЦ СО АН СССР ; No. 16 ). - С. 39-41.

1. Шарый С.П. О разрешимости линейной задачи о допусхах // Интервальные вычисления. -1991. - No. 1. - С. 92-97.

2. Шарый С.П. Новый класс алгоритмов для оптимального решения интервальных линейных систем // Конференция "Актуальные проблемы прикладной математики", Саратов, 20 - 22 мая 1991 г. - Саратов-,

1991. - С. 113-119.

3. Shaxy S.P. Optimal solution of interval linear algebraic systems. I. // Интервальные вычисления. - 1991. - No. 2. - С. 7-30.

4. Shary S.P. Solving interval linear algebraic systems optimally. I. // Advances in Modelling & Analysis, C. - 1992. - Vol. 33, No. 4. -

P. 1-28.