Триангуляризации элементарными устойчивыми матрицами типа М

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

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

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

Для каждого значения от до :

(i) Сравниваем Если переставляем элементы и

(ii) Вычисляем и записываем как на место Если на шаге (i) имела место перестановка, то ставится звездочка.

(iii) Для каждого значения от до

Вычисляем и записываем на место

(iv) Вычисляем и записываем на место

На практике мы можем пожертвовать последним разрядом в каждом и запоминать «единицу», если имела место перестановка перед вычислением и «нуль» в противном случае. Очевидно, что мы запомнили достаточное количество информации для раздельной обработки правой части.

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