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

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

Рассмотрим СЛАУ $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}.$

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

Цикл: пока не найдено решение, выполнять:

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

Выбор пространств $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$ :

В практических задачах методы использующие одномерные пространства $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.

Методы решения СЛАУ
Прямые методы	Матричный метод Метод Гаусса Метод Гаусса — Жордана Метод Крамера LU-разложение Разложение Холецкого Метод прогонки
Итерационные методы	Метод Якоби Метод Гаусса — Зейделя Метод итерации Метод релаксации Метод сопряженных градиентов Метод бисопряжённых градиентов Стабилизированный метод бисопряжённых градиентов
Общее	Обратная матрица Проекционные методы решения СЛАУ Предобуславливание

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

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

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

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

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

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

Литература

Дополнительно по теме

Категории