Виды сходимости:
- последовательность, сходящаяся к x*;
Линейная:
Квадратичная:
Кубическая:
Сходимость алгоритма:
Линейная для исходного алгоритм
Квадратная со сдвигами с несимметричной матрицей
Кубическая со сдвигами с симметричной матрицей
Сложность алгоритма:
QR разложение плотной матрицы NxN (итерация): , итоговая сложность , k - количество итераций
QR разложение трёхдиагональной матрицы NxN (итерация): , со сдвигами число итераций O(n), итоговая сложность
Почему:
Трехдиагональная:
При QR разложении для плотной матрицы обнуляются все элементы для столбца под диагональю, для трехдиагональной это всего 1 элемент.
Сдвиги:
Сдвиги увеличивают относительную разницу между собственными значениями
QR алгоритм чувствителен к отношению собственных чисел. Чем ближе к нулю тем быстрее сходимость.
Примеры сдвигов:
Рэлея: вычитаем последний элемент
Уилкинсона: вычисляем собственные значения матрицы 2x2 внизу справа через дискриминант, выбираем значение ближайшее к