Подпространство Крылова

Линейное подпространство, полученное из вектора, на который действует степенной ряд матрицы

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

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

Фон

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

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

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

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

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

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

Проблемы

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

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

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

Смотрите также

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

Ссылки

1. Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Серия Springer по исследованию операций и финансовому инжинирингу (2-е изд.). Нью-Йорк, штат Нью-Йорк: Springer. стр. 108. ISBN 978-0-387-30303-1.
2. Simoncini, Valeria (2015), «Подпространства Крылова», в Nicholas J. Higham; et al. (ред.), The Princeton Companion to Applied Mathematics , Princeton University Press, стр. 113–114
3. Крылов, А.Н. (1931). «О численном решении уравнения, с помощью которого в технических задачах определяются частоты малых колебаний материальных систем». Известия Академии наук СССР (на русском языке). 7 (4): 491–539.
4. Хеспанья, Жуан (2017), Теория линейных систем , Princeton University Press

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

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