The Minimal Residual Method or MINRES is a
Krylov subspace method
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pr ...
for the iterative solution of symmetric
linear equation systems. It was proposed by mathematicians
Christopher Conway Paige
Christopher is the English version of a Europe-wide name derived from the Greek name Χριστόφορος (''Christophoros'' or '' Christoforos''). The constituent parts are Χριστός (''Christós''), "Christ" or "Anointed", and φέρει ...
and
Michael Alan Saunders in 1975.
In contrast to the popular
CG method, the MINRES method does not assume that the
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
is
positive definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular:
* Positive-definite bilinear form
* Positive-definite f ...
, only the
symmetry
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
of the matrix is mandatory. The popular
GMRES In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of an indefinite nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with ...
method is an improved generalization of MINRES but requires much more memory.
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.
[
Therefore, MINRES tends to be used only when there is not enough memory for GMRES and the matrix is symmetric. Even then, sometimes other methods are preferred, particularly CG for positive-definite matrices.
]
Properties of the MINRES method
The MINRES method iteratively calculates an approximate solution of a linear system of equations of the form
: ,
where is a symmetric matrix
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of a symmetric matrix are symmetric with re ...
and a vector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
.
For this, the norm of the residual in a -dimensional Krylov subspace
In linear algebra, the order-''r'' Krylov subspace generated by an ''n''-by-''n'' matrix ''A'' and a vector ''b'' of dimension ''n'' is the linear subspace spanned by the images of ''b'' under the first ''r'' powers of ''A'' (starting from A^0=I), ...
:
is minimized. Here is an initial value (often zero) and .
More precisely, we define the approximate solutions through
: ,
where is the standard Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean s ...
on .
Because of the symmetry of , 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 ) can be orthogonalized, whereas in CR their images (below labeled with ) can be orthogonalized via the Lanczos recursion. There are more efficient and preconditioned variants with fewer AXPYs. Compare with the article.
First you choose arbitrary and compute
:
:
:
Then we iterate for in the following steps:
* Compute through
:
:
:
: if is smaller than a specified tolerance, the algorithm is interrupted with the approximate solution . Otherwise, a new descent direction is calculated through
:
:
* for (the step is not carried out in the first iteration step) calculate:
::
::
::
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:
: ,
where is the condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the input ...
of matrix . Because is normal, we have
::
: where and are maximal and minimal eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
of , respectively.
Implementation in GNU Octave / MATLAB
function , r= minres(A, b, x0, maxit, tol)
x = x0;
r = b - A * x0;
p0 = r;
s0 = A * p0;
p1 = p0;
s1 = s0;
for iter = :maxit p2 = p1;p1 = p0;
s2 = s1;s1 = s0;
alpha = r'*s1 / (s1'*s1);
x += alpha * p1;
r -= alpha * s1;
if (r'*r < tol^2)
break
end
p0 = s1;
s0 = A * s1;
beta1 = s0'*s1 / (s1'*s1);
p0 -= beta1 * p1;
s0 -= beta1 * s1;
if iter > 1
beta2 = s0'*s2 / (s2'*s2);
p0 -= beta2 * p2;
s0 -= beta2 * s2;
end
end
end
References
External links
Minimal Residual Method
Wolfram MathWorld, Jul 26, 2022.
Numerical linear algebra