Системы линейных алгебраических уравнений (СЛАУ)

ТЕМА №1

ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ

Системы линейных алгебраических уравнений (СЛАУ)

Рассмотрим систему линейных уравнений следующего вида:

(1)

- матрица системы размерности .

- вектор свободных членов (правых частей) размерности .

- вектор независимых переменных размерности .

СЛАУ в матричной форме: .

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

Если в СЛАУ все свободные члены , то система – однородная. В противном случае – неоднородная.

Решением системы уравнений называется такой вектор , при подстановке которого все уравнения системы превращаются в верные равенства. Если система имеет хотя бы одно решение, то она совместна. Иначе – несовместна.

Если система имеет единственное решение, то она называется определенной. Иначе – неопределенной.

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

Количество линейно независимых уравнений называется рангом СЛАУ (рангом матрицы ). Обозначается .

Возможны следующие варианты.

1.

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

Неоднородная система неразрешима, если . Если , то система имеет единственное решение.

2.

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

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

Рассмотрим систему (1). Выразим первые переменных:

(2)

(2) представляет собой общее решение (1).

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

Частным случаем частного решения является базисное решение СЛАУ. Оно формируется следующим образом: все свободные переменные полагаются равными 0, при этом базисные становятся равны свободным членам. Если все базисные переменные оказываются неотрицательными, то говорят о неотрицательном базисном решении.

3.

В этом случае СЛАУ является переопределенной. Среди уравнений системы обязательно есть линейно зависимые. Вычеркнув их, придем к одному из вышеописанных вариантов.

В рамках методов оптимизации нас будут интересовать, как правило, системы второго варианта.

Метод Гаусса

Метод Гаусса является методом определения ранга системы, а для систем первого варианта – методом отыскания решения.

Будем рассматривать СЛАУ второго варианта . Предположим для определенности, что все уравнения системы линейно независимы.

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

а) перестановка строк;

б) умножение строки на число;

в) замена строки на ее сумму с другой строкой, умноженной на некоторое число.

Пример

Найти общее, частное и базисное решение следующей системы:

.

Решение. Составим расширенную матрицу системы. Будем получать для определенности столбцы единичной матрицы на месте первого и второго столбца исходной матрицы. Для этого сначала разделим всю первую строку на «2»:

.

Теперь получим на пересечении второй строки и первого столбца «0» вместо «3». Для этого к каждому элементу второй строки прибавим соответствующий элемент первой строки, умноженный на «-3»:

.

Теперь получим «1» на пересечении второго столбца и второй строки. Для этого всю вторую строку поделим на элемент, стоящий на пересечении, т.е. на «0,5»:

.

Теперь получим «0» на пересечении первой строки и второго столбца (на месте «-1,5»). Для этого к каждому элементу первой строки прибавим соответствующий элемент второй строки, умноженный на «1,5»:

.

Процесс закончен. В получившейся матрице первый и второй столбцы – это столбцы единичной матрицы. Этой матрице соответствует система:

.

Общее решение:

.

Переменная является свободной, переменные - базисные.

Частное решение:

.

Базисное решение:

.

Оно является неотрицательным.