Обыкновенные и модифицированные жордановы исключения

Рассмотрим одно алгебраическое преобразование, лежащее в основе удобного вычислительного аппарата, используемого в математическом программировании.

Пусть дана система линейных функций) от неизвестных :

, (1)

где ─ постоянные величины .

Представим систему (1.1) в форме таблицы 1.

Таблица 1.

		…		…		…
		…		…		…
…	........................................................................................................................
		…		…		…
…	………………………………………………………………………………
		…		…		…
…	………………………………………………………………………………
		…		…		…

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

Выберем из системы (1) какое-либо уравнение, например е:

, (2)

и предположим, что коэффициент при в уравнении (2) отличен от нуля, т.е. . Затем представим себе схематизированную алгебраическую операцию перераспределения ролей между зависимой переменной и независимой , т.е. операцию решения уравнения относительно переменной :

, (3)

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

Выясним, как преобразуются элементы таблицы 1 в результате шага обыкновенного жорданова исключения. С этой целью значение из выражения (3) подставим в остальные равенства системы (1) и выполним необходимые преобразования:

. (4)

Обозначим в системе (4)

. (5)

Тогда система (4) запишется в виде

. (6)

Преобразованную систему (3),(6) перепишем в форме жордановой таблицы (таблица 2).

Таблица 2

		…		…
		…		…
…	…………………………………………………………………………….
		…		…
…	……………………………………………………………………………
		…		…

Сопоставляя таблицы 1 и 2, нетрудно заметить, что один шаг обыкновенного жорданова исключения с разрешающим элементом переводит таблицу 1 в новую таблицу 2 по схеме, состоящей из следующих четырех правил:

1) разрешающий элемент заменяется обратной величиной;

2) остальные элементы разрешающей строки делят на разрешающий элемент и меняют знаки;

3) остальные элементы разрешающего столбца делят на разрешающий элемент;

4) прочие элементы вычисляют по формуле (5).

На практике при вычислении элементов по формуле (5) удобно пользоваться правилом прямоугольника. Чтобы выяснить его суть, рассмотрим фрагмент таблицы 1, содержащий элементы, входящие в формулу (5):

………………………………
…		…		…
……………………………….
…		…		…
……………………………….

Они расположены в вершинах воображаемого «прямоугольника». Диагональ этого прямоугольника, на которой расположены разрешающий и преобразуемый элементы, назовем главной, а другую диагональ ─ побочной. Тогда из формулы (5) непосредственно следует, что преобразованный элемент равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленной на разрешающий элемент.

Сформулированного правила следует придерживаться независимо от того, в какой вершине прямоугольника расположен разрешающий элемент.

Из формулы (5) видно, что если в разрешающей строке некоторый элемент , то , т.е. элементы столбца, в котором расположен нулевой элемент разрешающей строки, остаются после шага жорданова исключения без изменения. Аналогично: если в разрешающем столбце есть нулевой элемент , то соответствующая ему строка остается на данном шаге неизменной, так как .

Вместо обыкновенных часто пользуются так называемыми модифицированными жордановыми исключениями, при которых система (1) записывается в форме жордановой таблицы 3, отличающейся от таблицы 1 тем, что переменные в заглавной строке записаны со знаком “минус”.

Таблица 3.

	…
…	………………………..

Можно показать, что один шаг модифицированного жорданова исключения переводиттаблицу 3 в новую таблицу по следующим правилам:

1) разрешающий элемент заменяется обратной величиной;

2) остальные элементы разрешающей строки делят на разрешающий элемент;

3) остальные элементы разрешающего столбца делят на разрешающий элемент и меняют знаки;

4) прочие элементы вычисляют по формуле (5).