Метод Хаусхолдера
29. В течение нескольких лет казалось, что процесс Гивенса, вероятно, должен быть самым эффективным методом приведения матрицы к трехдиагональному виду, но в 1958 г. Хаусхолдер высказал мысль, что это приведение можно выполнить более эффективно, используя матрицы
отражения вместо плоских вращений. В гл. 6, § 7 покажем, что преобразования Гйвенса и Хаусхолдера в основном совпадают.
Это приведение состоит из 
шагов, на 
из которых получаются нули в 
строке и 
столбце, причем сохраняются нули, полученные на предыдущих шагах. Структура элементов перед 
шагом иллюстрируется схемой (29.1) для случая 
Здесь 
вектор, имеющий 
компонент, 
трехдиагональная матрица порядка 
квадратная матрица порядка 
. Матрица 
преобразования может быть представлена в виде
где 
вектор единичной длины, имеющий 
компонент. Следовательно, имеем
где
Если выбрать 
так, что 
будет нулевым, за исключением первой компоненты, то 
в первых 
строках и столбцах будет трехдиагональной. Итак, мы представили условие, определяющее 
в стандартной форме, рассмотренной в гл. 3, §§ 37, 38, но приведенные там результаты удобно переформулировать на языке новых обозначений. Обозначим текущий элемент 
матрицы 
через 
опуская индекс 
Будем предполагать, что запоминается лишь верхний треугольник элементов, и представим все формулы в зависимости от их значений. Формулы становятся наиболее простыми, если мы представим матрицу 
в виде 
где 
есть вектор единичной длины, имеющий 
компонент, из которых первые 
равны нулю. Тогда имеем
где
В уравнении, определяющем 
знак 
берется равным знаку 
так что при сложении не может иметь место сокращение. Новое значение 
равно 
сравним это с методом Гивенса, для которого все внедиагональные элементы трехдиагональной матрицы, полученные по нашим формулам, неотрицательны.) Заметим, что если все элементы, которые должны быть исключены на данном шаге, уже равны нулю, то матрица преобразования не будет единичной, как можно было бы ожидать. (Действительно, I не является матрицей отражения согласно нашему определению.) Матрица преобразования отличается от единичной тем, что 
диагональный элемент равен —1 вместо 
Мы можем договориться, что в этом случае будем опускать соответствующее преобразование.
