Конъюгированный остаточный метод - Conjugate residual method

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

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

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

куда А обратимый и Эрмитова матрица, и б отличен от нуля.

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

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

${\displaystyle {\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}}}$

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

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

Предварительная подготовка

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

${\displaystyle {\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}}}$

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

Рекомендации

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