Minimal residual method

{{Short description|Computational method}}

File:Minres_illustration_de.svg (blue) and the MINRES method (green). The matrix used comes from a 2D boundary-value problem.]]

The Minimal Residual Method or MINRES is a Krylov subspace method for the iterative solution of symmetric linear equation systems. It was proposed by mathematicians Christopher Conway Paige and Michael Alan Saunders in 1975.{{Cite journal |title=Solution of sparse indefinite systems of linear equations |author=Christopher C. Paige, Michael A. Saunders |date=1975 |url=https://doi.org/10.1137/0712047 |journal=SIAM Journal on Numerical Analysis |volume=12 |issue=4|pages=617–629 |doi=10.1137/0712047 |url-access=subscription }}

In contrast to the popular CG method, the MINRES method does not assume that the matrix is positive definite, only the symmetry of the matrix is mandatory.

GMRES vs. MINRES

The GMRES method is essentially a generalization of MINRES for arbitrary matrices. Both minimize the 2-norm of the residual and do the same calculations in exact arithmetic when the matrix is symmetric. MINRES is a short-recurrence method with a constant memory requirement, whereas GMRES requires storing the whole Krylov space, so its memory requirement is roughly proportional to the number of iterations. On the other hand, GMRES tends to suffer less from loss of orthogonality.{{cite thesis |first=M. Naoufal |last=Nifa |title=Efficient solvers for constrained optimization in parameter identification problems|date=24 November 2017 | type=Doctoral Thesis|url=https://www.theses.fr/2017SACLC066.pdf|pages=51–52|publisher=Université Paris Saclay (COmUE) }}

Properties of the MINRES method

The MINRES method iteratively calculates an approximate solution of a linear system of equations of the form

Ax = b,

where A\in\mathbb{R}^{n\times n} is a symmetric matrix and b\in\mathbb{R}^n a vector.

For this, the norm of the residual r(x) := b - Ax in a k-dimensional Krylov subspace

V_k = x_0 + \operatorname{span}\{r_0, Ar_0\ldots,A^{k-1}r_0\}

is minimized. Here x_0\in\mathbb{R}^n is an initial value (often zero) and r_0 := r(x_0).

More precisely, we define the approximate solutions x_k through

x_k := \mathrm{argmin}_{x\in V_k} \|r(x)\|,

where \|\cdot\| is the standard Euclidean norm on \mathbb{R}^n.

Because of the symmetry of A, unlike in the GMRES method, it is possible to carry out this minimization process recursively, storing only two previous steps (short recurrence). This saves memory.

MINRES algorithm

Note: The MINRES method is more complicated than the algebraically equivalent Conjugate Residual method. The Conjugate Residual (CR) method was therefore produced below as a substitute. It differs from MINRES in that in MINRES, the columns of a basis of the Krylov space (denoted below by p_k) can be orthogonalized, whereas in CR their images (below labeled with s_k) can be orthogonalized via the Lanczos recursion. There are more efficient and preconditioned variants with fewer AXPYs. Compare with the article.

First you choose x_0\in\mathbb{R}^n arbitrary and compute

\begin{align}

r_0 &= b - A x_0 \\

p_0 &= r_0 \\

s_0 &= A p_0

\end{align}

Then we iterate for k=1,2,\dots in the following steps:

{{unordered list

| Compute x_k,r_k through

\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}

if \|r_k\| is smaller than a specified tolerance, the algorithm is interrupted with the approximate solution x_k. Otherwise, a new descent direction p_k is calculated through

p_k \leftarrow s_{k-1}

s_k \leftarrow As_{k-1}

| for l=1,2 (the step l=2 is not carried out in the first iteration step) calculate:

\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}

}}

Convergence rate of the MINRES method

In the case of positive definite matrices, the convergence rate of the MINRES method can be estimated in a way similar to that of the CG method.{{Cite book |title=Numerical Methods for Two-phase Incompressible Flows |publisher=Springer | author=Sven Gross, Arnold Reusken |date=6 May 2011 |location=section 5.2 |isbn=978-3-642-19685-0}} In contrast to the CG method, however, the estimation does not apply to the errors of the iterates, but to the residual. The following applies:

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

where \kappa(A) is the condition number of matrix A. Because A is normal, we have

\kappa(A) = \frac{\left|\lambda_\text{max}(A)\right|}{\left|\lambda_\text{min}(A)\right|},

where \lambda_\text{max}(A) and \lambda_\text{min}(A) are maximal and minimal eigenvalues of A, respectively.

Implementation in 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

References