Метод ітерацій Релея

Метод ітерацій Релея — ітеративний алгоритм обчислення власних значень і векторів, який доповнює ідею зворотного степеневого методу ітеративним обчисленням поточного наближення до власного значення за допомогою відношення Релея.

Метод Релея має дуже велику швидкість збіжності і часто для отримання розв'язку потрібно лише кілька ітерацій. Для симетричних і ермітових матриць за досить добре вибраних початкових значень збіжність кубічна. Однак час виконання кожної ітерації зазвичай пропорційний кубу розміру матриці, тоді як для зворотного степеневого і степеневого методу він квадратичний.

Алгоритм

Як і в зворотному степеневому методі ми задаємо деяке початкове наближення ${\displaystyle \mu _{0}}$ до власного значення матриці ${\displaystyle A}$ і початковий вектор ${\displaystyle b_{0}}$, який може бути або випадковим, або відомим наближенням до власного вектора. Далі ітеративно обчислюємо нові наближення до власного вектора ${\displaystyle b_{i+1}}$ за формулою

${\displaystyle b_{i+1}={\frac {(A-\mu _{i}I)^{-1}b_{i}}{||(A-\mu _{i}I)^{-1}b_{i}||}},}$, де ${\displaystyle I}$ одинична матриця.

На завершення ітерації обчислюємо наступне наближення до власного значення за допомогою відношення Релея:

${\displaystyle \mu _{i+1}={\frac {b_{i+1}^{*}Ab_{i+1}}{b_{i+1}^{*}b_{i+1}}}.}$

Приклад програмної реалізації

Нижче наведено приклад реалізації мовою 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. .
• Rainer Kress, «Numerical Analysis», Springer, 1991.