Вычисление при помощи ортогональных преобразований

14. Метод вычисления Химана основан на умножении справа матрицы Хессенберга на элементарную матрицу типа (гл. 1, § 40 (iv)), причем элементы выбираются так, что последний столбец переходит в кратное Было показано, что для численной устойчивости в прежних ситуациях существенно правило выбора ведущего элемента, но анализ ошибок §§ 12, 13 показал, что в нашем случае это не важно, и использование больших множителей не дает вреднего эффекта. Подобным же образом можно видеть, что, хотя мы и делим элементы на никакого вреда от этого не происходит, как бы малы они ни были. Можно ввести перестановки, но они в этом случае не принесут пользы. Способ, каким они могут быть введены, станет ясным в следующем параграфе, когда мы будем рассматривать использование плоских вращений.

Хотя боязнь численной неустойчивости здесь неосновательна, но все же естественна мысль об использовании плоских вращений (см., например, Уайт, 1958). Метод вычисления состоит из основного шага, причем на шаге получается нуль в позиции последнего столбца. Конфигурация перед началом шага в случае имеет вид

Основной шаг состоит из умножениясправа на вращение в плоскости причем угол вращения выбран так, что становится нулем. Шаг состоит в следующем:

(i) Вычисляем

(ii) Вычисляем

(iii) Для всех от 1 до вычисляем и записываем на места соответственно.

(iv) Заменяем на на нуль. Очевидно, что мы заменили столбцы их линейными комбинациями, так что нули, введенные на более ранних шагах, сохранились.

Окончательная матрица имеет ту же форму, что и матрица, соответствующая методу Химана, а определитель А равен

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

Поэтому метод устойчив, но оценка хуже, чем для метода Химана с стандартными вычислениями с плавающей запятой. Из соотношений (12.3) — (12.5) имеем

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

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

Рассмотрим теперь какое-либо преобразование подобия матрицы Записав такое преобразование в виде видим, что между элементами имеются те же соотношения, что и между элементами . Оценку влияния возмущения на собственные значения А можно рассматривать для самого хорошо обусловленного диагонального преобразования подобия матрицы А. Поэтому ясно, что перед применением метода Химана не нужно уравновешивать А. Ни одно из этих замечаний не применимо к использованию ортогональных преобразований или элементарных преобразований подобия с перестановками.