Проекционные методы решения СЛАУ

Проекционные методы решения СЛАУ — класс итерационных методов, в которых решается задача проектирования неизвестного вектора на некоторое пространство оптимально относительно другого некоторого пространства.

Постановка задачи

Рассмотрим СЛАУ $Ax=b,$ где $A$ - квадратная матрица размерности $n.$ Пусть $K$ и $L$ - два $m$-мерных подпространства пространства $R^{n}.$ Необходимо найти такой вектор ${\tilde {x}}\in K$, чтобы $b-A{\tilde {x}}\perp L,$ т.е. выполнялось условие:

$\forall l\in L:(A{\tilde {x}},l)=(b,l),$

называемое условием Петрова-Галёркина.

Если известно начальное приближение $x_{0}$, то тогда решение должно проектироваться на аффинное пространство $x_{0}+K.$ Представим ${\tilde {x}}=x_{0}+\delta$ и обозначим невязку начального приближения как $r_{0}=b-Ax_{0}.$

$b-A{\tilde {x}}=b-A(x_{0}+\delta )=b-Ax_{0}-A\delta =(b-Ax_{0})-A\delta =r_{0}-A\delta .$

Тогда постановку задачи можно сформулировать следующим образом: Необходимо найти такое $\delta \in K,$ чтобы $r_{0}-A\delta \perp L,$ т.е. выполнялось условие:

${\tilde {x}}=x_{0}+\delta ,\ \delta \in K$

$\forall l\in L:(r_{0}-A\delta ,l)=0$

Общий подход к построению проекционных методов

Введём матричные базисы в пространствах $K$ и $L:$

$V=[v_{1},v_{2},...,v_{m}]$ - матрица размера $n\times m$ составленная из базисных векторов-столбцов пространства $K.$ $W=[w_{1},w_{2},...,w_{m}]$ - матрица размера $n\times m$ составленная из базисных векторов-столбцов пространства $L.$

Тогда $\delta \ =Vy$ и вектор-решение ${\tilde {x}}$ может быть записан:

${\tilde {x}}=x_{0}+Vy,$

где $y\in R^{m}$ - вектор коэффициентов.

Тогда выражение $(r_{0}-A\delta \ ,l)=0$ может быть переписано в виде:

$W^{T}(r_{0}-A\delta \ )={\bar {0}},$

откуда $W^{T}AVy=W^{T}r_{0}$ и

$y=(W^{T}AV)^{-1}W^{T}r_{0},$

Таким образом решение должно уточняться в соответствии с формулой:

$x_{1}=x_{0}+V(W^{T}AV)^{-1}W^{T}r_{0},$

Общий вид любого метода проекционного класса:

Делать, пока не найдено решение.

1. Выбираем пару подпространств $K$ и $L.$
2. Построение для $K$ и $L$ базисов $V=[v_{1},v_{2},...,v_{m}]$ и $W=[w_{1},w_{2},...,w_{m}].$
3. $r_{0}=b-Ax_{0}.$
4. $y=(W^{T}AV)^{-1}W^{T}r_{0}.$
5. $x_{1}=x_{0}+Vy.$

Выбор пространств $K$ и $L$ и способ построения для них базисов полностью определяет вычислительную схему метода.

Выбор подпространств K и L

Случай одномерных подпространств K и L

В случае когда пространства $K$ и $L$ одномерны, их матричные базисы являются векторами: $V=[v]$ и $W=[w]$ и выражение ${\tilde {x}}=x_{0}+Vy,$ можно переписать как

$x_{k+1}=x_{k}+\gamma _{k}\ v_{k},$

где $\gamma _{k}\$ - неизвестный коэффициент, который легко находится из условия ортогональности $r_{k}-A(\gamma _{k}\ v_{k})\perp w_{k}:$

$(r_{k}-\gamma _{k}\ Av_{k},w_{k})=(r_{k},w_{k})-\gamma _{k}\ (Av_{k},w_{k})={\bar {0}},$

откуда $\gamma _{k}\ ={\frac {(r_{k},w_{k})}{(Av_{k},w_{k})}}.$

Методы с выбором одномерных подпространств $K$ и $L$ :

• Метод наискорейшего спуска
• Метод наискорейшего уменьшения невязки
• Метод Гаусса-Зейделя
• Методы ABS-класса

В практических задачах методы использующие одномерные пространства $K$ и $L$ обладают достаточно медленной сходимостью.

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

Методы Крыловского типа (или методы подпространства Крылова) - это методы для которых в качестве подпространства $K$ выбирается подпространство Крылова:

${\mathcal {K}}_{m}(r_{0},A)=span\{r_{0},Ar_{0},A^{2}r_{0},...,A^{m-1}r_{0}\},$

где $r_{0}=b-Ax_{0}$ - невязка начального приближения. Различные версии методов подпространства Крылова обуславливаются выбором подпространства $L.$

С точки зрения теории аппроксимации, приближения ${\tilde {x}},$ полученные в методах подпространства Крылова имеют форму

$A^{-1}b\approx {\tilde {x}}=x_{0}+q_{m-1}(A)r_{0},$

где $q_{m-1}$ - полином степени $m-1.$ Если положить $x_{0}=0,$, то

$A^{-1}b\approx q_{m-1}(A)b.$

Другими словами, $A^{-1}b$ аппроксимируется $q_{m-1}(A)b.$

Хотя выбор подпространства $L$ и не оказывает влияния на тип полиномиальной аппроксимации, он оказывает существенное влияние на эффективность метода. На сегодняшний день известны 2 способа выбора подпространства $L,$ дающие наиболее эффективные результаты:

• $L=K$ и $L=AK$
• $L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})$

$L=K$ и $L=AK$

Теорема. Если матрица А симметрична и положительно определена, то задача проектирования СЛАУ $Ax=b$ на любое подпространство $K$ ортогонально к подпространству $L=K$ эквивалентна задаче минимизации функционала $\Phi _{1}(x)=\parallel x-{\tilde {x}}\parallel _{A}^{2},$ где $\parallel x\parallel _{A}^{2}=(Ax,x).$

Доказательство

В силу положительной определённости матрицы $A$ функционал $\Phi _{1}(x)$ достигает своего минимума при $x={\tilde {x}}$ и является строго выпуклым. При этом

$\Phi _{1}(x)=(A(x-{\tilde {x}}),x-{\tilde {x}})=(Ax,x)-(A{\tilde {x}},x)-(Ax,{\tilde {x}})+(A{\tilde {x}},{\tilde {x}})=$ $=(Ax,x)-(Ax,{\tilde {x}})-(b,x)+(b,{\tilde {x}})=x^{T}Ax-{\tilde {x}}^{T}Ax-b^{T}x+b^{T}{\tilde {x}}.$

В силу симметричности матрицы $A$ справедливо ${\tilde {x}}^{T}Ax=b^{T}A(A^{-1})x=b^{T}x,$ и функционал равен

$\Phi _{1}(x)=x^{T}Ax-2b^{T}x+b^{T}{\tilde {x}}.$

По условию теоремы $K=L,$ следовательно $V=W.$ Функционал $\Phi _{1}(x)$ является строго выпуклым. Таким образом сформулированная в условии задача минимизации сводится к нахождению

$y=\arg \min _{y}\Phi _{1}(x_{0}+Vy).$

Рассмотрим эту задачу. В силу выпуклости достаточно найти стационарную точку функционала $\Psi (y)=\Phi _{1}(x_{0}+Vy),$ т.е. решить систему ${\mathcal {r}}\Psi (y)=0.$

$\Psi (y)=(x_{0}+Vy)^{T}A(x_{0}+Vy)-2b^{T}(x_{0}+Vy)+b^{T}{\tilde {x}}=$ $=(x_{0}^{T}A-b^{T})x_{0}-b^{T}x_{0}+2(x_{0}^{T}A-b^{T})Vy+y^{T}(V^{T}AV)y+b^{T}{\tilde {x}}=$ $=y^{T}(V^{T}AV)y-r_{0}^{T}x_{0}-b^{T}x_{0}-2r_{0}^{T}Vy+b^{T}{\tilde {x}}.$

Градиент этого функционала равен ${\mathcal {r}}\Psi _{1}(y)=2V^{T}AVy-2V^{T}r_{0}.$ Приравнивая его к нулю, получим

$y=(V^{T}AV)^{-1}V^{T}r_{0},$

что в точности совпадает с выражением $y=(W^{T}AV)^{-1}W^{T}r_{0},$ если положить в нём $V=W.$

Теорема. Если матрица А невырождена, то задача проектирования СЛАУ $Ax=b$ на любое подпространство $K$ ортогонально к подпространству $L=AK$ эквивалентна задаче минимизации функционала $\Phi _{2}(x)=\parallel r_{x}\parallel _{2}^{2}.$

Доказательство

Подставив в формулу $y=(W^{T}AV)^{-1}W^{T}r_{0}$ соотношение для базисов $W=AV,$ получим:

$y=(V^{T}A^{T}AV)^{-1}V^{T}A^{T}r_{0}.$

Это означает что рассматриваемая ситуация эквивалентна выбору $L=K$ для симметризованной системы $A^{T}Ax=A^{T}b.$

Учитывая соотношение

$\parallel x-{\tilde {x}}\parallel _{A^{T}A}^{2}=(A^{T}A(x-{\tilde {x}}),(x-{\tilde {x}}))_{2}=(A(x-{\tilde {x}}),A(x-{\tilde {x}}))_{2}=(r_{x},r_{x})_{2}=\parallel r_{x}\parallel _{2}^{2}$

и применяя к такой системе предыдущую теорему получим сформулированное в условии утверждение.

$L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})$

Для построения каждого нового вектора $v_{k}$ алгоритм ортогонализации Арнольди требует нахождения $(k-1)$ скалярных произведений и столько же операций линейного комбинирования.

Литература

• Saad Y. Iterative methods for sparse linear systems. — 2nd edition. — SIAM Society for Industrial & Applied Mathematics, 2003. — С. 477. — ISBN 0898715342.
• Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. — Новосибирск: НГТУ, 2000. — С. 70.
• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — Москва: Мир, 1999.
• Ильин В.П. Методы неполной факторизации для решения линейных систем. — Москва: Физматлит, 1995.