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

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

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

Метод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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