Numerical methods for Data Assimilation

• an non singular matrix.

• Krylov subspace

• Arnoldi algorithm on , startineg with generates an orthonormal set of vectors such that , with , upper-Hessenberg.

• Breakdown of the algorithm when is an -invariant subspace.

Iterate in the Krylov space

• The Ritz-Galerkin approach (e.g. FOM, Lanczos method, CG) :

  

• The minimum norm residual approach (e.g. GMRES, MINRES) :

  

• The Petrov-Galerkin approach (e.g. BiCG, QMR)

• The minimum norm error approach (e.g. SYMMLQ) :

  

The GMRES iterate is the vector of such that

The minimizer is n general inexpeensive to compute since it requires the solution of an linear least-squares problem.

• Take the basic GMRES method,

• And perturb the matrix-vector products

  . Easy way to control the inner accuracy.

• Why ?

  • The matrix is not known with full accuracy (Parameter estimation, Schur complement,...)

  • Computing with a poor accuracy is cheap (FMM)

Consider the normwise backward error , and .

Abundant numerical illustration in Bouras, Frayssé, Giraud (00) and Bouras, Frayssé (04) reports that if a {\color{red}{relaxed}} GMRES is run on a computer,

• using perturbations controlled so that

  ,

• The GMRES iterate reaches for some a backward error less than .

• BFG criterion

  ,

• Never perform perturbations

  • smaller than the target backward error ,

  • greater than

  • Theoretical criterion : knowledge of the exact required.

  • Scaling issues ...

Let . Arnoldi relation

• Invariance of the backward error of the GMRES iterates, while considering

  • , initial guess

  • , initial guess

  • , initial guess

• In practice, if the control is not scaling invariant, the perturbation size allowed by the relaxation criterion might be arbitrarily small/large.

• This might prevent the relaxed algorithm from converging to .

• Exact arithmetic assumed

• From the Gram-Schmidt process follows the inexact Arnoldi relation

  

  

• Least squares

• True residual

• Computed residual . The norm is readily available from the incremental solution of the least squares

Van den Eshof, Slejpen (04) and Szyld, Simoncini (03) define . The inexact Arnoldi reads

.

• The computed residuals norm are non increasing,

• there exists a family of matrices such that {

  , , then

• Information on the exact residual obtained from

View GMRES as a GMRES :

• The inexact Arnoldi relation reads

  

• The breakdown of Flexible GMRES studied in (Saad (03)) shows that an happy breakdown at step ( ) occurs if is nonsingular.

• .The happy breakdown

• In the case of Flexible GMRES, the solution to the original system is .

• In the inexact method, is not available.

Forthcoming activity : derive a relaxation strategy such that an happy breakdown necessarily occurs and that

Let . If , and if the perturbations are such that,

b where \ then at the breakdown, .

• Requires only the computed residual.

• Approximations of and needed.

• Replacing by leads to a more stringent criterion in which is not needed.

• The matrices are obtained using random matrices ( function )

• Strategy SI

  

• Strategy NSI ( )

  .

• Result of J.~Drkosova and M.Rozloznik and Z.Strakos and A.~Greenbaum(95) shows that if , the Householder GMRES running using the working precision reaches a backward error , where depends on the problem size and on the details of the arithmetic.

• Empirical Strategy SIBS defined by

  

  In this case, perturbations are never smaller than .