Krylov subspace

В линейной алгебре порядка r Крылова , порожденное n размера n матрицей A и вектором b размерности n, представляет собой линейное подпространство, натянутое на образы b подпространство при первых r степенях A (начиная с $A^{0}=I$ ), то есть, ^[1]^[2]

{\mathcal {K}}_{r}(A,b)=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}.

Фон

Концепция названа в честь русского прикладного математика и военно-морского инженера Алексея Крылова , опубликовавшего статью об этой концепции в 1931 году. ^[3]

Характеристики

${\mathcal {K}}_{r}(A,b),A\,{\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r+1}(A,b)$ .
Позволять $r_{0}=\operatorname {dim} \operatorname {span} \,\{b,Ab,A^{2}b,\ldots \}$ . Затем $\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}$ линейно независимы, если только $r>r_{0}$ , ${\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)$ для всех $r$ , и $\operatorname {dim} {\mathcal {K}}_{r_{0}}(A,b)=r_{0}$ . Так $r_{0}$ — максимальная размерность подпространств Крылова ${\mathcal {K}}_{r}(A,b)$ .
Максимальная размерность удовлетворяет $r_{0}\leq 1+\operatorname {rank} A$ и $r_{0}\leq n$ .
Учитывать $\dim \operatorname {span} \,\{I,A,A^{2},\ldots \}=\deg \,p(A)$ , где $p(A)$ является минимальным многочленом $A$ . У нас есть $r_{0}\leq \deg \,p(A)$ . Более того, для любого $A$ , существует $b$ для которого эта граница точна, т.е. $r_{0}=\deg \,p(A)$ .
${\mathcal {K}}_{r}(A,b)$ является циклическим подмодулем, порожденным $b$ кручения $k[x]$ -модуль $(k^{n})^{A}$ , где $k^{n}$ линейное пространство на $k$ .
$k^{n}$ можно разложить в прямую сумму подпространств Крылова. ^{[ нужны разъяснения ]}

Использовать

Подпространства Крылова используются в алгоритмах поиска приближенных решений многомерных задач линейной алгебры . ^[2] Многие тесты линейных динамических систем в теории управления , особенно те, которые связаны с управляемостью и наблюдаемостью , включают проверку ранга подпространства Крылова. Эти тесты эквивалентны поиску диапазона Грамианов, связанных с отображениями системы/выходов, поэтому неуправляемые и ненаблюдаемые подпространства являются просто ортогональным дополнением к подпространству Крылова. ^[4]

Современные итерационные методы, такие как итерация Арнольди, можно использовать для поиска одного (или нескольких) собственных значений больших разреженных матриц или решения больших систем линейных уравнений. Они стараются избегать матрично-матричных операций, а умножают векторы на матрицу и работают с полученными векторами. Начинаем с вектора $b$ , можно вычислить $Ab$ , затем этот вектор умножается на $A$ найти $A^{2}b$ и так далее. Все алгоритмы, работающие таким образом, называются методами подпространства Крылова; они являются одними из наиболее успешных методов, доступных в настоящее время в числовой линейной алгебре. Эти методы можно использовать в ситуациях, когда существует алгоритм вычисления умножения матрицы на вектор без явного представления $A$ , что привело к появлению безматрицальных методов .

Проблемы

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

Существующие методы

Наиболее известными методами подпространства Крылова являются сопряженный градиент , IDR(s) (индуцированное уменьшение размерности), GMRES (обобщенный минимальный невязка), BiCGSTAB (стабилизированный двусопряженный градиент), QMR (квазиминимальный невязочный), TFQMR (QMR без транспонирования) и МИНРЕС (метод минимальной невязки).

См. также

Итерационный метод , в котором есть раздел, посвященный методам подпространств Крылова.

Ссылки

^ Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Серия Springer по исследованию операций и финансовому инжинирингу (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 108. ИСБН 978-0-387-30303-1 .
^ Jump up to: ^а ^б Симончини, Валерия (2015), «Подпространства Крылова», Николас Дж. Хайэм; и др. (ред.), Princeton Companion to Applied Mathematics , Princeton University Press, стр. 113–114.
^ Krylov, A. N. (1931). "О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем" [On the Numerical Solution of Equation by Which are Determined in Technical Problems the Frequencies of Small Vibrations of Material Systems]. Izvestiia Akademii Nauk SSSR (in Russian). 7 (4): 491–539.
^ Эспанья, Жоао (2017), Теория линейных систем , Princeton University Press

Дальнейшее чтение

Неванлинна, Олави (1993). Сходимость итераций для линейных уравнений . Лекции по математике ETH Zürich. Базель: Birkhäuser Verlag. стр. viii+177 стр. ISBN 3-7643-2865-7 . МР 1217705 .
Саад, Юсеф (2003). Итерационные методы для разреженных линейных систем (2-е изд.). СИАМ . ISBN 0-89871-534-2 . OCLC 51266114 .
Жерар Мёрант и Юрьен Дуинтьер Теббенс: «Методы Крылова для несимметричных линейных систем - от теории к вычислениям», Серия Спрингера по вычислительной математике, том 57, (октябрь 2020 г.). ISBN 978-3-030-55250-3 , URL= https://doi.org/10.1007/978-3-030-55251-0 .
Иман Фарахбахш: «Методы подпространств Крылова с применением в решателях потоков несжимаемой жидкости», Уайли, ISBN 978-1119618683 (сентябрь 2020 г.).

[1] Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Серия Springer по исследованию операций и финансовому инжинирингу (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 108. ИСБН 978-0-387-30303-1 .

[PrincetonCompanion-2] Jump up to: ^а ^б Симончини, Валерия (2015), «Подпространства Крылова», Николас Дж. Хайэм; и др. (ред.), Princeton Companion to Applied Mathematics , Princeton University Press, стр. 113–114.

[3] Krylov, A. N. (1931). "О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем" [On the Numerical Solution of Equation by Which are Determined in Technical Problems the Frequencies of Small Vibrations of Material Systems]. Izvestiia Akademii Nauk SSSR (in Russian). 7 (4): 491–539.

[Linear_Systems_Theory-4] Эспанья, Жоао (2017), Теория линейных систем , Princeton University Press

[1]

[2]

[3]

[4]

v т и Численная линейная алгебра
Ключевые понятия	Плавающая точка Численная стабильность
Проблемы	Система линейных уравнений Матричное разложение Умножение матриц ( алгоритмы ) Расщепление матрицы Редкие проблемы
Аппаратное обеспечение	Кэш процессора TLB Алгоритм, не обращающий внимания на кэш SIMD Многопроцессорность
Программное обеспечение	АТЛАС МАТЛАБ Базовые подпрограммы линейной алгебры (BLAS) ЛАПАК Специализированные библиотеки Программное обеспечение общего назначения