Сходимость QR-алгорифма
29. Вообще говоря,
стремятся к верхней треугольной форме при несколько менее ограничительных условиях, необходимых для сходимости LR-алгорифма. Прежде чем детально рассматривать сходимость, укажем на одну небольшую разницу между сходимостями этих двух методов.
Если
верхняя треугольная, то в
-алгорифме мы имеем
следовательно,
при всех
Это не так в QR-алгорифме, если нам нужно, чтобы
имела положительные диагональные элементы. В самом деле, положив
имеем
Следовательно, хотя
имеет те же самые диагональные элементы, что и А и наддиагональные элементы умножаются на комплексный множитель, равный по модулю единице. Поэтому очевидно, что мы не можем ожидать, что матрицы
стремятся к пределу в буквальном смысле, если только не все собственные значения вещественны и положительны. Множитель, по модулю равный единице, несуществен, и мы будем говорить, что матрицы
«в основном» сходятся, если асимптотически
при некоторой унитарной диагональной
Как в § 5, мы сначала рассмотрим случай матрицы третьего порядка с
так что
имеет вид (5.5). Факторизацию удобно осуществлять при помощи процесса ортогонализации Шмидта с нормировкой (гл. 4, § 54). Первый столбец
поэтому равен первому столбцу
нормированному так, что его евклидова норма равна единице. Его компоненты находятся в отношениях
Если предположить, что не равен нулю, то эти элементы обязательно будут в отношении
Если считать, что все диагональные элементы всех
должны быть положительными, то первый столбец
принимает асимптотически вид
что дает сходимость в основном к первому столбцу унитарной матрицы, полученной при факторизации
Если
равен нулю, но
нет, то компоненты первого столбца
будут находиться в отношении
Подобное явление встречается в связи с
-техникой.
Заметим, что обращение в нуль
безразлично для
-алгорифма, в то время как это вызывает расходимость
-алгорифма. «Случайный» срыв
-процесса, вызванный тем, что
при некотором
обратилось в нуль, не имеет аналога в QR-технике.
Мы могли бы продолжать наш элементарный анализ, чтобы выяснить асимптотическое поведение второго и третьего столбцов
но это значительно более трудно, чем в
-алгорифме. Ясно, что мы можем ожидать, что
будут в основном сходиться к унитарному сомножителю