XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 31
Текст из файла (страница 31)
в)1 в)1 Таким образом, идемпотентное полукольцо Ял замкнутое. Итерация бинарного отношения р есть Р" = ( ) Р" = 1ол О Ц Р", в)1 в)0 где р", и > 1, — и-кратная композиция р с самим собой: р" = ~ ... р. Как видно, в общем случае р' уЕ Ы,1, т.Е. в в рвз этом полукольце итерация элемента, вообще говоря, не равна единице полуколы1а У Вьппе было показано, что всякое замкнутое полукольцо является индуктивным упорядоченным множеством. Следовательно, согласно теореме 1.7, любое непрерывное отпображение у замкнутого полукольца в себя имеет наименьшую неподвижную точку, т.е.
в любом замкнутом полукольце всякое уравне. ние вида х = у (х), где у" — непрерывное отображение носителя этого полукольца в себя, 'имеет наименьшее решение. Особенно важными для приложений являются линейные уравнения в замкнутом полукольце, имеющие вид (3.12) или х = ха+ Ь. (3.13) В силу непрерывности операций сложения полукольца (см. тождество (3.10)) и умножения полукольца (см. определение 3.2) правые части уравнений (3.12) и (3.13) есть непрерывные оп10- браженнл. Поэтому, согласно теореме 1.7 о неподвижной шочке, существуют наименьшие решения этих уравнений.
194 3. ПОЛУКОЛЪЦА И БУЛЕВЫ АЛГЕБРЫ Теорема З.Т. Наименьшими решениями уравнений (3.12) и (3.13) в замкнутых полукольцах являются соответственно (3.14) х=Ьа', (3.15) где а' — итерация элемента а. ~ Используя формулу (1.8) для вычисления наименьшей неподвижной точки и записывая вор в случае замкнутого полукольца как бесконечную сумму, для уравнения (3.14) получаем' х = Е1" (0) ьь)0 где 0 — нуль полукольца, а У(х) = ах+ Ь. Учитывая, что у0(0) =О, ~1(0) — Ь у ~(0) = аЬ+ Ь = (а+ 1) Ь, у"(0) = (а" 1+...+а +а+ 1)Ь, получаем ~~1 у"(0) = ~) (1+а+...+а" 1)Ь. ьь=1 Используя непрерывность умножения, вынесем Ь (вправо) за знак бесконечной суммы и получим 1 ьь ь ь...ь " ')ь= (1;ььь -ь...ь " '))ь.
ьь=1 ььь-1 З.З. Решение систем еииейиеш урааиеиий 195 Сумма 1+ а+... + ап ~ есть частичная сумма последователь- ности (а")п>с. Используя равенство (3.6), можем написать ~~) (1+а+...+оп )= ~) а"=а'. пме ппи Окончательно получаем ~~),)~(0) = а Ь. п=1 Анологично доказывается равенство (3.15). 1ь Формулы (3.14) и (3.15) дают именно наименьшие решения уравнений (3.12) и (3.13), а не все возможные их решения. Приведем в этой связи простой пример. В полукольце В (см. пример 3.2) можно определить только два уравнения: х = х+ 1 и х = х+ О.
Второе уравнение переписывается совсем просто: х = х; его решением является любой элемент полукольца — как О, так и 1. Но по формуле (3.14) получим х= 1'О= О, что, как и доказано вьппе, есть наименьшее решение уравнения. Заметим еще, что в полукольце, в котором итерация любого элемента равна единице полукольца, формулы (3.14) и (3.15) дают один и тот же результат: х = Ь, т.е. в данном случае наименьшее решение совпадает со свободным членом уравнения. 3.3. Решение систем линейных уравнений Полученные вьппе результаты (см. 3.2) можно распрострз нить на системы линейных уравнений вида х1 = анх1+...
+ аьпхп+ Ьм (3.16) хп = оп1х1+... + а„пхп+ Ьп, где все элементы а;, 1<1<п, 1<у <и, и Ь,, 1<1<п, суть элементы некоторого замккуяоео полукольца, и речь идет о решении системы (3.16) в этом полукольце. 196 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ Для этого введем в рассмотрение множество М,в„„(8) прямоугольных матриц типа ш х п с элементами ю произвольного идемпотентного полукольца 8 = (8,+,,0,1). Множество всех квадратных матриц порядка и с элементами ю полукольца 8 обозначим М„(8). Через МаФг(8) обозначим множество всех матриц любого типа с элементами из 8. Операции сложения и умножения матриц определяют точно так же, как и в числовом случае (1П], — с учетом того, что сложение и умножение элементов матриц понимаются в смысле данного идемпотентного полукольца 8, а именно: 1) суммой матриц А = (а0) и В = (Ь,у) типа гп х и называют матрицу С = (с; ) того же типа с элементами с;~ — — аИ+ЬИ, 1 = 1, т, у = 1, и, и используют обозначение С = А+ В; 2) произведением АВ матриц А = (а0) типа т х и и В = (ЬИ) типа п х р называют матрицу С = (с;~) типа гп х р с элементами Нулевая (0) и единичная (Е) матрицы любого порядка определяются с помощью единицы и нуля полукольца.
На множестве М„(8) всех квадратных матриц фиксированного порядка п можно определить алгебру М„(8) =(М„(8),+,,О,В). Теорема 3.8. Алгебра М„(8) есть идемпотентное полукольцо. Если полукольцо 8 замкнуто, то полукольцо М„(8) тоже замкнуто. ~ Операции суммы и произведения матриц определены таким образом, что все свойства операций сложения и умножения в полукольце сохраняются и для соответствующих операций над матрицами. Поэтому для суммы и произведения матриц из М„(8) выполнены аксиомы полукольца, и, кроме того, опера ция сложения матриц идемпотентна. Следователю*'но, М„(8)— идемпотентное полукольцо.
З.З. Решение систем вввевшев урвввеввв 197 Выясним смысл овтношенвл порядка в этом идемпотевтном полукольце. В силу определения есвтестлвенвого порядка идеипожентвмого полукольце неравенство А < В для матриц А и В означает, что А+ В = В, или для всех е, З справедливо ся + Ь;З вЂ” - Ь;~. Следоватеяьно, А ~ (В тогда и только тогда, когда для всех т, З справедливо ам < Ь; . Пусть 8 — замкнутое полукольцо. Докажем замкнутость идемпотентного полукольца М„(8) и существование точной верхней грани у любой последовательности матриц в М„(8). Пусть (Аш)шеи — произвольная последовательность квадратных матриц Аш = (а1~Ч) порядка и. Рассмотрим матрицу В= ( )', а~~).
КаждыйзлементЬ;. = ~', а~З этойматрицыесть шеи шеи точная верхняя грань последовательности элементов а~~. Эти точные верхние грани существуют, поскольку ашу — элементы замкнутого полукольца 8. Так как сложение матриц и отношение порядка в полукольце матриц определяются поэлементно, то матрица В и будет точной верхней гранью последовательности матриц Аш. Докажем теперь непрерывность умножения в М„(8), т.е.
что для любой последовательности (А„,~„,ен матриц и произвольной матрицы В имеет место В СА,„=~~ (ВАш). Матрица С = (с; ) = ~',А,„есть точная верхняя грань последо- вательности (А )„,ен. Тогда имеем в В ~ Аш = ВС = ~Я Ьись )~ Ьм1 Элемент сву есть точная верхняя грань последовательности (амшен элементов матриц Аш, т.е. тек 198 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ Используя непрерывность умножения в исходном полукольце 8, получаем и и и ~~1 ,'61йсй1 = (~) '6;й ~~1 ай1) = (~~1 "5 Ьййай~). й=1 й=1 ивЕН й=1ивЕН Следовательно, и В,,'в, Ат = ЯЬвй,~~, ай ). ивЕН й=1 ивЕН Используя непрерывность сюжения, получаем и и (ЯЬвй ~ ай1) = вВ (~~ Ь;йайу) = ,''В (ВАив).
й=1 ивЕН ивЕН й=1 ивЕН Аналогично доказывается, что ( Ави)В = 2 (АивВ). ~ь Полукольцо М„(8) будем называть пвьяриольцом мавпрац над полукольцом 8. Доказанная теорема позволяет нам применять к замкнутым полукольцам матриц над некоторым замкнутым полукольцом 8 теорему 3.7 и решать произвольные уравнения вида (3.17) Х= АХ+В (3.18) Х = ХА+В относительно неизвестной матрицы Х. Наименывие решения этих уравнений есть (3.19) Х=А*В (3.20) Х=ВА' соответственно, где А" — аиверапая матрицы А в М„(8).
Итерация А' матрицы А играет в теории линейных уравнений в З.З. Решение систем лииейиын уравнений 199 замкнутых полукольцах такую же роль, как обратная матрица в классической линейной алгебре. Основную роль при решении задач теории ориентированных графов и теории формальных языков играют праволппебпые уравпепил вида (3.17), поэтому мы будем, как правило, рассматривать только их. Лееолинебное уровпеипе (3.18) может быть проанализировано аналогично. Мы доказали существование решений матричных уравнений в матричном полукольце над замкнутым полукольцом. Теперь нам необходимо разработать технику поиска их решений и применить ее к решению систем вида (3.16).
Полагая, что (; — З-й столбец матрицы Х, а $ — З-й столбец матрицы В, уравнение (3.17) можно переписать как систему уравнений относительно неизвестных столбцов матрицы Х: б=Аб+РЗ, 0<у <и. (3.21) Каждая система вида (3.21) есть матричная форма записи указанной вьппе системы (3.16). Поэтому наименьшее решение этой системы, как следует из (3.19), есть (3.22) Для поиска решения системы вида (3.21) можно воспользоваться метподом последоваепельного исключения пеизвесепных, аналогичным классическому методу Гаусса. Поскольку система уравнений вида (3.16) имеет решение, мы можем подставить его в систему и работать с уравнениями как с тождествами. Рассмотрим процедуру решения системы уравнений (3.16).
Запишем первое уравнение системы так: х1 = аых1+ (аихэ +... + ашх„+ Ь1 ). Иэ первого уравнения системы выразим х1 через остальные неизвестные, воспользовавшись формулой (3.14): х1 = а1,(ашхэ+... + аых„+ Ь|). (3.23) 2ОО 3. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫ В формуле (3.23) выражение в скобках не содержит неювест- ного хд. Подставляя (3.23) вместо хд в остальные уравнения, получаем систему из дд — 1 уравнений, которая уже не содер- жит хд. хг = агдад,(адгхг+... +адвх„+61)+ + а22х2+ ° ° ° + агпх««+ 62« хз — аз1адд(адгхг +...
+ адвха + Ьд) + + азгхг + .. + азпхп + Ьз (3.24) х„= а„додд(адгхг +... + ад„х„+ Ьд) + + а««гхг +... + а««««хп + Ь««. Приводя подобные члены в каждом уравнении системы, полу- чаем: хг = (ашаддадг+ агг)хг+... ... + (агдаддаы+ аз„)х„+ агдад,Ь1+ 62, хз = (аздаддадг+азг)хг+... ... + (аздаддаы + аз««)х„+ аз1аддЬ1 + Ьз, (3.25) х„= (а„дад,адг+ а««г)хг+...
... +(авдаддадв+а„,„)х„+а„да1161+6„. Первое уравнение этой системы перепишем так: Х2 = («121«111«112 + «122)Х2 + 72 где 72 = агдад1 (адзхз +... + ад««х««+ Ь1) + а2зхз +... + аг««х„+ Ь2. (3.2б) Х2 ««272» гДе «дг = агдаддаш+агг не соДеРжит неювестных. ИспользУЯ полученное выражение, исключаем хг из остальных уравнений. Заметим, что 72 не содержит хд и хг. Воспользовавшись соот- ношением (3.14), будем иметь З.З. Ретеиве систем ливеввых ураввевий 201 Действуя подобным образом, на е-м шаге (1 < 1 < и) получаем (3.27) где выражение а,*. не содержит неизвестных, а выражение 7; может содержать только неизвестные, начинал с (1+ 1)-го, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
