РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИИ В

ЦЕЛОСТНОМ КОЛЬЦЕ ^{∗}

МАЛАШОНОК Г. И. (Львов)

Аннотация

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

1 Введение

Будем рассматривать систему линейных уравнений

∑_{j=1}^{n} a_{i,j}x_{j} = a_{i,n+1}, i = l, 2, …, ,  (1.1)

коэффициенты и свободные члены которой принадлежат некоторому целостному коммутативному кольцу К. Такую систему будем записывать с помощью расширенной матрицы с размерами n × (n + l):

B = ∥a_{ij}∥, i = l, 2, …, n, j = 1, 2, …, n + l.  (1.2)

Введем, как обычно, матрицу, образованную коэффициентами системы (1.1), которую обозначим через A, и матрицы A_{i}, i = 1, 2, …, n, которые получаются из матрицы A заменой элементов i-го столбца свободными членами, а их детерминанты обозначим, соответственно, Δ и Δ_{i}. Решение системы (1.1), вообще говоря, принадлежит полю частных кольца K (см. [1], [2]). Однако имеются алгоритмы решения системы (1.1), промежуточные результаты которых лежат в кольце K. К ним относится, например, схема умножения и вычитания метода Гаусса [З], а также метод решения по формулам Крамера

∗ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, Том 23, Ноябрь-Декабрь 1983, � 6, 1497-1500

x_{i} = Δ_{i}/Δ, i = l, 2, …, ,  (1.3)

когда определители ищутся разложением по строкам или столбцам.

Такие алгоритмы решения в кольце имеют то преимущество, что не допускают промежуточных ошибок округления, а также имеют более простые операции. Однако решение с помощью формул Крамера при непосредственном отыскании определителей только с помощью операций сложения, вычитания и умножения требует очень большого числа операций, а схема умножения и вычитания метода Гаусса приводит к быстрому росту разрядности чисел.

Рассматриваемый ниже алгоритм решения в целостном коммутативном кольце не требует большого количества операций и не приводит к быстрому росту разрядности элементов матриц из-за использования операции сокращения обеих частей уравнения на не равный нулю общий множитель, что позволительно в целостном кольце. Как обычно, совершим сначала прямой ход и приведем матрицу B к эквивалентной треугольной матрице B_{n}, а затем - обратный ход и придем к эквивалентной диагональной матрице D_{1}.

2 Преобразование к треугольному виду

Обозначим через A_{ij}^{k}, l ≤ k ≤ n, k ≤ j ≤ n + 1, квадратную матрицу порядка k, представляющую собой левую верхнюю часть матрицы B, окаймленную строкой i и столбцом j, т. е.

A_{ij}^{k} = ∥a_{pq}∥, p = 1, 2, …, k − 1, i, q = l, 2, …, k − 1, j,  (2.1)

и введем обозначение для ее детерминанта:

a_{ij}^{k} = |A_{ij}^{k}|.  (2.2)

Заметим, что a_{ij}^{1} = a_{ij}, i = 1, 2, …, n, j = l, 2, …, n + l.

Будем предполагать, что имеет место условие выполнимости алгоритма Гаусса, т. е. диагональные миноры не равны нулю:

a_{kk}^{k} ≠ 0, k = i, 2, …, n.  (2.3)

На первом шаге матрицу В преобразуем по схеме умножения и вычитания [3]: из каждой строки с индексом i, i ≥ 2, умноженной на a_{11}, вычтем первую строку, умноженную на a_{i1}. В результате получим матрицу

B_{2} = ∥b_{i,j}^{2}∥, b_{1j}^{2} = a_{1j}^{1}, b_{i1}^{2} = 0, b_{ij}^{2} = a_{ij}^{2}, i > 1,

элементы которой определяются формулами (2.2).

Каждый очередной шаг, кроме первого, требует выполнения операции сокращения на общий множитель. Покажем, как производится k-й шаг, k ≥ 2. Пусть на предыдущем шаге получена следующая матрица с элементами (2.2):

B_{k} = ∥b_{ij}^{k}∥, b_{ij}^{k} = \{ \begin{matrix}a_{ij}^{i} & при & i = 1, 2, …, k − 1, j ≥ i, \\ 0 & при & i > j, j = 1, 2, …, k − 1, \\ a_{ij}^{k} & при & i, j ≥ k. \end{matrix}  (2.4)

На k-м шаге матрицу B^{k} преобразуем так: из каждой строки с индексом i, i ≥ k + 1, умноженной на a_{kk}^{k} вычтем строку с индексом k, умноженную на a_{ik}^{k}, тогда элемент j-го столбца, j ≥ k + 1, строки i примет вид

a_{kk}^{k}a_{ij}^{k} − a_{ik}^{k}a_{kj}^{k}  (2.5)

а в первых k столбцах будут стоять нули.

Главная особенность этого метода состоит в том, что все элементы (2.5) можно сократить на ведущий элемент a_{k−1,k−1}^{k−1} и получить матрицу B_{k+1} в соответствии с (2.4).

Чтобы показать это, нам понадобится детерминантное тождество Сильвестра [4], которое для матрицы A порядка n и для любого s, s = l, 2, …, n− 1, в принятых выше обозначениях (2.1) и (2.2) запишется так:

|M^{s}| = (a_{s−1,s−1}^{s−1})^{n−s}Δ,  (2.6)

где M^{s}, s = l, 2, …, n, – матрицы порядка n − s + 1 с элементами a_{pq}^{s}, p, q = s, s + l, …, n.

Заметим, что детерминантное тождество Сильвестра справедливо для матриц над коммутативным целостным кольцом; чтобы показать это, достаточно в доказательстве данного тождества [4] воспользоваться методом Гаусса по схеме умножения и вычитания.

Запишем детерминантное тождество Сильвестра для матрицы A_{i,j}^{k+1} порядка k + l, k < i ≤ n, k < j ≤ n + 1, и при условии s = k:

| \begin{matrix}a_{kk}^{k} & a_{kj}^{k} \\ a_{ik}^{k} & a_{ij}^{k} \end{matrix} | = a_{k−1,k−1}^{k−1}a_{ij}^{k+1}.

Это тождество показывает, что выражение (2.5) раскладывается на произведение двух сомножителей, что позволяет сократить все строки начиная с (k+1)-й на общий множитель a_{k−1,k_{1}}^{k−1}, который не равен нулю в силу (2.3), и в результате получить матрицу B_{k+1}. После (n − 1)-го шага прямого хода получим искомую треугольную матрицу B_{n}, у которой по главной диагонали стоят диагональные миноры a_{kk}^{k}, k = 1, 2, …, n, а все элементы под главной диагональю – нули.

3 Преобразование к диагональному виду

Матрицу с размерами n × (n + 1) обозначим таким образом:

D_{k} = ∥d_{ij}∥, k = 1, 2, …, n,  (3.1a)

d_{i,j} = \{ \begin{matrix}0 & при & i > j, и при i = k, …, n − 1, j = i + 1, …, n; \\ a_{ij}^{i} & при & i = 1, 2, …, k − 1, j ≥ i; \end{matrix}

(3.1b)
d_{ii} = Δ; d_{i,n+1} = Δ_{i}, i = k, …, n.  (3.1c)

Заметим, что из определения (2.2) следует, что a_{nn}^{n} = Δ и a_{n,n+1}^{n} = Δ_{n}, поэтому D_{n} = B_{n}. Таким образом, на первом шаге обратного хода уже имеется матрица D_{n}.

Пусть на некотором шаге обратного хода получена матрица D_{k}, k = 2, 3, …, n. Чтобы совершить очередной шаг, умножим все элементы строки k − 1 на Δ и вычтем из нее все нижние строки с индексами i, i = k, k + i, …, n, умножая их предварительно на a_{k−1,i}^{k−1}. В результате в (k-1)-й строке диагональным элементом станет a_{k−1,k−1}^{k−1}Δ, элементом в последнем столбце станет

a_{k−1,n+1}^{k−1}Δ − ∑_{i=k}^{n} a_{k−1,i}^{k−1}Δ_{i},  (3.2)

а все остальные элементы обратятся в нуль.

Покажем теперь, что выражение (3.2) раскладывается на множители Δ_{k−1} и a_{k−1,k−1}^{k−1}. Для этого введем квадратные матрицы M_{j}^{s}, 1 ≤ s ≤ j ≤ n, образованные заменой j-го столбца на (n + 1)-й в матрице M^{s}; тогда тождество Сильвестра для матриц A_{j}, и для любого s, s = 1, 2, …, n, запишется в виде

|M_{j}^{s}| = (a_{k−1,k−1}^{k−1})^{n−s}Δ_{j}.  (3.3)

Подставим значения |M_{j}^{k−1}| и |M^{k−1}| из (3.3) и (2.6) в тождество

∑_{j=k−1}^{n} a_{k−1,j}^{k−1}|M_{j}^{k−1}| = a_{k−1,n+1}^{k−1}|M^{k−1}|,

справедливость которого легко проверяется разложением по столбцу j и заменой порядка суммирования в левой части.

После сокращения на (a_{k−2,k−2}^{k−2})^{n−k+1} и перегруппировки слагаемых получим тождество

a_{k−1,n+1}^{k−1}Δ − ∑_{i=k}^{n} a_{k−1,i}^{k−1}Δ_{i} = a_{k−1,j}^{k−1}Δ_{k−1}.

Таким образом, показано, что элементы (k−1)-й строки можно сократить на a_{k−1,k−1}^{k−1} и в результате получить матрицу D_{k−1}, в соответствии с (3.1).

После n − 1 шага обратного хода получим диагональную матрицу D_{1}, у которой все элементы на главной диагонали равны детерминанту основной матрицы Δ, в последнем столбце в i-й строке, i = l, 2, …, n, стоит детерминант Δ_{i}, а все остальные элементы равны нулю.

Таким образом, получено решение по формулам Крамера (1.3); вычисление всех детерминантов Δ и Δ_{i} проводилось одновременно, причем все время внутри кольца K.

4 Алгоритм

Выпишем теперь отдельно алгоритм, предполагая, что имеет место условие выполнимости алгоритма Гаусса (2.3).

Прямой ход.

1. Умножаем каждую строку расширенной матрицы (1.2) с номером i, i ≥ 2, на a_{11} и вычитаем из нее первую строку, умноженную на a_{i1}. В результате приходим к матрице B_{2}.

2. Пусть на предыдущем шаге получена матрица B_{k}, k = 2, 3, …, n−1. Умножаем каждую строку с номером i, i ≥ k + 1, на a_{kk}^{k} и вычитаем из нее строку с номером k, умноженную на a_{ik}^{k}. Строки с номерами k+1, k+ 2, …, n сокращаем на a_{k−1,k−1}^{k−1} и приходим к матрице B_{k+1}.

3. После (n − 1)-го шага приходим к треугольной матрице B_{n}, в последней строке которой два ненулевых элемента, a_{nn}^{n} = Δ и a_{n,n−1}^{n} = Δ_{n}.

Обратный ход.

1. Пусть уже известны Δ_{n}, Δ_{n−1}, …, Δ_{k+1}, 1 ≤ k ≤ n − 1; тогда, используя элементы матрицы B_{n} найдем Δ_{k} по формуле

Δ_{k} = \frac{Δa_{k,n+1}^{k} − ∑_{j=k+1}^{n} a_{k,j}^{k}Δ_{j}}{a_{kk}^{k}} ,

где дробная черта означает операцию деления нацело.

2. Решение системы находим по формулам Крамера x_{i} = Δ_{i}/Δ, i = 1, 2, …, n.

5 Вычисление элементов присоединенной матрицы

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

Пусть P = ∥p_{ij}∥, i, j = 1, 2, … n, – присоединенная матрица для матрицы A = ∥a_{i}, j∥, i, j = 1, 2, …, n; тогда определение ее элементов можно свести [3] к решению n систем вида

∑_{k=1}^{n} a_{ik}p_{kj} = Δδ_{i,j}, i = l, 2, …, n, j = 1, 2, …, n,

где δ_{i,j}, – дельта-символ Кронекера и Δ = |A|.

Как обычно, прямой ход для всех n матриц можно провести одновременно, если вместо (1.2) взять матрицу

B_{E} = ∥ \begin{matrix}a_{11} & … & a_{1n} & 1 & 0 & … & 0 \\ a_{21} & … & a_{2n} & 0 & 1 & … & 0 \\ … & … & … & … & … & … & … \\ a_{n1} & … & a_{nn} & 0 & 0 & … & 1 \end{matrix} ∥ .

В результате получим матрицу B_{En} = ∥a_{ij}^{n}∥, i = 1, 2, …, n, j = 1, 2, …, 2n, у которой все элементы ниже главной диагонали и выше последней диагонали – нули, а ненулевыми элементами в последней строке будут a_{nn}^{n} = Δ и a_{n,n+j}^{n} = p_{nj}, j = 1, 2, …, n.

Обратный ход совершается обычным образом: пусть уже известны элементы p_{ij}, i = k + l, k + 2, …, n, j = 1, 2, …, n, 1 ≤ k ≤ n − 1, последних n − k строк присоединенной матрицы P; тогда элементы k-й строки присоединенной матрицы получим, используя элементы матрицы B_{En}, по формуле

p_{kj} = \frac{Δa_{k,n+j}^{k} − ∑_{i=k+1}^{n} a_{k,i}^{k}p_{ij}}{a_{kk}^{k}} , j = 1, 2, …, n,

где дробная черта означает операцию деления нацело.

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

6 Литература

1. Ван дер Варден Б. Л. Алгебра. М.: Наука, 1979.

2. Мальцев А. И. Основы линейной алгебры. М.: Наука, 1970.

3. Фаддеев Д. К; Фаддеева В. К. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.

4. Гатмахер Ф. Р. Теория матриц. М.: Наука, 1968.

Поступила в редакцию 22.Х.1981

Переработанный вариант 4.Х.1982