Сходимость QR-алгорифма

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

Если верхняя треугольная, то в -алгорифме мы имеем следовательно, при всех Это не так в QR-алгорифме, если нам нужно, чтобы имела положительные диагональные элементы. В самом деле, положив

имеем

Следовательно, хотя имеет те же самые диагональные элементы, что и А и наддиагональные элементы умножаются на комплексный множитель, равный по модулю единице. Поэтому очевидно, что мы не можем ожидать, что матрицы стремятся к пределу в буквальном смысле, если только не все собственные значения вещественны и положительны. Множитель, по модулю равный единице, несуществен, и мы будем говорить, что матрицы «в основном» сходятся, если асимптотически при некоторой унитарной диагональной

Как в § 5, мы сначала рассмотрим случай матрицы третьего порядка с

так что имеет вид (5.5). Факторизацию удобно осуществлять при помощи процесса ортогонализации Шмидта с нормировкой (гл. 4, § 54). Первый столбец поэтому равен первому столбцу нормированному так, что его евклидова норма равна единице. Его компоненты находятся в отношениях

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

принимает асимптотически вид

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

Заметим, что обращение в нуль безразлично для -алгорифма, в то время как это вызывает расходимость -алгорифма. «Случайный» срыв -процесса, вызванный тем, что при некотором обратилось в нуль, не имеет аналога в QR-технике.

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