Linear00

ЛИНЕЙНАЯ АЛГЕБРА

Николай Гордеев

Введение.

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

Метод Гаусса алгоритм решения систем линейных уравнений, названный в честь К.Ф. Гаусса. Однако, этот метод был известен в Китае ещ¼ в середине II века до нашей эры. Изложен в древнекитайском трактате "Математика в девяти книгах".

Cистемы линейных уравнений.

1

i < j) .

Определение 0.4. Общим решением системы (0.2) называется последовательность k формул вида

вверх по системе"(0.2)), определяют соотношения между элементами любой последовательности (®1; : : : ; ®n) 2 Kn, являющейся решением x1 = ®1; : : : ; xn = ®n

системы (0.2).

Åñëè k = n, то формулы (0.3) имеют вид xi = fi, ãäå fi элементы поля K,

вычисляемые по правилам (0.4), без членов вида ¡cik+1xk+1 ¡ ¢ ¢ ¢ ¡ cinxn. Â ýòîì

случае система (0.2) имеет единственное решение.

Пусть k < n. Тогда переменные xk+1; : : : ; xn называются свободными. В этом случае любая последовательность ¯1; : : : ; ¯n¡k 2 K определяет решение системы (0.2) :

3

Это следует из определения построения общего решения (0.4). Кроме того, любое решение системы (0.2) может быть записано в виде (0.5). Если множество свободных переменных не пусто, то множество решений системы (0.2) равномощно множеству Kn¡k. Действительно, любая (n¡k)- последовательность ¯1; : : : ; ¯n¡k 2 K однозначно

определяет решение системы (0.2). Таким образом, если k < n, т.е., если множество

свободных переменных не пусто, множество решений системы (0.2) содержит более одного решения, а если к тому же поле K бесконечно, то множество решений

системы (0.2) также бесконечно. Суммируя, сказанное выше получаем

Предложение 0.2. Трапециевидная система линейных уравнений (0.2) - разрешима. Она имеет единственное решение тогда и только тогда, когда k = n.

Åñëè k < n, то множество е¼ решений имеет вид

f(f1(¯1; : : : ; ¯n¡k); : : : ; fk(¯1; : : : ; ¯n¡k); ¯1; : : : ; ¯n¡k) j (¯1; : : : ; ¯n¡k) 2 Kn¡kg:

В частности, если K бесконечное поле, то и множество решений системы (0.2) при k < n- бесконечно.

Элементарные преобразования систем линейных уравнений.

Определение 0.5. Следующие преобразования систем линейных уравнений называются элементарными:

I. перестановка местами двух уравнений;

II. перестановка местами двух(переменных (например, от системы

2x1 + 3x2 = 7 x1 ¡ x2 = 3

3x2 + 2x1 = 7 ); ¡x2 + x1 = 3

III. почленное умножение одного из уравнений на ненулевой элемент поля (например, вместо i-того уравнения в (0.1)

ai1x1 + ai2x2 + ¢ ¢ ¢ + ainxn = bi

записываем уравнение

®ai1x1 + ®ai2x2 + ¢ ¢ ¢ + ®ainxn = ®bi

для некоторого ® 2 K; ® =6 0);

IV. почленное прибавление к i-тому уравнению j-òîãî (i =6 j), умноженного (почленно) на некоторый элемент поля K (т.е. вместо уравнения

4

ai1x1 + ai2x2 + ¢ ¢ ¢ + ainxn = bi

записываем уравнение

(ai1 + ¸aj1)x1 + (ai2 + ¸aj2)x2 + ¢ ¢ ¢ + (ain + ¸ajn)xn = bi

для некоторого ¸ 2 K);

V. вычеркивание и приписывание нулевых уравнений, т.е. уравнений вида

0x1 + 0x2 + ¢ ¢ ¢ + 0xn = 0:

Замечание 0.1. При обозначении переменных в системах (0.1), (0.2) мы использовали естественную нумерацию слева направо. Однако, при перестановке переменных нумерация меняется. Следует сохранять первоначально принятую нумерацию и учитывать е¼ при описании множества решений в Kn. Например,

единственным решением системы

(

3x2 + 2x1 = 7 ¡x2 + x1 = 3

будет x2 := 15 ; x1 := 165 . Множество решений этой системы будем записывать, используя начальный порядок переменных f(165 ; 15 )g ½ K2.

Пусть S1 система линейных уравнений от n переменных над полем K, à S2 система, полученная из S1 одним из элементарных преобразований. Символом

S1 Ã S2

будем обозначать элементарное преобразование, переводящее систему S1 в систему

S2. Если нужно указать, какое именно элементарное преобразование использовано, будем ставить соответствующий номер преобразования:

Предложение 0.3. Каждое из элементарных преобразований обратимо, т.е. для любого элементарного преобразования S1 Ã S2 существует элементарное

преобразование S2 Ã S1.

Отметим, что тождественное преобразование также является элементарным; например, преобразование типа III при ® = 1 èëè òèïà IV ïðè ¸ = 0.

5

Определение 0.6. Две системы линейных уравнений от n переменных над полем K называются эквивалентными, если множества их решений совпадают.

Предложение 0.4. Любая последовательность элементарных преобразований переводит систему линейных уравнений в эквивалентную.

Доказательство. Очевидно, что достаточно проверить утверждение только для случая одного элементарного преобразования S1 Ã S2. Из определений 0.1, 0.5

следует, что любое решение системы S1 является также решением системы S2. Поскольку существует элементарное преобразование S2 Ã S1 (предложение 0.3), любое решение системы S2 также будет решением системы S1. Таким образом, множества решений систем S1; S2 совпадают, а значит это эквивалентные системы (определение 0.6). ¤

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

Доказательство. Пусть (0.1) ненулевая разрешимая система. Тогда существует хотя бы один коэффициент aij 6= 0 (действительно, если все коэффициенты нули,

а система ненулевая, то в системе имеется уравнение 0x1 + 0x2 + ¢ ¢ ¢ + 0xn = bi 6=

0). Элементарными преобразованиями типа I, II можно добиться, чтобы член aijxj

располагался в левом верхнем углу системы. Поэтому можно сразу предполагать, что a11 6= 0.

Далее проведем доказательство нашего утверждения индукцией по m ( = число уравнений). Для m = 1 утверждение очевидно ( одно уравнение это трапециевидная

система). Предположим, что утверждение теоремы истинно для всех ненулевых разрешимых систем, у которых число уравнений меньше, чем m. Рассмотрим систему

(0.1), для которой a11 6= 0. Для любого i > 1 к строке с номером i прибавим первую

строку, умноженную на ¡ai1

a11 . Получим систему

6

для некоторых a0ij; b0 2 K. Ввиду предложения 0.4, система линейных уравнений (0.6)

Следствие 0.1. Однородная система уравнений над полем K, у которой число уравнений m меньше числа переменных n имеет ненулевое решение. Если при этом, поле K бесконечно, то множество решений такой системы бесконечно.

Доказательство. Однородная система уравнений разрешима ( (0; : : : ; 0) является

решением такой системы). Ввиду теоремы 0.1 такая система приводится к эквивалентной трапециевидной системе. ¤

Алгоритм Гаусса.

Доказательство теоремы 0.1 содержит алгоритм, позволяющий выяснить разрешимость ненулевой1 системы линейных уравнений (0.1) и в случае е¼ разрешимости найти общее решение системы. А именно, алгоритм состоит из следующих шагов:

Замечание 0.2. В схеме, приведенной выше, Шаги представляют собой набор элементарных действий, порядок выполнения которых, не определ¼н здесь

однозначно. Например, в Шаге 1 поиск коэффициента aij =6 0 можно организовать следующим образом: для фиксированного номера переменной j = 1; : : : ; n, меняя номер уравнения i = 1; : : : ; m, проверяем, является ли нулем соответствующий коэффициент aij.

1множество решений нулевой системы линейных уравнений это вс¼ множество Kn

7

проделать очередной шаг алгоритма Гаусса, имеют вид

0x1 + 0x2 + ¢ ¢ ¢ + 0xn = bi

(è bi 6= 0 хотя бы для одного i). Следовательно, для разрешимости системы (0.1)

необходимым и достаточным условием является возможность приведения системы к трапециевидной форме (0.2) методом Гаусса.

Ниже будем обозначать:

(i) ¡ уравнение с номером i; [j] ¡ переменная с номером j: Элементарными преобразованиями приводим систему к трапециевидной форме:

9