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

Дб. Слеранскш, ЛВ. Куприянова. Некоторые задачи теортдрскретных пшенных систем

УДК 688.511.2

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

Д.В. Сперанский, Л.В. Куприянова

Саратовский государственный университет,

кафедра математической кибернетики и компьютерных наук

E-mail: speranskiydv@info.sgu.ru

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

1. Введение

Some interval problems of the theory of discrete linear systems

D.V. Speranskiy, L.V. Kupriyanova

Artificial neural networks can be used effectively for a quite general class of problems. Still there exists no formal foundation of some important constructions used in the theory. In this paper an attempt is undertaken to formalize some concepts of neuroinformatics and consider their properties from the point of view of applied universal algebra. It is proposed to treat neural networks as heterogeneous algebras which has made it possible to prove for them basic results similar to algebraic theorems on homomorphisms and congruences.

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

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

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

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

Ясно, что "смешанные" СЛАУ можно решать известными методами, ориентирующимися на интервальные системы. Однако применение вышеупомянутых методов в этом случае напоминает стрельбу из пушки по воробьям.

Предлагаемая статья посвящена некоторым задачам, возникающим в теории линейных систем, которые сводятся к решению смешанных СЛАУ. Для решения таких систем мы предлагаем использовать метод, основанный на некоторых результатах Шарого [6].

2. Объект исследования и основные понятия

Объектом нашего исследования является дискретная ЛС [8], заданная над полем вещественных чисел R следующими уравнениями переходов и выходов:

s

y

Здесь t — момент дискретного времени; А = [ад]пхп, В = [¿у]„х/, С = [cy]mx„, D = [d'v]mxJ — характеристические матрицы. Все элементы матрицы — точные величины из R. Входной вектор й(t), выходной вектор y(t) и вектор состояния J(t) представляют собой упорядоченные наборы-столбцы из того же поля R:

«(О=[«,»•,U,(/)]', ко - U (0,-.ут (Of, s(t)=к(t),...,sn(t)l

Пространство состояний ЛС обозначим Sn, и величину п назовём размерностью системы.

Методом математической индукции можно доказать, что конечное состояние и выходная реакция ЛС на входную последовательность ¿7(0), ¿7(1),..., U(k-Y) длины к при начальном состоянии s (0) ЛС вычисляются по формулам

s

у

По аналогии с терминологией в теории дискретных линейных автоматов (ЛА) [7], формулу (4) назовём формулой полной реакции ЛС.

Для ЛС введём некоторые понятия, имеющие аналогии в теории линейных автоматов.

Входная последовательность м(0), м(1),..., и(к-Х) называется синхронизирующей последовательностью (СП), если и только если

^(0Ш0)е

А%

Д.В. Сперанский, ЛЯ Куприянова. Некоторые задачи теории дискретных пшенных систем

Содержательно это определение означает, что СП переводит ЛС в одно и то же финальное состояние независимо от того, из какого состояния она стартовала.

Теорема 1. Для того чтобы ЛС, заданная уравнениями (1) и (2), имела СП длины к, необходимо и достаточно, чтобы Ак = [0], где [0] — нулевая матрица.

Доказательство. Перенеся правую часть уравнения (5) налево, мы получим

^(0), ?2(0)е Ак (5, (0)-52 (0)) = [0].

Поскольку ^ (0) и 52(0) — произвольные состояния из 5„, то их разность (обозначим её через 5) также является произвольным состоянием из Бп, тогда последний предикат перепишется в виде

Ак1 = [0].

Очевидно, что последнее равенство имеет место тогда и только тогда, когда Ак = [0].

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

Финальное состояние ЛС после подачи на её вход некоторой СП назовём синхросостояни-ем этой ЛС. Если ЛС имеет СП, то такую ЛС назовём синхронизируемой.

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

Теперь введём ещё два новых понятия для ЛС, которые подобно СП имеют аналогии в теории линейных автоматов.

Назовём входную последовательность и (0), й(1),..., й(к — \) диагностической последовательностью (ДП) для ЛС, заданной уравнениями (1) и (2), тогда и только тогда, когда

А (САк~%(0) + САк-гВй{0) +... + Du(k -1) =

к=0 ^

: САк~%

->5|(0) = 52(0).

i-i

Здесь знак л означает конъюнкцию t равенств, стоящих после этого знака, когда к пробе-

к=0

гает значения от 0 до t—\.

По существу, данное определение означает, что ДП позволяет однозначно определить начальное состояние ЛС по наблюдаемой реакции ЛС на эту последовательность.

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

Что касается понятий синхронизируемой ЛС и ЛС БПИ, то их прямых аналогов ранее в теории линейных систем не вводилось.

Назовём, следуя [7], задачу определения начального состояния ЛС с использованием ДП диагностической задачей. В теории непрерывных ЛС [8] этой задаче соответствует так называемая задача наблюдения. Последняя заключается в оценке состояния Л С в момент времени t0 по даным о входных и (?) и выходных y(t) величинах, измеренных при t > t0.

Отметим, что в общем случае оценку s(t) состояния ~s(t) в момент времени t понимают как

их близость. Однако близость s(t) и s (t) можно трактовать в двух смыслах: либо как стремление ошибки к нулю, т.е. s(t) - J(t) —» 0, когда t -» 0, либо как точное совпадение векторов J(t0) и s(t0) в момент времени /0. Мы понимаем близость в последнем смысле. Используя введённые понятия, перейдём теперь к постановке рассматриваемых задач.

3. Формулировка задач

В начале сформулируем следующую задачу. Пусть синхронизируемая JIC задана своими характеристическими матрицами и задано некоторое синхросостояние J(t) этой ЛС. Требуется найти такую СП длины к, которая переводит J1C в заданное синхросостояние s(t). Используя формулу (3) и принимая во внимание теорему 1 предыдущего раздела, можно записать следующее матричное уравнение:

Лк-хВй{ 0) + Ак~2Ви

Выражение (6), переписанное в координатной форме, будем интерпретировать как СЛАУ относительно неизвестных ¿¿ДО),...,и,(0),...,щ(к-1),...,и,(к-1), представляющих собой координаты входных векторов ¿7(0),¿7(1),...,¿7(£-l). Очевидно, что эти векторы и будут представлять собой решения сформулированной задачи.

Поскольку координаты конечного состояния I после подачи СП на вход ЛС определяются путём измерений, то за счет погрешности использованного измерительного прибора в действительности координаты будут получены с некоторой погрешностью и поэтому представляются в форме интервалов. В силу того, что вектор s является интервальным, СЛАУ (6) есть система с интервальными правыми частями.

Решением этой системы будем считать такой набор величин, при подстановке которого в левую часть системы (6) получаются значения, принадлежащие соответствующим интервальным координатам данного вектора I. Заметим, что при таком определении решение системы (6) может оказаться не единственным.

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

Перейдём к формулировке следующей рассматриваемой задачи. Пусть ЛС БПИ задана своими характеристическими матрицами, и начальное состояние этой системы I(0).

Пусть на входы ЛС подаётся неизвестная последовательность ¿7(0), ¿7(1),..., й(к-\) длины к, и реакция ЛС на этой последовательности наблюдается и измеряется. На основе измеряемой реакции, которая представляется в виде выходной последовательности ^(0),У(1),...,5Ч&-1) интервальных векторов, и известного начального состояния s(0) требуется найти неизвестную входную последовательность, генерирующую наблюдаемую реакцию.

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

Dü(0) = y(0)-Cs(0),

СВ17(0) + Z)¿7(1) = p(l) - CAs(0),

......................................................................................................

CAk~2Bi7(0) +... + CBñ{k - 2) + Dü(k -1) - y(k -1) - CAk~ls(0).

Так как выходы ЛС у

Д.В. Сперанский, ЛВ. Куприянова. Некоторые задачи теории дискретных линейных систем

записать в координатной форме, то решение такой системы определяется также как и решение системы (6). Решением системы (7) является входная последовательность м (0), и(1),... ,й(к-1), такая, что координаты вектора реакции данной ЛС на упомянутую последовательность принадлежат соответствующим координатным интервалам векторов у(0),у(\),...,у(к-\).

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

Обратимся, наконец, к диагностической задаче для ЛС. Отметим, что поиск неизвестного начального состояния я (0) ЛС предполагает знание множества допустимых начальных состояний (состояние ?(0) — элемент этого множества). Мы предположим далее, что упомянутое множество совпадает с множеством всех состояний ЛС. Вообще говоря, диагностическая задача не всегда разрешима. В то же самое время, если эта проблема разрешима, то её решение является решением матричной системы

Эта система получена на основе формулы полной реакции ЛС с учётом того, что при подаче соответствующей ДП м(0), м(1),..., й(к-\) наблюдается и измеряется реакция ЛС ^(0),>41),...,у(к-\). Так как реакция ЛС получена с помощью измерительной аппаратуры, то векторы роямуьа являются интервальными векторами. Но тогда и правые части системы (8) также являются интервальными. Представив матричную систему (8) в координатной форме, решение такой системы определим так же, как и решения систем (6) и (7). При этом решению системы (8) соответствуют вектора-состояния ^(0), стартуя из которых ЛС выдаёт вектора-реак-ции, координаты которых принадлежат координатным интервалам векторов у{0),у(\),.,.,у(к-\).

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

Перейдём теперь к описанию методов решения соответствующих систем.

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

Системы (6)-(8) кратко можно записать в виде

