Зворотний степеневий метод

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

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

Метод

Нехай є квадратна матриця $A$ і її наближене власне значення $\mu$. Початковий вектор $b_{0}$ може бути випадковим або відомим наближенням власного вектора. Метод зводиться до послідовного обчислення векторів за формулою

$b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},$

де $C_{k}$ нормувальні константи.

Зазвичай на кожному кроці просто нормують вектор $b_{k+1}$ до одиничної довжини. Послідовність векторів не обов'язково збігається, але починаючи з деякого кроку будь-який вектор послідовності є власним з точністю до похибок округлення під час множення на матрицю. Йому відповідає найближче до $\mu$ власне значення. Після того, як знайдено власний вектор $b$, можна точно обчислити це власне значення за формулою:

$\mu _{b}={\frac {b^{T}Ab}{b^{T}b}}={\frac {(b,Ab)}{(b,b)}}$

Що ближче $\mu$ до власного значення, то швидша збіжність. Коли відомі хороші наближення власних значень, може знадобитися всього 2-3 ітерації.

Обґрунтування і збіжність

Зворотний степеневий метод відрізняється від степеневого методу тільки використовуваною для множення матрицею. Тому він дозволяє знайти власний вектор, відповідний найбільшому за модулем власному значенню матриці $(A-\mu I)^{-1}$. Власні значення цієї матриці — $(\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},$ де $\lambda _{i}$ власні значення матриці $A$. Найбільше за модулем власне значення відповідає найменшому за модулем значенню $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$

Власні вектори $A$ і $(A-\mu I)^{-1}$ збігаються, оскільки:

$Av=\lambda v\Leftrightarrow (A-\mu I)v=\lambda v-\mu v\Leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1}v$

Зокрема, якщо задати $\mu =0$, а матриця $A$ має зворотну, ми знайдемо власний вектор з найменшим за модулем власним значенням.

У плані ітерацій зворотний степеневий метод нічим не відрізняється від степеневого методу. Тому доведення його збіжності ідентичне і метод має таку ж лінійну швидкість збіжності.

Якщо невідомі наближення власних значень

Межі для власних значень матриці можна знайти за допомогою векторно підпорядкованої норми матриці. А саме

$\left\|A\right\|\geq |\lambda |,$ для будь-якого власного значення $\lambda$.

Якщо власні значення матриці досить добре розділені, то вибираючи на відрізку $[-\left\|A\right\|,\left\|A\right\|]$ початкове значення $\mu$ з досить малим кроком можна знайти всі власні значення і вектори матриці. Однак у цьому випадку ефективнішим може виявитися метод ітерацій Релея.