Сравнение LR- и QR-алгорифмов

47. Сейчас сравним относительные достоинства LR- и QR- алгорифмов при приложении их к матрицам Хессенберга. По моему мнению, следует отдать предпочтение унитарным преобразованиям со значительно большей уверенностью, чем в предыдущих случаях, когда мы сталкивались с подобным выбором Свойства сходимости LR-алгорифма с перестановками далеко не удовлетворительны, и требуется довольно значительное число преобразований, так что обусловленность матриц может ухудшаться, а недиагональные элементы увеличиваться. С другой стороны, для -алгорифма легко показать, используя метод гл. 3, § 45, что в точности унитарно подобна где мала. Например, можно показать, что при использовании арифметики с плавающей запятой с накоплением скалярных произведений, где это нужно, Более того, оказалось, что количество итераций, необходимых при использовании QR, как правило меньше, чем при

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

В § 32 мы заметили, что если матрица имеет собственных значений, равных по абсолютной величине, то на каждом этапе итераций при отсутствии сдвига на диагонали могут возникнуть квадратные блоки порядка Это может создать впечатление, что отделение таких групп представляет трудности. Однако при использовании сдвигов это обычно неверно. Например, для каждой из матриц

был применен обычный способ двойного сдвига для Хотя модуль собственных значений матриц равен единице, среднее число итераций на собственное значение меньше трех. Сдвиги определяются стандартным способом, и модифицированные матрицы уже не имеют равных по модулю собственных значений, так что все трудности пропадают. Это не так для матрицы (32.6), характеристическое уравнение которой есть Эта матрица инвариантна по отношению к QR, и оба сдвига, определенные обычным способом, равны нулю. Однако если мы выполним одну итерацию с произвольным сдвигом, то процесс будет сходиться. Кроме того, если ( сомножитель в характеристическом уравнении, то это еще не означает, что нули этого сомножителя не будут разделяться при помощи -алгорифма. Если предположить, что другие сомножители таковы, что применяются ненулевые сдвиги, то процесс будет сходиться. Пример такого случая дает вторая матрица. Характеристический полином равен ( но после первой итерации обычный процесс определяет ненулевой сдвиг. Все пять собственных значений были определены с 12 десятичными знаками за 12 итераций.