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

Постановка задачи Рассмотрим СЛАУ где - квадратная матрица размерности Пусть и - два -мерных подпространства пространства Необходимо найти такой вектор , чтобы т.е. выполнялось условие:

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

Если известно начальное приближение , то тогда решение должно проектироваться на аффинное пространство Представим и обозначим невязку начального приближения как

Тогда постановку задачи можно сформулировать следующим образом: Необходимо найти такое чтобы т.е. выполнялось условие:

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

- матрица размера составленная из базисных векторов-столбцов пространства - матрица размера составленная из базисных векторов-столбцов пространства

Тогда и вектор-решение может быть записан:

где - вектор коэффициентов.

Тогда выражение может быть переписано в виде:

откуда и

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

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

Делать, пока не найдено решение. Выбираем пару подпространств и Построение для и базисов и

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

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

Случай одномерных подпространств K и L В случае когда пространства и одномерны, их матричные базисы являются векторами: и и выражение можно переписать как

где - неизвестный коэффициент, который легко находится из условия ортогональности

откуда

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

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

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

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

где - невязка начального приближения. Различные версии методов подпространства Крылова обуславливаются выбором подпространства

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

где - полином степени Если положить , то

Другими словами, аппроксимируется

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

и Теорема Если матрица А симметрична и положительно определена, то задача проектирования СЛАУ на любое подпространство ортогонально к подпространству эквивалентна задаче минимизации функционала

где

Теорема Если матрица А невырождена, то задача проектирования СЛАУ на любое подпространство ортогонально к подпространству эквивалентна задаче минимизации функционала

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

Литература

Категория:Методы решения СЛАУ