Треугольное разложение с перестановкой строк

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

Мы опишем здесь эквивалент выбора главного элемента по столбцу в арифметике с фиксированной запятой. Он состоит из основных шагов причем на шаге мы определяем столбец строку Состояние в начале шага иллюстрируется случаем

Теперь основной шаг заключается в следующем.

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

(ii) Предположим, что есть максимум из Тогда записываем и переставляем целиком строки включая Округляем новое до одинарной точности, чтобы получить и записываем его на место

Для получения вычисляем и записываем его на место

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

(v) Вычисляем снова накапливая скалярное произведение и округляя его, чтобы получить Записываем на место

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

Заметим, что мы могли бы организовать обработку правой части таким же образом и для исключения Гаусса. Она включала бы перестановку целых строк на шаге (i) из § 34. Тогда мы могли бы выполнить раздельную обработку правой части с накоплением скалярных произведений.

В табл. 4 мы показываем треугольное разложение с перестановками для матрицы 4-го порядка с переставленными строками из табл. 1.

Таблица 4 (см. скан)

Продолжение табл. 4 (см. скан)

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