FN_Alg19 (Лекции 2009), страница 4

Поэтому sij 6 s0ij , i, j = 1, n,∞Pи S 6 S 0 . Значит, S — точная верхняя грань последовательности {Sm } и сумма рядаAk .k=1Убедимся в непрерывности операции умножения по своим аргументам. Для этого нужно∞PAk и произвольной матрице B проверить равенствапри произвольном рядеÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓAk B =k=1∞Xk=1BAk .k=1Проверка неравенств проводится по одной схеме. Поэтому можно ограничиться одним из них,например первым.(k)Положим, как и выше, Ak = (aij ), а также B = (bij ). Тогда элементами [SB]ij произведенияSB суммы ряда S на матрицу B будут[SB]ij =nXsip bpj =p=1n X∞X(k)aip bpj=p=1 k=1n∞ XX(k)aip bpj=k=1 p=1∞X[Ak B]ij .k=1Здесь мы воспользовались свойством бесконечной коммутативности, а затем свойством бесконечной дистрибутивности (непрерывности умножения).

Таким образом,∞ XB = SB =∞XAk B,k=1т.е. бесконечная дистрибутивность в полукольце Mn (K) доказана. I(19.2)ÔÍ-12x1 = a∗11 (a12 x2 + a13 x3 + . . . + a1n xn + b1 )ÌÃÒÓИтак, если полукольцо K замкнуто, то и полукольцо Mn (K) тоже замкнуто. В этом случаематричное уравнение X = AX + B (также X = XA + B) имеет наименьшее решение. Но такоеуравнение на самом деле распадается на совокупность матричных уравнений Xj = AXj +Bj , гдеBj — j-й столбец матрицы B.

При этом наименьшие решения Xj этих систем в совокупностисоставляют наименьшее решение уравнения X = AX + B. Поскольку наменьшее решение Xminуравнения X = AX + B задается равенством Xmin = A∗ B, то исходя из правил вычисленияпроизведения матриц заключаем, что Xj = A∗ Bj .Выберем произвольный столбец b и рассмотрим матричное уравнение x = Ax + b. Положив B = (b, b, . . . , b) (квадратная матрица B получена повторением одного столбца), найдемрешение X = A∗ B, у которого в силу выбора матрицы B все столбцы будут одинаковые. Этистолбцы будут решениями матричного уравнения x = Ax + b, они равны xmin = A∗ b.Вычисление итерации элемента может быть трудной задачей даже в полукольце скаляров“”K, а уж тем более в полукольце матриц Mn (K).

Поэтому непосредственное использованиеформулы xmin = A∗ b для наименьшего решения xmin системы x = Ax + b может натолкнутьсяна трудности.Существует, однако, способ поиска наименьшего решения системы (19.1), по духу близкий кметоду исключения Гаусса. Суть его такова. Из первого уравнения, рассматривая неизвестныеx2 , x3 , . . . , xn как параметры, находим наименьшее решениеÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Ak =∞XÔÍ-12ÌÃÒÓDk=1k=1ÔÍ-12Ak B,∞XÌÃÒÓÌÃÒÓ∞XÔÍ-12ÔÍ-12k=1ÌÃÒÓIСледовательно, в силу монотонности сложения и умноженияe0 + ee0 + ee0.ea21 x1∗ + A22 xb2 6 ea21 x01 + A22 xb2 = xÌÃÒÓe0 = ee0 + exa21 x01 + A22 xb2 .ÔÍ-12тe0Пусть x0 = x01 , x— наименьшее решение этой системы.

