Вычислительная Математика / lecture_5

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

1

Система линейных алгебраических уравнений (СЛАУ).

В общем виде СЛАУ можно записать в следующем виде

a11x1 + a12x2 + .......		+a1mxm = b1
.a21x1 +	a22x2 + .......	+a2mxm = b2
.........	.......... ....... ...........		....
an1x1 +	an2x2 + .......	+anmxm = bn

Совокупность коэффициентов системы можно представить в виде матрицы:

=	a	11	a	12	a			a
					13			1m
A	=[A]= a21		a22		a23			a2m		, i=1,2,3,…,n; j=1,2,3,….,m
			an2		an3
	an1							anm
Совокупность неизвестных системы – в виде вектора столбца:
							x
					→	=	1
					x		x2	, j=1,2,3,…,m
							...
							xm

Совокупность свободных членов – в виде и вектора столбца:

b1

→ b

b = 2 , i=1,2,3,…,n...

bn

Используя выше приведенные определения, запишем СЛАУ в матричном виде:

= → →

A x = b

Решить СЛАУ значить найти такие значения вектора

			x*1
→
x	*	=	x*2		,
			...
			x*m

подстановка которого в систему, обращает каждое уравнение этой системы в тождество.

Классификация СЛАУ

1.Если число уравнений больше чем число неизвестных, т.е. n>m, то СЛАУ называется переобусловленой

2.Если число уравнений меньше чем число неизвестных, т.е. n<m, то СЛАУ называется недообусловленой

3.Если число уравнений равно числу неизвестных, т.е. n=m, то СЛАУ называется нормальной

→→

4.Если вектор свободных членов равен нулю b = 0 , то СЛАУ называется однородной

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

2

→ →

5.Если вектор свободных членов не равен нулю b ≠ 0 , то СЛАУ называется неоднородной

6.Если система, имеет хотя бы одно решение, она называется совместной. Система, не имеющая решений, называется несовместной.

7.Совместная система, имеющая единственное решение, называется определен-

ной, а имеющая бесчисленное множество решений, называется неопределенной.

Очевидно, что однородная система всегда совместна, так как имеет хотя бы од-

→ →

но решение x = 0 , которое называется тривиальным.

примеры графической интерпретации:

2x1 + x2 = 3 x2 = 3 -2x1 система совместная и определенная. 2x1+ 2x2 = 4 x2 = 2 - x1

	4
	3
	2
	1
	0
-1	0	1	2	3	4
	-1

2x1 + x2 = 3			x2 = 3 - 2x1		система совместная и неопределенная.
4x1+ 2x2 = 6 x2 = 3 - 2x1
	4
	3
	2
	1
	0
-1	0	1	2	3	4
	-1
2x1 + x2 = 3			x2 = 3 - 2x1		система несовместная.
4x1+ 2x2 = 4 x2 = 2 - 2x1
	4

3

2

1

0

-1

0

1

2

3

4

-1

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

3

Методы решения СЛАУ

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

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

Итерационные методы дают некоторую последовательность приближений к решению. Пределом этой последовательности является решение системы уравнений. Решение, возможно, определить лишь с некоторой, как правило, заданной степенью точности ε. Количество итераций для достижения требуемой точности решения определяется величиной ε, выбором начального приближения и видом системы уравнений.

Точные методы Метод обратной матрицы

= → → =−1 = →	=−1 → = →	=−1 → →	=−1 →
A x = b A A x	= A b E x	= A b x* = A b

	=		→	2.00
A			b	= 1.00
				2.00

1.00	1.00		4.00		=−1			0.50	0.20	−0.10
−1.50	−0.50				A	=		0.50	−0.60
			−1.00							−0.20
2.00	4.00		8.00						0.20	0.40
							−0.50

→				0.50	0.20	−0.10				4.00			1.00
x	*	=		0.50	−0.60							=
						−0.20			−1.00				1.00
					0.20	0.40				8.00
			−0.50										1.00

4.1. Метод Гаусса

Требуется решить систему n линейных уравнений с n неизвестными.

= → →

A x = b

Метод Гаусса включает два этапа.

Первый этап (прямой ход) заключается в последовательном исключении неизвестных из системы уравнений и состоит из n–1 шага. На первом шаге с помощью первого уравнения исключается x1 из всех последующих уравнений начиная со второго, на втором шаге с помощью второго уравнения исключается x2 из последующих уравнений начиная с третьего и т.д. Последним исключается xn-1 из последнего n-го уравнения так, что последнее уравнение будет содержать только одно неизвестное xn. Такое последовательное исключение неизвестных равносильно приведению матрицы коэффициентов к треугольному виду. Строка, с помощью которой ис-

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

4

ключаются неизвестные, называется ведущей строкой, а диагональный элемент в этой строке – ведущим элементом.

a11 x1

+

a12 x2

+

a13 x3

+ ...

+

a1n xn

= b1

a

21

x

+

a

22

x

2

+

a

23

x

3

+ ...

+

a

2n

x

n

= b

2

1

+

a32 x2

+

a33 x3

+ ...

+

a3n xn

= b3

a31 x1

...

...

...

...

...

...

a

n1

x

+

a

n2

x

2

+

a

n3

x

3

+ ...

+

a

nn

x

n

= b

n

1

a11 x1 + a12 x2

+ a13 x3

+

... + a1n xn

= b1

0

+

(1)

x2

+

(1)

x3

+

...

+

a2n

(1)

xn

(1)

a22

a23

= b2

0

+

0

+

a33 x3(2)

+

...

+

a3n

(2) xn

= b3(2)

...

...

...

...

...

...

(n−1)

(n−1)

0

+

0

+

0

+

... +

ann

xn

= bn

Второй этап (обратный ход) заключается в последовательном вычислении искомых неизвестных и состоит из n шагов. Решая последнее уравнение, находим неизвестное xn. Далее используя это значение из предыдущего уравнения вычисляем неизвестное xn-1 и т.д. Последним найдем неизвестное x1 из первого уравнения.

=

Матрица, содержащая помимо коэффициентов при неизвестных A столбец

→

свободных членов b , называется расширенной

=		=		→
C = A				b .

Алгоритм.

1.

=

размерностью n на n+1, приписав, справа к

Строим расширенную матрицу С

=

→

=

=

→

матрицы A вектор b .

С= A

b

т.е. ci,j=ai,j , ci,n+1=bi , где i=1,2,3,…,n

j=1,2,3,…,n

c

c

c

....

c

c

11

12

13

1n

1,n+1

=

=

→

c21

c22

c23 ....

c2n

c2,n+1

= c31

c32

c33 ....

c3n

c3,n+1

. Задаем номер ведущей строки k = 1

С= A

b

...

.... .... .... .... ....

cn2

cn3 ....

cnn

cn,n+1

cn1

2.Преобразуем все строки, расположенные ниже k-ой так, чтобы элементы cik=0, для этого вычисляем множитель β=-сi,k/ck,k и каждую i-ую строку заменяем

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич	5
суммой i–ой и k-ой умноженной на β, т.е. ci,j=ci,j+β*ck,j	где i =
k+1,k+2,k+3,….,n и j = k,k+1,k+2,…,n+1

3.Проверяем k = n-1 если нет, то выбираем новую ведущую строку k=k+1 и переходим на пункт 2, иначе выполняем пункт 4.

4.Обратный ход. Из последнего n-ого уравнения определяем последнее n-ое не-

известное. xn=cn,n+1/cn,n

Последовательно, из предыдущих уравнений начиная с i=n-1, вычисляем соответствующие неизвестные xi. Последним, определяется первое неизвестное из пер-

		n
		(ci,n−1 − ∑ci, j * x j)
	вого уравнение. xi =	j=i+1	i = n-1, n-2, n-3,…,1
		ci,i

Блок-схема метода Гаусса

	Начало
		xi :=	ci,n+1	−s
	=		cii
	n,C ,

i:=n–1 шаг –1 до n–1

k:=1 шаг 1 до n–1

→

x i :=

c i , n +1 − s

x

c ii

Конец

i:=k+1 шаг 1 до n

s:=0

β := −

c ik

c kk

j=i+1 шаг 1 до n

j:=k+1 шаг 1 до n+1

s = s + c ij x j

c ij = c ij

+ β c kj

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

6

Пример. Решить СЛАУ методом Гаусса.

−7.000		−2.000	2.000		x			−7.000
	1.000	−7.000			1		=
			−3.000		x2			−7.000
		−1.000
−3.000			−5.000		x3			−5.000

Первый этап. Строим расширенную матрицу и преобразуем её к ступенчатому виду.

−7.000		− 2.000	2.000				−7.000
	1.000	−7.000	−3.000
							−7.000
		−1.000	−5.000
−3.000							−5.000
−7.000		−2.000	2.000				−7.000
	0.000	−7.286	−2.714
					−8.000
		−1.000	−5.000
−3.000					−5.000
−7.000		−2.000	2.000				−7.000
	0.000	−7.286	−2.714
							−8.000
	0.000	−0.143	−5.857
							−2.000
−7.000		−2.000	2.000		−7.000
	0.000	−7.286	−2.714
					−8.000
	0.000	0.000	−5.804
					−1.843

Второй этап. Вычисляем неизвестные.

x3 = −−5.8041.843 =0.318

x2 = (−8 −(−2.714 0.318)) =0.980 −7.286

x1 = (−7 −(−2 0.980 +2 0.318)) =0.811

−7

0.811

→ =

ответ x 0.9800.318

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

7

Модификации метода Гаусса

Для уменьшения погрешности вычислений при реализации алгоритма метода Гаусса используют его модификации, такие как метод Гаусса с частичным или полным выбором «ведущего» элемента. В модификации с частичным выбором на k-м шаге прямого хода в качестве «ведущего» выбирается наибольший по модулю элемент из неприведённой части k-го столбца матрицы, т.е.

ckk = max cik , i = k,k +1,k +2,...,n

i

Строка, содержащая этот элемент, переставляется с k-й строкой расширенной матрицы.

При полном выборе в качестве «ведущего» элемента выбирается максимальный по модулю элемент из всей неприведённой части матрицы коэффициентов системы:

ckk = max cij , i, j = k,k +1,k +2,...,n

i, j

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

Пример. Решить СЛАУ методом Гаусса с частичным выбором.

	1.000	6.000	−1.000		x				0.000
	2.000	1.000			1		=
			5.000		x2				10.000
	5.000	−1.000
			2.000		x3			−10.000

Первый этап. Строим расширенную матрицу и преобразуем её к ступенчатому виду.

1	6	−1		0
	1	5
2				10
	−1	2		−10
5

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

5	−1 2			−10		5 −1		2		−10
	1	5		10			1.4	4.2
2						0				14
	5	−1		0			6.2	−1.4		2
1						0

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

8

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

5	−1	2		−10		5	−1	2		−10
	6.2	−1.4		2			1.4	4.2
0						0				14
0	1.4	4.2		14		0	0	4.516
										13.548

Второй этап. Вычисляем неизвестные.

		x3	=	13.548			=3
			4.516
x2	=	(2 +1.4 3)			=			6.2	=1
							6.2
			6.2

x = −10 −((−1) 1+ 2 3) = −3
1	5
	→		−3
		=		1
	ответ x
				3

Обусловленность систем линейных алгебраических уравнений.

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

Исходную систему уравнений

		= →	→
		A x	= b
	→
с учетом погрешности в векторе b можно записать в виде:
= →	→	→	→	→		→
A x* = b		+∆ b , где x* = x			+∆ x .
Получаемое решение, отличающееся от точного						→	→
						x на величину ошибки	∆ x .

→

Заменив, x* получим

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

9

= → → → →

= → →

=

→ →

A (x +∆ x ) = b +∆ b или A x

− b

+A ∆ x

= ∆ b и тогда

=

→

→

A ∆ x

= ∆ b отсюда можно выразить абсолютную погрешность решения

→

=−1

→

∆ x

= A

∆ b

норма этой погрешности определяется соотношением:

→

=−1

→

→

=−1

→

|| ∆ x || =|| A

∆ b ||

или || ∆ x || ≤|| A

|| || ∆ b ||

Определим относительную погрешность

→

=−1

→

|| ∆ x || ≤ || A || || ∆ b ||

→

→

|| x ||

|| x ||

=

→

→

=

→

→

из исходной системы A

x

= b

получим || A ||

|| x ||≥|| b ||

=

далее определим

1

≤

|| A ||

и подставим в определение относительной погрешно-

→

→

сти получим:

|| x ||

|| b ||

→

=−1

=

→

|| ∆ x ||

|| ∆ b ||

→

≤|| A

|| || A ||

→

|| x ||

|| b ||

Вводим понятие числа обусловленности:

=

= −1

=

→

→

|| ∆ x ||

|| ∆ b ||

Коб.=Cond( A )=|| A

|| || A ||

и тогда

≤ Kоб

.

→

→

|| x ||

|| b ||

Следует иметь ввиду, что мы определяем предельную относительную погрешность, реальная может быть и меньше.

Пример.

Определить обусловленность систем уравнений:

1)	−x1 + 2x2 =1							2)	− x1 + 2x2 =1				,
	2x −	x	2	=1					−10x	+ 21x	2	=11
	1								1
				→	0.1		,		→
			при ∆ b		=			|| ∆b || =0.1
					0.0

(С) ИиКМ РХТУ январь 2006г. Калинкин Владимир Николаевич

10

Без учета погрешности точное решение одно и тоже для обеих систем:

→

1.00

x =

1.00

=

−1

2

→

1

=

0.33

0.67

для 1-ой системы A =

, b =

, A−1 =

2

−1

1

0.67

0.33

=

=

|| A−1 ||=1.05

cond=3.33

|| A ||= (−1)2 +22 + 22 +(−1)2 =3.16 ,

→

12 +12 =1.41

|| b ||=

→

0.1

|| δ b ||=

=0.071

1.41

→

=0.24

|| δ x ||=3.33* 0.071

=

−1

2

→

1

=−1

−21

2

для 2-ой системы A =

, b

=

, A

=

−10

21

11

−10

1

=

=

|| A−1 ||= 23.37

cond=546.0

|| A ||= (−1)2 + 22 +(−10)2 +212 = 23.37 ,

→

12 +112 =11.05

|| b ||=

→

0.1

|| δ b ||=

=0.0091

11.05

→

= 4.94

|| δ x ||=546 0.0091

Метод простых итераций

Алгоритм метода состоит из трёх этапов.

Первый этап. Приведение СЛАУ к итерационному виду, для этого разрешим каждое уравнение относительно соответствующего неизвестного: