Козенко, Галанина Информатика_ч1

2.Решение системы уравнений прямыми методами

2.1.Решение системы уравнений методом Гаусса

Одним из наиболее широко используемых прямых методов является метод последовательного исключения неизвестных, или метод Гаусса. Согласно этому методу, исходная система линейных уравнений (1.7) преобразуется путем последовательного исключения неизвестных в эквивалентную систему уравнений, имеющую так называемый «треугольный» вид.

Последнее уравнение «треугольной» системы должно содержать лишь одно неизвестное (Сm), предпоследнее – два (Сm, Сm-1) и т.д. Решение полученной системы уравнений осуществляется последовательным («снизу вверх») определением Сm из последнего уравнения «треугольной» системы, Сm-1 из предпоследнего и т.д. Применительно к системе уравнений (1.7) преобразование к «треугольному» виду осуществляется за (m – 1) шагов.

Процедура описанного выше преобразования будет следующая.

• На первом шаге выделяется первое уравнение системы (1.7). Это уравнение не преобразуется, и оно объявляется ведущим уравнением.

Затем исключается неизвестное С1 из второго уравнения. Для этого

ведущее уравнение умножается на коэффициент q21 = a21 и вычи- a11

тается из второго уравнения.

В результате получим следующее уравнение:

(a -	a21	a ) C +(a -							a21	a ) C +
									a
21 a			11		1		22			12		2
11								11
+...+(a			-	a21		a	) C	=b		-	a21	b .
											a
	2m			a		1m	m	2				1
			11							11

Очевидно, что коэффициент (a21 -a21 a11) при С1 равен нулю.

a11

Аналогичную процедру можно проделать с третьим уравнением системы (1.7).

Умножая ведущее уравнение на q31 = a31 и вычитая резуль- a11

тат умножения из третьего уравнения, получим эквивалентное уравнение

11

Очевидно, что коэффициент при С1 также равен нулю.

Для исключения С1 из m-го уравнения необходимо умножить веду-

щее уравнение на qm1 = am1 и вычесть результат из m-го уравнения. a11

В результате получим

(a -	a31	a )C +(a -						a31	a )C +
31	a		11		1		32	a		12		2
	11							11
+...+(a			-	a31		a	)C	=b		-	a31		b .
	3m			a		1m	m	3			a	1
			11							11

Вводя новые обозначения для коэффициентов

alk(1) =alk -ql1a1k, k = (2, …, m), l = (2,..., m)

и свободного члена

bl(1) =bl -ql1b1,

можно представить систему уравнений (1.7) в виде

a11C1 +a12 C2 +...+a1m Cm =b1 0C1 +a22(1) C2 +...+a2(1m) Cm =b2(1) 0C1 +a32(1) C2 +...+a33(1) Cm =b3(1)

............................................
0C +a(1)		C ...+ +a(1)		C =b(1) .	(2.1)
1	m2	2	mm	m m

• На втором шаге ведущим объявляется второе уравнение системы (2.1) и исключается неизвестное C2 из уравнений с номерами от третьего до последнего. Исключение неизвестного проводится по схеме, описанной на первом шаге. Для исключения C2 из третьего уравнения системы (2.1) ведущее

уравнение умножается на q32 = a32 и результат умножения a22

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

12

Аналогично первому шагу введем новые обозначения для коэф-

фициентов

alk(2) =alk -ql2 a2k, k = (2, …, m), l = (2,..., m)

и свободного члена

bl(2) =bl -ql2 b2 .

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

a11C1 +a12 C2 +a13 C3 +...+ a1m Cm =b1
0C +a(1) C +a(1) C +...+a(1)						C =b(1)
1	22	2	23 3		2m	m	2
0C + 0C +a(2)				C +...+a(2) C =b(2)
1	2		33	3	3m	m	3
......................................................
0C + 0C		+a(2)		C +...	+a(2)	C	=b(2) .	(2.2)
1	2		m3	3	mm	m	m

Отметим, что неизвестное С1 входит только в первое уравнение,

анеизвестное С2 — в первое и второе уравнения.

•На (m−1) шаге исключается неизвестное Cm-1 из последнего m-го уравнения, и в результате система уравнений принимает окончательный «треугольный» вид.

Определим обобщенные формулы для расчета коэффициентов системы в процессе прямого хода метода Гаусса. На i–м шаге неиз-

вестное Сi исключается из всех уравнений с номерами l, где i + 1 ≤ l ≤ m, при этом ведущее уравнение (с номером i) умножается на

qli =ali(i-1) / aii(i-1) и результат умножения вычитается из l-го уравнения. Новые значения коэффициентов (в уравнении с номером l) при

неизвестных Ck, (i + 1 ≤ k ≤ m) равны

a(i) =a(i-1) -q a(i-1) ,			(2.3)
lk	lk	li ik

новое значение свободного члена

b(i) =b(i-1) -q			b(i-1) .	(2.4)
l	l	li	l

Система уравнений (2.5) эквивалентна исходной системе уравнений (1.7).

13

a11C1 +a12 C2				+a13 C3		+...+a1m Cm =b1
0C	+a(1)	C +a(1) C +...+a(1)					C		=b(1)
1	22		2	23 3		2m	m		2
0C	+ 0C		+a(2)		C +...+a(2) C			=b(2)
1	2			33	3	3m	m		3
0C1	+0C2		+0C3 +...			+amm(m-1) Cm =bm(m-1) .				(2.5)

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

Решение треугольной системы уравнений (2.5) носит название обратного хода метода Гаусса и заключается в последовательном определении всех неизвестных, начиная с последнего Cm. Действительно, из последнего уравнения системы (2.5) сле-

дует, что

Cm =bm(m-1) amm(m-1) .

Значение Cm-1 находится при решении предпоследнего уравнения

a(m-2)	C	+a(m-2) C =b(m-2) .
m-1, m-1 m-1		m-1,m m	m-1

Так как Cm уже определено, то

C	=	(bm(m--12) -am(m--12,m) Cm)			.
			a(m-2)
m-1
			m-1,m-1

Приведенная процедура применяется последовательно ко всем уравнениям, включая и первое, из которого определяется

C1 =(b1 -a12 C2 -...-a1m Cm) .

a11

Обобщенная формула вычисления Ci имеет вид

(bi-1 -ai(,ii-+11) Ci+1	-...-aii,-m1Cm)	.
Ci =			(2.6)
a(i-1)
i,i

В процессе прямого хода метода Гаусса может оказаться, что коэффициент aii(i-1) ведущего уравнения равен нулю. Тогда исключить Сi из остальных уравнений рассмотренным методом нельзя. Однако уравнения системы можно поменять местами и объявить ведущим то уравнение, у которого коэффициент при неизвестном Сi отличен

14

Начало

Прямой ход

Обратный ход

Конец

Рис. 2.1 Обобщенная схема алгоритма (метод Гаусса)

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

определение ведущего элемента.

2.2. Схема алгоритма решения системы линейных уравнений

методом Гаусса

Обобщенная схема алгоритма решения системы уравнений методом последовательного исключения неизвестных представлена на рис. 2.1.

В результате прямого хода система уравнений (1.7) преобразуется в треугольную систему уравнений (2.5). В процессе обратного хода последовательно определяются все неизвестные, начиная с Cm.

Для описания алгоритма введем следующие обозначения: m – порядок системы уравнений;

A – квадратная матрица размером m×m, элементы которой первоначально равны коэффициентам системы уравнений (1.7), а далее, в процессе прямого хода – коэффициентам преобразованных систем (2.2) – (2.5);

С – вектор размера m, являющийся решением системы уравнений (1.7).

На рис. 2.2 представлена схема алгоритма прямого хода метода Гаусса. Переменная i – номер шага исключения, неизвестное Сi исключается из уравнений с номерами l, принимающими значения от (i + 1) до m. Из приведенного выше описания процедуры прямого хода следует, что исключение неизвестного Сi требует преобразования коэффициентов и свободных членов системы

15

Начало

i = 0... m –1

Определение

ведущего элемента в i-м столбце

Перестановка i-й и IM-й строк

l=i+1... m –1

Расчет

коэффциентов l-го уравнения

l

i

Конец

Начало цикла исключения переменной с номером i

Выполнение действий в соответствии со схемой алгоритма (рис. 2.3)

Выполнение действий в соответствии со схемой алгоритма (рис. 2.4) Начало цикла исключения переменной Ci из уравнения с номером l

Выполнение действий в соответствии со схемой алгоритма (рис. 2.5)

Конец цикла по l

Конец цикла по i

Рис.2.2 Схема алгоритма прямого хода метода Гаусса

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

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

На рис.2.3 приведена схема алгоритма поиска ведущего элемента, где l – номер преобразуемого уравнения системы, i + 1 ≤ l ≤ m. Ведущим элементом на i–м шаге исключения принимается максимальный по модулю коэффициент при неизвестном Ci, то есть максимальный по модулю элемент последовательности Aii Ai + 1,i, …, Аm−1,i, Am,i. На схеме алгоритма (рис.2.3) переменная MaxA –

16

Начало

	MaxA = 0	Присваивание переменным MaxA
		и IM начальных значений
	IM = –1
		Начало цикла k перебора и срав-
	k = i…m–1	нения коэффициентов системы
		в столбце с номером i

| aki | >| MaxA |				Нет	Если значение модуля коэффици-
Да					ента больше значения модуля те-
					кущего максимума, то необходимо
MaxA = aki					изменить значения текущего мак-
					симума MaxA и номера IM соответ-
IM=k					ствующей строки
					Конец цикла по k
k
					Проверка условия вырожденности
				Да	матрицы системы
IM= – 1
Нет				Вывод («Матрица
				вырожденная»)
				Аварийное
				завершение
Конец

Рис.2.3 Схема алгоритма определения ведущего элемента

величина этого максимума, а переменная IM – его номер, то есть

MaxA = AIM,i = max | Ali |. i ≤ l ≤ m

Если начальное значение переменной IM не изменилось, то это означает, что для любого k при i ≤ k ≤ m коэффициенты системы Aki = 0, и, следовательно, неизвестное Ci не входит в оставшиеся

17

	Начало
			Нет		В случае «Нет» значение коэффи-
	IM ≠ i				циента Aij является максималь-
Да					ным в столбце i и перестановка не
	j = i...m–1				нужна
					Начало цикла перестановки j–х
	temp = Aij				элементов строк матрицы A с но-
					мерами i и IM
	Aij = AIM,j
	AIM,j = temp
	j
					Конец цикла по j
	temp = Bj
	Bj = BIM				Перестановка правых частей урав-
	BIM = temp				нений с номерами i и IM

Конец

Рис.2.4 Схема алгоритма перестановки уравнений

уравнения системы. В этом случае определитель матрицы А равен нулю, и, как известно, существование бесконечного числа решений или отсутствие последнего зависит от вида правой части системы (1.7) – вектора В. В обоих случаях процедура прямого хода метода Гаусса прекращается (алгоритм завершается «аварийно»), и необходимы другие методы исследования и получения решения (если они существуют).

Замечание. При реализации алгоритма (рис.2.3) на языке С необходимо иметь в виду, что нумерация строк матрицы начинается с нуля, поэтому начальное значение переменной IM должно быть меньше нуля, например, IM = – 1.

После определения ведущего элемента (рис.2.3), необходимо поменять местами уравнения с номерами i и IM (рис. 2.4), что фактически означает перестановку двух строк (с номерами i и IM ) матрицы А и вектора В.

Такая перестановка требует дополнительной переменной (переменная temp) (рис. 2.4) для временного хранения переставляемого значения.

18

Определение множителя Q, на который умножается ведущее уравнение

Коэффициент при неизвестном Ci в уравнении с номером l должен быть равен нулю Начало цикла пересчета коэффициентов при неизвестных Cj в уравнении с номером l

Новое значение элемента Alj (2.3)

Конец цикла по j

Расчет правой части уравнения (2.4)

Начало

Q = Ali/Aii

Aji = 0

j = i + 1...m–1

Alj = Alj–Q×Aij

j

Bl = Bl − Q×Bi

Конец

Рис.2.5 Схема алгоритма расчета коэффициентов уравнений

Исключение неизвестного Сi из уравнения с номером l представлено на рис. 2.5. Напомним, что исключение переменной сводится к определению новых значений элементов l–й строки матрицы А и элемента Вl. Переменная Q – множитель qli, на который умножается ведущее уравнение. Он выбирается не зависящим от индексов l и i, так как необходим только для вычисления коэффициентов l–й строки и хранить постоянно его не нужно.

Если в результате поиска максимального значения MaxA выяснилось, что i = IM, то ведущим является само уравнение с номером i, и перестановка не нужна.

Ali = Ali – Q Aii,

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

Обратный ход метода Гаусса (рис. 2.6) начинается с определения Cm, а затем последовательно определяются неизвестные Ci, i = m – 1, m – 2, …, 1 по формуле (2.6).

19

Начало

Cm–1 = Bm–1/Am–1.m–1

i = n–2...0(–1)

Sum = Bj

j = i+1...n–1

Sum = Sum–Aij×Cj

j

Ci = Sum/Aii

i

Конец

Определение последнего неиз-

вестного Cm-1

Начало цикла с шагом (-1) последовательного определения неизвестных Сi, начиная с Сm−2 и кончая С0 (2.6)

Начальное значение суммы

Начало цикла по j (вычисление значения суммы)

Конец цикла по j

Определение неизвестного Ci

Конец цикла по i

Рис.2.6 Схема алгоритма обратного хода метода Гаусса

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

обратной матрицы

Один из методов решения системы линейных алгебраических уравнений (1.7), записываемой в матричной форме A × C = B, связан

сиспользованием обратной матрицы А−1 [3].

Вэтом случае решение системы уравнений получается в виде

C = А−1 × B,

(2.7)

где А−1 – матрица, определяемая следующим образом.

20