Линейная алгебра (стр. 6 )

Столбец свободных членов	3
	- 4
	0

по очереди подставим вместо 1-го, 2-го и 3-го столбцов определителя Δ.

Имеем,		3	1	- 1
	Δх = 1	- 4	2	3	=15
		0	-1	1
		1	3	- 1
	Δх = 2	1	- 4	3	= - 17
		- 2	0	1
		1	1	3
	Δх = 3	1	2	- 4	= 13
		- 2	- 1	0

Ни один из определителей не равен "0", следовательно, система однозначно определена и решение ее:

х1= Δх /Δ

1

х2= Δх /Δ

2

х3= Δх /Δ , т. е.

3

х1 = - 3

х2 = 17/5

х3 = - 13/5

Сделаем проверку:

-  3 +17/5 +13/5 =3

-  3 +2 * 17/5 +3 (- 13/5) =- 4

-  2 (-3) – 17/5 – 13/5 =0

Уравнения обратились в тождества. Следовательно, решение найдено верно.

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

Рассмотрим систему:

а11x1 + a12x2 + a13x3 + … + a1nxn = b1

а21x1 + a22x2 + a23x3 + … + a2nxn = b2 (1)

а31x1 + a32x2 + a33x3 + … + a3nxn = b3

…………………………………………………………

аn1x1 + an2x2 + an3x3 + … + annxn = bn

Система не изменится, если

1)  поменять местами любые 2 уравнения;

2)  умножить правую и левую часть уравнения на одно и то же число (разумеется, не равное "0");

3)  прибавить к одному уравнению другое, умноженное на любое число.

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

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

а11x1 + a12x2 + a13x3 + … + a1nxn = b1

а21x1 + a22x2 + a23x3 + … + a2nxn = b2 +(1)(- а21/а11)

а31x1 + a32x2 + a33x3 + … + a3nxn = b3 +(1)(- а31/а11)

…………………………………………………………

аn1x1 + an2x2 + an3x3 + … + annxn = bn +(1)(- аn1/а11); а11¹0

После 1-го шага получим систему в следующем виде:

а11x1 + a12x2 + a13x3 + … + a1nxn = b1

(2) a¢22x2 + a¢23x3 + … + a¢2nxn = b¢2

a¢32x2 + a¢33x3 + … + a¢3nxn = b¢3 +(2)( - а¢32/а¢22)

…………………………………………………………

a¢n2x2 + a¢n3x3 + … + a¢nnxn = b¢n +(2)( - а¢n2/а¢22); а¢22¹0

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

а11x1 + a12x2 + a13x3 + … + a1nxn = b1

(3) a¢22x2 + a¢23x3 + … + a¢2nxn = b¢2

a¢¢33x3 + … + a¢¢3nxn = b¢¢3

a¢¢43x3 + … + a¢¢4nxn = b¢¢4

…………………………………………………………

a¢¢n3x3 + … + a¢¢nnxn = b¢¢n

Делая последовательно (n–1) шаг, мы исключим все неизвестные, кроме xn, оставшегося в последнем уравнении.

После (n-1) шага система будет иметь следующий вид (4):

а11x1 + a12x2 + a13x3 + … + a1nxn = b1

(4) a¢22x2 + a¢23x3 + … + a¢2nxn = b¢2

a¢¢33x3 + … + a¢¢3nxn = b¢¢3

………………………………………………………

a(n-1) nnxn = b(n-1) n

(4) будем называть треугольным видом, причем 2-е уравнение осталось после 1-го шага, 3-е – после 2-го, 4-е – после 3-го и т. д., последнее - после (n-1) преобразования. На этом этап исключения неизвестных закончился. Видно, что теперь можно найти все неизвестные, начиная с xn из последнего уравнения:

хn=bn(n-1) / ann(n-1)

Найденный xn, подставленный в предпоследнее уравнение, даст хn-1 и т. д. Двигаясь снизу вверх, по очереди будут найдены все n-неизвестные: (xn, xn-1, …, x2, x1).

Неизвестные исключаются так: (x1, x2, …, xn), находились они в обратном порядке.

