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

Введение

Решение систем линейных алгебраических уравнений (СЛАУ) является одной из основных задач линейной алгебры. Эта задача имеет важное прикладное значение при решении научных и технических проблем. Кроме того, является вспомогательной при реализации многих алгоритмов вычислительной математики, математической физики, обработки результатов эксᴨȇриментальных исследований.

Применяемые на практике численные методы решения СЛАУ делятся на две группы - прямые и итерационные.

В прямых (или точных) методах решение системы получают за конечное число арифметических действий. К ним относятся известное правило Крамера нахождения решения с помощью определителей, метод последовательного исключения неизвестных (метод Гаусса) и его модификации, метод прогонки и другие. Сопоставление различных прямых методов проводится обычно по числу арифметический действий, необходимых для получения решения. Прямые методы являются универсальными и применяются для решения систем до порядка 103. Отметим, что вследствие погрешностей округления при решении задач на ЭВМ прямые методы на самом деле не приводят к точному решению системы.

Итерационные (или приближенные) методы являются бесконечными и находят решение системы как предел при k последовательных приближений x(k), где k - номер итерации. Обычно задается точность и вычисления проводятся до тех пор, пока не будет выполнена оценкаx(k) - x(k-1) < . Число итераций n(), которое необходимо провести для получения заданной точности, для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных методов можно сравнивать по необходимому числу итераций n(). Эти методы особенно предпочтительны для систем с матрицами сᴨȇциального вида - симметричными, трехдиагональными, ленточными и большими разреженными матрицами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретическая часть.

§1. Обыкновенные Жордановы исключения.

Пусть рассматривается система

yi = ai1* x1 + ai2 * x2 + … + ai n * xn , i = 1, … , m (1.1)

из m линейных форм с n независимыми переменными x1, x2, …,xn. Эта система может быть представлена в виде следующей таблицы:

	x1	…	xs	…	xn
y1 =	a11	…	a1 s	…	a1 n
…			…
yr =	a r1	…	a r s	…	a r n	(1.2)
…			…
ym =	a m1	…	a m s	…	a m n

 

Такое табличное представление системы (2.5) позволяет в дальнейшем производить различные действия над системой схематизировано, т.е. осуществлять пересчет коэффициентов таблицы аij по определенному алгоритму, а именно с помощью аппарата жордановых[2] исключений.

Пусть, например, возникла необходимость выразить независимую переменную xs из уравнения

yr = a r1 * x1 + a r2 * x2 + … a rs * xs + … + a r n * xn , (1.3)

где yr является переменной, которая зависит от переменных x1, x2, …, xn, и подставить полученное выражение во все остальные уравнения системы (1.1). Эту операцию можно выполнить по определенной схеме, которая достаточно просто алгоритмизируется.

• Итак, будем называть шагом обыкновенного жорданова исключения, произведенным над таблицей (1.2) с разрешающим элементом a rs ≠ 0 с r-ой разрешающей строкой и s-ым разрешающим столбцом, схематизированную операцию перемены ролями между зависимой переменной yr и независимой xs, т.е. операцию решения уравнения (1.3) относительно xs, подстановки полученного выражения во все остальные уравнения системы (1.1) и записи полученной системы в виде новой таблицы, аналогичной (1.2).

Новая таблица будет иметь вид

	x1	…	yr	…	xn
y1 =	b11	…	a 1 s	…	b1 n
…			…
xs =	- a r1	…	1	…	- a r n	(1.4)
…			…
ym =	b m	…	a m s	…	a m n	,

 

 

где b i j = a i j * a r s - a i s * a r j , (i ≠ r , j ≠ s ) (1.5)

Причем, как видно из (1.4), все элементы таблицы делятся на разрешающий элемент a rs.

Новая таблица (1.4) получена из таблицы (1.2) по следующей схеме (СХЕМА 1):

________________________________________________________________

[2] Жордановы исключения названы по имени известного французского математика Камиля Жордана (1838-1922 гг.), внесший существенный вклад в развитие алгебры, теории функций и топологии.

1) разрешающий элемент  заменяется единицей и делится  на разрешающий элемент;

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

3) остальные элементы  разрешающей (s - ой) строки меняют  свой знак на противоположный  и делятся на разрешающий элемент;

4) все остальные элементы  таблицы вычисляются по формуле (1.5) и делятся на разрешающий  элемент a rs; формула (1.5) иногда называется "правилом прямоугольника", так как схема вычисления элемента bij соответствует вычислению разности произведений элементов, стоящих по основной и побочной диагоналям прямоугольника, образованного в таблице вида (1.2) всеми элементами, вошедшими в формулу (1.5).

Пример 1.1

В системе

y1 = x1 – 2*x2,

y2 = - x1 + x2 +2*x3,

y3 = 2*x1 – x2 – x3

необходимо поменять ролями переменные x3 и y2, т.е. сделать зависимую переменную y2 независимой, а независимую переменную x3 зависимой. Запишем исходную систему в виде жордановой таблицы:

	x1	x2	x3
y1 =	1	- 2	0
y2 =	- 1	1	2
y3 =	2	- 1	- 1

 

Выполнив один шаг обыкновенных жордановых исключений, т.е. заменив переменную x3 на y2 по СХЕМЕ 1, изложенной выше, получим следующую таблицу:

	x1	x2	y2
y1 =	1	- 2	0
x3 =	0,5	- 0,5	0,5
y3 =	1,5	- 0,5	- 0,5

 

Рассмотрим подробнее вычисление последней таблицы, например, коэффициента b31. Так как разрешающим является элемент a23= 2, то b31 = (a 31 * a 23 - a 21 * a 33) : a 23 = (2 * 2 – ( - 1)* ( - 1) ) : 2 = 3/2 = 1,5 , т.е. была реализована схема:

 

 

 

 

 

§2. Модифицированные жордановы исключения.

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

Перепишем систему (1.1) в виде эквивалентной ей системы:

yi = -ai1*(-x1) - ai2 *(- x2)- … - ai n *(- xn) , i = 1, … , m.

Составим по полученной системе таблицу, учитывая минус при переменных хj наверху таблицы:

	- x1	…	- xs	…	- xn
y1 =	a11	…	a1 s	…	a 1 n
…			…
yr =	a r1	…	a r s	…	a r n
…			…
ym =	am1	…	a m s	…	a m n	,

 

Один шаг модифицированного жорданова исключения с разрешающим элементом ars означает переход к новой таблице:

	- x1	…	- yr	…	- xn
y1 =	b11	…	b1 s	…	b 1 n
…			…
xs =	b r1	…	1	…	b r n	: α r s
…			…
ym =	bm1	…	b m s	…	b m n

 

Эта таблица формируется по схеме 2, которая очень напоминает схему обыкновенных жордановых исключений, в ней меняются только 2 и 3 пункты, а именно:

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

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

Пример 2.1

Систему

y1 = 2x1 – x2 +3x3,

y2 = - x1 + 4x2 -2*x3,

y3 = 5*x1 + 2x2 – 4x3

запишем в виде таблицы

	-x1	-x2	-x3
y1 =	-2	1	- 3
y2 =	1	-4	2
y3 =	-5	- 2	4

 

Произведем один шаг модифицированного жорданова исключения с разрешающими второй строкой и третьим столбцом. Получим

	- x1	- x2	-y2
y1 =	-0,5	- 5	1,5
x3 =	0,5	- 2	0,5
y3 =	- 7	6	- 2

 

что означает, что мы получили новую систему в виде:

y1 = 0,5x1 +5 x2 - 1,5 y2,

x3 = - 0,5x1 + 2x2 -0,5* y2,

y3 = 7*x1 - 6x2 + 2 y2.

Табличное представление задачи ЛП

Рассмотрим еще раз каноническую форму ЗЛП:

	Z = c1x1 + c2 x2 + … + c n xn → max
	ai1* x1 + ai2 * x2 + … + ai n * xn + yi = bi , i = 1, … , m
	xj ≥ 0, j = 1, ... , n
	yi ≥ 0, i = 1, ... , m.

 

Очевидно, систему функциональных ограничений

ai1* x1 + ai2 * x2 + … + ai n * xn + yi = bi , i = 1, … ,m

можно переписать в виде (это удобно для построения симплекс-таблицы):

yi = -ai1* x1 -…- ai n * xn + bj = ai1* (-x1) -… - ai n * (-xn) + bj, i = 1,…, m

 

 

 

 

 

 

§3.  Базисные решения систем линейных уравнений.

Из бесконечного множества решений неопределенной системы линейных алгебраических уравнений выделяют так называемые базисные решения. Базисным решением системы называется всякое ее решение, в котором свободные переменные равны нулю.

Каждому набору из r базисных неизвестных (r – ранг матрицы системы) отвечает только одно базисное решение. При этом некоторым наборам из r разных базисных неизвестных может соответствовать одно и то же базисное решение.

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

Число всех базисных решений конечно и не превосходит числа Сnr, которое  вычисляется по формуле

Базисное решение, у которого хотя бы одно из базисных неизвестных равно нулю, называется вырожденным базисным решением. Если у базисного решения все базисные неизвестные отличны от нуля, то решение называется невырожденным.

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

Базисные неотрицательные решения системы называются опорными решениями. Такие решения играют важную роль в линейном программировании – теории нахождения экстремумов линейной функции многих переменных при наличии системы ограничений в виде равенств и неравенств.

Число опорных решений не превосходит числа базисных решений этой системы.

В линейном программировании существенную роль играют системы с базисом и канонические системы уравнений.

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

Примером системы с базисом является система вида

 

                                                             (1.1)

 

Ранг матрицы А этой системы равен r. Угловой минор r-го порядка этой матрицы является ранговым минором: