Ускорение сходимости QR-, QL-алгоритмов. Сдвиг по отношению Рэллея, по Уилкинсону

Рассмотрим вопрос об ускорении сходимости -алгоритма. Можно доказать, что

, .

Из этого вытекает, что если матрица - вырожденная, то -алгоритм сходится за 1 шаг (поскольку для вырожденной матрицы минимальное по модулю собственное значение , тогда ). Тогда для ускорения сходимости -алгоритма можно использовать следующую стратегию. Если - невырожденная, то вместо целесообразно было бы рассмотреть матрицу (где - минимальное по модулю собственное значение ). Тогда у матрицы минимальное по модулю собственное значение равно 0. Действительно, если - собственная пара матрицы , то - собственная пара матрицы . Покажем это:

.

Однако, чаще всего для данной матрицы собственное значение неизвестно. Но в -алгоритме приближением к на -м шаге является элемент матрицы , именно его и можно выбрать в качестве сдвига:

. (10)

Учитывая, что можно представить в виде

,

т.е. значение совпадает со значением отношения Рэллея для матрицы и вектора , то предложенный вид (10) сдвига называется сдвигом по отношению Рэллея.

Рассмотрим случай трехдиагональной симметричной матрицы:

.

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

В случае сдвига по отношению Рэллея собственное значение приближается при помощи . Но это собственное значение можно приблизить лучше.Рассмотрим для этого главную подматрицу порядка 2 исходной матрицы:

.

В качестве сдвига выберем собственное значение этой матрицы, которое будет ближе к . Такой сдвиг называется сдвигом по Уилкинсону.

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