Метод Хаусхолдера

3. Подобным же образом имеем естественную аналогию метода Хаусхолдера, описанного в главе 5. Снова здесь основных шага, и непосредственно перед шагом имеет, например, для следующую форму:

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

где единичный вектор с компонентами. Следовательно, имеем

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

Снова, так же как в гл. 5, § 29, все формулы будут иметь простейший вид, если где единичный вектор, имеющий компонент, из которых первые равны нулю. Тогда мы имеем

где

В (3.5) обозначает элемент Новый элемент равен Знак выбирается обычным образом.

4. Так как теперь нет симметрии, умножения справа и слева на нужно рассматривать отдельно. При умножении слева имеем

а при умножении справа —

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

где первые элементов равны нулю из-за нулей Тогда имеем

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

Вектор не имеет нулевых компонент. Так как первые компонент равны нулю, при вычислении требуется умножений. Окончательно имеем

и это требует еще умножений. Заметим, что в (4.4) и (4.6) требуется вектор а сам необходим лишь для вычисления получаемого последовательно по мере вычисления Эту трудность можно обойти, если работать с но ценой извлечения квадратного корня из

Если матрица размещена во внешней памяти и главным требованием является экономия переносов, то следующая формулировка, вероятно, наиболее удобна. Определим векторы и скаляр соотношениями

Затем вычислим из соотношений

Здесь много общего с симметричным случаем гл. 5, §§ 29 и 30, но член теперь нельзя разделить между двумя другими членами.

Число умножений для полного приведения, с использованием любого из этих вариантов, равно приблизительно

В симметричном варианте метода Хаусхолдера число умножений равно

Снова замечаем, что метод Хаусхолдера требует вдвое меньше умножений, чем метод Гивенса.