Stability of some variational iterative algorithms

Abstract

In this work we consider parallel variational algorithms for solution of linear systems AX == F, where A is a nonsingular symmetric matrix of dimension N x N, F is the right-hand side vector, and X is the solution vector. Theoretical analysis explains the superlinear convergence rate for two step gradient descent method X"+1 = X" - TnP", k >: 0, (1) / on p11^ where at odd iterations the Steepest Descent method is used (i.e. T» = (AH" B"0' an<^ a* even iterations the Minimal Residuals method is are used (i.e. Tn = /^fi" Afl"))' A new modification of the algorithm is proposed. We also consider a very interesting modification of the SD method is proposed in [2]. The following computational algorithm is used t-D-n. •Dn yn+l _ Y» _ n Q T R" T — ' ' / X -X 0.9 TnR , ^-(^n^n)- Results of computational experiments are given for a linear system of equations approximating 3D elliptic boundary value problem. All algorithms are implemented using parallel array object tool ParSol, then a parallel algorithm follows semi-automatically from the serial one [1]. As it follows from the theoretical analysis the superlinear convergence of the TSGD method follows due to high nonlinear effect of the obtained iterative operator. In fact we deal with the bifurcation of the function describing the error or residual of the iteration sequence. A smooth trend of these functions are changed with abrupt jumps at some iterations. This feature is sensitive to small perturbations of iterative parameters. Thus we can expect that the numbers of iterations of the parallel versions of these algorithms will depend on the number of processors. This prediction is confirmed by computational experiments.