XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 32
Текст из файла (страница 32)
хе+и " ~ хи. При1=и имеем (3.28) хи = с"и7и1 где выражения а,', и 7в не содержат неизвестных. Таким образом, исходная система (3.16) преобразована к „треугольному" виду: правзл часть уравнения (3.28) не содержит неизвестных, уравнение (3.27) при 1 = и — 1 в правой части содержит только одно неизвестное х„г и каждое следующее уравнение при просмотре „снизу вверх" на одно неизвестное больше, чем предыдущее. Первое уравнение системы — уравнение (3.23) — в правой части содержит все неизвестные от хг до х„. На этом завершается первый этап алгоритма, который называют ирлммм ходом метода Гаусса.
Второй этап алгоритма, называемый обратным ходом метода Гаусса, состоит в последовательном нахождении значения всех неизвестных хм ..., х„м начиная с х„ь Подставив в выражение для х„1 вместо х„правую часть (3.28), найдем х„г. Затем определим х„г, подставив полученные значения х„и х„г в правую часть выражения (3.27) при 1 = и — 2, и так далее до тех пор, пока не найдем хь Замечание 3.2.
Положив В = Е в уравнении (3.17), получим Х = А'Е = А'. Таким образом, чтобы вычислить итерацию матрицы А, достаточно решить матричное уравнение (3.21) для всех у = 1, и при,8г, равном у-му столбцу единичной матрицы Е. Пример 3.6. Проиллюстрируем приведенную схему решения системы из двух линейных уравнений. Имеем < х1 = амх1+ а1гхг+Ьм хг = аг1х1+ аггхг + Ьг. 202 3. ПОЛУКОЛЪЦА И БУЛЕБЫ АЛГЕБРЫ Из первого уравнения выразим х1: х1 = а;,(а~гхг+ Ь1).
Подставляя это выражение во второе уравнение, получаем хг = (аг1а11а1г+ агг)'(аиаы Ь1+ Ьг). Подставляя этот результат в написанное вьппе выражение для х1, находим окончательное решение: х1 = аы(а1г(аг1а11а1г + агг)" (аг1аыЬ1 + Ьг) + Ьг). Особенно просто решение выглядит в случае тривиальной итерации, т.е. тогда, когда в полукольце итерация любого элемента равна единице полукольца (как в полукольцах В, Ж+, 8А, 8( г)). В этом случае для системы из двух уравнений решение равно х1 = а1г(аг1Ь1 + Ьг) + Ь1, хг = аг1Ь1 + Ьг Пример З.Т. Рассмотрим в полукольце 8(е1) (см. пример 3.3.г) систему линейных уравнений х1 = О,бх1+0)4хг+ 0,2, хг =0,3х1+0,9хг+0,6. Решим эту систему уравнений, следуя общему алгоритму.
Иэ первого уравнения получаем х1 = 0,5'(0,4хг+ 0,2) = 1(0,4хг+0,2) = 0,4хг+0,2. Далее, хг = 0 3(0 4хг+ 0 2) + 0 9хг + 0 6 = 0 Зхг + 0 2+ 0 9хг + 0 6. Отсюда хг = (0,3+0,9)хг+ 0,6 = 0,9хг+ 0,6 = 0,9*0,6 = 0,6. 3.3. Решенно систем двнейвык уравнений 203 Подбтавляя хз = 0,6 в полученное выражение для х1, находим, что х1=0,4 0,6+0,2=0,4+0,2 =0,4.
Не всякое бесконечное идемпотентное полукольцо является замкнутым. Однако можно заметить, что при решении линейных уравнений и систем требовалось вычисление точной верхней грани последовательностей специального вида, а именно нахождение итерации элементов. Поэтому помимо замкнутых полуколец интерес для приложений представляют так называемые полукольца с итперациезь Под полукольцом с итерацией в данном контексте мы будем понимать идемпотентное полукольцо, которое является подполукольцом' некоторого замкнутого полукольца и вместе с каждым элементом содержит его итерацию.
Важнеюпим примером такого полукольца является цолуко.еьцо регулярных лэыкое (см. 7). Рассматривая в полукольце с итерацией произвольное линейное уравнение, т.е. уравнение вида (3.12) или (3.13), получаем следующие результаты. Во-первых, это уравнение имеет наименьшее решение, так как полукольцо с итерацией содержится в некотором замкнутом полукольце в качестве подполу- кольца.
Во-вторых, это наименьшее решение снова окажется в этом же полукольце, поскольку носитель полукольца с итерацией замкнут относительно итерации. Таким образом, носитель полукольца 8 с итерацией замкнут относительно операции нахождения наименьшей неподвижной точки любого линейного отображения ах+ Ь (или ха+ Ь), где а и Ь вЂ” элементы 8. Не составляет труда распространить этот результат на произвольные матричные уравнения. Можно доказать следующее утверждение. 'Поауковьцо Я= (Я, +с з О, 1) называют водно,аркоеьцомповукольца К = (й, +,, О, 1), если множество я есть подмножество множества тс, замкнутое относительно операцвй свеженин и умножение полукольца зС, а также содержащее нуль и едиющу полукольца Я..
204 3. ПОЛУКОЛЪЦА Н БУЛЕВЫ АЛГЕБРЫ Теорема 3.9. Если А — матрица, все элементы которой принадлежат некоторому полукольцу с итерацией, то все элементы ее итперации А' также принадлежат этому полукольцу с итерацией. 3.4. Булены алгебры Теория булевых алгебр является классическим разделом дискретной математики. Булевы алгебры возникли в трудах английского математика Дж. Буля в 50-х годах Х1Х века как аппарат логики. При этом элементы булевой алгебры трактовались как высказывания, а операциями являлись диэъюнкция, конъюнкция и отрицание. Существуют различные подходы к определению булевой алгебры. Мы определим булеву алгебру как частный случай идемиотпентного полукольца. Определение 3.3.
Полукольцо 8 = (Я, +,, О, 1) называют сиятметричнььк (или взаимным), если оно идемпотентно и в нем выполнены следующие тождества: 1) а ° а = а ( идемпотпентность операции умножения полукольца); 2) а Ь = Ь а (коммутиативность операции умножения полукольца); 3) а+(Ь.с) =(а+Ь) (а+с) (дистрибутпивностпь операции сложения полукольца относительно умножения); 4) 1+а = 1 (аннулирутотцее свойство единицы полукольца относительно сложения). Можно дать определение, равносильное определению 3.3.
Идемпотентное полукольцо 8 = (Я, +,, О, 1) называется симметричным (или взаимным), если алгебра 8' = (Я,, +, 1, О) также является идемпотентным полукольцом. При этом будем говорить, что идемпотентное полукольцо 8' есть полукольцо, двойстпвенное к идемпотентному полукольцу 8. 205 З.4. Булевм аегебом Из определения следует, что в двойственном идемпотентном полукольце операция сложения — это операция умножения в исходном полукольце и наоборот; нуль двойственного полукольца — это единица исходного полукольца и наоборот. Легко видеть,что полукольцо 8", двойственное к двойственному полукольцу 8', есть исходное полукольцо о'.
Запишем полностью все аксиомы (основные тождества) симметричного полукольца, объединяя двойственные аксиомы в пары (табл. 3.3). Таблица 8.8 В табл. 3.1 можно увидеть, что в симметричном полукольце операции сложения и умножения, равно как и элементы О и 1, полностью евэаимозаменяемые", или взаимно двойственные. Таким образом, справедлив принцип двобсгпвенносгпи для симметричных полуколец: любое тождество в симметричном полукольце остается верным, если в нем операцию сложения заменить операцией умножения и наоборот, а единицу заменить нулем и наоборот. Пример 3.8. а. Полукольцо В (см.
пример 3.2) симметричное. б. Полукольцо Я.+ (см. пример 3.1) не является симметричным в силу неидемпотентности умножения полукольца, хотя в 206 3. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫ нем единица полукольца (число О) имеет аннулирующее свойство, поскольку шш(0, я) = О. в. Полукольцо 8А (см. пример З.З.б) симметрично в силу известных свойств операций пересечения и объединения множеств.
г. Полукольцо ЯА (см. пример З.З.в) не является симметричным. д. Полукольцо 8(, й) (см. пример З.З.г) симметрично. Пример 3.9. Рассмотрим алгебру Р„= (Дел(п), НОК, НОД, 1, и), где Дел(п) — множество всех делителей натурального числа и; НОК вЂ” операция вычисления наименьшего общего кратного; НОД вЂ” операция вычисления наибольшего общего делителя двух чисел. Эта алгебра является симметричным полукольцом. Действительно, для любых двух натуральных чисел тв и р верно представление 2е1 Зей рвй и р 2)ч ЗДй рлй й й ~ где рй — наибольший простой множитель в разложении т и р.
Тогда НОК(ш р) = 2~~(~"~')З~~("'®...р ~Р) НО я(~~~ р1 2~~~(е1 Д1)Зяця(е1 йа) р~~~(~» Л~ ) Д гп1р) = "рй Таким образом, свойства операций НОК и НОД определяются свойствами операций шах и п1ш. В силу этого рассматриваемая алгебра и является симметричным полукольцом (см. пример З.З.г). Рассмотрим некоторые свойства симметричного полукольца, вытекающие из его аксиом. 207 3.4.
Буяеэы аагебры Свойство 3.1. Для любых элементов симметричного полукольца выполняются равенства х(х+у) = х, х+ ху = х. м Имеем х(х+ у) = хх+ ху = х+ ху = х(1+ у) = х 1 = х. в Равенства, приведенные в формулировке свойства 3.1, нз зывают тпоэкдестпеами погяоиаения. Свойство 3.2. В симметричном полукольце неравенство х < у имеет место тогда и только тогда, когда ху = х. м Вспомним, что по определению есшесшеенного порядка произвольного иденпотпенпьноео полукольца х < у еь х+ у = у. Пусть х < у.
Тогда ху = х(х+ у) = х (по свойству 3.1). Пусть теперь ху = х. Тогда х+ у = ху+ у = у. Следовательно, х< у. ° Свойство 3.2 выражает связь умножения с естестиеенным порядком идемпотпентпноео полукольца: меньший сомножитель поглощает болыпий, т.е. порядок в двойственном полукольце 8' является порядком, деойстеенным к порядку в полукольце 8. Но, как известно, при переходе к двойственному порядку наибольший (максимальный) эяеменпь становится наименьшим (минимальным) эяеменюпом, а точная еерхняя ерань — точной нижней гранью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
