22.Схема решения системы линейных уравнений методом Гауса

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

Алгоритм решения системы линейных уравнений методом Гаусса подразделяется на два этапа.

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

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

23.Теорема Кронекера-Капелли: с доказательством и иллюстрацией применения.

Теорема Кронекера — Капелли: Система линейных алгебраических уравнений совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы. В частности:

Количество главных переменных системы равно рангу системы.

Совместная система будет определена (её решение единственно), если ранг системы равен числу всех её переменных.

Доказательство (условия совместности системы)

Необходимость

Пусть система совместна. Тогда существуют числа такие, что . Следовательно, столбец b является линейной комбинацией столбцов матрицы A. Из того, что ранг матрицы не изменится, если из системы его строк (столбцов) вычеркнуть или приписать строку (столбец), которая является линейной комбинацией других строк (столбцов) следует, что .

Достаточность

Пусть . Возьмем в матрице A какой-нибудь базисный минор. Так как , то он же и будет базисным минором и матрицы B. Тогда согласно теореме о базисном миноре последний столбец матрицы B будет линейной комбинацией базисных столбцов, то есть столбцов матрицы A. Следовательно, столбец свободных членов системы является линейной комбинацией столбцов матрицы A.

Теорема: Система совместна (имеет хотя бы одно решение) тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы.

Очевидно, что система (1) может быть записана в виде:

x1 + x2 + … + xn

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

1) Если решение существует, то столбец свободных членов есть линейная комбинация столбцов матрицы А, а значит добавление этого столбца в матрицу, т.е. переход А->А* не изменяют ранга.

2) Если RgA = RgA*, то это означает, что они имеют один и тот же базисный минор. Столбец свободных членов – линейная комбинация столбцов базисного минора, те верна запись, приведенная выше.

Пример. Определить совместность системы линейных уравнений: