ABSTRACT
FOM algorithm is an orthogonal projection method. This method seeks an approximate solution X m from the affine subspace +X K A rm ( , )0 0 by imposing the Galerkin condition
= +X X V Ym m m ,0 (4)
β= −Y H em m ( ),1 1 (5) in which β = r0 2, e1 is the first column of the ×m m identity matrix, V Hm m, are matrices created by Arnoldi algorithm. As for Approximate solution X m, the following relations hold:
Lemma 2.1 [2]. The residual vector of the approximate solution X m computed by the FOM algorithm is such that
− = − + +b AX h e Y vm m m m T
or
− = +b Ax h e Ym m m m T
GMRES algorithm is also an orthogonal projection method. Its approximate solution is given by the formula (2.3). Unlike the FOM algorithm, Ym is not given by formula (2.4), but is obtained by minimizing norm
β −e H Ym1 2. That is = +X X V Ym m m ,0 (8)
β= −Y e H Ym mmin ,1 2 (9) where Ym is the least-squares solution of overdetermined equation β −e H Ym1 2. A common technique to solve the least-squares problem min β −e H Ym1 2 is to transform the Hessenberg matrix
into upper triangular form by using Givens plane rotations. Let H m
by which H m make m times Givens plane rotations. Define
(10)
=
+ =
+
s h
h h c
h
h h i
i i( ) ,
( ) .1,
Define
+Q P P Pm m
= +H Q Hm m
And
β − = ∆ −e H Y H Ym mm mmmin min .1 2 ( ) ( )
Similar to notation Hm, define Hm m( ) and ∆m
m( ) as ×m m an upper triangular matrix and m vector which
by deleting their last row respectively. Then the least-squares solution of over-determined equation β −e H Ym1 2 hold:
As for the error of GMRES, we have the following lemma.
