Полукольца и системы линейных уравнений

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

[cbm]\left\{\!\begin{gathered}x_1= a_{11}x_1+a_{12}x_2+\ldots+ a_{1n}x_n+b_1,\hfill\\ x_2= a_{21}x_1+a_{22}x_2+\ldots+ a_{2n}x_n+b_2,\hfill\\[-5pt] \vdots\\[-3pt] x_n= a_{n1}x_1+a_{n2}x_2+\ldots+ a_{nn}x_n+b_n.\hfill \end{gathered}\right.[/cbm]
(3.16)

где все элементы [cbm]a_{ij},~ 1 \leqslant i \leqslant n,~ 1 \leqslant j \leqslant n[/cbm] и [cbm]b_i, 1 \leqslant i \leqslant n[/cbm] , суть элементы некоторого замкнутого полукольца, и речь идет о решении системы (3.16) в этом полукольце.

Для этого введем в рассмотрение множество [cbm]\mathbb{M}_{m\times n}(\mathcal{S})[/cbm] прямоугольных матриц типа [cbm]m\times n[/cbm] с элементами из произвольного идемпотентного полукольца [cbm]\mathcal{S}=(S,+,\cdot,\bold{0},\bold{1})[/cbm] . Множество всех квадратных матриц порядка [cbm]n[/cbm] с элементами из полукольца [cbm]\mathcal{S}[/cbm] обозначим [cbm]\mathbb{M}_n(\mathcal{S})[/cbm] . Через [cbm]\mathsf{Matr}(\mathcal{S})[/cbm] обозначим множество всех матриц любого типа с элементами из [cbm]\mathcal{S}[/cbm] .

Операции сложения и умножения матриц определяют точно так же, как и в числовом случае, — с учетом того, что сложение и умножение элементов матриц понимаются в смысле данного идемпотентного полукольца [cbm]\mathcal{S}[/cbm] , а именно:

1) суммой матриц [cbm]A=(a_{ij})[/cbm] и [cbm]B=(b_{ij})[/cbm] типа [cbm]m\times n[/cbm] называют матрицу [cbm]C=(c_{ij})[/cbm] того же типа с элементами [cbm]c_{ij}=a_{ij}+ b_{ij},[/cbm] [cbm]i=\overline{1,m},~ j=\overline{1,n}[/cbm] , и используют обозначение [cbm]C=A+B[/cbm] ;

2) произведением [cbm]AB[/cbm] матриц [cbm]A=(a_{ij})[/cbm] типа [cbm]m\times n[/cbm] и [cbm]B=(b_{ij})[/cbm] типа [cbm]m\times p[/cbm] называют матрицу [cbm]C=(c_{ij})[/cbm] типа [cbm]m\times p[/cbm] с элементами

[cbm]c_{ij}=\sum\limits_{k=1}^{n}a_{ik}b_{kj}\,.[/cbm]

Нулевая [cbm](O)[/cbm] и единичная [cbm](E)[/cbm] матрицы любого порядка определяются с помощью единицы и нуля полукольца.

На множестве [cbm]\mathbb{M}_n(\mathcal{S})[/cbm] всех квадратных матриц фиксированного порядка [cbm]n[/cbm] можно определить алгебру

[cbm]\mathsf{M}_n(\mathcal{S})= \bigl(\mathbb{M}_n(\mathcal{S}),+,\cdot, O,E \bigr).[/cbm]

Теорема 3.8. Алгебра [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] есть идемпотентное полукольцо. Если полукольцо [cbm]\mathcal{S}[/cbm] замкнуто, то полукольцо [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] тоже замкнуто.

Операции суммы и произведения матриц определены таким образом, что все свойства операций сложения и умножения в полукольце сохраняются и для соответствующих операций над матрицами. Поэтому для суммы и произведения матриц из [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] выполнены аксиомы полукольца, и, кроме того, операция сложения матриц идемпотентна. Следовательно, [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] — идемпотентное полукольцо.

Выясним смысл отношения порядка в этом идемпотентном полукольце. В силу определения естественного порядка идемпотентного полукольца неравенство [cbm]A\leqslant B[/cbm] для матриц [cbm]A[/cbm] и [cbm]B[/cbm] означает, что [cbm]A+B=B[/cbm] , или для всех [cbm]i,\,j[/cbm] справедливо [cbm]a_{ij}+b_{ij}=c_{ij}[/cbm] . Следовательно, [cbm]A\leqslant B[/cbm] тогда и только тогда, когда для всех [cbm]i,\,j[/cbm] справедливо [cbm]a_{ij}\leqslant b_{ij}[/cbm] .

Пусть [cbm]\mathcal{S}[/cbm] — замкнутое полукольцо. Докажем замкнутость идемпотентного полукольца [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] и существование точной верхней грани у любой последовательности матриц в [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] .

Пусть [cbm]\{A_m\}_{m\in\mathbb{N}}[/cbm] — произвольная последовательность квадратных матриц [cbm]A_m=(a_{ij}^m)[/cbm] порядка [cbm]n[/cbm] . Рассмотрим матрицу [cbm]\textstyle{B= \Bigl(\sum\limits_{m\in\mathbb{N}}a_{ij}^{m}\Bigr)}[/cbm] . Каждый элемент [cbm]\textstyle{b_{ij}=\sum\limits_{m\in\mathbb{N}}a_{ij}^{m}}[/cbm] этой матрицы есть точная верхняя грань последовательности элементов [cbm]a_{ij}^{m}[/cbm] . Эти точные верхние грани существуют, поскольку [cbm]a_{ij}^{m}[/cbm] — элементы замкнутого полукольца [cbm]\mathcal{S}[/cbm] . Так как сложение матриц и отношение порядка в полукольце матриц определяются поэлементно, то матрица [cbm]B[/cbm] и будет точной верхней гранью последовательности матриц [cbm]A_m[/cbm] .

Докажем теперь непрерывность умножения в [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] , т.е. что для любой последовательности [cbm]\{A_m\}_{m\in \mathbb{N}}[/cbm] матриц и произвольной матрицы [cbm]B[/cbm] имеет место

[cbm]B\cdot \sum A_m= \sum(B\cdot A_m).[/cbm]

Матрица [cbm]\textstyle{C=(c_{ij})= \sum A_m}[/cbm] есть точная верхняя грань последовательности [cbm]\{A_m\}_{m\in \mathbb{N}}[/cbm] . Тогда имеем

[cbm]B\cdot \sum A_m= BC= \left(\sum\limits_{k=1}^{n}b_{ik}\cdot c_{kj}\right)\!.[/cbm]

Элемент [cbm]c_{kj}[/cbm] есть точная верхняя грань последовательности [cbm]\{a_{kj}^{m}\}_{m\in \mathbb{N}}[/cbm] элементов матриц [cbm]A_m[/cbm] , т.е.

[cbm]c_{ij}= \sum\limits_{m\in \mathbb{N}} a_{ij}^{m}.[/cbm]

Используя непрерывность умножения в исходном полукольце [cbm]\mathcal{S}[/cbm] , получаем

[cbm]\sum\limits_{k=1}^{n}b_{ik} c_{ik}= \left(\sum\limits_{k=1}^{n}b_{ik} \sum\limits_{m=1}^{\infty} a_{kj}^{m}\right)= \left(\sum\limits_{k=1}^{n} \sum\limits_{m=1}^{\infty} b_{ik}b_{kj}^{m}\right)\!.[/cbm]
Следовательно,
[cbm]B\cdot \sum\limits_{k=1}^{\infty}A_m= \sum\limits_{k=1}^{n}b_{ik} \sum\limits_{m=1}^{\infty}a_{kj}^{m}.[/cbm]

Используя непрерывность сложения, получаем

[cbm]\sum\limits_{k=1}^{n}b_{ik} \sum\limits_{m=1}^{\infty}a_{kj}^{m}= \sum\limits_{m=1}^{\infty} \left(\sum\limits_{k=1}^{n}b_{ik}a_{kj}^{m}\right)= \sum\limits_{m=1}^{\infty} (BA_m).[/cbm]

Аналогично доказывается, что [cbm]\textstyle{(\sum A_m)B= \sum(A_mB)}[/cbm] .


Полукольцо матрицы

Полукольцо [cbm]\mathsf{M}_n(\mathcal{S})[/cbm] будем называть полукольцом матриц над полукольцом [cbm]\mathcal{S}[/cbm] . Доказанная теорема позволяет нам применять к замкнутым полукольцам матриц над некоторым замкнутым полукольцом [cbm]\mathcal{S}[/cbm] теорему 3.7 и решать произвольные уравнения вида (относительно неизвестной матрицы [cbm]X[/cbm] ):

[cbm]X=A\cdot X+B[/cbm]
(3.17)
или
[cbm]X=X\cdot A+B[/cbm]
(3.18)
Наименьшие решения этих уравнений есть
[cbm]X=A^{\ast}\cdot B[/cbm]
(3.19)
и
[cbm]X=B\cdot A^{\ast}[/cbm]
(3.20)

соответственно, где [cbm]A^{\ast}[/cbm] — итерация матрицы [cbm]A[/cbm] в [cbm]\mathsf{S}_n(\mathcal{S})[/cbm] . Итерация [cbm]A^{\ast}[/cbm] матрицы [cbm]A[/cbm] играет в теории линейных уравнений в замкнутых полукольцах такую же роль, как обратная матрица в классической линейной алгебре.

Основную роль при решении задач теории ориентированных графов и теории формальных языков играют праволинейные уравнения вида (3.17), поэтому мы будем, как правило, рассматривать только их. Леволинейное уравнение (3.18) может быть проанализировано аналогично.

Мы доказали существование решений матричных уравнений в матричном полукольце над замкнутым полукольцом. Теперь нам необходимо разработать технику поиска их решений и применить ее к решению систем вида (3.16).

Полагая, что [cbm]\xi_j[/cbm] — j-й столбец матрицы [cbm]X[/cbm] , a [cbm]\beta_j[/cbm] — j-й столбец матрицы [cbm]B[/cbm] , уравнение (3.17) можно переписать как систему уравнений относительно неизвестных столбцов матрицы [cbm]X:[/cbm]

[cbm]\xi_j=A\cdot\xi_j+\beta_j,\quad 0\leqslant j\leqslant n\,.[/cbm]
(3.21)

Каждая система вида (3.21) есть матричная форма записи указанной выше системы (3.16). Поэтому наименьшее решение этой системы, как следует из (3.19), есть

[cbm]\xi_j=A^{\ast}\cdot\beta_j\,.[/cbm]
(3.22)

Для поиска решения системы вида (3.21) можно воспользоваться методом последовательного исключения неизвестных, аналогичным классическому методу Гаусса.

Поскольку система уравнений вида (3.16) имеет решение, мы можем подставить его в систему и работать с уравнениями как с тождествами.

Рассмотрим процедуру решения системы уравнений (3.16). Запишем первое уравнение системы так:

[cbm]x_1=a_{11}x_1+(a_{12}x_2+\ldots+a_{1n}x_n+b_1).[/cbm]

Из первого уравнения системы выразим [cbm]x_1[/cbm] через остальные неизвестные, воспользовавшись формулой (3.14):

[cbm]x_1=a_{11}^{\ast}\cdot (a_{12}x_2+\ldots+a_{1n}x_n+b_1).[/cbm]
(3.23)

В формуле (3.23) выражение в скобках не содержит неизвестного [cbm]x_1[/cbm] . Подставляя (3.23) вместо [cbm]x_1[/cbm] в остальные уравнения, получаем систему из [cbm]n-1[/cbm] уравнении, которая уже не содержит [cbm]x_1:[/cbm]

[cbm]\left\{\!\begin{gathered} x_2=a_{21}a_{11}^{\ast} (a_{12}x_2+\ldots+a_{1n}x_n+b_1)+ a_{22}x_2+\ldots+ a_{2n}x_n+b_2, \hfill\\ x_3=a_{31}a_{11}^{\ast} (a_{12}x_2+\ldots+ a_{1n}x_n+ b_1)+ a_{32}x_2+\ldots+ a_{3n}x_n+b_3, \hfill\\[-5pt] \vdots\\[-3pt] x_n=a_{n1}a_{11}^{\ast} (a_{12}x_2+\ldots+a_{1n}x_n+b_1)+ a_{n2}x_2+\ldots+ a_{nn}x_n+b_n.\hfill \end{gathered}\right.[/cbm]
(3.24)

Приводя подобные члены в каждом уравнении системы, получаем:

[cbm]\left\{\!\begin{gathered}x_2= (a_{21}a_{11}^{\ast}a_{12}+a_{22})x_2+\ldots+ (a_{21}a_{11}^{\ast}a_{1n}+a_{2n})x_n+ a_{21}a_{11}^{\ast}b_1+b_2,\hfill\\ x_3= (a_{31}a_{11}^{\ast}a_{12}+a_{32})x_2+\ldots+ (a_{31}a_{11}^{\ast}a_{1n}+a_{3n})x_n+ a_{31}a_{11}^{\ast}b_1+b_3,\hfill\\[-5pt] \vdots\\[-3pt] x_n= (a_{n1}a_{11}^{\ast}a_{12}+a_{n2})x_2+\ldots+ (a_{n1}a_{11}^{\ast}a_{1n}+a_{nn})x_n+ a_{n1}a_{11}^{\ast}b_1+b_n.\hfill \end{gathered}\right.[/cbm]
(3.25)

Первое уравнение этой системы перепишем так:

[cbm]x_2=(a_{21}a_{11}^{\ast}a_{12}+a_{22})x_2+\gamma_2,[/cbm]
где
[cbm]\gamma_2= a_{21}a_{11}^{\ast}(a_{13}x_3+\ldots+a_{1n}x_n+b_1)+ a_{23}x_3+ \ldots+ a_{2n}x_n+b_2\,.[/cbm]

Заметим, что [cbm]\gamma_3[/cbm] не содержит [cbm]x_1[/cbm] и [cbm]x_2[/cbm] . Воспользовавшись соотношением (3.14), будем иметь

[cbm]x_2=\alpha_{2}^{\ast}\cdot\gamma_2\,,[/cbm]
(3.26)

где [cbm]\alpha_2=a_{21}a_{11}^{\ast}a_{12}+a_{22}[/cbm] не содержит неизвестных. Используя полученное выражение, исключаем [cbm]x_2[/cbm] из остальных уравнений.

Действуя подобным образом, на i-м шаге [cbm](1\leqslant i\leqslant n)[/cbm] получаем

[cbm]x_i=\alpha_{i}^{\ast}\cdot\gamma_{i}\,,[/cbm]
(3.27)

где выражение [cbm]\alpha_{i}^{\ast}[/cbm] не содержит неизвестных, а выражение [cbm]\gamma_i[/cbm] может содержать только неизвестные, начиная с (i+1)-го, то есть [cbm]x_{i+1},\ldots,x_n[/cbm] .

При [cbm]i=n[/cbm] имеем

[cbm]x_n= \alpha_{n}^{\ast}\cdot \gamma_{n}\,,[/cbm]
(3.28)

где выражения [cbm]\alpha_{n}^{\ast}[/cbm] и [cbm]\gamma_{n}[/cbm] не содержат неизвестных. Таким образом, исходная система (3.16) преобразована к "треугольному" виду: правая часть уравнения (3.28) не содержит неизвестных, уравнение (3.27) при [cbm]i=n-1[/cbm] в правой части содержит только одно неизвестное [cbm]x_{n-1}[/cbm] и каждое следующее уравнение при просмотре "снизу вверх" на одно неизвестное больше, чем предыдущее. Первое уравнение системы — уравнение (3.23) — в правой части содержит все неизвестные от [cbm]x_2[/cbm] до [cbm]x_n[/cbm] . На этом завершается первый этап алгоритма, который называют прямым ходом метода Гаусса.

Второй этап алгоритма, называемый обратным ходом метода Гаусса, состоит в последовательном нахождении значения всех неизвестных [cbm]x_1,\ldots,x_{n-1}[/cbm] начиная с [cbm]x_{n-1}[/cbm] . Подставив в выражение для [cbm]x_{n-1}[/cbm] вместо [cbm]x_n[/cbm] правую часть (3.28), найдем [cbm]x_{n-1}[/cbm] . Затем определим [cbm]x_{n-2}[/cbm] , подставив полученные значения [cbm]x_{n}[/cbm] и [cbm]x_{n-1}[/cbm] в правую часть выражения (3.27) при [cbm]i=n-2[/cbm] , и так далее до тех пор, пока не найдем [cbm]x_1[/cbm] .

Замечание 3.2. Положив [cbm]B=E[/cbm] в уравнении (3.17), получим [cbm]X=A^{\ast}E=A^{\ast}[/cbm] . Таким образом, чтобы вычислить итерацию матрицы [cbm]A[/cbm] , достаточно решить матричное уравнение (3.21) для всех [cbm]j=\overline{1,n}[/cbm] при [cbm]\beta_j[/cbm] , равном j-му столбцу единичной матрицы [cbm]E[/cbm] .


Пример 3.6. Проиллюстрируем приведенную схему решения системы из двух линейных уравнений. Имеем

[cbm]\begin{cases}x_1= a_{11}x_1+a_{12}x_2+b_1,\\ x_2= a_{21}x_1+a_{22}x_2+b_2. \end{cases}[/cbm]

Из первого уравнения выразим [cbm]x_1:[/cbm] — получим [cbm]x_1= a_{11}^{\ast} (a_{12}x_2+ b_1)[/cbm] . Подставляя это выражение во второе уравнение, получаем

[cbm]x_2= (a_{21}a_{11}^{\ast}a_{12}+a_{22})^{\ast} (a_{21}a_{11}^{\ast}b_1+ b_2).[/cbm]

Подставляя этот результат в написанное выше выражение для xi, находим окончательное решение:

[cbm]x_1= a_{11}^{\ast} \bigl(a_{12}(a_{21}a_{11}^{\ast}a_{12}+a_{22})^{\ast} (a_{21}a_{11}^{\ast}b_1+ b_2)+b_1\bigr).[/cbm]

Особенно просто решение выглядит в случае тривиальной итерации, т.е. тогда, когда в полукольце итерация любого элемента равна единице полукольца (как в полукольцах [cbm]\mathcal{B}, \mathcal{R}^{+}, \mathcal{S}_A, \mathcal{S}_{[a,b]}[/cbm] ). В этом случае для системы из двух уравнений решение равно

[cbm]\begin{cases}x_1=a_{22}(a_{22}b_1+b_2)+b_1,\\ x_2=a_{21}b_1+b_2. \end{cases}[/cbm]

Пример 3.7. Рассмотрим в полукольце [cbm]\mathcal{S}_{[0;1]}[/cbm] (см. пример 3.3.г) систему линейных уравнений

[cbm]\begin{cases}x_1=0,\!5x_1+0,\!4x_2+0,\!2;\\ x_2=0,\!3x_1+0,\!9x_2+0,\!6. \end{cases}[/cbm]

Решим эту систему уравнений, следуя общему алгоритму. Из первого уравнения получаем

[cbm]x_1=0,\!5^{\ast} (0,\!4x_2+0,\!2)= 1(0,\!4x_2+0,\!2)=0,\!4x_2+0,\!2\,.[/cbm]
Далее,
[cbm]x_2=0,\!3(0,\!4x_2+0,\!2)+ 0,\!9x_2+0,\!6= 0,\!3x_2+0,\!2+0,\!9x_2+0,\!6\,.[/cbm]

Отсюда [cbm]x_2=(0,\!3+0,\!9)x_2+0,\!6= 0,\!9x_2+0,\!6= 0,\!9^{\ast}0,\!6= 0,\!6\,.[/cbm] . Подставляя [cbm]x_2=0,\!6[/cbm] в полученное выражение для [cbm]x_1[/cbm] , находим, что

[cbm]x_1=0,\!4\cdot0,\!6=0,\!4+0,\!2=0,\!4\,.[/cbm]

Полукольца с итерацией

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

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

Полукольцо [cbm]\mathcal{Q}= (Q,+,\cdot,\bold{0},\bold{1})[/cbm] называют подполукольцом полукольца [cbm]\mathcal{R}= (R,+,\cdot,\bold{0},\bold{1})[/cbm] , если множество [cbm]Q[/cbm] есть подмножество множества [cbm]R[/cbm] , замкнутое относительно операций сложения и умножения полукольца [cbm]\mathcal{R}[/cbm] , а также содержащее нуль и единицу полукольца [cbm]\mathcal{R}[/cbm] .

Рассматривая в полукольце с итерацией произвольное линейное уравнение, т.е. уравнение вида (3.12) или (3.13), получаем следующие результаты. Во-первых, это уравнение имеет наименьшее решение, так как полукольцо с итерацией содержится в некотором замкнутом полукольце в качестве подполукольца. Во-вторых, это наименьшее решение снова окажется в этом же полукольце, поскольку носитель полукольца с итерацией замкнут относительно итерации. Таким образом, носитель полукольца [cbm]\mathcal{S}[/cbm] с итерацией замкнут относительно операции нахождения наименьшей неподвижной точки любого линейного отображения [cbm]ax+b[/cbm] (или [cbm]xa+b[/cbm] ), где [cbm]a[/cbm] и [cbm]b[/cbm] — элементы [cbm]\mathcal{S}[/cbm] .

Не составляет труда распространить этот результат на произвольные матричные уравнения. Можно доказать следующее утверждение.

Теорема 3.9. Если [cbm]A[/cbm] — матрица, все элементы которой принадлежат некоторому полукольцу с итерацией, то все элементы ее итерации [cbm]A^{\ast}[/cbm] также принадлежат этому полукольцу с итерацией.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: