- Проекционные методы решения СЛАУ
-
Проекционные методы решения СЛАУ — класс итерационных методов, в которых решается задача проектирования неизвестного вектора на некоторое пространство оптимально относительно другого некоторого пространства.
Содержание
Постановка задачи
Рассмотрим СЛАУ
где
- квадратная матрица размерности
Пусть
и
- два
-мерных подпространства пространства
Необходимо найти такой вектор
, чтобы
т.е. выполнялось условие:
называемое условием Петрова-Галёркина.
Если известно начальное приближение
, то тогда решение должно проектироваться на аффинное пространство
Представим
и обозначим невязку начального приближения как
Тогда постановку задачи можно сформулировать следующим образом: Необходимо найти такое
чтобы
т.е. выполнялось условие:
Общий подход к построению проекционных методов
Введём матричные базисы в пространствах
и
- матрица размера
составленная из базисных векторов-столбцов пространства
- матрица размера
составленная из базисных векторов-столбцов пространства
Тогда
и вектор-решение
может быть записан:
где
- вектор коэффициентов.
Тогда выражение
может быть переписано в виде:
откуда
и
Таким образом решение должно уточняться в соответствии с формулой:
Общий вид любого метода проекционного класса:
Делать, пока не найдено решение.
- Выбираем пару подпространств
и
- Построение для
и
базисов
и
Выбор пространстви
и способ построения для них базисов полностью определяет вычислительную схему метода.
Выбор подпространств K и L
Случай одномерных подпространств K и L
В случае когда пространства
и
одномерны, их матричные базисы являются векторами:
и
и выражение
можно переписать как
где
- неизвестный коэффициент, который легко находится из условия ортогональности
откуда
Методы с выбором одномерных подпространств
и
:
- Метод наискорейшего спуска
- Метод наискорейшего уменьшения невязки
- Метод Гаусса-Зейделя
- Методы ABS-класса
В практических задачах методы использующие одномерные пространстваи
обладают достаточно медленной сходимостью.
Методы Крыловского типа
Методы Крыловского типа (или методы подпространства Крылова) - это методы для которых в качестве подпространства
выбирается подпространство Крылова:
где
- невязка начального приближения. Различные версии методов подпространства Крылова обуславливаются выбором подпространства
С точки зрения теории аппроксимации, приближения
полученные в методах подпространства Крылова имеют форму
где
- полином степени
Если положить
, то
Другими словами,
аппроксимируется
Хотя выбор подпространства
и не оказывает влияния на тип полиномиальной аппроксимации, он оказывает существенное влияние на эффективность метода. На сегодняшний день известны 2 способа выбора подпространства
дающие наиболее эффективные результаты:
и
и
Теорема.
Если матрица А симметрична и положительно определена, то задача проектирования СЛАУна любое подпространство
ортогонально к подпространству
эквивалентна задаче минимизации функционала
где
ДоказательствоВ силу положительной определённости матрицы
функционал
достигает своего минимума при
и является строго выпуклым. При этом
В силу симметричности матрицы
справедливо
и функционал равен
По условию теоремы
следовательно
Функционал
является строго выпуклым. Таким образом сформулированная в условии задача минимизации сводится к нахождению
Рассмотрим эту задачу. В силу выпуклости достаточно найти стационарную точку функционала
т.е. решить систему
Градиент этого функционала равен
Приравнивая его к нулю, получим
что в точности совпадает с выражением
если положить в нём
Теорема.
Если матрица А невырождена, то задача проектирования СЛАУна любое подпространство
ортогонально к подпространству
эквивалентна задаче минимизации функционала
ДоказательствоПодставив в формулу
соотношение для базисов
получим:
Это означает что рассматриваемая ситуация эквивалентна выбору
для симметризованной системы
Учитывая соотношение
и применяя к такой системе предыдущую теорему получим сформулированное в условии утверждение.
Для построения каждого нового вектора
алгоритм ортогонализации Арнольди требует нахождения
скалярных произведений и столько же операций линейного комбинирования.
Литература
- Saad Y. Iterative methods for sparse linear systems. — 2nd edition. — SIAM Society for Industrial & Applied Mathematics, 2003. — С. 477. — ISBN 0898715342
- Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. — Новосибирск: НГТУ, 2000. — С. 70.
- Голуб Дж., Ван Лоун Ч. Матричные вычисления. — Москва: Мир, 1999.
- Ильин В.П. Методы неполной факторизации для решения линейных систем. — Москва: Физматлит, 1995.
Для улучшения этой статьи желательно?: - Проверить достоверность указанной в статье информации.
- Проставив сноски, внести более точные указания на источники.
- Проставить интервики в рамках проекта Интервики.
- Добавить иллюстрации.
Категория:- Методы решения СЛАУ
- Выбираем пару подпространств
Wikimedia Foundation. 2010.