Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




29.06.2022


27.06.2022


26.06.2022


26.06.2022


25.06.2022


24.06.2022


21.06.2022





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

Степенной метод

07.03.2022


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

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

Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер.

Алгоритм

В начале алгоритма генерируется случайный вектор r 0 {displaystyle r_{0}} . Далее проводятся последовательные вычисления по итеративной формуле:

r k + 1 = A r k ‖ A r k ‖ {displaystyle r_{k+1}={frac {Ar_{k}}{|Ar_{k}|}}}

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

Последовательность

μ k = r k T A r k r k T r k = ( r k , A r k ) ( r k , r k ) {displaystyle mu _{k}={frac {r_{k}^{T}Ar_{k}}{r_{k}^{T}r_{k}}}={frac {(r_{k},Ar_{k})}{(r_{k},r_{k})}}}

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

Для нормальных операторов

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

Пусть r k {displaystyle r_{k}} — нормированный собственный вектор с максимальным по модулю собственным значением матрицы A {displaystyle A} нормального оператора. Тогда матрица

A 1 = A − λ r k r k T {displaystyle A_{1}=A-lambda r_{k}r_{k}^{T}}

сохраняет все собственные векторы матрицы A {displaystyle A} , кроме вектора r k {displaystyle r_{k}} , и позволяет искать степенным методом следующий собственный вектор с максимальным по модулю собственным значением.

Доказательство сходимости

Упорядочим собственные значения по невозрастанию абсолютной величины и допустим, что λ 1 > λ 2 ≥ . . . ≥ λ n {displaystyle lambda _{1}>lambda _{2}geq ...geq lambda _{n}} . Тогда начальный вектор можно представить как

r 0 = ∑ i = 1 n v i + w {displaystyle r_{0}=sum _{i=1}^{n}v_{i}+w} ,

где v i {displaystyle v_{i}} — собственные векторы, вектор w {displaystyle w} обнуляется при первом умножении на матрицу, а v 1 ≠ 0 {displaystyle v_{1} eq 0} по предположению.

Рассмотрим результат k {displaystyle k} умножений матрицы на начальный вектор:

R k = A k ( ∑ i = 1 n v i + w ) = ∑ i = 1 n λ i k v i = λ 1 k ( v 1 + O ( ( λ 2 λ 1 ) k ) {displaystyle R_{k}=A^{k}(sum _{i=1}^{n}v_{i}+w)=sum _{i=1}^{n}{lambda _{i}^{k}v_{i}}={lambda _{1}}^{k}(v_{1}+O(({frac {lambda _{2}}{lambda _{1}}})^{k})} .

Поделив левую и правую часть на ‖ R k ‖ {displaystyle |R_{k}|} , получим

r k = λ 1 v 1 ‖ λ 1 v 1 ‖ + O ( ( λ 2 λ 1 ) k ) . {displaystyle r_{k}=lambda _{1}{frac {v_{1}}{|lambda _{1}v_{1}|}}+O(({frac {lambda _{2}}{lambda _{1}}})^{k}).}

Приложения

Метод применяется в первую очередь для разреженных матриц. Например, Гугл использует его для расчёта рангов страниц в Интернете, а Twitter использует его для рекомендаций «за кем следовать».

Имя:*
E-Mail:
Комментарий: