Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


\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] \quad\vdots\hfill\\[-3pt] x_n= a_{n1}x_1+a_{n2}x_2+\ldots+ a_{nn}x_n+b_n.\hfill \end{gathered}\right.
(3.16)

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


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


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


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


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


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

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


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


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



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


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


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


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


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


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


B\cdot \sum A_m= \sum(B\cdot A_m).

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


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

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


c_{ij}= \sum\limits_{m\in \mathbb{N}} a_{ij}^{m}.

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


\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)\!.
Следовательно,
B\cdot \sum\limits_{k=1}^{\infty}A_m= \sum\limits_{k=1}^{n}b_{ik} \sum\limits_{m=1}^{\infty}a_{kj}^{m}.

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


\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).

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




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


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


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

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


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


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


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


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

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


\xi_j=A^{\ast}\cdot\beta_j\,.
(3.22)

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


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


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


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

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


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

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


\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.
(3.24)

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


\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.
(3.25)

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


x_2=(a_{21}a_{11}^{\ast}a_{12}+a_{22})x_2+\gamma_2,
где
\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\,.

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


x_2=\alpha_{2}^{\ast}\cdot\gamma_2\,,
(3.26)

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


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


x_i=\alpha_{i}^{\ast}\cdot\gamma_{i}\,,
(3.27)

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


При i=n имеем

x_n= \alpha_{n}^{\ast}\cdot \gamma_{n}\,,
(3.28)

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


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


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




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


\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}

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


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

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


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).

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


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



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


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

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


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

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


x_1=0,\!4\cdot0,\!6=0,\!4+0,\!2=0,\!4\,.



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


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


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


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


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


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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved