Введение
Линейное подпространство, сгенерированное из вектора, на который действует степень матрицы В линейной алгебре, подпространство Крилова порядка r, сгенерированное n на n матрицы A и вектором b измерения n, является линейным подпространством, охваченным изображениями b под первыми степенями r A (начиная с ), то есть
In linear algebra, the order r Krylov subspace generated by an n by n matrix A and a vector b of dimension n is the linear subspace spanned by the images of b under the first r powers of A (starting from ), that is,
Предыстория
Название концепции дано в честь русского прикладной математика и морского инженера Алексея Крылова, который опубликовал статью о концепции в 1931 году.
Свойства
- Да . - Да . Пусть Тогда линейно независимы, если , для всех , и Так является максимальное измерение подпространств Крылова Максимальное измерение удовлетворяет и Рассмотрим , где минимальный полином у нас есть Кроме того, для любого , существует a для которого эта граница является жесткой, т. е. является циклическим подмодулем, генерируемым модулем кручения , где линейное пространство на может быть разложено как прямая сумма подпространств Крылова.
Consider , where is the minimal polynomial of We have Moreover, for any , there exists a for which this bound is tight, i. e. is a cyclic submodule generated by of the torsion module , where is the linear space on can be decomposed as the direct sum of Krylov subspaces.
Использование
Подпространства Крылова используются в алгоритмах для поиска приблизительных решений высокомерных линейных задач алгебры. Современные итеративные методы, такие как итерация Арнольди, могут использоваться для нахождения одного (или нескольких) собственных значений больших матриц или решения больших систем линейных уравнений. Они стараются избегать матричных операций, а скорее умножают векторы на матрицу и работают с полученными векторами. Начиная с вектора, вычисляем, затем умножаем этот вектор на и так далее. Все алгоритмы, которые работают таким образом, называются методами подпространства Крылова; они являются одними из самых успешных методов, доступных в настоящее время в численной линейной алгебре. Эти методы могут использоваться в ситуациях, когда существует алгоритм для вычисления умножения векторов матрицы без явного представления , что приводит к созданию методов без матрицы.
Проблемы
Поскольку векторы обычно становятся почти линейно зависимыми из-за свойств итерации мощностей, методы, опирающиеся на подпространство Крылова, часто включают в себя некоторую схему ортогонализации, такую как итерация Ланчоса для матриц Гермита или итерация Арнольди для более общих матриц.
Существующие методы
Наиболее известными методами подпространства Крылова являются Конъюгированный градиент, IDR ((s) (индуцированное уменьшение измерений), GMRES (упрощённое минимальное остаточное), BiCGSTAB (стабилизированный биконъюгированный градиент), QMR (квазиминимальное остаточное), TFQMR (транспозиционное свободное QMR) и MINRES (метод минимального остаточного).