 |
Метод модифицированных жордановых исключений
|
|
|
|
Данный метод аналогичен методу обыкновенных жордановых исключений. Только независимые переменные записывают в верхнюю заглавную строку жордановой таблицы с противоположным знаком. При этом несколько изменяется алгоритм пересчета коэффициентов системы. Пусть, по-прежнему, дана система линейных равенств:
a 11 x 1 + a 12 x 2 +…+ a 1 jxj + … + a 1 sxs + … + a 1 nxn + y 1 = 0,
……………………………………………………………...
ai 1 x 1 + ai 2 x 2 +…+ aijxj + …+ aisxs + … + ainxn + yi = 0,
………………………………………………………………
ar 1 x 1 + ar 2 x 2 + …+ arjxj +… + arsxs + … + arn xn + yr = 0, (1.6)
………………………………………………………………
am 1 x 1 + am 2 x 2 +…+ amjxj + … + amsxs + …+ amnxn + ym = 0.
Перенесем все слагаемые, содержащие xj в правую часть равенств. Получим систему:
y 1 = a 11(– x 1) + a 12(– x 2) +…+ a 1 j (– xj) + … + a 1 s (– xs) + … + a 1 n (– xn),
…………………………………………………………………..……....
yi = ai 1(– x 1) + ai 2(– x 2) +…+ aij (– xj) + …+ ais (– xs) + … + ain (– xn),
………………………………………………………………………..…
yr = ar 1(– x 1) + ar 2(– x 2) + …+ arj (– xj) +… + ars (– xs) + … + arn (– xn), (1.7)
………………………………………………….…………………….…
ym = am 1(– x 1)1 + am 2(– x 2) +…+ amj (– xj) + … + ams (– xs) + …+ amn (– xn).
Из произвольного (r -го) равенства выразим произвольную переменную xs, и подставим во все остальные равенства. Коэффициент ars при
(– xs) должен быть отличен от нуля. Число ars по-прежнему называется разрешающим элементом. Мы получим следующую систему:
y 1 = b 11(– x 1) + b 12(– x 2) +…+ b 1 j (– xj) + … + b 1 s (– yr) + … + b 1 n (– xn),
………………………………………………………………..………....
yi = bi 1(– x 1) + bi 2(– x 2) +…+ bij (– xj) + …+ bis (– yr) + … + bin (– xn),
………………………………………………………………………..…
xs = br 1(– x 1) + br 2(– x 2) + …+ brj (– xj) +… + brs (– yr) + … + brn (– xn), (1.8)
…………………………………………………………………..………
ym = bm 1(– x 1)1 + bm 2(– x 2) +…+ bmj (– xj) + … + bms (– yr) + …+ bmn (– xn).
|
|
|
Вычислим коэффициенты полученной системы (1.8) через коэффициенты исходной системы (1.7). Начнем с r -го уравнения, которое после выражения переменной xs через остальные переменные, примет вид:
(1.9)
Таким образом, новые коэффициенты r -го уравнения вычисляются по следующим формулам:
(1.10)
Вычислим теперь новые коэффициенты bij произвольного уравнения (i ¹ r). Для этого подставим выраженную в (1.3) переменную xs в i -е уравнение системы (1.1):
После приведения подобных членов получим:
(1.11)
Из равенства (1.11) получим формулы, по которым вычисляются коэффициенты системы произвольного уравнения системы (1.8), за исключением r -го уравнения:
(1.12)
Преобразования систем линейных уравнений методом модифицированных жордановых исключений оформляется в виде таблиц, аналогичных таблицам метода обыкновенных жордановых исключений. Только переменные, находящиеся в верхней заглавной строке таблицы, берутся со знаком минус. Таким образом, задаче (1.7) ставится в соответствие следующая жорданова таблица:
| – x 1 | – x 2 | … | – xj | … | – xs | … | – xn | |
| y 1 | a 11 | a 12 | a 1 j | a 1 s | a 1 n | |||
| ………………………………………………………………….. | ||||||||
| yi | ai 1 | ai 2 | aij | ais | ain | |||
| ………………………………………………………………….. | ||||||||
| yr | ar 1 | ar 2 | arj | ars | arn | |||
| …………………………………………………………………. | ||||||||
| yn | am 1 | am 2 | amj | ams | amn |
Табл. 1.5.
После совершения одного шага, в результате которого независимая переменная xs заменяется переменной yr, мы приходим к следующей таблице:
| – x 1 | – x 2 | … | – xj | … | – yr | … | – xn | |
| y 1 | b 11 | b 12 | b 1 j | b 1 s | b 1 n | |||
| ………………………………………………………………….. | ||||||||
| yi | bi 1 | bi 2 | bij | bis | bin | |||
| ………………………………………………………………….. | ||||||||
| xs | br 1 | br 2 | brj | brs | brn | |||
| …………………………………………………………………. | ||||||||
| yn | bm 1 | bm 2 | bmj | bms | bmn |
Табл. 1.6.
|
|
|
Заметим, что в левый заглавный столбец переменная xs попадает со знаком плюс, а в верхнюю заглавную строку переменная yr попадает со знаком минус. Разрешающий элемент ars мы по-прежнему будем выделять жирным шрифтом.
Алгоритм пересчета коэффициентов при переходе от таблицы (1.5) к таблице (1.6), вытекающий из формул (1.10) и (1.12), почти не отличается от соответствующего алгоритма метода обыкновенных жордановых исключений. Отличие состоит только в изменении знаков пересчитываемых коэффициентов разрешающей строки и разрешающего столбца:
1. Разрешающий элемент заменяется обратным числом: 
2. Остальные элементы разрешающей строки делятся на разрешающий элемент: 
3. Остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный: 
4. Элементы, не попавшие в разрешающую строку и разрешающий столбец, пересчитываются по формулам: 
Последнюю формулу, так же как и раньше, можно запоминать, используя диаграмму:
| aij | ais | ||
| + | – | ||
| arj | ars |
Пример 1.2. Пусть дана система линейных равенств:
y 1 = 3 x 1 – 2 x 2 – 4 x 3 + 2 x 4,
y 2 = 3 x 1 – 9 x 2 + 2 x 3 – 8 x 4,
y 3 = –3 x 1 + 7 x 2 – 5 x 3 + 6 x 4.
Применяя метод модифицированных жордановых исключений, запишем данную систему в виде следующей жордановой таблицы:
| – x 1 | – x 2 | – x 3 | – x 4 | |
| y 1 | –3 | –2 | ||
| y 2 | –3 | –2 | ||
| y 3 | –7 | –6 |
Табл. 1.7.
Выберем в качестве разрешающего элемента число –2, находящееся на пересечении 2-ой строки и 3-го столбца. При этом переменная x 3 меняется с переменной y 2 местами, и мы получим новую таблицу:
| – x 1 | – x 2 | – y 2 | – x 4 | |
| y 1 | -9 | |||
| x 3 | 1,5 | –4,5 | –0,5 | –4 |
| y 3 | –4,5 | 15,5 | 2,5 |
Табл. 1.8.
Элементы таблицы 1.8 вычислялись по описанному выше алгоритму:
1. Разрешающий элемент заменился на обратное число:
2. Остальные элементы разрешающей строки вычислялись по формуле:
3. Остальные элементы разрешающего столбца вычислялись по формуле:
4. Остальные коэффициенты системы пересчитывались по формулам:
|
|
|
В заключение первой главы отметим, что, несмотря на похожесть двух описанных выше методов, оба они находят свое применение в различных разделах математики. Так, в линейной алгебре гораздо чаще используется метод обыкновенных жордановых исключений как менее громоздкий по сравнению с методом модифицированных жордановых исключений. Метод модифицированных жордановых исключений был специально разработан для решения задач математического программирования. Дело в том, что метод модифицированных жордановых исключений обладает одним замечательным свойством: на каждом шаге элементы разрешающего столбца меняют свои знаки, а разрешающей строки – нет (за исключением разрешающего элемента). На использовании этого свойства и построен так называемый метод Штифеля, описанный в третьей главе настоящего пособия.
ГЛАВА II
ПРИМЕНЕНИЕ МЕТОДА ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ
В ЛИНЕЙНОЙ АЛГЕБРЕ
|
|
|
