Глава II. Вычисления в линейной алгебре

Речь пойдёт, в основном, о решении систем линейных уравнений вида A·X = b с квадратной невырожденной матрицей A Î M(n, F). Такие системы можно решать методом Гаусса, который состоит, как известно из курса алгебры, в последовательном приведении расширенной матрицы (A | b) системы A·X = b к каноническому ступенчатому виду. В случае квадратной невырожденной матрицы A каноническая матрица выглядит просто: (I_n | X), где I_n – единичная (n´ n)- матрица, а X – решение системы уравнений.

Вычислительные проблемы с методом Гаусса обусловлены двумя основными обстоятельствами. Первое обстоятельство: метод Гауссатребует достаточно много алгебраических операций. Оценим количество операций. Для обнуления остальных n – 1 элементов каждого столбца за счёт главного элемента этого столбца необходимо:

– произвести одно деление (вычислить обратный элемент к главному),

– выполнить 2·(n – 1)·k умножений (умножить все k ненулевых элементов строки главного элемента на вычисленный обратный и на обнуляемый элемент),

– произвести (n – 1)·k сложений (прибавить k ненулевых элементов сроки главного элемента к каждой из остальных строк).

Таким образом, всего требуется 1 + (n – 1)·[2·k + k] операций в каждом столбце, а всего для приведения (n´ n)- матрицы к каноническому виду потребуется n делений, = (n – 1)²·n умножений и вполовину меньше сложений, т.е. n + 1, 5·(n – 1)²·n операций.Видно, что общее количество операций имеет порядок n³. При выполнении большого объёма вычислений общая погрешность может значительно возрастать (даже погрешность суммы оценивается как сумма погрешностей). Значит, метод Гаусса даёт не точное, а лишь приближённое решение системы линейных уравнений, точность которого может быть далека от заданной предельной погрешности вычислений.