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

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

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

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

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


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

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


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


[math]\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.[/math]
(3.16)

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


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


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


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


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


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

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


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


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



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


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


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


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


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


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


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

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


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

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


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

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


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

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


[math]\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).[/math]

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




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


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


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

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


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


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


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


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

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


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

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


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


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


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

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


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

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


[math]\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.[/math]
(3.24)

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


[math]\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.[/math]
(3.25)

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


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

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


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

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


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


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

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


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

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

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


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


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




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


[math]\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}[/math]

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


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

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


[math]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).[/math]

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


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



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


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

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


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

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


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



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


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


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


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


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


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


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


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


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

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