Триангуляризация, использующая матрицы отражения

46. Теперь обратимся к другим методам триангуляризации, существование которых указывалось в § 15. Сначала опишем метод, принадлежащий Хаусхолдеру и основанный на использовании матриц отражения, и чтобы иметь возможность сравнить его с нашим общим анализом, остановимся на преобразовании. Всего в методе основных шагов, и после окончания шага матрица в своих первых столбцах будет уже верхней треугольной. Мы можем написать

где верхняя треугольная матрица порядка На шаге используется матрица вида

вместо матрицы использованной в методе Гаусса. Имеем

так что здесь изменяется лишь Мы должны выбрать и так, чтобы первый столбец матрицы был нулевым, кроме своего первого элемента. Эту задачу мы рассматривали в гл. 3, §§ 37—45. Если обозначим элементы первого столбца через

опуская для простоты верхний индекс, то можем написать

где

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

Матрица вычисляется из выражения

по шагам:

Если во время триангуляризации нам известна правая часть, то на основном шаге мы можем умножить ее на Однако если мы

хотим решать уравнение с правой частью, которая определяется после триангуляризации, то должны сохранить всю необходимую информацию. Наиболее удобно хранить элементов вектора и на месте, занимаемом первым столбцом Так как из то все элементы, кроме уже на месте. Это означает, что мы дополнительно должны запомнить диагональные элементы верхней треугольной матрицы; они несколько иначе, чем остальные элементы, используются в обратной подстановке, поэтому это не так существенно. Нам также нужны значения, равные но они могут быть определены из соотношений Если принимается последний вариант, то, помимо места для матрицы нужно дополнительно иметь ячеек памяти. Будем называть этот метод триангуляризацией Хаусхолдера.