Метод ітерацій Релея
Метод ітерацій Релея — ітеративний алгоритм обчислення власних значень і векторів, який доповнює ідею зворотного степеневого методу ітеративним обчисленням поточного наближення до власного значення за допомогою відношення Релея.
Метод Релея має дуже велику швидкість збіжності і часто для отримання розв'язку потрібно лише кілька ітерацій. Для симетричних і ермітових матриць за досить добре вибраних початкових значень збіжність кубічна. Однак час виконання кожної ітерації зазвичай пропорційний кубу розміру матриці, тоді як для зворотного степеневого і степеневого методу він квадратичний.
Алгоритм
Як і в зворотному степеневому методі ми задаємо деяке початкове наближення до власного значення матриці і початковий вектор , який може бути або випадковим, або відомим наближенням до власного вектора. Далі ітеративно обчислюємо нові наближення до власного вектора за формулою
, де одинична матриця.
На завершення ітерації обчислюємо наступне наближення до власного значення за допомогою відношення Релея:
Приклад програмної реалізації
Нижче наведено приклад реалізації мовою GNU Octave.
function x = rayleigh(A, epsilon, mu, x)
x = x / norm(x);
% the backslash operator in Octave solves a linear system
y = (A - mu * eye(rows(A))) \ x;
lambda = y' * x;
mu = mu + 1 / lambda
err = norm(y - lambda * x) / norm(y)
while err > epsilon
x = y / norm(y);
y = (A - mu * eye(rows(A))) \ x;
lambda = y' * x;
mu = mu + 1 / lambda
err = norm(y - lambda * x) / norm(y)
end
end
Посилання
- Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. ISBN 0-89871-361-7.
- Rainer Kress, «Numerical Analysis», Springer, 1991. ISBN 0-387-98408-9