WikiSort.ru - Не сортированное

Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа.

Постановка задачи

Пусть дана система линейных уравнений: ${\displaystyle Ax=b}$ . Причём матрица системы — это действительная матрица, обладающая следующими свойствами: ${\displaystyle A=A^{T}>0}$ , то есть это симметричная положительно определённая матрица. Тогда процесс решения СЛАУ можно представить как минимизацию следующего функционала:

За ${\displaystyle (\cdot ,\cdot )}$ обозначено скалярное произведение. Минимизируя данный функционал, используя подпространства Крылова, получаем алгоритм метода сопряженных градиентов.

Алгоритм

Подготовка перед итерационным процессом

1. Выберем начальное приближение ${\displaystyle x^{0}}$
2. ${\displaystyle r^{0}=b-Ax^{0}}$
3. ${\displaystyle z^{0}=r^{0}}$

${\displaystyle k}$ -я итерация метода^[1]

1. ${\displaystyle \alpha _{k}={\frac {(r^{k-1},r^{k-1})}{(Az^{k-1},z^{k-1})}}}$
2. ${\displaystyle x^{k}=x^{k-1}+\alpha _{k}z^{k-1}}$
3. ${\displaystyle r^{k}=r^{k-1}-\alpha _{k}Az^{k-1}}$
4. ${\displaystyle \beta _{k}={\frac {(r^{k},r^{k})}{(r^{k-1},r^{k-1})}}}$
5. ${\displaystyle z^{k}=r^{k}+\beta _{k}z^{k-1}}$

Критерий остановки

Поскольку минимизируемый функционал квадратичный, то процесс должен дать ответ на ${\displaystyle n}$ -й итерации, однако при реализации метода на компьютере существует погрешность представления вещественных чисел, в результате чего может потребоваться и больше итераций. Так же оценивать точность можно по относительной невязке ${\displaystyle {\frac {||r^{k}||}{||b||}}}$ , и прекращать итерационный процесс когда невязка станет меньше заданного числа.

Алгоритм для предобусловленной системы

Пусть предобусловленная система имеет вид: ${\displaystyle SAQx=Sb}$ , тогда алгоритм метода для такой системы можно записать следующим образом:

Подготовка перед итерационным процессом

1. Выберем начальное приближение ${\displaystyle x^{0}}$
2. ${\displaystyle r^{0}=Q(b-SAx^{0})}$
3. ${\displaystyle z^{0}=r^{0}}$
4. ${\displaystyle {\widetilde {x}}^{0}=Qx^{0}}$

${\displaystyle k}$ -я итерация метода

1. ${\displaystyle \alpha _{k}={\frac {(r^{k-1},r^{k-1})}{(SAQz^{k-1},z^{k-1})}}}$
2. ${\displaystyle {\widetilde {x}}^{k}={\widetilde {x}}^{k-1}+\alpha _{k}z^{k-1}}$
3. ${\displaystyle r^{k}=r^{k-1}-\alpha _{k}SAQz^{k-1}}$
4. ${\displaystyle \beta _{k}={\frac {(r^{k},r^{k})}{(r^{k-1},r^{k-1})}}}$
5. ${\displaystyle z^{k}=r^{k}+\beta _{k}z^{k-1}}$

После итерационного процесса

1. ${\displaystyle x^{*}=Q^{-1}{\widetilde {x}}^{m}}$ , где ${\displaystyle x^{*}}$  — приближенное решение системы, ${\displaystyle m}$  — общее число итераций метода.

Критерий остановки

В данном случае можно использовать те же критерии остановки, что и для обычной системы, только с учётом предобуславливания. Например относительная невязка станет вычисляться как: ${\displaystyle {\frac {||{\widetilde {r}}^{k}||}{||Sb||}}}$ , однако можно пользоваться и невязкой исходной системы, которая вычисляется следующим образом: ${\displaystyle {\frac {||r^{k}||}{||b||}}={\frac {||Q^{-1}{\widetilde {r}}^{k}||}{||b||}}}$

Особенности и обобщения

Как и все методы на подпространствах Крылова, метод сопряженных градиентов от матрицы требует только возможность умножать её на вектор, что приводит к возможности использовать специальные форматы хранения матрицы(такие, как разреженный) и сэкономить память на хранении матрицы.
Метод часто используется для решения конечноэлементых СЛАУ.
У метода есть обобщения: метод бисопряженных градиентов, для работы с несимметричными матрицами. И комплексный метод сопряженных градиентов, где матрица ${\displaystyle A}$ может содержать комплексные числа, но должна удовлетворять условию: ${\displaystyle A=A^{*}>0}$ , то есть быть самосопряженной-положительно определённой матрицей.

Примечания