Cтраница 1
Основной QL-алгоритм для неразложимой трехдиагональной А сходится в один шаг, если А вырождена. Поэтому сдвиги выбираются так, чтобы аппроксимировать собственные значения. Сходимость основного алгоритма обеспечивает, что ai) e AAe1 - Я при k - 00, поэтому кажется разумным использовать а в качестве сдвига после того, как значение этого элемента уже в какой-то степени установилось. Однако обсуждаемая ниже стратегия сдвигов отбрасывает осторожность и использует а как сдвиг с самого начала. [1]
Гарантированная сходимость QL-алгоритма обеспечивает, что pt - О, ocj - О при / г - оо, но судьба Р2 не определена. Доказательство этого утверждения вынесено в упр. [2]
Вариант PWK QL-алгоритма без квадратных корней ( § 8.15) не был опубликован в открытой литературе. [3]
При использовании QL-алгоритма без операции извлечения квадратного корня с разумными сдвигами все 0 - могут быть вычислены примерно за 9 / 2 умножений. С другой стороны, комбинируя QL-алгоритм с делением спектра, можно вычислить р экстремальных собственных чисел в каждом конце спектра приблизительно за Збр / умножений. При этом мы отводим 1.8 QL-итераций на одно собственное число и 10 / умножений на одну QL-итерацию. [4]
Преобразование Хаусхолдера и QL-алгоритм - наиболее эффективные методы для вычисления всех собственных значений и, если необходимо, собственных векторов. Соответствующие процедуры характеризуются большей скоростью в сравнении с процедурой jacobi, особенно когда требуется вычислять только собственные значения. В этом случае оптимальным является сочетание процедур tredl и tqll; если необходима экономия памяти, то процедуру tredl следует заменить процедурой tredS, поскольку в последней исходная симметрическая матрица записана в массиве лишь из Vg п ( я 1) элементов. Процедуры iredl и tql весьма эффективны, если требуется экономия памяти; лишь п2 0 ( п) ячеек памяти необходимо для решения полной проблемы. Ортогональность собственных векторов гарантирована с высокой точностью независимо от распределения собственных значений. [5]
Показать, что основной QL-алгоритм, примененный к вырожденной неразложимой трех диагональ ной матрице, должен сходиться за один шаг. [6]
Мы обнаружим, что QL-алгоритм может сходиться медленно. [7]
С практической точки зрения QL-алгоритм решает проблему вычисления собственных значений малых матриц. Тем не менее он был изобретен лишь в 1958 - 1959 годах, а по достоинству оценен в середине 1960 - х годов. Ключевая идея принадлежит Рутисхаузеру, который в 1958 году построил родственный метод, называемый LR-алгоритмом. [8]
Такой алгоритм носит название QL-алгоритма. [9]
Теперь мы установим связь QL-алгоритма с более хорошо знакомыми нам методами, описанными в гл. [10]
При сдвигах по отношению Релея QL-алгоритм сходится почти всегда, и если он действительно сходится, то асимптотическая скорость сходимости кубическая. [11]
Есть возможность видоизменить внутренний цикл стандартного QL-алгоритма так, что вектор e S модифицируется каждым вращением. [12]
В 1968 году Уилкинсон доказал, что трехдиагональный QL-алгоритм с предложенными им сдвигами всегда сходится. [13]
Чтобы завершить теорию, стоящую за этой неявной модификацией QL-алгоритма, нужен еще один результат. [14]
Соответствующий собственный вектор матрицы X, вычисленный с помощью QL-алгоритма с явным сдвигом, имеет значительно меньшую точность. [15]