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

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

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

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

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

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

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

$b-A\tilde{x}=b-A(x_0+\delta )=b-A{x}_0-A\delta =(b-A{x}_0)-A\delta =r_0-A\delta .$

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

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

$\mathrm{\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 )=\overline{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-A{x}_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}A{v}_k,w_k)=(r_k,w_k)-{\gamma }_k(A{v}_k,w_k)=\overline{0},$

откуда ${\gamma }_k=\frac{(r_k,w_k)}{(A{v}_k,w_k)}.$

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

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

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

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

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

${𝒦}_m(r_0,A)=span\{r_0,A{r}_0,A^2{r}_0,...,A^{m-1}{r}_0\},$

где $r_0=b-A{x}_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={𝒦}_m({\tilde{r}}_0,A^T)$

$L=K$ и $L=AK$

$L={𝒦}_m({\tilde{r}}_0,A^T)$

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга