Русская Википедия:Проекционные методы решения СЛАУ
Проекционные методы решения СЛАУ — класс итерационных методов, в которых решается задача проектирования неизвестного вектора на некоторое пространство оптимально относительно другого некоторого пространства.
Постановка задачи
Рассмотрим СЛАУ <math>Ax=b,</math> где <math>A</math> - квадратная матрица размерности <math>n.</math> Пусть <math>K </math> и <math>L</math> - два <math>m</math>-мерных подпространства пространства <math>R^n.</math> Необходимо найти такой вектор <math>\tilde{x} \in K </math>, чтобы <math> b-A\tilde{x} \perp L, </math> т.е. выполнялось условие:
<math>\forall l\in L: (A\tilde{x} ,l)=(b,l), </math>
называемое условием Петрова-Галёркина.
Если известно начальное приближение <math>x_0</math>, то тогда решение должно проектироваться на аффинное пространство <math>x_0 +K. </math> Представим <math>\tilde{x} =x_0+ \delta </math> и обозначим невязку начального приближения как <math>r_0 = b- Ax_0. </math>
<math>b-A \tilde{x} =b-A( x_0 + \delta ) =b- Ax_0 - A \delta =(b- Ax_0)- A \delta = r_0 -A \delta .</math>
Тогда постановку задачи можно сформулировать следующим образом: Необходимо найти такое <math>\delta \in K, </math> чтобы <math> r_0 -A \delta \perp L ,</math> т.е. выполнялось условие:
<math>\tilde{x}=x_0+ \delta,\ \delta \in K </math>
<math> \forall l\in L:(r_0-A \delta ,l)=0</math>
Общий подход к построению проекционных методов
Введём матричные базисы в пространствах <math>K</math> и <math>L:</math>
<math>V=[ v_1 , v_2 , ... , v_m ]</math> - матрица размера <math>n \times m </math> составленная из базисных векторов-столбцов пространства <math>K.</math> <math>W=[ w_1 , w_2 , ... , w_m ]</math> - матрица размера <math>n \times m </math> составленная из базисных векторов-столбцов пространства <math>L.</math>
Тогда <math>\delta\ = Vy</math> и вектор-решение <math>\tilde{x} </math> может быть записан:
<math>\tilde{x} = x_0 + Vy, </math>
где <math>y\in R^m </math> - вектор коэффициентов.
Тогда выражение <math> (r_0-A \delta\ ,l)=0</math> может быть переписано в виде:
<math>W^T (r_0-A \delta\ )= \bar{0}, </math>
откуда <math>W^T A Vy = W^T r_0</math> и
<math>y = (W^T A V)^{-1} W^T r_0,</math>
Таким образом решение должно уточняться в соответствии с формулой:
<math>x_1 = x_0 + V(W^T A V)^{-1} W^T r_0,</math>
Общий вид любого метода проекционного класса:
Делать, пока не найдено решение.
- Выбираем пару подпространств <math>K</math> и <math>L.</math>
- Построение для <math>K</math> и <math>L</math> базисов <math>V=[ v_1 , v_2 , ... , v_m ]</math> и <math>W=[ w_1 , w_2 , ... , w_m ].</math>
- <math>r_0 = b - Ax_0. </math>
- <math>y = (W^T A V)^{-1} W^T r_0.</math>
- <math>x_1 = x_0 + Vy.</math>
Выбор пространств <math>K</math> и <math>L</math> и способ построения для них базисов полностью определяет вычислительную схему метода.
Выбор подпространств K и L
Случай одномерных подпространств K и L
В случае когда пространства <math>K</math> и <math>L</math> одномерны, их матричные базисы являются векторами: <math>V=[v]</math> и <math>W=[w]</math> и выражение <math>\tilde{x} = x_0 + Vy, </math> можно переписать как
<math>x_{k+1} = x_k + \gamma_k\ v_k, </math>
где <math> \gamma_k\ </math> - неизвестный коэффициент, который легко находится из условия ортогональности <math> r_k - A( \gamma_k\ v_k ) \perp w_k :</math>
<math>(r_k - \gamma_k\ Av_k,w_k) =(r_k , w_k) - \gamma_k\ (Av_k,w_k)= \bar{0},</math>
откуда <math>\gamma_k\ = \frac {(r_k , w_k)}{(Av_k,w_k)}.</math>
Методы с выбором одномерных подпространств <math>K</math> и <math>L</math> :
- Метод наискорейшего спуска
- Метод наискорейшего уменьшения невязки
- Метод Гаусса-Зейделя
- Методы ABS-класса
В практических задачах методы использующие одномерные пространства <math>K</math> и <math>L</math> обладают достаточно медленной сходимостью.
Методы Крыловского типа
Методы Крыловского типа (или методы подпространства Крылова) - это методы для которых в качестве подпространства <math>K</math> выбирается подпространство Крылова:
<math>\mathcal{K}_m (r_0,A) = span \{r_0, Ar_0, A^2 r_0, ..., A^{m-1} r_0\} ,</math>
где <math>r_0=b-Ax_0</math> - невязка начального приближения. Различные версии методов подпространства Крылова обуславливаются выбором подпространства <math>L.</math>
С точки зрения теории аппроксимации, приближения <math>\tilde{x},</math> полученные в методах подпространства Крылова имеют форму
<math>A^{-1}b \approx \tilde{x}=x_0+q_{m-1}(A)r_0,</math>
где <math>q_{m-1}</math> - полином степени <math>m-1.</math> Если положить <math>x_0=0,</math>, то
<math>A^{-1}b \approx q_{m-1}(A)b.</math>
Другими словами, <math>A^{-1}b</math> аппроксимируется <math>q_{m-1}(A)b.</math>
Хотя выбор подпространства <math>L</math> и не оказывает влияния на тип полиномиальной аппроксимации, он оказывает существенное влияние на эффективность метода. На сегодняшний день известны 2 способа выбора подпространства <math>L,</math> дающие наиболее эффективные результаты:
- <math>L=K</math> и <math>L=AK</math>
- <math>L=\mathcal{K}_m (\tilde{r}_0,A^T)</math>
- <math>L=K</math> и <math>L=AK</math>
- <math>L=\mathcal{K}_m (\tilde{r}_0,A^T)</math>
Для построения каждого нового вектора <math>v_k</math> алгоритм ортогонализации Арнольди требует нахождения <math>(k-1)</math> скалярных произведений и столько же операций линейного комбинирования.
Литература
Шаблон:Методы решения СЛАУ Шаблон:Rq
