В численной линейной алгебре , то итерация Арнольди является собственным значением алгоритма и является важным примером итерационного метода . Арнольди находит приближение собственных значений и собственных векторов общих (возможно, неэрмитовых ) матриц путем построения ортонормированного базиса подпространства Крылова , что делает его особенно полезным при работе с большими разреженными матрицами .
Метод Арнольди принадлежит к классу алгоритмов линейной алгебры, которые дают частичный результат после небольшого количества итераций, в отличие от так называемых прямых методов, которые должны завершиться, чтобы дать какие-либо полезные результаты (см., Например, преобразование Хаусхолдера ). Частичным результатом в данном случае являются несколько первых векторов основы, которую строит алгоритм.
Применительно к эрмитовым матрицам он сводится к алгоритму Ланцоша . Итерация Арнольди была изобретена У. Э. Арнольди в 1951 г. [1]
Крыловские подпространства и степенная итерация
Интуитивно понятный метод нахождения наибольшего (по модулю) собственного значения заданной матрицы размера m × mэто итерация мощности : начиная с произвольным начальным вектором Ь , вычислить Ab , 2 б , 3 б , ... нормализация результата после каждого применения матрицы A .
Эта последовательность сходится к собственному вектору, соответствующему собственному значению с наибольшим модулем,. Однако многие потенциально полезные вычисления тратятся впустую из-за использования только конечного результата,. Это говорит о том, что вместо этого мы формируем так называемую матрицу Крылова :
Столбцы этой матрицы, как правило, не ортогональны , но мы можем извлечь ортогональный базис с помощью такого метода, как ортогонализация Грама – Шмидта . Таким образом, полученный набор векторов является ортогональным базисом подпространства Крылова ,. Можно ожидать, что векторы этого базиса будут охватывать хорошие приближения собственных векторов, соответствующих наибольшие собственные значения по той же причине, что аппроксимирует доминантный собственный вектор.
Итерация Арнольди
Итерация Арнольди использует модифицированный процесс Грама – Шмидта для создания последовательности ортонормированных векторов q 1 , q 2 , q 3 ,…, называемых векторами Арнольди , так что для каждого n векторы q 1 ,…, q n охватывают подпространство Крылова. В явном виде алгоритм выглядит следующим образом:
- Начнем с произвольного вектора q 1 с нормой 1.
- Повторите для k = 2, 3,…
- для j от 1 до k - 1
В J -loop проектов из компонента в направлениях . Это обеспечивает ортогональность всех сгенерированных векторов.
Алгоритм не работает, когда q k является нулевым вектором. Это происходит , когда минимальный многочлен из А имеет степень к . В большинстве приложений итерации Арнольди, включая приведенный ниже алгоритм собственных значений и GMRES , алгоритм сходится в этой точке.
Каждый шаг k -цикла требует одного произведения матрицы на вектор и примерно 4 mk операций с плавающей запятой.
В языке программирования Python:
импортировать numpy как npdef arnoldi_iteration ( A , b , n : int ): "" "Вычисляет базис (n + 1) -крыловского подпространства в A: пространство, натянутое на {b, Ab, ..., A ^ nb}. Аргументы A: массив m × m b: начальный вектор (длина m) n: размерность подпространства Крылова, должно быть> = 1 Возвращает Q: массив mx (n + 1), столбцы являются ортонормированным базисом подпространства Крылова. h: (n + 1) xn массив, A на основе Q. Это верхний Гессенберг. ""» М = . Форма [ 0 ] ч = NP . Нули (( п + 1 , п )) Q = NP . Нули (( т , п + 1 )) д = б / пр . Linalg . Норма ( б ) # Нормализовать входной вектор Q [:, 0 ] = q # Использовать его как первый вектор Крылова для к в диапазоне ( п ): V = A . dot ( q ) # Сгенерируйте новый вектор-кандидат для j в диапазоне ( k + 1 ): # Вычтите проекции на предыдущие векторы h [ j , k ] = np . точка ( Q [:, j ] . con (), v ) v = v - h [ j , k ] * Q [:, j ] h [ k + 1 , k ] = np . linalg . norm ( v ) eps = 1e-12 # Если v короче этого порога, это нулевой вектор, если h [ k + 1 , k ] > eps : # Добавить полученный вектор в список, если q = v / h [ k + 1 , k ] # создается нулевой вектор. Q [:, k + 1 ] = q else : # Если это произойдет, прекратите итерацию. возврат Q , ч возврат Q , ч
Свойства итерации Арнольди
Пусть Q n обозначает матрицу размером m на n, образованную первыми n векторами Арнольди q 1 , q 2 ,…, q n , и пусть H n будет (верхняя матрица Гессенберга ), образованная числами h j , k, вычисленными с помощью алгоритм:
Метод ортогонализации должен быть выбран таким образом, чтобы нижние компоненты Арнольди / Крылова удалялись из высших векторов Крылова. В видемогут быть выражены через q 1 ,…, q i + 1 по построению, они ортогональны q i + 2 ,…, q n ,
Тогда у нас есть
Матрицу H n можно рассматривать как A в подпространствес векторами Арнольди в качестве ортогонального базиса; A ортогонально проецируется на. Матрицу H n можно охарактеризовать следующим условием оптимальности. Характеристический полином из Н п сводит к минимуму || p ( A ) q 1 || 2 среди всех приведенных многочленов степени n . Эта проблема оптимальности имеет уникальное решение тогда и только тогда, когда итерация Арнольди не дает сбоев.
Связь между Q- матрицами в последующих итерациях определяется выражением
где
представляет собой матрицу размером ( n +1) на n, образованную добавлением дополнительной строки к H n .
Нахождение собственных значений с помощью итерации Арнольди
Идея итерации Арнольди как алгоритма собственных значений заключается в вычислении собственных значений в подпространстве Крылова. Собственные значения H n называются собственными значениями Ритца . Поскольку H n представляет собой матрицу Хессенберга небольшого размера, ее собственные значения можно эффективно вычислить, например, с помощью алгоритма QR или, в некоторой степени, алгоритма Фрэнсиса. Также сам алгоритм Фрэнсиса можно рассматривать как относящийся к степенным итерациям, работающим на вложенном подпространстве Крылова. На самом деле, самая основная форма алгоритма Фрэнсис , как представляется, чтобы выбрать Ь равным Ae 1 , и расширение п до полной размерности A . Улучшенные версии включают в себя один или несколько сдвигов, а более высокие степени A могут применяться за один шаг. [1]
Это пример метода Рэлея-Ритца .
Это часто наблюдается на практике , что некоторые из собственных Ритца сходится к собственным A . Так как Н п является п матрицу с размерностью п , оно имеет не более п собственных значений, а не все собственные значения А может быть аппроксимирована. Как правило, собственная Ritz сходятся к наибольшим собственным значениям А . Чтобы получить наименьшие собственные значения A , вместо этого следует использовать обратную (операцию) A. Это может быть связано с характеристикой H n как матрицы, характеристический многочлен которой минимизирует || p ( A ) q 1 || следующим образом. Хороший способ получить р ( А ) Мало выбрать полином р такие , что р ( х ) мало , когда х является собственным значением A . Следовательно, нули р (и , таким образом , собственные значения Ritz) будут близки к собственным значениям А .
Однако детали еще не до конца изучены. Это в отличие от случая , когда является симметричным . В этой ситуации итерация Арнольди становится итерацией Ланцоша , для которой теория является более полной.
Неявно перезапущенный метод Арнольди (IRAM)
Из-за практических соображений хранения общие реализации методов Арнольди обычно перезапускаются после некоторого количества итераций. Одно из основных нововведений в перезапуске произошло благодаря Лехуку и Соренсену, которые предложили метод неявно перезапущенного Арнольди. [2] Они также реализовали алгоритм в свободно доступном программном пакете ARPACK . [3] Это привело к появлению ряда других вариаций, включая неявно перезапускаемый метод Ланцоша. [4] [5] [6] Это также повлияло на то, как анализируются другие перезапускаемые методы. [7] Теоретические результаты показали, что сходимость улучшается с увеличением размерности подпространства Крылова n . Однако априорное значение n, которое привело бы к оптимальной сходимости, неизвестно. Недавно была предложена стратегия динамического переключения [8] , которая изменяет размерность n перед каждым перезапуском и, таким образом, приводит к увеличению скорости сходимости.
Смотрите также
Обобщенный метод минимального остаточный (GMRES) представляет собой метод решения Ax = B , основанный на Арнольди итерации.
Рекомендации
- ^ WE Арнольди, "Принцип минимальных итераций в решении матричной проблемы собственных значений", Quarterly of Applied Mathematics , том 9, страницы 17–29, 1951
- ^ RB Lehoucq & DC Соренсен (1996). «Методы дефляции для неявно перезапущенной итерации Арнольди». СИАМ . DOI : 10.1137 / S0895479895281484 . hdl : 1911/101832 .
- ^ РБ Лехук; Д.К. Соренсен и К. Ян (1998). «Руководство пользователя ARPACK: решение крупномасштабных проблем собственных значений с помощью неявно перезапущенных методов Арнольди» . СИАМ. Архивировано из оригинала на 2007-06-26 . Проверено 30 июня 2007 .
- ^ Д. Кальветти ; Л. Райхель и Д. К. Соренсен (1994). "Неявно перезапущенный метод Ланцоша для больших симметричных задач на собственные значения" . ETNA.
- ^ Э. Кокиопулу; К. Бекас и Э. Галлопулос (2003). "Неявно перезапущенный метод бидиагонализации Ланцоша для вычисления наименьших сингулярных триплетов" (PDF) . СИАМ.
- ^ Чжунсяо Цзя (2002). «Усовершенствованный гармонический метод Арнольди и неявно перезапущенный усовершенствованный алгоритм для вычисления внутренних собственных пар больших матриц». Прил. Нумер. Математика . DOI : 10.1016 / S0168-9274 (01) 00132-5 .
- ^ Андреас Статопулос, Юсеф Саад и Кешенг Ву (1998). «Динамический толстый перезапуск Дэвидсона и неявно перезапускаемые методы Арнольди». СИАМ . DOI : 10,1137 / S1064827596304162 .
- ^ К. Дукхитрам, Р. Буджавон и М. Бхурут (2009). «Новый метод ускорения алгоритмов Арнольди для крупномасштабных собственных задач». Математика. Comput. Simulat . DOI : 10.1016 / j.matcom.2009.07.009 .
- У. Е. Арнольди, "Принцип минимальных итераций в решении матричной проблемы собственных значений", Ежеквартальный вестник прикладной математики , том 9, страницы 17–29, 1951.
- Юсеф Саад , Численные методы для больших задач на собственные значения , Manchester University Press, 1992. ISBN 0-7190-3386-1 .
- Ллойд Н. Трефетен и Дэвид Бау, III, Численная линейная алгебра , Общество промышленной и прикладной математики, 1997. ISBN 0-89871-361-7 .
- Яшке, Леонхард: Предварительно обусловленные методы Арнольди для систем нелинейных уравнений . (2004). ISBN 2-84976-001-3
- Реализация: Matlab поставляется со встроенным ARPACK. Как хранимые, так и неявные матрицы можно анализировать с помощью функции eigs () .