Глава II. Алгоритм Гаусса и некоторые его применения

§ 1. Метод исключения Гаусса

1. Пусть дана система  линейных уравнений с  неизвестными  и правыми частями :

                             (1)

В матричной форме эта система может быть записана так:

.                                                                 (1')

Здесь , — столбцы и квадратная матрица коэффициентов.

Если  — неособенная матрица, то можно написать:

                                                          (2)

или в развернутом виде:

    .          (2')

Таким образом, задача вычисления элементов обратной матрицы  эквивалентна задаче решения системы уравнений (1) при любых правых частях . Элементы обратной матрицы определяются формулами (25) главы I. Однако фактическое вычисление элементов матрицы  по этим формулам при большом  весьма затруднительно. Поэтому большое практическое значение имеют эффективные методы вычисления элементов обратной матрицы и, следовательно, решения системы линейных уравнений.

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

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

.                          (3)

Коэффициенты при неизвестных и свободные члены в последних  уравнениях определяются формулами

,    ,  ( ).             (3')

Пусть . Тогда таким же образом мы исключим   из послед них  уравнений системы (3) и получим систему уравнении

                   (4)

При этом новые коэффициенты и правые части связаны с предыдущими формулами:

     ().          (5)

Продолжая этот алгоритм далее, мы на ()-м этапе приведем исходную систему (1) к треугольной рекуррентной системе

                 (6)

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

3. Выразим коэффициенты и правые части приведенной системы через коэффициенты и правые части исходной системы (1). При этом мы не будем предполагать, что в процессе приведения все числа , , …,  оказываются отличными от нуля, а рассмотрим общий случай, когда первые  из этих чисел отличны от нуля:

, , …,     ,                (7)

что дает возможность (на -м этапе приведения) привести исходную систему уравнений к виду:

                            (8)

Матрицу коэффициентов в этой системе уравнений обозначим через :

.                 (9)

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

               (10)

Из этих формул, учитывая структуру (9) матрицы , найдем:

,                                (11)

    .             (12)

Деля почленно второе из этих равенств на первое, получим основные формулы

                .                   (13)

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

,         ,    ,….                (14)

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

,    ,…., .                              (15)

Тогда из (14) находим:

,    ,

, …,  .                              (16)

Для того чтобы в алгоритме исключения Гаусса можно было последовательно исключить  нужно, чтобы все величины (16) были отличны от нуля, т. е. чтобы выполнялись неравенства (15). В то же время формулы для  имеют смысл, если выполняется только последнее из условий (15).

4. Пусть матрица коэффициентов в системе уравнений (1) имеет ранг . Тогда надлежащей перестановкой уравнений и изменением нумерации неизвестных можно добиться выполнения неравенств

    .                                     (17)

Это позволяет последовательно исключить  и получить систему уравнений

                                        (18)

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

   

и матрица  получающаяся из матрицы  после применения -этапного алгоритма исключения Гаусса, имеет вид

.                         (19)

Последние  уравнений (18) сводятся к условиям совместности

   .                                                     (20)

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

               .                   (21)

В частности, условия совместности (20) сводятся к известным условиям

                              .                      (22)

Если , т. е. матрица  неособенная, и

       ,

то при помощи алгоритма Гаусса можно последовательно исключить  и привести систему уравнений к виду (6).