Прямоугольные системы уравнений

Прямоугольные системы уравнений.

a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2

…

am1x1 + am2x2 + ... + amnxn = bn

Ax = b, где А = (aij)m . n x = b =

A – основная матрица системы

[A M b] – расширенная матрица системы

Алгоритм Гаусса приведения матрицы у верхнетреугольному виду.

1. Каждая строка расширенной матрицы по очереди служит ведущей.

2. В очередной ведущей строке выбирается произвольный ненулевой элемент, называемый ведущим (лучше на диагонали).

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

Новая матрица:

Теорема

Системы Ax = b и – эквивалентны, т. е. имеют одно и то же множество решений.

Определение

Рангом матрицы A называется размер ее наибольшей невырожденной квадратной подматрицы.

	B

A = rank (A) = k, т. е. размерность подматрицы В равна k

1) det (B) ¹ 0,

2) если размер подматрицы больше k, то она вырождена.

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

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

B

A = B - базисная (ранговая) подматрица.

После применения метода Гаусса:

0
0 … 0 … 0	0 … 0 … 0 0

0
0 … 0		0 … 0
0 … 0 …0	0 0 …0 0 … 0 … 0 0

Но тогда получится матрица размера k + 1, также невырожденная, что противоречит условию

Невозможный случай

 

Случаи расположения базисной (ранговой) подматрицы:

B

N

1. A =

B

N

b

Расширенная матрица: A =

 

После применения метода Гаусса:

rank (A) = m, A - матрица полного ранга

Преобразованная расширенная матрица

 

XB

XN

X = XB – базисные неизвестные

XN – свободные (небазисные) неизвестные

 

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

B

N

2. A = rank (A) = n, A - матрица полного ранга

 

B	bI
N	bII

Þ расширенная матрица

После применения метода Гаусса:

1) = 0, то нижние уравнения лишние и мы имеем единственное решение, как в случае квадратной матрицы; 2) ¹ 0, значит система уравнений противоречива, решений нет.

0 0 … 0 0 0 … 0 … 0 0 … 0

 

3. Общий случай:

B

rank(A) = k det(B) ¹ 0

A =

rank (A)=k, det (B) ≠0,

 

B	N
C	D

расширенная матрица:

 

0	0

после применения метода Гаусса:

 

1) если = 0, то блок – лишние уравнения и их можно убрать.

В итоге:

2) bII ¹ 0 – решений нет.

Пример:

x1	x2	x3
1	1	0	1
1	0	1	2
0	1	1	4
1	1	0	1
0	-1	1	1
0	1	1	4
1	1	0	1
0	-1	1	1
0	0	2	5

1) x1 + x2 = 1

rank = 3 Δ = -2 (единственное решение) Þ x1 + x2 = 1 - x2 + x3 = 1 2x3 = 5 Ответ:

x1 + x3 = 2

x2 + x3 = 4

x1	x2	x3
1	1	0	1
1	1	1	2
1	2	1	3
1	1	0	1
0	1	1	2
0	1	1	2
1	1	0	1
0	1	1	2
0	0	0	0

2) x1 + x2 = 1

x2 + x3 = 2

x1 + 2x2 + x3 = 3

Теорема Кронекера-Капелли

Система линейных уравнений совместна тогда и только тогда, когда ранги расширенной и основной матриц совпадают.

Метод Жордана – Гаусса.

1.Эквивалентные преобразования систем линейных уравнений.

Пусть Ax = b, A = (aij)m . n – матрица коэффициентов, x = – вектор неизвестных

b = вектор правых частей.

a11x1 + a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2

…

am1x1 + am2x2 + … + amnxn = bm

Теорема.

Пусть Dm . m – не вырожденная (т. е. det(D) ¹ 0) тогда системы Ax = b и D . Аx = Db эквивалентные (равносильные), то есть имеют одно и то же множество решений

Доказательство:

Þ Пусть ( - решение)

Ü Пусть (т. к. D – невырожденная)

Примеры эквивалентных преобразований

 

1. D = где λ ¹ 0 находится в k–й строке det(D) = λ

DA – матрица A, у которой k-я строка умножена на λ.

 

2. D = k-я строка det (D) = 1

DA – матрица, к k-ой строке которой прибавляется другая строка, умноженная на λ.

 

3. D = - перестановочная матрица (перестановка строк или столбцов в

единичной матрице).

DA – перестановка строк,

AD – перестановка столбцов.

 

D = D-1 = D . D-1 =

Перестановочные матрицы обратны сами себе.

Метод Жордана - Гаусса:

Все преобразования проводятся с расширенной матрицей!

На каждой итерации выделяется ведущая строка и с ней проводятся определенные действия:

1. В ведущей строке ищется произвольный ненулевой элемент , он называется ведущим,

как и столбец, в котором он расположен.

2. Элементы ведущей строки делятся на ведущий элемент.

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

Возможные варианты завершения:

Пусть матрица A полного ранга.

B

N

m

b

A = det(B) ¹ 0 rank(A) = m £ n

Метод Жордана - Гаусса:

1 0 … 0 0 0 1 … 0 0 … 0 0 … 0 1

1 0 … 0 0 0 1 … 0 0 … 0 0 … 0 1
0 0 … 0 0

ç невозможно, так как наличие нулевой строки означает, что det(B) = 0

 

Серия преобразований:

Ax = b

D1Ax = D1b

D2D1Ax = D2D1b

… …

DLDL-1 … D1Ax = DLDL-1 … D1b

D0 - итоговая матрица

D0 [ A M b] = D0[ B M N M b] = [ D0B M D0N M D0b] = [ E MM ]

Отсюда D0B = E

D0N = Þ D0 = B-1

D0b =

xT
	B	N

 

xT
	1 0 … 0 0 0 1 … 0 0 … 0 0 … 0 1

 

~

 

Явная формула:

Пример:

x1 + x2 +x4 = 1 n = 4

x2 + x3 = 1 m = 2

 

x1	x2	x3	x4
1 0 1	0 1 1 0	1 1
0 1 0	1 1
1 0 0 1	-1 1 1 0	0 1

x1 - x3 + x4 = 0 - система эквивалентна исходной

x2 + x3 = 1

Общий вид решения:

t1, t2 – произвольные параметры

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

Рассмотрим несколько систем:

Ax = e1 Где A = (aij)m . m, det (A) ¹ 0.

Ax = e2

…

Ax = em

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

x1, x2, … xm
A	1 1 … 1

Метод Жордана – Гаусса:

D0A

D0E

1 1 … 1

D0E

D0 = DLDL-1 … D1 итоговая матрица

=

Вывод: D0 = A­­-1

Пример:

A = A-1 = A . A-1 =

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

Задание. Рассмотреть остальные 2 случая расположения ранговой матрицы:

B	N
C	D

B

N

и

Свойства.

1. Пусть b = 0, тогда Ax = 0. Такие системы называются однородными.

- Е

2.  Пусть b = 0, тогда каждый столбец матрицы H =

является решением однородной системы Ax = 0. Назовем эту систему решений фундаментальной (т. к. никаких других решений нет и каждый ее элемент является решением уравнения).

(все параметры равны нулю)

3. Первое слагаемое является частным решение системы Ax = b

4. Пусть x = и x = – решения системы Ax = b, тогда их разность x = - есть решение однородной системы Ax = 0, т. к. A(- ) = A- A = b – b = 0.

Теорема.

Любое решение полноранговой системы Ax = b, где n ³ m = rank(A), представимо в виде суммы ее частного решения и общего решения однородной системы.