Лекции - 2004 / Лекции / lecture_6_1

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

1

Лекция –6

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

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

a11 x1 +

a12 x2

+ .......

+ a1m xm =

b1

.a21 x1 +

a22 x2

+ .......

+ a2m xm =

b2

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

....

an1 x1 +

an2 x2

+ .......

+ anm xm

=

bn

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

=

a

a

a

a

11

12

13

1m

A = [A]

= a21

a22

a23

a2m

, где . i=1,2,3,…,n;

j=1,2,3,….,m

an2

an3

an1

anm

x

_

→

1

совокупность xj в виде вектора столбца неизвестных X

= x

= x2

, j=1,2,3,…,m , а совокупность

...

xm

	b
_ →	1
bi в виде и вектора столбца свободных членов (правых частей) B =b	= b2		, i=1,2,3,…,n
	...
	bn

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

= _ _	= →	→
A X = B или A x		= b	1
		x
		*
	_	→ *
Решить СЛАУ значить найти такие значения вектора X * = x* = x 2					при подстановки которого
		...
		x*m

в систему обращает каждое уравнение этой системы в тождество. Классификация СЛАУ

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

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

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

→→

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

→→

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

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

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

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

2

→ →

Очевидно, что однородная система всегда совместна, так как имеет хотя бы одно решение 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

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

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

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

3

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

Точные методы

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

= → →

=

= →

=

→

= →

=

→

→

=

→

A x

= b A−1

A x = A−1

b E x = A−1

b x* = A−1

b

=

→

2.00

1.00

1.00

4.00

=

0.50

0.20

−0.10

A

b

=

1.00

−1.50

−0.50

−1.00

A−1

=

0.50

−0.60

−0.20

2.00

4.00

0.20

2.00

8.00

−0.50

0.40

−0.10

→

0.50

0.20

4.00

1.00

x

*

0.50

−0.60

=

−0.20

* −1.00

= 1.00

0.20

0.40

−0.50

8.00

1.00

Метод Гаусса

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

Метод Гаусса состоит из двух этапов.

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

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

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

1

2

* x1

+

a32

* x2

+

a33

* x3

+ ....

+

a3n * xn

= b3

B

a31

....

....

....

....

....

a

n1

* x

+

a

n2

* x

2

+

a

n3

* x

3

+ ....

+

a

nn

* x

n

= b

n

1

a

* x

+

a

* x

+

a

* x

+

........

+

a

* x

= b

11

1

+

12

(1)

2

+

13

(1)

3

+

........

+

1n

(1)

n

1

(1)

0

a22

* x2

a23

* x3

a2n

* xn

= b2

0

+

0

+

a33

* x3

(2)

+

........

+

a3n (2) * xn

= b3

(2)

...........

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

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

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

0

+

0

+

0

+

........

+

a

nn

(n−1) * x

n

= b

(n−1)

n

..

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

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

4

Алгоритм.

1.

=

=

Строим расширенную матрицу С размерностью n на n+1, приписав, справа к матрицы A

→

=

=

→

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

j=1,2,3,…,n

вектор b . С

= A

b

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 =

...

.... ....

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

c

c

c

....

c

c

n,n+1

n1

n2

n3

nn

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

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

(ci,n−1 − ∑n

ci, j * x j )

xi

=

j=i+1

i = n-1, n-2, n-3,…,1

ci,i

начало

ввод n,[A],[B]

xn=cn,n+1/cn,n

i=n-1 шаг -1 до 1

формирование

матрицы [C]

k=1 шаг 1 до n-1

s:=0

Вывод

[X]

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

xi=(ci,n+1-s)/cii

конец

β:=-cik/ckk

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

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

cij=cij+β*ckj

s:=s+ail*blj

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

5

Option Explicit

Option Base 1

Sub Gauss()

Dim n%, c!(), x!()

Dim i%, j%, k%, bet!, s!

n = Cells(1, 1): ReDim c(n, n + 1), x(n)

For i = 1 To n: For j = 1 To n + 1: c(i, j) = Cells(i + 1, j): Next j: Next i For k = 1 To n - 1

For i = k + 1 To n

bet = -c(i, k) / c(k, k) For j = k To n + 1

c(i, j) = c(i, j) + bet * c(k, j) Next j

Next i Next k

x(n) = c(n, n + 1) / c(n, n) For i = n - 1 To 1 Step -1

s = 0

For j = i + 1 To n

s = s + c(i, j) * x(j) Next j

x(i) = (c(i, n + 1) - s) / c(i, i) Next i

For j = 1 To n: Cells(n + 3, j) = x(j): Next j End Sub

Пример:

2	1	1	4	k=1 i=2,3	2	1	1	4	k=2	i=3	2	1	1	4
1	-1.5	-0.5	-1	-0.5	0	-2	-1	-3			0	-2	-1	-3
2	2	4	8	-1	0	1	3	4	+0.5		0	0	2.5	2.5
	x3= 1			x2= 1		x1=	1

Реально вычисления проводятся на ЭВМ с ограниченной разрядной сеткой, поэтому точность решения определяется суммарной погрешностью округления на промежуточных шагах вычисления. Погрешность результата, в основном, определяется значением ведущего элемента на каждом шаге прямого и обратного хода. Решить СЛАУ с учетом 4-х значащих цифр.

		→	−1
	Точное решение x		=
			1
	-1.000*10-2 6.000*100				6.010*100		β=-2.500*100/(-1.000*10-2)= 2.500*102
	2.500*100	5.000*100			2.500*100
	c22=c22 + β*c12							0.005*103
								+
	c22=5.000*100 + 2.500*102*6.000*100=5.000*100 + 1.500*103;							1.500 *103
								−−−−−−−−−−−
	c23=c23 + β*c13							1.505*103
								0.002 *103
								+
	c23=2.500*100 + 2.500*102*6.010*100=2.500*100 +1.5025*103							1.502 *103
								−−−−−−−−−−−
								1.504 *103

	(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич						6
	-1.000*10-2	6.000*100		6.010*100
	0	1.505*103		1.504*103

1.505*103*X2=1.504*103; X2=9.9933*10-1; ; X2=9.993*10-1 X1=(6.010*100-6.000*100*9.993*10-1)/(-1.000*102)=(6.010*100-5.9958*100)/(-1.000*10-2)= (6.010*100-5.995*100)/(-1.000*10-2)=1.5*10-2/(-1.000*10-2)=-1.5*100

				→	=			0		не является точным.
	Полученное решение системы x					−1.500 *10
						9.993*10−1
	Переставим уравнения местами.
							β=-(-1.000*10-2/(2.500*100)= 4.000*10-3
	2.500*100	5.000*100		2.500*100
	-1.000*10-2	6.000*100		6.010*100
											6.000 *100
											+
	c22=6.000*100 + 4.000*10-3*5.000*100=6.000*100+2.000*10-2;										0.020 *100
											−−−−−−−−−−−
	c23=c23 + β*c13										6.020 *100
											6.010 *100
											+
	c23=6.010*100 + 4.000*10-3 2.500*100=6.010*100 + 1.000*10-2;										0.010 *100
											−−−−−−−−−−−
											6.020 *100
	2.500*100	5.000*100		2.500*100
	0.000*100	6.020*100		6.020*100
	6.020*100*X2=6.020*100; X2=1.000*100;
	X1=(2.500*100-5.000*100*1.000*100)/ 2.500*100 = -1.000*100
				→	=			0		является точным.
	Полученное решение системы x					−1.000 *10
							1.000 *100

Приведенный пример показывает, что на каждом шаге преобразования следует подбирать ведущий элемент ckk. Для этого используются модификации метода Гаусса. В модификации с частичным выбором на k-ом шаге прямого хода в качестве ведущего выбирается наибольший по модулю элемент из неприведенной части k-ого столбца, т.е. ckk=maxi|cik|, i=k,k+1,k+2,…,n

И строка, содержащая этот элемент, переставляется с k-ой строкой расширенной матрицы. При полном выборе в качестве ведущего элемента выбирается максимальный по модулю элемент из всей неприведенной части матрицы коэффициентов системы, ckk=maxij|cij|, i,j=k,k+1,k+2,…,n Для этого осуществляется необходимая перестановка как строк, так и столбцов в расширенной матрице коэффициентов. При этом следует помнить, что перестановка столбцов равносильна переименованию неизвестных.

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

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

					= →	→				→
Исходную систему уравнений A* x						= b с учетом погрешности в векторе b можно записать в виде.
= →	→	→	→	→	→						→
A* x* = b		+ ∆b , где x* = x			+ ∆ x - получаемое решение, отличающееся от точного x на величину
		→		→		= → →	→	→	= → →	= →	→
ошибки ∆ x . Заменив x* получим A * ( x ∆ x ) =							b + ∆	b	или A* x −b	+ A∆ x	= ∆b и тогда

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

7

= →

→

→

=

→

A∆ x

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

= A−1 ∆b норма этой

→

=

→

→

=

→

погрешности определяется соотношением || ∆ x || =|| A−1 ∆b || или || ∆ x || ≤||

A−1

|| * || ∆b ||

→

=

→

|| ∆ x

||

|| A

−1

|| * ||

∆b

||

= → →

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

≤

из исходной системы A* x = b

||

→

→

x ||

|| x ||

=

=

→

→

1

||

A ||

получим || A || * || x ||≥|| b || далее определим

=≤

и подставим в определение

→

→

|| x ||

||

b ||

	→
относительной погрешности получим	|| ∆ x ||
	→
	|| x ||

=			→
		=	|| ∆b ||
≤|| A	−1	|| * || A || *		.
			→

|| b ||

=

=

=

Вводим понятие числа обусловленности Коб.=Cond( A )=|| A−1

|| * || A || и тогда

→

→

|| ∆ x ||

≤ Kоб *

|| ∆b ||

следует иметь ввиду, что мы определяем предельную относительную

→

→

|| x ||

|| b ||

погрешность, реальная может быть и меньше. Пример.

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

− x

+

2x

2

=1

− x

+

2x

2

=1

→

0.1

→

1)

1

2)

1

при ∆b = 0.0 ,

|| ∆b || =0.1

2x

−

x

2

=1

−10x

+ 21x

2

=11

1

1

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

→

1.00

x

=

1.00

=

−1

2

→

1

=

=

0.33

0.67

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

, b =

, A−1

2

−1

1

0.67

0.33

=

(−1)2 + 22 + 22

+(−1)2

= 3.16 ,

=

cond=3.33

|| A ||=

|| A−1 ||=1.05

→

2

2

→

0.1

→

|| b ||=

1

+1

=1.41,

|| δ b ||=

= 0.071,

тогда|| δ x ||= 3.33* 0.071

= 0.24

1.41

=

−1 2

→

=

1

=

−21

2

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

, b

, A−1

=

−10

−10

21

11

1

=

(−1)2 + 22 +(−10)2

+ 212

= 23.37 ,

=

cond=546.0

|| A ||=

|| A−1 ||= 23.37

→

2

2

→

0.1

→

|| b ||=

1

+11

=11.05 ,

|| δ b ||=

= 0.0091,

тогда|| δ x ||= 546 * 0.0091 = 4.94

11.05