Метод Гаусса решения систем линейных алгебраических систем уравнений.

Свойства определителей.

Транспонирование не меняет определителя. (Транспонирование – взаимная замена строк и столбцов.)

Возьмём любой член определителя (-1)^ti⁺^tja_i₁_j₁*a_i₂_j₂*a_i₃_j₃*…*a_injn_.

Из вида любого члена определителя видно, что при транспонировании они не меняются.

det A^T = det A

1) Если в определителе поменять местами 2 строки, то знак определителя поменяется на противоположный.

Доказательство: Берём произвольный член определителя. Взаимное расположение -> поменялись первые 2 индекса -> чётность изменилась -> изменился знак.

2) Если в определителе 2 строки (столбца) одинаковы, то det = 0.

Если 2 одинаковые строки поменять местами, то ничего не меняется, но по св-ву 2 знак меняется. Это происходит, если △=0. (△=-△, 2△=0, △=0)

3) Если в определителе есть 2 пропорциональные строки, то он тоже = 0.

det = k det

после того, как k вынесен, 2 строки равны. По св-ву 3 △ =0.

4) Если в некоторой строке определителя все элементы в виде 1 и той же комбинации чисел, а именно k-я строка (αck1 + βdk1 + αck2+ βdk2) = α|ck1+ck2…+ckn|+β|dk1+dk2…+dkn|.

5) Если в любой строке определителя прибавить любую другую строку с противоположным коэффициентом, то определитель не изменится.

6) Если строка в определителе состоит из нулей, то определитель = 0.

7) Если какая-либо строка определителя есть линейная комбинация других строк, то определитель = 0.

₁ = (a₁₁,a_1n)

₂ = (a₂₁,a_2n)

_n = (a_n1,a_nn)

	₁
Det A=	₂
	_n

Пусть _k есть линейная комбинация остальных

_k = α₁ ₁ + α₂ ₂ +…+ α_k_-1 _k_-1 + α_k₊₁ _k₊₁ +…+ α_n _n

В соответствии со свойством 7 определитель равен сумме этих определителей, равных нулю. Количество определителей = (n-1)и в каждой из которых имеются одинаковые строки.

Разложение определителя по элементам строки или столбца.

Минором элемента определителя a_ik называется определитель n-1 порядка, получающийся вычёркиванием строки и столбца, на пересечении которых стоит элемент a_ik.

Алгебраическим дополнением А_ik элемента определителя a_ik называется A_ik = (-1)ⁱ⁺^kM_ik_.

Теорема. Определитель равен сумме произведений элементов какой-либо строки на их алгебраические дополнения.

det A = a_k1A_k1+a_k2A_k2+…+a_knA_kn=

1) Доказательство: Пусть определитель имеет вид:

a₁₁

Определитель 1 порядка, полученный вычёркиванием 1 строки и 1 столбца.

Тем самым, для 1 случая теорема доказана.

2) Пусть определитель имеет вид:

= (-1)^j

a_n₁ a_n₂ a_n₃ a_n₄ … a_nm

Передвинем последовательными шагами столбец этого элемента a_kj (столбец с номером j) влево до занятия им места 1 столбца. При этом определитель при каждом шаге меняет знак и итоге приобретает множитель (-1)^j и приобретает вид:

a_nj a_n₁ a_n₂ a_n₃ … a_nm

Далее перемещаем строку с номером k вверх последовательно, пока она не займёт место 1^ойстроки, т.е. определитель будет иметь вид:

a_nj a_n₁ a_n₂ a_n₃ … a_nm

При этом определитель приобретает ещё один множитель (-1)k. В итоге

a_nj a_n₁ a_n₂ a_n₃ … a_nm

Мы пришли к 1 случаю, для которого справедливость была доказана.

det A = (-1)^j+ka_kjM_kj+0*A_k1+…+0*A_k2*…*0*A_kn

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

a₁₁	a₁₂	…	a_1m
…	…	…	…
a_k1	a_k2	…	a_km
…	…	…	…
a_n1	a_n2	…	a_nm

=(-1)^k+1a_k1M_k1+(-1)^k+2a_k2M_k2+…+(-1)^k+na_knM_kn

Это правило вычисления определителя называется разложением по I строке (столбцу).

2. Равенство нулю суммы произведений элементов строки (столбца, алгебраическое дополнение другой строки (столбца)).

Сумма произведений элементов какой-либо строки на алгебраическое дополнение другой строки равна нулю, т.е.:

(*) а_k₁А_j₁+ а_k₂А_j₂+…+ а_knА_jn=0

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

Рассмотрим определитель:

	…	…	…	…
j-я строка	a_j1	a_j2		a_jn	= а_j₁А_j₁+ а_j₂А_j₂+…+ а_jnА_jn (**)
k-я строка	a_k1	a_k2		a_kn

В выражении (*) коэффициент А_jm получились вычёркиванием j-ой строки -> а_jmА не зависят от тех чисел, которые могут стоять в j-ой строке.

В определителе (**) на место j-ой строки поставим k-ую строчку. Тогда этот определитель равен det А = а_k₁А_j₁+ а_k₂А_j₂+…+ а_knА_jn

Но это равенство равно нулю, так как определитель имеет две одинаковые строки. Ч.т.д.

3. Ранг матрицы. Вычисление ранга методом окаймляющих миноров.

Пусть имеется прямоугольная матрица nхm.

Минором K-ого порядка матрицы А (k<m,k<n) называется определитель, получающийся из элементов, стоящих на пересечении каких-либо строк и каких-либо столбцов.

Рангом матрицы называется целое, положительное число r=Rang А, такое, что в данной матрице присутствует хотя бы один минор порядка r≠0, а все миноры следующего порядка (r+1 и далее) =0.

Метод окаймления миноров.

Если в матрице найден отличный от нуля минор k-ого порядка, то все миноры k+1 порядка считать не обязательно, так как имеет место теорема:

Если все окаймляющие данный минор k-ого порядка миноры k+1 порядка равны нулю, то и все вообще миноры k+1 –ого порядка = 0.

Найдём окаймляющие миноры 3-его порядка для M₂: (положим, М₂≠0)

а₁₁	а₁₂	а₁₃	а₁₄
а₂₁	а₂₂	а₂₃	а₂₄
а₃₁	а₃₂	а₃₃	а₃₄
а₄₁	а₄₂	а₄₃	а₄₄

	а₁₁	а₁₂	а₁₃
M₃⁽¹⁾=	а₂₁	а₂₂	а₂₃
	а₃₁	а₃₂	а₃₃

	а₁₁	а₁₃	а₁₄
M₃⁽²⁾=	а₂₁	а₂₃	а₂₄
	а₃₁	а₃₃	а₃₄

	а₁₁	а₁₂	а₁₃
M₃⁽³⁾=	а₂₁	а₂₂	а₂₃
	а₄₁	а₄₂	а₄₃

	а₁₁	а₁₃	а₁₄
M₃⁽⁴⁾=	а₂₁	а₂₃	а₂₄
	а₄₁	а₄₃	а₄₄

4. Теорема о базисном миноре. Понятие линейно независимых строк (столбцов) определителя. Необходимое и достаточное условие равенства 0 определителя.

При нахождении ранга матрицы минор порядка r (ранг матрицы) называется базисным.

Все строки матрицы являются линейными комбинациями строк базисного минора. (к столбцам относится то же самое).

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

a₁₁	a₁₂	…	a_1r	a_1j	a_1r+1	…	a_1n
a₂₁	a₂₂	…	a_2r	a_2j	a_2r+1	…	a_2n
a₃₁	a₃₂	…	a_3r	a_3j	a_3r+1	…	a_3n
…	…	…	…	…	…	…	…
a_r1	a_r2	…	a_rr	a_rj	a_rr+1	…	a_rn
a_k1	a_k2	…	a_kr	a_kj	a_kr+1	…	a_kn
a_m1	a_m2	…	a_mr	а_mj	a_mr+1	…	a_mn

Берём любую строку с номером произвольным k. Ставим её под базисный минор. Вправо от минора ставим произвольный столбец с номером j. Рассмотрим минор Mr+1, окаймляющий базисный снизу. K-ой строкой, справа k-ым столбцом.

Разложим его:

Mr+1=0=c1a1j+ c2a2j+ crarj+ Arakj |:Ar (Ar≠0)

Akj=-c1*a1j/Ar- c2*a2j/Ar+…- cr*arj/Ar

Так как akj – координаты вектора строки с номером k, это вернодля любого столбца (коэффициенты ci/Ar одинаковы для любого j) -> сам вектор

строка ak=-c1a1/Ar- c2a1/Ar -crar/Ar

Следствие из теоремы о базисном миноре:

Определитель матрицы равен нулю тогда и только тогда, когда ранг матрицы <n (порядок квадратной матрицы)

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

а₁₁	а₁₂	…	а₁_n
а₂₁	а₂₂	…	а₂_n
а_m₁	а_m₂	…	а_mn

det A = 0

Rang A < n

1) Необходимость: дано: det A = 0, доказать: Rang A<n

Так как det A = 0, то по карйней мере одна из строк есть линейная комбинация строк. Это значит, что число линейно независимых строк < n. Число линейно независимых строк и есть Rang A -> r<n

2) Достаточность: дано: Rang A<n, доказать: det A = 0

Так как Rang A<n, а ранг – число линейно независимых строк, то в А число линейно независимых строк <n. Значит, по крайней мере одна из строк есть линейная комбинация остальных, а это значит, что det A = 0 (по св-вам определителя).

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

а₁₁	а₁₂	…	а₁_n
а₂₁	а₂₂	…	а₂_n
а_m₁	а_m₂	…	а_mn

Рассмотрим строки как векторы (координаты aij (j=1,2,3…n))

1=(а₁₁, а₁₂, а₁₃,…,а₁_n);

₂=(а₂₁, а₂₂, а₂₃,…,а₂_n);

_m=(а_m₁, а_m₂, а_m₃,…,а_mn);

Строки называются линейно независимыми, если они линейно независимы в смысле векторов, т.е. единственная линейная комбинация векторов, равная 0, это та, все коэффициенты нули.

Линейная комбинация – с₁ ₁ + с₂ ₂+ … + с_m _m равна нулю тогда и только тогда, когда все числовые коэффициенты с₁= с₂= с_n = 0. Тогда векторы линейно независимы.

Если вектор – линейная комбинация остальных, то система линейно зависима: ak= с₁ ₁ + с₂ ₂+ … + с_k-1 _k-1+ с_k+1 _k+1+ с_n _n

5. Системы линейных алгебраических уравнений. Правило Крамера.

х1, х2, …, хn – неизвестные

aik – постоянные коэффициенты

Матрица системы:

а₁₁	а₁₂	…	а₁_n
а₂₁	а₂₂	…	а₂_n
а_m₁	а_m₂	…	а_mn

1) Кмножаем каждую строку системы на алгебраическое дополнение 1-ого элемента строки.

2) Сложим уравнения.

*x₁+ *x₂+ … + *x_n =

3) Поступим так же со вторым столбцом. (каждый элемент строки умножаем на А второго элемента строки). Слева получим △х₂, справа - △2

Если определитель системы △≠0, то система имеет, и притом единственное, решение, даваемое формулами крамера:

△ – определитель системы, составленный из коэффициентов при неизвестных.

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

Если определитель системы △ = 0:

Если хотя бы один △_i ≠ 0, то система несовместна (ᴓ) (решений нет)

Если все △_i = 0, то решение существует и их бесконечно много. Система несовместна и называется неопределённой.

В случае неопределённой системы не все числа х₁, х₂, …, х_n можно брать произвольными, так как даже если одно уравнение осталось в системе, а все остальные – следствие из него, то это уравнение связывает между собой переменные, а это и значит, что все их брать произвольными нельзя.

6. Необходимое и достаточное условие совместимости системы. Теорема Кронекера – Капелле.

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

а₁₁	а₁₂	…	а₁_n	b₁
а₂₁	а₂₂	…	а₂_n	b₂
а_m₁	а_m₂	…	а_mn	b₃

Rang A = Rang

Вектор столбец

(*) a₁x₁ + a₂x₂ +…+ a_nx_n =b

1) Необходимость: Дано: совместная система, доказать: Rang A = Rang

Доказательство: Так как система совместна, то есть, имеет решение, то существует такой набор чисел x₁=c₁, x₂=c₂, x_n=c_n, при подставлении которых в систему (*) получится верное равенство. Следовательно, b есть линейная комбинация остальных столбцов.

₁x₁ + ₂x₂ +…+ _nx_n =

-> линейная комбинация столбцов . Если в матрице один столбец является линейной комбинацией остальных, то при добавлении к матрице А этого столбца, её Rang не меняется, т.е. Rang A = Rang

2) Достаточность:

Дано: Rang A = Rang

Доказать: система (*) совместна.

Доказательство: Матрицы A и отличаются только и т.к. их ранги равны, то дабавление к А не меняет её ранга. Значит, этот столбец – линейная комбинация остальных столбцов. Т.е. существует такие числа c₁, c₂, c₃,…,c_n, что ₁c₁+ ₂c₂+…+ _nc_n= . Но это и есть система (*)

-> (*) удовлетворилась при x₁=c₁, x₂=c₂, x_n=c_n ч.т.д.

Т.е. с₁,с₂,с_n – решения системы.

Метод Гаусса решения систем линейных алгебраических систем уравнений.

Метод Гаусса. Пусть дана система линейных уравнений с неизвестными . Выпишем расширенную матрицу системы/ Цель алгоритма -- с помощью применения последовательности элементарных операций к матрице добиться, чтобы каждая строка, кроме, быть может, первой, начиналась с нулей, и число нулей до первого ненулевого элемента в каждой следующей строке было больше, чем в предыдущей. Находим первый ненулевой столбец в матрице . Пусть это будет столбец с номером . Находим в нем ненулевой элемент и строку с этим элементом меняем местами с первой строкой. Чтобы не нагромождать дополнительных обозначений, будем считать, что такая смена строк в матрице уже произведена, то есть . Тогда ко второй строке прибавим первую, умноженную на число , к третьей строке прибавим первую, умноженную на число , и т.д. В результате получим матрицу

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

Этому уравнению не удовлетворяет ни один набор чисел Матрицу можно записать в виде

где

По отношению к матрице выполняем описанный шаг алгоритма. Получаем матрицу

где , . Эту матрицу снова можно записать в виде

и к матрице снова применим описанный выше шаг алгоритма.

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

Далее выполняется так называемый обратный ход метода Гаусса. По матрице составляем систему уравнений. В левой части оставляем неизвестные с номерами, соответствующими первым ненулевым элементам в каждой строке, то есть . Заметим, что . Остальные неизвестные переносим в правую часть. Считая неизвестные в правой части некоторыми фиксированными величинами, несложно выразить через них неизвестные левой части. Теперь, придавая неизвестным в правой части произвольные значения и вычисляя значения переменных левой части, мы будем находить различные решения исходной системы . Чтобы записать общее решение, нужно неизвестные в правой части обозначить в каком-либо порядке буквами , включая и те неизвестные, которые явно не выписаны в правой части из-за нулевых коэффициентов, и тогда столбец неизвестных можно записать в виде столбца, где каждый элемент будет линейной комбинацией произвольных величин (в частности, просто произвольной величиной ). Эта запись и будет общим решением системы. Если система была однородной, то получим общее решение однородной системы. Коэффициенты при , взятые в каждом элементе столбца общего решения, составят первое решение из фундаментальной системы решений, коэффициенты при -- второе решение и т.д. Фундаментальную систему решений однородной системы можно получить и другим способом. Для этого одному переменному, перенесенному в правую часть, нужно присвоить значение 1, а остальным -- нули. Вычислив значения переменных в левой части, получим одно решение из фундаментальной системы. Присвоив другому переменному в правой части значение 1, а остальным -- нули, получим второе решение из фундаментальной системы и т.д. Замечание 15.4 У читателя может возникнуть вопрос: "Зачем рассматривать случай, когда некоторые столбцы матрицы нулевые? Ведь в этом случае соответствующие им переменные в системе уравнений в явном виде отсутствуют." Но дело том, что в некоторых задачах, например, при нахождении собственных чисел матрицы, такие системы возникают, и игнорировать отсутствующие переменные нельзя, так как при этом происходит потеря важных для задачи.