Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




18.04.2021


18.04.2021


18.04.2021


16.04.2021


15.04.2021





Яндекс.Метрика





Обратный степенной метод

08.03.2021

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

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

Метод

Пусть имеется квадратная матрица A {displaystyle A} и её приближённое собственное значение μ {displaystyle mu } Начальный вектор b 0 {displaystyle b_{0}} может быть случайным или известным приближением собственного вектора. Метод сводится к последовательному вычислению векторов по формуле

b k + 1 = ( A − μ I ) − 1 b k C k , {displaystyle b_{k+1}={frac {(A-mu I)^{-1}b_{k}}{C_{k}}},}

Где C k {displaystyle C_{k}} нормирующие константы. Обычно на каждом шаге просто нормируют вектор b k + 1 {displaystyle b_{k+1}} к единичной длине. Последовательность векторов не обязательно сходится, но начиная с некоторого шага любой вектор последовательности является собственным с точностью до ошибок округления при умножении на матрицу. Ему соответствует ближайшее к μ {displaystyle mu } собственное значение. После того как найден собственный вектор b {displaystyle b} можно точно вычислить это собственное значение по формуле:

μ b = b T A b b T b = ( b , A b ) ( b , b ) {displaystyle mu _{b}={frac {b^{T}Ab}{b^{T}b}}={frac {(b,Ab)}{(b,b)}}}

Чем ближе μ {displaystyle mu } к собственному значению тем быстрее сходимость. Когда известны хорошие приближения собственных значений, может потребоваться всего 2 — 3 итерации.

Обоснование и сходимость

Обратный степенной метод отличается от степенного метода только используемой для умножения матрицей. Поэтому он позволяет найти собственный вектор, соответствующий максимальному по модулю собственному значению матрицы ( A − μ I ) − 1 {displaystyle (A-mu I)^{-1}} . Собственные значения этой матрицы — ( λ 1 − μ ) − 1 , . . . , ( λ n − μ ) − 1 , {displaystyle (lambda _{1}-mu )^{-1},...,(lambda _{n}-mu )^{-1},} где λ i {displaystyle lambda _{i}} собственные значения матрицы A {displaystyle A} . Наибольшее по модулю собственное значение соответствует наименьшему по модулю значению ( λ 1 − μ ) , . . . , ( λ n − μ ) . {displaystyle (lambda _{1}-mu ),...,(lambda _{n}-mu ).}

Собственные вектора A {displaystyle A} и ( A − μ I ) − 1 {displaystyle (A-mu I)^{-1}} совпадают, поскольку:

A v = λ v ⇔ ( A − μ I ) v = λ v − μ v ⇔ ( λ − μ ) − 1 v = ( A − μ I ) − 1 v {displaystyle Av=lambda vLeftrightarrow (A-mu I)v=lambda v-mu vLeftrightarrow (lambda -mu )^{-1}v=(A-mu I)^{-1}v}

В частности, если задать μ = 0 {displaystyle mu =0} , а матрица A {displaystyle A} имеет обратную мы найдём собственный вектор с минимальным по модулю собственным значением.

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

Если неизвестны приближения собственных значений

Пределы для собственных значений матрицы можно найти с помощью векторно подчинённой нормы матрицы. А именно

‖ A ‖ ≥ | λ | , {displaystyle left|A ight|geq |lambda |,} для любого собственного значения λ {displaystyle lambda } .

Если собственные значения матрицы достаточно хорошо разделены, то выбирая на отрезке [ − ‖ A ‖ , ‖ A ‖ ] {displaystyle [-left|A ight|,left|A ight|]} начальные значения μ {displaystyle mu } с достаточно малым шагом можно найти все собственные значения и вектора матрицы. Однако в этом случае более эффективным может оказаться метод итераций Рэлея.