Решение систем линейных уравнений

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

где все элементы a_ij, 1 ≤ i ≤ n, 1 ≤ j ≤ n, и b_i, 1 ≤ i ≤ n, суть элементы некоторого замкнутого полукольца, и речь идет о решении системы (3.16) в этом полукольце.

Для этого введем в рассмотрение множество M_m×n(S) прямоугольных матриц типа тхпс элементами из произвольного идемпотентного полукольца S = (S,+,⋅,0,1). Множество всех квадратных матриц порядка п с элементами из полукольца S обозначим M_n(S). Через Matr(S) обозначим множество всех матриц любого типа с элементами из S.

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

1) суммой матриц А = (а_ij) и В = (b_ij) типа m×n называют матрицу С = (c_ij) того же типа с элементами с_ij = a_ij + b_ij, i = 1, m, j = 1,n, и используют обозначение С = А + В;

2) произведением АВ матриц А = (а_ij) типа m×n и B = (b_ij) типа n×p называют матрицу С = (c_ij) типа m×p с элементами

На множестве M_n(S) всех квадратных матриц фиксированного порядка n можно определить алгебру

M_n(S) = (M_n(S) , +, ⋅, O, E).

Теорема 3.8. Алгебра M_n(S) есть идемпотентное полукольцо. Если полукольцо S замкнуто, то полукольцо M_n(S) тоже замкнуто.

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

Выясним смысл отношения порядка в этом идемпотентном полукольце. В силу определения естественного порядка идемпотентного полукольца неравенство А ≤ В для матриц А и В означает, что А + В = B, или для всех i, j справедливо a_ij + b_ij = b_ij. Следовательно, А ≤ В тогда и только тогда, когда для всех i, j справедливо a_ij ≤ b_ij.

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

Пусть {А_m}_m∈ℕ — произвольная последовательность квадратных матриц А_m = (а^mij) порядка n. Рассмотрим матрицу . Каждый элемент этой матрицы есть точная верхняя грань последовательности элементов а^mij. Эти точные верхние грани существуют, поскольку а^mij — элементы замкнутого полукольца S. Так как сложение матриц и отноше- отношение порядка в полукольце матриц определяются поэлементно, то матрица В и будет точной верхней гранью последователь- последовательности матриц А_m.

Докажем теперь непрерывность умножения в M_n(S), т.е. что для любой последовательности {А_m}_m∈ℕ матриц и произвольной матрицы В имеет место

B ∑ A_m = ∑ (B A_m ).

Матрица С = (с_ij) = ∑ A_m есть точная верхняя грань последовательности {А_m}_m∈ℕ. Тогда имеем

Элемент с_kj есть точная верхняя грань последовательности {а^mkj}_m∈ℕ элементов матриц А_m, т.е.

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

Следовательно,

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

Аналогично доказывается, что (∑ A_m) B = ∑ (A_mB).▶

Полукольцо М_n(S) будем называть полукольцом матриц над полукольцом S. Доказанная теорема позволяет нам применять к замкнутым полукольцам матриц над некоторым замкнутым полукольцом S теорему 3.7 и решать произвольные уравнения вида

Х = АХ + В    (3.17)

или

Х = ХА + В    (3.18)

относительно неизвестной матрицы X.

Наименьшие решения этих уравнений есть

X = А* В    (3.19)

и

Х = ВА*    (3.20)

соответственно, где А* — итерация матрицы А в M_n(S). Итерация А* матрицы А играет в теории линейных уравнений в замкнутых полукольцах такую же роль, как обратная матрица в классической линейной алгебре.

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

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

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

ξ_j = Aξ_j + β_j, 0 ≤ j ≤ n. (3.21)

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

ξ_j = А* β_j. (3.22)

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

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

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

х₁ = a₁₁x₁ + (a₁₂x₂ + ... + a_1nx_n + b₁).

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

х₁ = a^*11 (a₁₂x₂ + ... + a_1nx_n + b₁).    (3.23)

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

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

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

x₂ = (a₂₁a^*11a₁₂ + a₂₂) x₂ + γ₂,

где

γ₂ = a₂₁a^*11  (a₁₃x₃ + ... + a_1nx_n +b₁) + a₂₃x₃ + a₂₃x₃ + ... + a_2nx_n + b₂.

Заметим, что γ₂ не содержит x₁ и x₂. Воспользовавшись соотношением (3.14), будем иметь

x₂ = α^*2 γ₂,   (3.26)

где α₂ = a₂₁a^*11 a₁₂ + a₂₂ не содержит неизвестных. Используя полученное выражение, исключаем x₂ из остальных уравнений.

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

x_i = α^*i γ_i,    (3.27)

где выражение α^*i  не содержит неизвестных, а выражение γ_i может содержать только неизвестные, начиная с (i + 1)-го, т.е. x_i+1, ..., x_n.

При i = n имеем

x_n = α^*i γ_n,     (3.28)

где выражения α^*i и γ_n не содержат неизвестных. Таким образом, исходная система (3.16) преобразована к "треугольному" виду: правая часть уравнения (3.28) не содержит неизвестных, уравнение (3.27) при i = n - 1 в правой части содержит только одно неизвестное x_n-1 и каждое следующее уравнение при просмотре „снизу вверх" на одно неизвестное больше, чем предыдущее. Первое уравнение системы — уравнение (3.23) — в правой части содержит все неизвестные от x₂ до х_n. На этом завершается первый этап алгоритма, который называют прямым ходом метода Гаусса.

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

Замечание 3.2. Положив В = Е в уравнении (3.17), получим X = А*Е = А*. Таким образом, чтобы вычислить итерацию матрицы А, достаточно решить матричное уравнение (3.21) для всех j = 1, n при β_j, равном j-му столбцу единичной матрицы Е.

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

Из первого уравнения выразим x₁:

x₁ = a^*11  (a₁₂x₂ + b₁).

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

x₂ = (a₂₁a^*11  a₁₂ + a₂₂)*(a₂₁a^*11  b₁ + b₂).

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

x₁ = a^*11  (a₁₂(a₂₁a^*11  a₁₂ + a₂₂)*(a₂₁a^*11  b₁ + b₂) + b₁).

Особенно просто решение выглядит в случае тривиальной итерации, т.е. тогда, когда в полукольце итерация любого элемента равна единице полукольца (как в полукольцах В, R⁺, S_a, S_[a,b]). В этом случае для системы из двух уравнений решение равно

x₁ = a₁₂ (a₂₁b₁ + b₂) + b₁,

x₂ = a₂₁ba₁ + b₂.

Пример 3.7. Рассмотрим в полукольце S_[0,1](см. пример З.З.г) систему линейных уравнений

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

х₁ = 0,5* (0,4x₂ + 0,2) = 1(0,4x₂ + 0,2) = 0,4х₂ + 0,2.

Далее,

х₂ = 0,3(0,4x₂ + 0,2) + 0,9x₂ + 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.

Подётавляя x₂ = 0,6 в полученное вьражение для х₁, находим, что

х₁ = 0,4 ⋅ 0,6 + 0,2 = 0,4 + 0,2 = 0,4. #

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

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

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

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

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

Теорема 3.9. Если А — матрица, все элементы которой принадлежат некоторому полукольцу с итерацией, то все элементы ее итерации А* также принадлежат этому полукольцу с итерацией.