Cтраница 3
Хотя до 1958 г. ничего похожего на алгоритмы QR и QL не было и в помине, появившись, они быстро утвердились как самый эффективный способ нахождения всех собственных значений малой симметричной матрицы. Вначале посредством последовательности отражений ( § 7.4) заполненная матрица приводится к трех-диагональной форме, а затем QL-алгоритм быстро уменьшает величину внедиагональных элементов, пока они не станут пренебрежимо малыми. На каждом шаге алгоритма применяется довольно сложное подобное преобразование, чем порождается последовательность матриц, сходящаяся к диагональной матрице. Более того, сохраняется трехдиагональная форма. [31]
Метод гарантирует точность, сравнительную с точностью вычислительной машины, на которой реализован алгоритм. Для этого требуется от 6 до 10 циклов или от Зп2 до 5п2 вращений. Метод прост и компактен. Этот метод неэффективен при использовании двухступенчатой памяти. По затратам машинного времени он уступает методам, основанным на предварительном приведении к трехдиагональной форме, поскольку не использует преимуществ симметричных ленточных матриц. [32]
Поскольку нас интересует det ( Л - КЕ), то для его вычисления надо в формулах ( 15) - ( 16) вместо нештрихованных величин aftfe всюду подставить ak /, - L Этот способ позволяет вычислить определитель за я2 арифметических действий. Видно, что метод оказывается не быстрым, но довольно простым и устойчивым. Дальше мы увидим, что есть заметно более быстрые способы нахождения собственных значений почти треугольной матрицы, основанные на преобразовании матрицы к трехдиагональной форме. [33]