Метод минимальной невязки

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

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

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

ГМРЕС против МИНРЕС

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

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

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

Для этого норма остатка $r(x):=b-Ax$ в $k$-dimensional Krylov subspace $$V_{k}=x_{0}+\operatorname {span} \{r_{0},Ar_{0}\ldots ,A^{k-1}r_{0}\}$$ сведен к минимуму. Здесь $x_{0}\in \mathbb {R} ^{n}$ — начальное значение (часто нулевое) и $r_{0}:=r(x_{0})$.

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

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

Алгоритм МИНРЕС

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

Сначала вы выбираете $x_{0}\in \mathbb {R} ^{n}$ произвольный и вычислительный $${\begin{aligned}r_{0}&=b-Ax_{0}\\p_{0}&=r_{0}\\s_{0}&=Ap_{0}\end{aligned}}$$

Затем мы повторяем $k=1,2,\dots$ в следующих шагах:

• Вычислить $x_{k},r_{k}$ через

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

  $$s_{k}\leftarrow As_{k-1}$$
• для $l=1,2$ (шаг $l=2$ не выполняется на первом шаге итерации) вычисляем: $$\beta _{k,l}={\frac {\langle s_{k},s_{k-l}\rangle }{\langle s_{k-l},s_{k-l}\rangle }}$$ $$p_{k}\leftarrow p_{k}-\beta _{k,l}p_{k-l}$$ $$s_{k}\leftarrow s_{k}-\beta _{k,l}s_{k-l}$$

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

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

$$\|r_{k}\|\leq 2\left({\frac {{\sqrt {\kappa (A)}}-1}{{\sqrt {\kappa (A)}}+1}}\right)^{k}\|r_{0}\|,$$

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

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

function [x, r] = minres(A, b, x0, maxit, tol)
  x = x0;
  r = b - A * x0;
  p0 = r;
  s0 = A * p0;
  p1 = p0;
  s1 = s0;
  for iter = 1:maxit
    p2 = p1; p1 = p0;
    s2 = s1; s1 = s0;
    alpha = r'*s1 / (s1'*s1);
    x = x + alpha * p1;
    r = r - alpha * s1;
    if (r'*r < tol^2)
      break
    end
    p0 = s1;
    s0 = A * s1;
    beta1 = s0'*s1 / (s1'*s1);
    p0 = p0 - beta1 * p1;
    s0 = s0 - beta1 * s1;
    if iter > 1
      beta2 = s0'*s2 / (s2'*s2);
      p0 = p0 - beta2 * p2;
      s0 = s0 - beta2 * s2;
    end
  end
end

Внешние ссылки

• Метод минимальной невязки , Wolfram MathWorld, 26 июля 2022 г.