Решение системы линейных уравнений методом сопряженных градиентов

Метод сопряженных градиентов - это наиболее популярный метод для решения системы линейных уравнений с разреженной симметричной положительно определенной матрицей. Алгоритм обладает тремя притягательными чертами. Во-первых, он использует только операцию умножения матрицы системы на вектор, т.е. может применяться как для решения задач, в которых матрица системы задана в явной форме, так и для решения задач, в которых матрица доступна только через операцию умножения на вектор. Во-вторых, алгоритм требует фиксированного времени на каждую итерацию, независимо от числа осуществленных итераций (в некоторых алгоритмах это условие не выполняется: например, трудоемкость отдельной итерации алгоритма GMRES растет прямо пропорционально её номеру). Третим достоинством является то, что алгоритм всегда сходится.

Метод сопряженных градиентов является одним из методов подпространств Крылова, т.е. методов, строящих ортогональный базис подпространства span{ r₀ , Ar₀ , A ²r₀ , ..., A ⁱr₀ } для некоторого стартового вектора r₀ . Решение исходной системы Ax = b ищется на этом подпространстве путем минимизации невязки. Два свойства алгоритма, отмеченные выше, вытекают из того, что для построения ортогонального базиса используются последовательное умножение стартового вектора на матрицу A и трехчленные рекуррентные соотношения для ортогонализации генерируемых векторов (отсюда постоянные затраты на одну итерацию - каждый новый вектор ортогонализируется путем операций только с двумя предыдущими векторами). В связи с тем, что метод сопряженных градиентов описан в ряде источников, я не буду приводить здесь более подробное описание алгоритма. Краткое, но емкое изложение можно найти в Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, рекомендую всем ознакомиться с материалом.

Приведенная здесь реализация алгоритма решает систему с разреженной матрицей в формате проекта ALGLIB. Этот формат и способы работы с матрицами, представленными в нем, описаны на странице "базовые операции", здесь предполагается, что читатель уже знаком с этой информацией. Как уже говорилось, алгоритм использует матрицу системы только через операцию умножения на вектор, так что если матрица системы задана неявным способом, программист может самостоятельно переписать подпрограмму SparseCG, заменив вызов подпрограммы SparseMV на собственную реализацию умножения матрицы системы на вектор.

This article is intended for personal use only.

Скачать ALGLIB