Computational method
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.
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.
Properties of the MINRES method.
The MINRES method iteratively calculates an approximate solution of a linear system of equations of the form
formula_1
where formula_2 is a symmetric matrix and formula_3 a vector.
For this, the norm of the residual formula_4 in a formula_5-dimensional Krylov subspace
formula_6
is minimized. Here formula_7 is an initial value (often zero) and formula_8.
More precisely, we define the approximate solutions formula_9 through
formula_10
where formula_11 is the standard Euclidean norm on formula_12.
Because of the symmetry of formula_13, 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 formula_14) can be orthogonalized, whereas in CR their images (below labeled with formula_15) can be orthogonalized via the Lanczos recursion. There are more efficient and preconditioned variants with fewer AXPYs. Compare with the article.
First you choose formula_7 arbitrary and compute
formula_17
Then we iterate for formula_18 in the following steps:
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. 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:
formula_19
where formula_20 is the condition number of matrix formula_13. Because formula_13 is normal, we have
formula_23
where formula_24 and formula_25 are maximal and minimal eigenvalues of formula_13, 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