Рассмотрим элемент x1∗ =т 0∗e + b1 ) — наименьшее решение первого уравнения относительно x1 при значениях отa11 (ea12 xсальных неизвестных, соответствующих наименьшему решению всей системы (ниже она будетт 0e + b1 , то x1∗ 6 x01 .называться исходной). Поскольку x01 — решение уравнения x1 = a11 x1 + ea12 xИспользуя решение системы x0 , делаем заключение, чтоÌÃÒÓТеорема 19.11. Решение системы x = Ax + b, получаемое методом Гаусса, являетсянаименьшим.ттe ) , b = b1 , ee, eJ Используем блочную запись векторов x, b в виде x = (x1 , xb , где xb —соответствующие векторы без первой компоненты.

Тогда рассматриваемую систему можнозаписать в виде(тe + b1 ,x1 = a11 x1 + ea12 xe=exa21 x1 + A22 x + eb2 .ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓJ Это свойство вытекает из записи наименьшего решения через итерацию матрицы A. Действительно, верны равенства x1 = A∗ b1 и x2 = A∗ b2 . В силу монотонности умножения по своимаргументам и неравенства b1 6 b2 заключаем, чтоÔÍ-12Лемма. Пусть x1 — наименьшее решение системы x = Ax + b1 , а x2 — наименьшее решение системы x = Ax + b2 . Если b1 6 b2 , то x1 6 x2 .ÌÃÒÓÌÃÒÓÌÃÒÓ61и подставляем это решение вместо x1 в остальные уравнения системы. В результате мы получим n − 1 уравнений с n − 1 неизвестным: неизвестное x1 из уравнений будет исключено.Повторяя процедуру исключения, мы, в конце концов, получим уравнение с одним неизвестнымxn .

Решив его, найдем xn . Зная xn , по предыдущему уравнению найдем xn−1 . Повторяя этупроцедуру, получим значения всех неизвестных.В описанном методе просматривается два этапа. На первом этапе исключения мы приходимк системе с треугольной матрицей. Этот этап называют прямым ходом метода исключения. На втором этапе определяются значения неизвестных, начиная с последнего и заканчиваяпервым.

Этот этап обратный ход метода исключения.В отличие от обычных систем линейных уравнений замена первого уравнения системы (19.1)уравнением (19.2) не является эквивалентной в том смысле, что такая замена изменяет множество решений всей системы уравнений. Можно в этой ситуации лишь утверждать, что такаязамена приводит к уменьшению множества решений: каждой решение новой системы будет ирешением исходной системы. Отсюда можно сделать заключение, что наименьшее решениесистемы, полученной исключением переменного x1 , не может быть меньше наименьшего решения исходной системы.

Это же относится к решению, полученному методом исключения: оноявляется решением исходной системы, но, возможно, не наименьшим.Оказывается, что в действительности метод исключения, хотя и приводит к сокращениюмножества решений, дает наименьшее решение системы. Чтобы перейти к обоснованию этогофакта, отметим следующий важный момент. Наименьшее решение системы линейных уравнений, как функция правых частей системы, является монотонным.x1 = A∗ b1 6 A∗ b2 = x2ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12e0 = ee0 + exa21 x1∗ + A22 xb2∗ ,e0означающее, что вектор x1∗ , xтявляется решением системы(тe + b1 ,x1 = a11 x1 + ea12 xe=exa21 x1 + A22 x + eb2∗ .Но тогда наименьшее решение x00 этой системы не превышает x0 . Следовательно, выполняются неравенстваттe0 .e 0 6 x0 = x01 , xx00 6 x1∗ , xОднако, при этом правые части второй системы превышают правые части первой, и мы имеети такое неравенство: x0 6 x00 .

Поэтому в действительностиe0x00 = x1∗ , xтe0= x0 = x01 , xти x01 = x1∗ .тe + b1 ),Подставив во вторую часть исходной системы вместо x1 выражение x1 = a∗11 (ea12 xполучим систему, для которой столбец x0 является решением. Поскольку все решения новойсистемы в то же время являются решениями исходной системы, то x0 будет наименьшим решением новой системы.Тем самым мы доказали, что в результате исключения неизвестного x1 мы получаем систему с тем же наименьшим решением, что и исходная, т.е. в смысле наименьшего решенияисключение неизвестных — эквивалентное преобразование.

IВ рассматриваемом полукольце итерация любого элемента равна единице полукольца:1 + x + x2 + x3 + . . . = 1,ÌÃÒÓтак как xn 6 1 для любой степени n.Из первого уравненияx1 = 0,5∗ (0,4x2 + 0,2) = 0,4x2 + 0,2.ÔÍ-12Пример 19.4. Рассмотрим систему в полукольце U[0,1](x1 = 0,5x1 + 0,4x2 + 0,2;x2 = 0,3x1 + 0,9x2 + 0,6.ÌÃÒÓÌÃÒÓ2e 0 , получим равенствоПоложив eb2∗ = eb +xÔÍ-12ÔÍ-12ÌÃÒÓ62ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓПодставив найденное представление во второе уравнение, получим:x2 = 0,3(0,4x2 + 0,2) + 0,9x2 + 0,6,илиВыполнив операции (сумма — максимум, произведение — минимум), находим:x2 = 0,9x2 + 0,6.Следовательно, x2 = 0,9∗ · 0,6 = 0,6 и x1 = 0,4 · 0,6 + 0,2 = 0,4.

Итак, наименьшее решениерассматриваемой системы: x1 = 0,4, x2 = 0,6.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12x2 = (0,3 · 0,4 + 0,9)x2 + (0,3 · 0,2 + 0,6).ÌÃÒÓJ Первое свойство следует из равенств x+0 = x, x+1 = 1 (второе равенство есть аннулирующеесвойство единицы по отношению к сложению).Первое из тождеств поглощения вытекает из равенствx + xy = x · 1 + xy = x(1 + y) = x · 1 = xIЗамечание. Принцип двойственности для симметричных полуколец можно расширить,если добавить двойственность inf –sup.Булева алгебра — симметричное полукольцо K с дополнительной унарной операцией дополнения x → x, которая со сложением и умножением связана условиямx · x = 0.(19.3)Примером булевой алгебры является полукольцо SA = 2A , {∪, ∩, ∅, A} . В этом полукольце каждому множеству X соответствует дополнение X = A\X, удовлетворяющее условиямX ∪ X = A,X ∩ X = ∅.(19.4)Это полукольцо часто называют алгеброй множеств.ÔÍ-12x + x = 1,ÌÃÒÓx1 + x2 + .

. . + xk = sup {x1 , x2 , . . . , xk }.ÔÍ-12(опять использовано аннулирующее свойство единицы по сложеннию). Второе тождество поглощения является двойственным к первому и следует из принципа двойственности.Третье свойство можно получить из тождеств поглощения. Если x 6 y, то x + y = y.

В силувторого тождества поглощения xy = x(x + y) = x. Наоборот, если xy = x, то в соответствии спервым тождеством поглощения x + y = xy + y = y, что равносильно неравенству x 6 y.Наконец, последние два свойства вытекают из того, что отношение порядка двойственногополукольца является обратным (двойственным) к естественному порядку полукольца. Поэтомусвойство г) двойственно к свойству a + b = 0 ⇒ a = b = 0, а свойство д) является двойственнымпо отношению к равенствуÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Идемпотентное полукольцо (S, +, ·) симметрично, если алг.

система (S, ·, +) тоже идемпотентное полукольцо. Дополнительные аксиомы: а) коммутативность умножения; б) дистрибутивность сложения по отношению к умножению; в) идемпотентность умножения; г) аннулирующее свойство единицы по отношению к сложению. Двойственное полукольцо. Двойственностьв симметричных полукольцах.Свойства:а) 0 6 x 6 1;б) тождества поглощения x + xy = x и x(x + y) = x;в) x 6 y ⇔ xy = x;г) xy = 1 ⇒ x = y = 1;д) x1 x2 . . . xk = inf {x1 , x2 , . . . , xk };ÌÃÒÓÌÃÒÓИдемпотентное полукольцо (S, +, ·) симметрично, если алг. система (S, ·, +) тоже идемпотентное полукольцо.

Дополнительные аксиомы: а) коммутативность умножения; б) дистрибутивность сложения по отношению к умножению; в) идемпотентность умножения; г) аннулирующеесвойство единицы по отношению к сложению. Пример: SA = 2A , {∪, ∩, ∅, A} . Двойственноеполукольцо.