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

Два выбора подпространств

В разделе 2.2.2 были рассмотрены методы наискорейшего спуска, в котором подпространства K и L были связаны соотношением K = L, и наискорейшего уменьшения невязки который основан на соотношении L = A K. Сами подпространства являлись одномерными, в качестве базиса K выступал вектор невязки. В этих случаях задача проектирования эквивалентна задаче минимизации функционалов. Как оказывается, подобные утверждения справедливы и в гораздо более общих случаях, которые имеют важное значение при построении более сложных и эффективных методов.

Так если матрица A симметрична и положительно определенна, то задача проектирования решения СЛАУ (1.1) на любое подпространство K ортогонально к нему самому (т.е. ортогонально к пространству L = K) является эквивалентной задаче минимизации || x – x _*|| _A ² на пространстве K. Для произвольной невырожденной матрицы A задача проектирования решения СЛАУ (1.1) на любое подпространство K ортогонально подпространству L = A K, эквивалентна задаче минимизации || r _x||₂² на подпространстве K.

При построении и реализации проекционных методов важную роль играют так называемые подпространства Крылова, часто выбираемые в качестве K. Подпространством Крылова размерности m, порожденным вектором n и матрицей A называется линейное пространство

Km (n, A)=span{n, An, A^2n,…,A ^m ^–1n}.

(2.21)

В качестве вектора n обычно выбирается невязка начального приближения r ₀; тогда выбор подпространства L и способ построения базисов подпространств полностью определяет вычислительную схему метода.

К идее использования подпространств Крылова можно прийти, например, следующим образом. При построении релаксационных методов использовалось представление матрицы A в виде A = D – E – F. Было также показано, что методы Якоби-Зейделя являются частными случаями класса методов, основанного на расщеплении A в виде разности (2.9) двух матриц K и R. Тогда исходная система (1.1) может быть записана в виде

Kx=b+Rx=b+(K–A)x,

что позволяет построить итерационный процесс

Kx _{k +1}=Kx _k +(b–Ax _k),

или, что то же самое,

x k +1=x k +K^–1r k.

(2.22)

Если выбрать K = I и R = I – A, тогда процесс (2.22) будет сведен к виду

x k +1=x k +r k,

(2.23)

откуда следует

x k =x0+r0+r1+…+r k –1.

(2.24)

Умножив обе части (2.23) слева на (– A) и прибавив к ним b, получится

b–Ax _{k +1}=b–Ax _k –Ar _k =r _k –Ar _k,

что позволяет найти выражение для невязки на k -ой итерации через невязку начального приближения:

r k =(I–A)r k –1=(I–A) ^k r0.

(2.25)

После подстановки (2.25) в (2.24) получается

x _k =x₀+ r₀,

т.е. d _k Î span{ r ₀, Ar ₀, …, A ^{k -1} r ₀}= K_k (r ₀, A). Из (2.25) следует, что в методах, использующих подпространства Крылова, невязка на k -ой итерации выражается через начальную невязку некоторым матричным полиномом.

Дата добавления: 2014-12-27