Главная > Математика > Алгебраическая проблема собственныx значений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Кубическая сходимость QR-алгорифма

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

Если мы положим

то из общей теории § 32 мы знаем, что если не используются сдвиги, то стремится к нулевой матрице, собственные значения матрицы стремятся к соответствующим а все собственные значения матрицы стремятся к Предположим, что мы достигли стадии, когда

Мы знаем, что ранг равен на всех шагах. Из (54.4) следует, что ранг также равен Следовательно, мы должны иметь

что

Имеем

Эти результаты показывают, что норма недиагональных элементов порядка и что все диагональные элементы отличаются от на величины порядка В частности,

и мы выводим, что

Рассмотрим теперь эффект выполнения одного шага QR со сдвигом Так как порядка не зависят от то из общей теории сходимости (§ 19) можно ожидать, что элементы будут умножаться на множитель порядка но полезно дать точное доказательство. Пусть это такая ортогональная матрица, что верхняя треугольная. Тогда, написав

имеем

и

Следовательно,

и из

Следовательно, окончательно имеем

Таким образом, кубическая сходимость доказана. Заметим, что это означает, что все совпадающих собственных значений будут найдены одновременно, так что совпадение собственных значений является скорее преимуществом, чем недостатком.

На практике мы начинаем применять сдвиг значительно раньше, чем в нашем доказательстве, обычно тогда, когда установился один двоичный знак

<< Предыдущий параграф Следующий параграф >>
Оглавление