Matrix Approximation Problems and Nonsymmetric Iterative Methods
Kim Chuan Toh · 1996
The following contains mathematical formulae and symbols that may become distorted in ASCII text format. The GMRES algorithm, which solves systems of equations Ax = b, constructs the nth iterate as the solution to the vector approximation problem min (sub p) ||p(A)b|| =:||p(sub b)(A)b||, for polynomials p of degree n normalized at z=0. The ideal GMRES problem is obtained if one considers the matrix approximation problem min (sub p) ||p(A)|| =:||p*(sub n)(A)|| instead. The Arnoldi and ideal Arnoldi problems are the analogs of the GMRES and ideal GMRES problems, except that the minimizations are over monic polynomials of degree n. In the usual convergence analysis of Krylov subspace methods, the vector approximation problems actually solved by the iterations (exactly or approximately) are replaced by the conceptually simpler ideal problems, which are in turn analyzed in terms of scalar approximation problems on the complex plane. This thesis explores certain connections between the GMRES and Arnoldi iterations and various approximation problems.