Проекционные методы решения СЛАУ — класс итерационных методов, в которых решается задача проектирования неизвестного вектора на некоторое пространство оптимально относительно другого некоторого пространства.
Рассмотрим СЛАУ где - квадратная матрицаразмерности Пусть и - два -мерных подпространства пространства
Необходимо найти такой вектор , чтобы т.е. выполнялось условие:
называемое условием Петрова-Галёркина.
Если известно начальное приближение , то тогда решение должно проектироваться на аффинное пространство
Представим и обозначим невязку начального приближения как
Тогда постановку задачи можно сформулировать следующим образом:
Необходимо найти такое чтобы т.е. выполнялось условие:
Хотя выбор подпространства и не оказывает влияния на тип полиномиальной аппроксимации, он оказывает существенное влияние на эффективность метода.
На сегодняшний день известны 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.