где С = — вещественная тхи-матрица, f — (!",) — интервальный т-вектор, х — искомый интервальный вектор, в зависимости от задачи, составленный либо из оценок координат входных векторов ¿7(0),м(1),...,й(к-1) (задача синхронизации и задача отыскания неизвестной входной последовательности), либо из оценок координат вектора-состояния (диагностическая задача).

Как известно, в случае интервальных систем линейных алгебраических уравнений в понятие решения можно вкладывать различный смысл [6, с.22]. Для систем с интервальной матрицей Сх = { актуальными и наиболее изученными являются следующйе три множества решений.

Су(0) = у(0)-£>ы(0),

СА1( 0) = у (1) - СВй( 0) - Ш(1),

САк~11 (0) = у (к -1) - САк~2 5м (0) -... - СВй(к - 2) - Ой (к -1) •

Хзэ := {хе Я" \ (3(7 ей) (3/ е ) бх = /} - объединенное множество решений.

:={хе Я" | (\/(7е С ) (3/е f) бх = /} - допустимое множество решений, ХЗУ := {хе Я" | (V/е f) (3Се G)Gx = /} -управляемое множество решений.

По смыслу нашей прикладной задачи нас интересует второе — допустимое множество решений, которое в случае вещественной матрицы С -С, очевидно, совпадает с первым — объединённым множеством решений, а третье множество в данном случае пусто. Обозначим интересующее нас множество X и опишем его явно.

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

Для системы уравнений (9) найти внутреннюю интервальную оценку его множества решений Х= {хе Я" |(3/е f) Сх = /}, т.е. интервальный вектор, такой, что хсХ.

Понятно, что такую задачу можно решать с использованием известных методов нахождения внутренних оценок как допустимого, так и объединённого множеств решений интервальных систем линейных алгебраических уравнений (ИСЛАУ). Но нам представляется наиболее привлекательным так называемый алгебраический подход, позволяющий сводить исходную задачу к задаче нахождения формального решения уравнения в интервальном пространстве. Этот подход начал развиваться одновременно Шарым и Куприяновой, и наиболее детально был разработан в работе Шарого [6]. В частности, из теоремы о внутренней оценке объединённого множества решений [9], а также из более общих теорем Шарого [6, с. 193-195] следует, что максимальный по включению интервальный вектор х, превращающий систему (9) в тождество, является максимальной внутренней оценкой множества X, определённого (10). Затем уже новая задача нахождения такого интервального вектора сводится, как показано в [6], к задаче нахождения решения обычной вещественной системы линейных алгебраических уравнений.

Дадим некоторые необходимые обозначения и определения.

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

Теорема 2. Если интервальный вектор х является максимальным по включению формальным решением системы бх = £ то х является максимальной по включению внутренней оценкой множества

ХИлеЯ"! (3/е О <& = /}•

Ш:={х = [х,х] | х,хе Ы, х<х} - множество, элементы которого будем называть интервалами. Множество интервальных векторов обозначим Ш".

ИГ:={х = (х,,х2,...,х„)т | € 1К,г = 1,...,и}

Пусть х,уе Ш,х = [х,х],у = [у,у], тогда для * е {+, •, /}

х*у:={х*>' | хех,уе у}.

X :={хеД"|(3/еОСх = /}.

Д.В. Сперанский, Лб. Куприянова. Некоторые задачи теории дискретных линейных систем

Доказательство. Хотя это утверждение есть частный случай более общих теорем [6, 9], его доказательство элементарно и легко получается без привлечения этих теорем. Пусть х — формальное решение Ох = £ тогда

V* Г,=(вх),=и ¿£у*,=[тт(^)„тах(Сх),].

^ ТТ хех

хех ]=\

Поскольку каждый интервал fi составлен из всевозможных произведений г'-й строки матрицы б на векторы х из х, то для любого хех найдётся вещественное число £ из интервала , такое, что (Сх), и, следовательно,

Мы получили (\/хех) хеХ => хеХ. Кроме того, для х'гэх, в силу монотонности по включению интервальных арифметических операций, Сх' э Ох, при этом равенства быть не может, иначе х' бьшо бы формальным решением, поэтому Ох' з> Сх = Г а это и означает, что

(Зхех'Х \Zfef) Сх*/.

Следовательно, х'ссХ, а интервальный вектор х — максимален по включению.  Таким образом, задача внутреннего оценивания искомого множества решений сводится к задаче отыскания формального решения уравнения (9).

Заметим, что умножение системы (9) слева на обратную матрицу С1 не даёт формального решения, так как в силу невыполнения дистрибутивного закона в интервальной арифметике, вообще говоря, не является эквивалентным преобразованием. В результате произведение С^'Г даёт внешнюю оценку искомого множества, а не внутреннюю.

Далее, чтобы перенести процесс отыскания формального решения (9) в линейное пространство, рассмотрим погружение интервального пространства Ж" в линейное Я2".

Определение 4.1 [6]. Для интервального отображения (р: Ш" —Ш" и некоторого биективного отображения I: Ш" —где и — линейное пространство, будем называть отобра-

1°<р°Г1 -.и —>и

линейного пространства в себя индуцированным отображением для (р.

Определение 4.2 [6]. Пусть в интервальном пространстве Ш" задано уравнение

<р

где (р : Ш" —> Ши — некоторое отображение, и фиксированное биективное отображение 1: 1К" —> и. Будем называть индуцированным уравнением для (11) такое уравнение

Ф

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

Ф = I о (р о I

Итак, вместо исходного уравнения в интервальном пространстве решается уравнение в линейном пространстве. При этом искомое решение х в Ж" однозначно восстанавливается по решению у уравнения (12) соотношением х - /-1(у).

Определение 4.3 [6]. Отображение ст : Ш" —> И2", которое действует по правилу

»

(X, 5^2' ' ) ' ^ ( — 1 5 —2 ' * *' ' — п ' ' ' ''" ' ^п

будем называть стандартным погружением интервального пространства 1Л" в К2".

Шарый [6] показал, что для оператора умножения на вещественную матрицу

<p(x) = Q\

для некоторой Q е R"x", Q = (q¡j), индуцированное отображение при стандартном погружении а

Ф = О" °(р °<7~'

является линейным преобразованием пространства R2", а матрица этого индуцированного линейного преобразования <у°(р°о~] является блочной 2их2я-матрицей вида

ОТ <2\

где «хи-подматрицы = {ц+ч) и 0~ = ) — это положительные и отрицательные части т.е. матрицы, образованные положительными и отрицательными частями Q соответственно.

Матрицу, определённую (13), Шарый назвал сопутствующей матрицей для О,. Этот факт предоставляет нам возможность сведения исходного уравнения Gx-f к индуцированному уравнению в линейном пространстве:

ву = а

где О - сопутствующая матрица для б, а решение хеЖ" исходного уравнения (9) находится по решению у е R2" уравнения (14) следующим образом:

х=<х-1(у),

а именно х = (хь х2, ..., х„), где хг = [-уьу1+п\ г=1

Интересным и весьма полезным фактом является также и то, что частичный порядок "<" на R2" является порядком, индуцированным стандартным погружением сг для порядка по включению "с" на 1КИ, т.е.

(хсу, х,уеШ") <=> (сг(х) < б (у) в R2").

Отношения порядка "с" и "<" понимаются в покомпонентном смысле.

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

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

Уо<У1< ... <уп<у основной итерационной последовательности.

ДВ. Сперанский, Aß. Куприянова. Некоторые задачи теории дискретных линейных систем

Численный пример. Для системы с вещественной ЗхЗ-матрицей и интервальной правой частью

f 12.6500 2.8400

V

3.2000 9.0600 Л 1.2300 -8.9400 -10.2200 -3.5600 8.9400

х =

получим следующее индуцированное уравнение в R6:

'[-441.62,-417.04]Л [-93.85,-87.90] [196.31,218.77]

'12.6500 3.2000 9.0600 0 0 о N ' 441.62 >

2.8400 1.2300 0 0 0 8.9400 93.85

0 0 8.9400 10.2200 3.5600 0 -196.31

0 0 0 12.6500 3.2000 9.0600 У - -417.04

0 0 8.9400 2.8400 1.2300 0 -87.90

10.2200 \ 3.5600 0 0 0 8 9400 218.77 ^ /

Его приближённое решение следующее:

V =

-6.5369 4 117.7882 16.2679 7.4181 -117.2921 -14.9610

А решение исходного уравнения выглядит так:

х = ст-1(у) =

[6.5369,7.4181] 4 [-117.7882,-117.2921] [-16.2679,-14.9610]

Библиографический список

1. Заде Л., Дезоер Ч. Теория линейных систем. М., 1970.

2. КалманР., ФалбП., Арбиб М. Очерки по математической теории систем. М., 1971.

3. Фомин В Н. Методы управления линейными дискретными объектами. Л., 1985.

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

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

6. Шарый СП. Интервальные алгебраические зада-

чи и их численное решение: Дис. ... д-ра физ.-мат. наук. Новосибирск, 2000.

7. Гилл А. Линейные последовательностные машины. М., 1974.

8. Первозванский A.A. Курс теории автоматического управления. М., 1986.

9. Kupriyanova L. Inner estimation of the united solution set of interval linear algebraic system // Reliable Computing. 1995. V. 1, № 1. P. ß—31.

10. Collats L. Funktionalanalysis und Numerische Mathematik. Berlin; Göttingen; Heidelberg, 1964.