Метод минимального остатка
Метод расчета
Сравнение нормы ошибки и остатка в методе CG (синий) и методе MINRES (зеленый). Используемая матрица взята из 2D краевой задачи .

Метод минимальной невязки или MINRES — это метод подпространства Крылова для итерационного решения симметричных систем линейных уравнений . Он был предложен математиками Кристофером Конвеем Пейджем и Майклом Аланом Сондерсом в 1975 году. [1]

В отличие от популярного метода CG , метод MINRES не предполагает, что матрица положительно определена , обязательна только симметрия матрицы.

GMRES против MINRES

Метод GMRES по сути является обобщением MINRES для произвольных матриц. Оба минимизируют 2-норму остатка и выполняют те же вычисления в точной арифметике, когда матрица симметрична. MINRES является короткорекуррентным методом с постоянным требованием к памяти, тогда как GMRES требует хранения всего пространства Крылова, поэтому его требование к памяти примерно пропорционально числу итераций. С другой стороны, GMRES имеет тенденцию меньше страдать от потери ортогональности. [1] [2]

Свойства метода MINRES

Метод MINRES итеративно вычисляет приближенное решение линейной системы уравнений вида , где — симметричная матрица , а вектор . А х = б , {\displaystyle Ах=b,} А ∈ Р н × н {\displaystyle A\in \mathbb {R} ^{n\times n}} б ∈ Р н {\displaystyle b\in \mathbb {R} ^{n}}

Для этого минимизируется норма невязки в -мерном подпространстве Крылова . Здесь — начальное значение (часто ноль) и . г ( х ) := б − А х {\displaystyle r(x):=b-Ax} к {\displaystyle к} В к = х 0 + охватывать ⁡ { г 0 , А г 0 … , А к − 1 г 0 } {\displaystyle V_{k}=x_{0}+\operatorname {span} \{r_{0},Ar_{0}\ldots ,A^{k-1}r_{0}\}} х 0 ∈ Р н {\displaystyle x_{0}\in \mathbb {R} ^{n}} г 0 := г ( х 0 ) {\displaystyle r_{0}:=r(x_{0})}

Точнее, мы определяем приближенные решения через , где — стандартная евклидова норма на . х к {\displaystyle x_{k}} х к := а г г м я н х ∈ В к ‖ г ( х ) ‖ , {\displaystyle x_{k}:=\mathrm {argmin} _{x\in V_{k}}\|r(x)\|,} ‖ ⋅ ‖ {\displaystyle \|\cdot \|} Р н {\displaystyle \mathbb {R} ^{n}}

Из-за симметрии , в отличие от метода GMRES , можно проводить этот процесс минимизации рекурсивно, сохраняя только два предыдущих шага (короткое повторение). Это экономит память. А {\displaystyle А}

Алгоритм MINRES

Примечание: Метод MINRES сложнее алгебраически эквивалентного метода сопряженных остатков. Поэтому ниже в качестве замены был создан метод сопряженных остатков (CR). Он отличается от MINRES тем, что в MINRES столбцы базиса пространства Крылова (обозначаемого ниже как ) могут быть ортогонализированы, тогда как в CR их образы (обозначаемые ниже как ) могут быть ортогонализированы с помощью рекурсии Ланцоша. Существуют более эффективные и предобусловленные варианты с меньшим количеством AXPY. Сравните со статьей. п к {\displaystyle p_{k}} с к {\displaystyle s_{k}}

Сначала вы выбираете произвольное и вычисляете х 0 ∈ Р н {\displaystyle x_{0}\in \mathbb {R} ^{n}} г 0 = б − А х 0 п 0 = г 0 с 0 = А п 0 {\displaystyle {\begin{align}r_{0}&=b-Ax_{0}\\p_{0}&=r_{0}\\s_{0}&=Ap_{0}\end{align}}}

