44. Сходимость и сложность QR алгоритма.

Виды сходимости:

         - последовательность, сходящаяся к x*;

Линейная:

Квадратичная:         

Кубическая:

Сходимость алгоритма:

Линейная для исходного алгоритм

Квадратная со сдвигами с несимметричной матрицей

Кубическая со сдвигами с симметричной матрицей

Сложность алгоритма:

QR разложение плотной матрицы NxN (итерация): , итоговая сложность , k - количество итераций

QR разложение трёхдиагональной матрицы NxN (итерация): , со сдвигами число итераций O(n), итоговая сложность

Почему:

Трехдиагональная:

При QR разложении для плотной матрицы обнуляются все элементы для столбца под диагональю, для трехдиагональной это всего 1 элемент.

Сдвиги:

Сдвиги увеличивают относительную разницу между собственными значениями

QR алгоритм чувствителен к отношению собственных чисел. Чем ближе  к нулю тем быстрее сходимость.

Примеры сдвигов:

Рэлея: вычитаем последний элемент

Уилкинсона: вычисляем собственные значения матрицы 2x2 внизу справа через дискриминант, выбираем значение ближайшее к