Реализация сингулярного разложения. Алгоритмы QR алгоритм начинается с разложения матрицы по Грамму-Шмидту, затем меняются местами сомножители Эта матрица подобна первоначальной, Этот процесс продолжается, причем собственные значения не изменяются Эта формула описывает QR алгоритм без сдвигов.
Обычно время которое тратится на такой процесс пропорционально кубу размерности матрицы n3. Необходимо процесс ускорить, для чего используется предварительное приведение матрицы А к форме Хессенберга Матрица А хессенбергова верхняя хессенбергова если для j i 1 сохраняется одна диагональ ниже главной диагонали.
Если матрица симметричная то хессенбергова матрица становится трехдиагональной. а также используется алгоритм со сдвигом. Форма Хессенберга представляет из себя верхнюю треугольную матрицу верхняя форма Хессенберга у которой сохранена одна диагональ ниже главной, а элементы ниже этой диагонали равны нулю. Если матрица симметрична, то легко видеть, что матрица Хессенберга превращается в трехдиагональную матрицу Симметричная матрица А есть трехдиагональная при для i-j 1. Трехдиагональная матрица это частный случай хесенберговой матрицы При использовании матрицы Хессенберга время процесса пропорционально n2, а при использовании трехдиагональной матрицы n. Можно использовать другие соотношения где Qs унитарная, а Ls нижняя треугольная матрица.
Такой алгоритм носит название QL алгоритма. В общем случае, когда все собственные значения матрицы различны, последовательность матриц As имеет пределом нижнюю треугольную матрицу, диагональные элементы которой представляют собой собственные значения матрицы А, расположенные в порядке возрастания их модулей.
Если матрица А имеет кратные собственные значения, то предельная матрица не является треугольной, а содержит диагональные блоки порядка p, соответствующие собственному числу кратности p. В общем случае, наддиагональный элемент матрицы As на s-ом шаге асимптотически равен, где kij постоянная величина. Сходимость QL алгоритма вообще говоря недостаточна.
Сходимость можно улучшить, если на каждом шаге вместо матрицы As использовать матрицу As-ksI QL алгоритм со сдвигом. Последовательность вычислений в этом случае описывается следующими соотношениями которые определяют матрицу. При этом асимптотическое поведение элемента определено соотношением, а не, как прежде. Если сдвиг ks выбрать близко к величине наименьшее собственное значение, то в пределе внедиагональные элементы первой строки будут очень быстро стремиться к нулю. Когда ими можно пренебречь, элемент с рабочей точностью равен, остальные являются собственными значениями оставшейся матрицы n-1-го порядка.
Тогда, если QL алгоритм выполнен без ускорения сходимости, то все равно, и поэтому автоматически можно выделить величину сдвига ks. Если матрица А эрмитова, то очевидно, что и все матрицы Аs эрмитовы если А действительная и симметричная, то все Qs ортогональны и все Аs действительны и симметричны. 2.2.