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

Прием двойного сдвига для LR

46. Можно описать, пренебрегая перестановками, подобный прием двойного сдвига для LR-алгорифма. Аналогичные (41.1) и (41.4) уравнения будут

и обозначив имеем

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

где В — верхняя матрица Хессенберга, то равна а В равна (гл. 6, § 11). По аналогии с алгорифмом QR будем вместо сомножителей искать сомножители

Первый столбец так же как и раньше, имеет только три отличных от нуля элемента выписанные в (41.11). Определим далее элементарную матрицу типа которая приводит первый столбец к кратному Очевидно, что первый столбец будет первым столбцом Наконец, вычисляем равную и приводим ее к форме Хессенберга, используя элементарные иеунитарные матрицы типа (гл. 6, § 8). Следовательно,

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

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

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

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