Метод сопряженных остатков

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

Этот метод используется для решения линейных уравнений вида

$\mathbf {A} \mathbf {x} =\mathbf {b}$

где A — обратимая эрмитова матрица , а b — ненулевой.

Метод сопряженных остатков отличается от близкородственного метода сопряженных градиентов . Он включает в себя больше числовых операций и требует больше памяти.

Учитывая (произвольную) начальную оценку решения $\mathbf {x} _{0}$, метод описан ниже:

${\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {Ar} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {Ar} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\end{aligned}}$

итерацию можно остановить один раз $\mathbf {x} _{k}$ было признано сходящимся. Единственная разница между этим методом и методом сопряженных градиентов заключается в вычислении $\alpha _{k}$ и $\beta _{k}$ (плюс дополнительный инкрементный расчет $\mathbf {Ap} _{k}$ в конце).

Примечание: приведенный выше алгоритм можно преобразовать так, чтобы на каждой итерации выполнялось только одно симметричное умножение матрицы на вектор.

Предварительное кондиционирование

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

${\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {M} ^{-1}(\mathbf {b} -\mathbf {Ax} _{0})\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {M} ^{-1}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {M} ^{-1}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {A} \mathbf {r} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\\\end{aligned}}$

Предварительный обусловливатель $\mathbf {M} ^{-1}$ должна быть симметричной положительно определенной. Обратите внимание, что вектор невязки здесь отличается от вектора невязки без предварительной обработки.

Ссылки

• Юсеф Саад , Итеративные методы для разреженных линейных систем (2-е изд.), стр. 194, SIAM. ISBN   978-0-89871-534-7 .