Анализ ошибок метода Гаусса

24. Шаги, рассматриваемые в методе Гаусса с перестановками, охватываются общим анализом гл. 3, § 48, за исключением того, что мы должны обосновать внесение нулей на соответствующие позиции в преобразованных матрицах. Но тот первый анализ, который мы дали, формально самый простой, поэтому мы предполагаем привести здесь довольно подробное описание так, чтобы читатель мог понять все существенные особенности.

Дадим сначала более общий анализ, который относится к вычислениям как с фиксированной, так и с плавающей запятой. Для удобства анализа предположим, что исходная матрица переставлена так, как описано в § 22, чтобы не требовать перестановки. Наш анализ будет относиться лишь к вычисленным матрицам и следовательно, не возникнет никакой путаницы, если обычные черточки будут всюду опущены.

Рассмотрим теперь изменение элементов в позиции в последовательных матрицах .

(i) Если то этот элемент изменяется на шагах ; после этого он становится элементом ведущей строки и в дальнейшем не изменяется. Мы можем написать

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

(ii) Если то этот элемент изменяется на шагах и, наконец, на шаге когда он становится нулем и используется для вычисления Поэтому уравнения будут такими же, как (24.1), за исключением того, что последним будет уравнение

Кроме того, имеем

Представляя это последнее уравнение в таком же виде, как уравнения (24.1), получаем

Заметим, что нуль в левой части этого уравнения соответствует нулю, который вставляется в позицию после преобразования. Складывая уравнения (24.1), сокращая общие члены и перегруппировывая,

имеем для

а для с включенным уравнением (24.4)

Аналогично для правой части системы имеем

откуда

Уравнения (24.5), (24.6) и (24.8) выражают тот факт, что

где

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

Выделим два главных следствия из этих результатов:

I. Точный определитель который равен

есть точный определитель .

II. Точное решение системы есть точное решение системы