Затем мы повторяем следующие шаги: к = 1 , 2 , … {\displaystyle k=1,2,\точки}

  • Вычислить через х к , г к {\displaystyle x_{k},r_{k}}

    α к − 1 = ⟨ г к − 1 , с к − 1 ⟩ ⟨ с к − 1 , с к − 1 ⟩ {\displaystyle \alpha _{k-1} = {\frac {\langle r_{k-1},s_{k-1} \rangle {\langle s_{k-1},s_{k-1} \rangle }}} х к = х к − 1 + α к − 1 п к − 1 {\displaystyle x_{k}=x_{k-1}+\альфа _{k-1}p_{k-1}} г к = г к − 1 − α к − 1 с к − 1 {\displaystyle r_{k}=r_{k-1}-\альфа _{k-1}s_{k-1}} если меньше указанного допуска, алгоритм прерывается приближенным решением . В противном случае новое направление спуска вычисляется через ‖ г к ‖ {\displaystyle \|r_{k}\|} х к {\displaystyle x_{k}} п к {\displaystyle p_{k}} п к ← с к − 1 {\displaystyle p_{k}\leftarrow s_{k-1}}

    с к ← А с к − 1 {\displaystyle s_{k}\leftarrow As_{k-1}}
  • для (шаг не выполняется на первом шаге итерации) вычислить: л = 1 , 2 {\displaystyle l=1,2} л = 2 {\displaystyle l=2} β к , л = ⟨ с к , с к − л ⟩ ⟨ с к − л , с к − л ⟩ {\displaystyle \beta _{k,l} = {\frac {\langle s_{k},s_{kl} \rangle {\langle s_{kl},s_{kl}\rangle }}} п к ← п к − β к , л п к − л {\displaystyle p_{k}\leftarrow p_{k}-\beta _{k,l}p_{kl}} с к ← с к − β к , л с к − л {\displaystyle s_{k}\leftarrow s_{k}-\beta _{k,l}s_{kl}}

Скорость сходимости метода MINRES

В случае положительно определенных матриц скорость сходимости метода MINRES можно оценить аналогично методу CG. [3] Однако в отличие от метода CG оценка применяется не к ошибкам итераций, а к остаткам. Применяется следующее:

‖ г к ‖ ≤ 2 ( к ( А ) − 1 к ( А ) + 1 ) к ‖ г 0 ‖ , {\displaystyle \|r_{k}\|\leq 2\left({\frac {{\sqrt {\kappa (A)}}-1}{{\sqrt {\kappa (A)}}+1}}\right)^{k}\|r_{0}\|,}

где — число обусловленности матрицы . Поскольку является нормальным, то имеем , где и — максимальные и минимальные собственные значения матрицы , соответственно. к ( А ) {\displaystyle \каппа (А)} А {\displaystyle А} А {\displaystyle А} к ( А ) = | λ макс ( А ) | | λ мин ( А ) | , {\displaystyle \kappa (A)={\frac {\left|\lambda _{\text{max}}(A)\right|}{\left|\lambda _{\text{min}}(A)\right|}},} λ max ( A ) {\displaystyle \lambda _{\text{max}}(A)} λ min ( A ) {\displaystyle \lambda _{\text{min}}(A)} A {\displaystyle A}

Реализация в GNU Octave / MATLAB

функция [x, r] = minres ( A, b, x0, maxit, tol )  х = х0 ;   г = б - А * х0 ;       р0 = г ;   s0 = А * р0 ;     р1 = р0 ;   с1 = с0 ;   для iter = 1 : maxit    р2 = р1 ; р1 = р0 ;      с2 = с1 ; с1 = с0 ;      альфа = r '* s1 / ( s1 '* s1 );     х = х + альфа * р1 ;       г = г - альфа * s1 ;       если ( г '* г < толь ^ 2 )    перерыв конец р0 = с1 ;   s0 = А * s1 ;     бета1 = s0 '* s1 / ( s1 '* s1 );     p0 = p0 - бета1 * p1 ;       s0 = s0 - бета1 * s1 ;       если итер > 1    бета2 = s0 '* s2 / ( s2 '* s2 );     р0 = р0 - бета2 * р2 ;       s0 = s0 - бета2 * s2 ;       конец конецконец

Ссылки

  1. ^ ab Кристофер С. Пейдж, Майкл А. Сондерс (1975). «Решение разреженных неопределенных систем линейных уравнений». Журнал SIAM по численному анализу . 12 (4): 617– 629. doi :10.1137/0712047.
  2. ^ Нифа, М. Науфаль (24 ноября 2017 г.). Эффективные решатели для ограниченной оптимизации в задачах идентификации параметров (PDF) (Докторская диссертация). Университет Париж Сакле (COmUE). стр.  51–52 .
  3. ^ Свен Гросс, Арнольд Реускен (6 мая 2011 г.). Численные методы для двухфазных несжимаемых течений . раздел 5.2: Springer. ISBN 978-3-642-19685-0.{{cite book}}: CS1 maint: location (link)
  • Метод минимального остатка, Wolfram MathWorld, 26 июля 2022 г.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimal_residual_method&oldid=1264242825"