Здравствуйте, Александр! Спасибо за вопрос.
Пусть дана матрица A, состоящая из n строк и m столбцов. Имеется столбец b длиной n. Будем считать, что уравнения совместны, то есть решение существует.
Как найти частное решение СЛАУ Ax=b?
- Прямым ходом метода Гаусса приводим расширенную матрицу системы к ступенчатому виду.
- Исключаем нулевые строки. Количество исключённых строк обозначим через r. Обозначим k=n-r.
- Исключаем m-k столбцов из матрица коэффициентов так, чтобы в итоге получилась квадратная матрица с ненулевыми элементами на главной диагонали. Переменные, соответствующие исключённым столбцам называются свободными. Оставшиеся переменные называются базисными.
- Получившуюся квадратную матрицу коэффициентов (при базисных переменных) обозначим через A1. Эта матрица невырождена, поэтому базисные переменные можно однозначно найти (например, обратным ходом метода Гаусса).
- Записываем вектор x, присваивая свободным переменным нулевые значения, а базисным - полученные на предыдущем шаге. Мы получили частное решение СЛАУ.
Сколько частных решений имеет СЛАУ Ax=b?
В пункте 4 мы выделили столбцы, соответствующие базисным переменным и составили из них матрицу A1. Поступим аналогично для свободных переменных и из соответствующих им столбцам (именно их мы исключили в пункте 3) составим марицу A2. Эта матрица имеет k строк и m-k столбцов.
Размерность пространства решений СЛАУ равна рангу матрицы A2. Почему? Соберём все базисные переменные в вектор x1, а все свободные - в вектор x2. Тогда по определению имеем
Ax = A1 x1 + A2 x2
Далее, из Ax=b вытекает, что
x1 = A1^{-1} b - A1^{-1} A2 x2 (1)
Введём ещё обозначения:
z = A1^{-1} b
B = -A1^{-1} A2
Тогда уравнение (1) примет вид:
x1 = z + B x2 (2)
По сути z - это частное решение неоднородной системы, а B x2 - общее решение однородной системы. Однако, в матрице B столбцы могут быть линейно зависимы (это означает, что некоторые свободные переменные либо не влияют не решение, либо могут быть выражены через остальные. Безжалостно исключаем линейно зависимые столбцы из матрицы: получаем матрицу B1. Ранги матриц B1, B, A2 совпадают потому что невырожденное преобразование не меняет ранг. После этой зачистки обозначим столбец оставшихся свободных переменных через c. Тогда уравнение (2) примет окончательный вид:
x1 = z + B1 c (3)
Формула описывает общее решение неоднородной системы. По сути компоненты вектора c - это независимые произвольные константы. Присваивая им произвольные значения, получим все возможные частные решения исходной СЛАУ.
Заметим, что, как правило, существует несколько различных вариантов разбиения переменных на свободные и базисные, поэтому представление (3) неоднозначно. На целенаправленном переборе этих вариантов основан симплекс-метод линейного программирования. Подробное изложение можно найти в книге, например, в
этой книге.