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


В линейной алгебре подпространством Крылова размерности m {displaystyle m} , порождённым вектором v ∈ C n {displaystyle vin mathbb {C} ^{n}} и матрицей A ∈ C n × n {displaystyle Ain mathbb {C} ^{n imes n}} , называется линейное пространство

K m ( v , A ) = span ⁡ { v , A v , A 2 v , . . . , A m − 1 v } . {displaystyle {mathcal {K}}_{m}(v,A)=operatorname {span} {v,Av,A^{2}v,...,A^{m-1}v}.}

Подпространство Крылова является подпространством векторного пространства над полем комплексных чисел: K m ⊂ C n . {displaystyle {mathcal {K}}_{m}subset mathbb {C} ^{n}.}

Такие пространства были названы в честь русского прикладного математика и военно-морского инженера А. Н. Крылова, который опубликовал работу по этой проблеме в 1931 году.

Размерность подпространства Крылова

В силу конечномерности пространства C n {displaystyle mathbb {C} ^{n}} найдётся такое p ( 0 ≤ p ≤ n ) , {displaystyle p;(0leq pleq n),} что векторы v , A v , A 2 v , . . . , A p − 1 v {displaystyle v,;Av,;A^{2}v,;...,;A^{p-1}v} линейно-независимы, а A p v {displaystyle A^{p}v} есть линейная комбинация этих векторов с коэффициентами γ 1 , γ 2 , . . . , γ p : {displaystyle gamma _{1},;gamma _{2},;...,;gamma _{p}:}

A p v = − γ 1 A p − 1 v − γ 2 A p − 2 v − . . . − γ p v {displaystyle A^{p}v=-gamma _{1}A^{p-1}v-gamma _{2}A^{p-2}v-...-gamma _{p}v}

Составим полином φ ( λ ) = λ p + γ 1 λ p − 1 + γ 2 λ p − 2 + . . . + γ p {displaystyle varphi (lambda )=lambda ^{p}+gamma _{1}lambda ^{p-1}+gamma _{2}lambda ^{p-2}+...+gamma _{p}} и получим:

φ ( A ) v = 0. {displaystyle varphi (A)v=0.}

Полином φ ( A ) {displaystyle varphi (A)} степени p {displaystyle p} является минимальным многочленом вектора v относительно матрицы A.

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

1. K p {displaystyle {mathcal {K}}_{p}} инвариантно относительно A {displaystyle A} и K m = K p {displaystyle {mathcal {K}}_{m}={mathcal {K}}_{p}} для любого m ≥ p . {displaystyle mgeq p.} 2. d i m ( K m ) = min { m , p } . {displaystyle dim({mathcal {K}}_{m})=min{m,p}.}

Методы Крыловского типа

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

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

K m ( v , A ) = span ⁡ { v 1 , v 2 , v 3 , . . . , v m } , {displaystyle {mathcal {K}}_{m}(v,A)=operatorname {span} {v_{1},v_{2},v_{3},...,v_{m}},}

где

v 1 = v , v 2 = A v 1 , v 3 = A v 2 , . . . , v m = A v m − 1 {displaystyle v_{1}=v,;v_{2}=Av_{1},;v_{3}=Av_{2},;...,;v_{m}=Av_{m-1}} .

Самые известные методы подпространства Крылова — Метод Арнольди, Метод Ланцоша, Метод сопряжённых градиентов, GMRES, BiCG, BiCGSTAB, QMR, TFQMR и MinRES.