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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Постановка задачи[править | править код]

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

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

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

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

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

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

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

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

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

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

откуда и

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

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

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

  1. Выбираем пару подпространств и
  2. Построение для и базисов и

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

Выбор подпространств K и L[править | править код]

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

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

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

откуда

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

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

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

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

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

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

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

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

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

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

где

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

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

Литература[править | править код]

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