Связь методов Гивенса и Хаусхолдера

7. Как метод Гивенса, так и метод Хаусхолдера дают приведение А о к верхней матрице Хессенберга при помощи ортогонального преобразования подобия. Покажем, что матрицы, полученные при помощи этих двух преобразований, совпадают с точностью до множителя ±1 в каждом столбце. Сначала докажем следующую несколько более общую теорему, которая понадобится нам впоследствии.

Если где унитарные, верхние матрицы Хессенберга, и если первый столбец совпадает с первым столбцом то, вообще говоря,

где диагональная матрица, элементы которой по модулю равны единице.

Нам надо только показать, что если

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

Приравнивая первые столбцы (7.2), имеем

Следовательно, в силу унитарности

Первое уравнение дает а второе

так что 52 определен с точностью до множителя

Приравнивая вторые столбцы (7.2), имеем

и следовательно,

Первые два уравнения дают третье —

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

Заметим, что если мы потребуем, чтобы были вещественными и положительными, то единственным образом определяются первым столбцом Доказательство не проходит, если какой-либо из равен нулю, так как тогда есть произвольный нормированный вектор, ортогональный Теперь эквивалентность методов Гивенса и Хаусхолдера следует, если мы заметим, что первый столбец матрицы каждого из преобразований равен Это вытекает из того, что в методе Гивенса нет вращений, включающих первую плоскость, и все векторы в методе Хаусхолдера имеют равный нулю первый элемент. Эквивалентность симметричных методов Гивенса и Хаусхолдера является, конечно, частным случаем только что доказанного результата. Доказательство следует сравнить с доказательством § 53 гл. 4. Снова мы подчеркиваем, что хотя матрицы полного преобразования Гивенса и Хаусхолдера в основном одинаковы, матрицы, при помощи которых получаются нули в столбце, различны для этих двух методов. Доказательство почти совпадает с соответствующим доказательством, данным в гл. 4, § 53.

Несмотря на формальную эквивалентность этих двух преобразований и на тот факт, что оба они «устойчивы», на практике ошибки округления могут привести к различным окончательным результатам. Это не удивительно, так как мы видели в гл. 5, § 28, что даже если применить два раза к одной и той же матрице метод Гивенса, работая со слегка разной точностью, то можно получить сильно отличающиеся трехдиагональные матрицы. Мы видели, что такие расхождения двух вычислений должны иметь место, если на каком-либо основном шаге все элементы, которые нужно аннулировать, малы. Заметим, что согласно (7.5) и (7.8) элемент

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