Если в результате преобразований на к-м шаге коэффициенты при неизвестных в некотором уравнении обнулились, а правая часть этого уравнения не равна 0, то преобразование необходимо прекратить, так как очевидно, что в этом случае система не совместна. Если же в результате преобразования в некотором уравнении обнулились и коэффициенты при неизвестных и правая часть, то такое уравнение следует вычеркнуть, т. е. оно не будет принимать участие в дальнейших преобразованиях. Таких уравнений может быть несколько. В этом случае система (1) не может быть приведена к треугольному виду (4), а может быть приведена к трапециевидному виду (5):

а11x1 + a12x2 + a13x3 + a14x4+ … + a1nxn = b1

(5) a¢22x2 + a¢23x3 + a¢24x4 + … + a¢2nxn = b¢2

a¢¢33x3 + a¢¢34x4 + … + a¢¢3nxn = b¢¢3

a(3)44x4 + … + a(3)4nxn = b(3) 4

………………………………………………………

a(к-1) ккxк + a(к-1) к, к+1xк+1 + …+ a(к-1) кnxn = b(к-1) n

Очевидно, что в этом случае система определена не однозначно, т. е. имеет бесконечное множество решений, связанных линейной зависимостью неизвестных (xк, xк+1, …, xn).

Надо это понимать так: для всех (xк, xк+1, …, xn) таких что a(к-1) ккxк + a(к-1) к, к+1xк+1 + …+ a(к-1) кnxn = b(к-1) n, могут быть найдены все неизвестные, начиная с хк-1 до х1.

В некоторых частных случаях в системе (1) некоторые из диагональных коэффициентов (а11, а22, …, аnn) могут быть равны 0.

Так, например, а11=0. Тогда 1-й шаг, предполагающий вычисление а21 / а11, а31 / а11, …, аn1 / а11, невозможен. Это означает, что невозможно исключение неизвестного х1. В этом случае можно поменять местами 1-е уравнение с любым другим, у которого коэффициент при неизвестном х1 не равен 0, либо начать исключать неизвестные не с х1, а с любого другого. При этом, если исключаются неизвестные в выбранном порядке, находить их необходимо в обратном выбранному порядке.

Так, например, имея систему линейных уравнений 5-го порядка (т. е. систему с 5-ю неизвестными), мы исключали неизвестные так:

(х3, х2, х1, х4, х5)

Тогда находить их надо обязательно в обратном порядке:

(х5®х4®х1®х2®х3)

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

Пример.

х1 + х2 + х3 + х4 = 10

х1 + 2х2 + 3х3 + 4х4= 30

х1 + 3х2 + 4х3 + 5х4= 39

х1 + 4х2 + 5х3 + 6х4= 52

Составим расширенную матрицу системы и будем обнулять коэффициенты при х1, х2, х3, начиная со 2-го, 3-го уравнения:

1	1	1	1	10		®	1	1	1	1	10		®
1	2	3	4	30	-(1)	0	1	2	3	20
1	3	4	5	39	-(1)	0	2	3	4	29	-(2)*2
1	4	5	6	52	-(1)	0	3	4	5	42	-(2)*3
®
1	1	1	1	10			®	1	1	1	1	10		®
0	1	2	3	20			0	1	2	3	20
0	0	-1	-2	-11	*(-1)	0	0	1	2	11
0	0	-2	-4	-18	*(-0,5)	0	0	1	2	9	-(3)

®	1	1	1	1	10
0	1	2	3	20
0	0	1	2	11
0	0	0	0	-2

Последняя строчка расширенной матрицы соответствует уравнению 0х1 + 0х2 + 0х3 + 0х4= -2, что невозможно не при каких х1, х2, х3, х4, следовательно, система несовместна.

Метод последовательного исключения неизвестных имеет преимущества перед методом Крамера:

1)  быстродействие;

2)  в случае бесконечного множества решений существует возможность указать линейную зависимость, образующую бесконечное множество решений. Другими словами метод Гаусса дает возможность описать бесконечное множество решений, а метод Крамера только констатирует факт;

3)  методом можно пользоваться и в случае, когда число неизвестных не равно числу уравнений;

4)  алгоритм Гаусса позволяет быстро вычислять определители высших порядков.

Лекция 6.
Матрицы. Действия над матрицами.

Матрицы

Матрицей А называется таблица элементов аij, размерами m´n, где

i – номер строки, iÎ[1, m];

j – номер столбца, jÎ[1,n].

 

А=	а11	а12	…	а1n	=[ аij]m´n
а21	а22	…	а2n
………………….
аm1	аm2	…	аmn

Условно матрицы можно классифицировать следующим образом: