Решение систем линейных уравнений методом Гаусса

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

Расширенной матрицей системы называется матрица коэффициентов при неизвестных A, к которой присоединён столбец свободных членов B, отделённый от A вертикальной чертой. Расширенная матрица имеет вид .

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

Сначала рассмотрим метод Гаусса на примере системы трёх линейных уравнений с тремя неизвестными в предположении, что главный определитель системы отличен от нуля[*]. В этом случае суть метода Гаусса состоит в преобразовании данной системы в систему с треугольной матрицей.

Для системы матрица является расширенной матрицей.

Схематично метод Гаусса можно изобразить так:

Первый этап Второй этап Третий этап

~ ~ ~ .

Преобразования можно продолжить с целью получить систему с единичной матрицей. В этом случае говорят о методе Гаусса-Жордана.

~ ~

Третий этап Четвёртый этап Пятый этап

Пример. Пусть дана система

Выпишем расширенную матрицу и выполним нужные преобразования: ~ ~ ~ ~

~ ~ ~ ~ ~ .

Последняя матрица соответствует системе . Подставив во второе уравнение , найдём, что . Затем, подставляя в первое уравнение и , найдём, что . Решение системы методом Гаусса завершено.

Метод Гаусса-Жордана отличается от метода Гаусса тем, что вычисление неизвестных производится в матричной форме. Матрица подвергается дальнейшим преобразованиям: прибавляем ко второй и к первой строкам третью, умноженную на –2 и на –3, соответственно. Далее, ~ ~ , откуда .

E …….. …….. …….. . . . 0   k n-k k m m-k n

Рассмотрим теперь метод Гаусса в ситуации, когда либо число уравнений не совпадает с числом неизвестных, либо неизвестно, отличен ли от нуля главный определитель системы. Приведём при помощи допустимых преобразований расположенную до черты часть расширенной матрицы к каноническому или почти каноническому виду. При этом матрица A, превратится в имеющую канонический или почти канонический вид матрицу . Столбец B также изменится и станет столбцом . В результате получается преобразованная расширенная матрица .

исследуем систему с такой расширенной матрицей на совместность.

Если , и хотя бы один элемент столбца , с номером большим k, не равен нулю, пусть это будет элемент (), то система несовместна, так как содержит уравнение , не имеющее решений при .

Во всех остальных случаях система совместна. Рассмотрим эти случаи.

E …….. …….. …….. . . . 0     k n-k   k m m-k n

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

Имеется два варианта: и . При

E …….. …….. …….. . . . k n-k k = m n

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

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

Однородные (с нулевыми правыми частями) системы линейных уравнений всегда совместны, поскольку имеют нулевое (состоящее из нулей) решение. Это решение единственно, если . Если же , множество решений однородной системы бесконечно и, что особенно важно, содержит ненулевые решения.

Отметим, что во всех случаях, когда система совместна, матрица , так же как и , имеет канонический вид.

Пример. Пусть расширенная матрица некоторой системы линейных уравнений при помощи допустимых преобразований приведена к виду . Система, очевидно, совместна. Найдём все её решения. Отбрасывая третью и четвёртую строчки (они состоят из нулей), получим систему . Пусть t, u, v – произвольные числа. Положим свободные неизвестные равными этим числам, то есть будем считать, что . Тогда из первого уравнения следует, что , а из второго, что . Полученные формулы вычисления неизвестных дают бесконечно много решений.

Если в столбце свободных членов третий или четвёртый элемент был бы не 0, а, например, 1, то система была бы несовместной, так как одно из её уравнений имело бы вид: . Такое уравнение, а вместе с ним и система, решений не имеет.

Ранг матрицы

Число r называется рангом матрицы A (), если какой-нибудь её минор r -го порядка отличен от нуля, а все миноры (r +1)-го порядка (если они существуют) равны нулю.

Иными словами, рангом матрицы называется наивысший порядок отличных от нуля миноров.

Ранг матрицы, состоящий из нулей, считается равным нулю.

Ранг невырожденной квадратной матрицы n -го порядка равен n. В частности, ранг треугольной матрицы равен её порядку.

Ранг матрицы размерности не превышает наименьшего из чисел m и n, так как минор не может содержать строк и столбцов больше, чем сама матрица. Если и найдётся минор порядка m, отличный от нуля, то ранг матрицы равен m. Если и найдётся минор порядка n, отличный от нуля, ранг матрицы равен n.

Например, , , .

Очевидно, что ранг матрицы не изменяется при транспонировании.

E …….. …….. …….. 0   k n-k k m m-k n

легко найти ранг матрицы, имеющей канонический или почти канонический вид. Очевидно, что ранг такой матрицы равен k. Действительно, единичная матрица даёт нам минор k -го порядка, отличный от нуля, а любой минор (k +1)-го порядка равен нулю, так как содержит строку, состоящую из нулей.

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

Т е о р е м а. Ранг матрицы не меняется при допустимых преобразованиях.

Доказательство[†]. Остановимся на допустимых преобразованиях, связанных со строками (перестановка столбцов рассматривается аналогично перестановке строк). Возьмём какой-нибудь минор преобразуемой матрицы. Если преобразование его не затронуло или в преобразовании участвовали только его строки, то этот минор остаётся таким же, как был, либо равным нулю, либо отличным от нуля. Измениться, в этом смысле, минор может, только если в преобразовании участвовала строка, назовём её действующей, элементы которой в минор не входили. При этом возможны два случая: а) изменяемая строка, была переставлена с действующей; б) к изменяемой строке прибавлена действующая строка, умноженная на число, не равное нулю.

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

В случае а) в преобразованной матрице возьмём минор, составленный из строк выделенного нами минора, не затронутых преобразованием, и строки, оказавшейся на месте действующей. Этот минор может отличаться от исходного минора лишь знаком и, следовательно, не равен нулю.

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

И в том, и в другом случае преобразованная матрица обладает минором r -го порядка, отличным от нуля, так что ранг матрицы не уменьшился.

Теперь покажем, что все миноры (r +1)-го порядка преобразованной матрицы (так же как и исходной) равны нулю.

Предположим, что какой-нибудь минор (r +1)-го порядка исходной матрицы перестал быть равным нулю. В случае а) это означает, что он содержит элементы r строк, не участвующих в перестановке, и часть элементов действующей строки. Но минор с такими строками уже был в исходной матрице и должен был быть равным нулю как минор (r +1)-го порядка, поэтому наше предположение о том, что рассматриваемый минор стал отличным от нуля ошибочно. В случае б) преобразованный минор представляет собой сумму исходного минора и другого минора исходной матрицы, умноженного на число. Оба минора, будучи минорами (r +1)-го порядка, равны нулю, значит, равна нулю и их сумма. Значит, и в этом случае следует признать ошибочность нашего предположения. Таким образом, ранг матрицы не увеличился.

Итак, если матрица A при помощи допустимых преобразований, приведена к матрице , ранги этих матриц равны.

Вот почему к треугольному виду можно привести только невырожденную матрицу.

Пример. Чтобы вычислить ранг матрицы , нужно привести её к каноническому или почти каноническому виду. Это было сделано нами на страницах 16 и 17. Были полученные две матрицы: (канонического вида) и (почти канонического вида). В левом верхнем углу каждой из этих матриц расположена невырожденная квадратная матрица третьего порядка. Все миноры четвёртого порядка равны нулю, так как содержат строку, состоящую из нулей. Значит, ранг всех трёх матриц равен трём.

E …….. …….. …….. . . . 0     k n-k k m m-k n

При помощи понятия «ранг матрицы» можно гораздо короче сформулировать полученные нами ранее условия совместности и несовместности систем линейных уравнений.

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

Несовместность системы, как мы видели, была связана с тем, что столбец содержал ненулевой элемент (). С помощью этого элемента можно составить отличный от нуля минор (k +1)-го порядка, присоединив к единичному (треугольному) блоку столбец и строку . Их общий элемент станет при этом (k +1)-м диагональным элементом минора. Ясно, что , тогда как , то есть .

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

Т е о р е м а (Кронекера-Капелли). Для того чтобы система линейных уравнений была совместна, необходимо и достаточно, чтобы ранг матрицы коэффициентов при неизвестных был равен рангу расширенной матрицы.

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

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

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

собственные числа и собственные векторы

О п р е д е л е н и е. Ненулевой алгебраический вектор X и число λ называются, соответственно, собственным вектором и собственным числом квадратной матрицы A, если .

каждому собственному числу λ отвечает бесконечно много собственных векторов, поскольку при умножении собственного вектора на какое-нибудь отличное от нуля число t, получается также собственный вектор, . Обычно бывает достаточно найти один из них.

Матричное равенство равносильно равенству или, что то же самое, . Вынося за скобки X, получим равенство , которое можно рассматривать как матричную запись однородной системы линейных уравнений.

Для того чтобы эта система имела ненулевое решение, необходимо и достаточно, чтобы её главный определитель был равен нулю. Значит, число λ будет собственнымчислом матрицы A в том и только в том случае, когда , то есть λ должно быть корнем этого уравнения.

Уравнение называется характеристическим уравнением матрицы A.

Приведём пример вычисления собственных чисел и собственных векторов квадратной матрицы.

Пусть , тогда – характеристическое уравнение этой матрицы. Вычислив определитель, получим уравнение , решив которое, найдём, собственные числа , , .

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

Если , то и . Решаем систему методом Гаусса.

~ ~ ~ .

Пусть [‡], тогда , , так что .

Если , то и .

~ ~ ~ .

Пусть **, тогда , , так что .

Если , то и .

~ ~ ~ . Вторая строка соответствует равенству , то есть нельзя выбирать произвольно. Пусть , тогда , так что .