Практическое применение QR-алгорифма

35. Типичный шаг -алгорифма требует выполнения факторизации Для теоретических целей было удобно думать о ней как об ортонормализации Шмидта столбцов Как было указано в гл. 4, § 55, на практике это обычно приводит к которая отнюдь не ортогональна. В этом случае численная устойчивость, обычно присущая ортогональным преобразованиям подобия, может быть потеряна. На практике обычно определяем такую матрицу что

Матрица не определяется явно, чаще она определяется в виде произведения либо плоских вращений, либо матриц отражения, используемых при приведении матрицы к треугольному виду по методу Гивенса или Хаусхолдера соответственно. Матрица вычисляется затем при помощи последовательных умножений справа на транспонированные сомножители для Мы показали в гл. 3, §§ 26, 35, 45, что произведение вычисленных сомножителей будет почти точно ортогональным и что вычисленная будет близка к матрице, полученной при точном умножении на вычисленные сомножители. Следовательно, можно показать, что вычисленная близка к точному ортогональному преобразованию вычисленной (Мы не можем показать, что вычисленная близка к такому преобразованию вычисленной которое получилось бы при точном выполнении шага, и, вообще говоря, это неверно.)

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

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

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