Использование полиномов Чебышева

45. Предположим, мы знаем, что все собственные значения от до лежат в некотором интервале и что лежит вне этого интервала. Для эффективной итерационной схемы мы хотим определить функцию матрицы А так, чтобы было как можно больше по сравнению с максимально возможными значениями в интервале Если мы ограничимся полиномами, то решение этой проблемы дают полиномы Чебышева.

Применение преобразования

переводит интервал в и полином степени , удовлетворяющий нашим требованиям, равен

Следовательно, если мы определим В соотношением

то наиболее эффективным полиномом степени будет Полиномы Чебышева удовлетворяют рекуррентным соотношениям

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

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

Существует обширная литература об использовании ортогональных полиномов для вычисления собственных векторов. Такие методы широко используются для вычисления наименьшего собственного значения больших матриц, содержащих большое количество нулей, которые получаются из конечноразностных приближений к уравнениям в частных производных. Вообще говоря, успех весьма существенно зависит от деталей практической процедуры. Сошлемся на работы Штифеля (1958) и Энгели и др. (1959).