On a method of finding approximate solutions of ill-conditioned algebraic systems and parallel computation

Abstract

A new method of finding approximate solutions of linear algebraic systems with ill-conditioned or singular matrices is presented. This method can be effectively used for arranging parallel computations for matrices of large size. Let A be a quadratic matrix of order n ≥ 1 and f be an n-dimensional vector. If n is large, then in order to speed up the process of solving the equation Ax = f several computers are usually used. In this case the problem of parallel computation arises. In the well-known books [1]-[4] the problem of parallel computation is solved for band and for sparse matrices A. We suggest a method which allows to do this for an arbitrary matrix A. In particular, we cover the cases of matrices with small determinants or even non-invertible matrices. Instead of solving the equation Ax = f we consider the problem of finding a vector &hat;x such that
inf_x ||Ax - f|| = ||A&hat;x - f||
Here the infimum is taken with respect to all n-dimensional vectors x. If the matrix A is invertible, then clearly &hat;x is the unique solution of the equation Ax = f. If the problem has more than one solution, then we choose as &hat;x the one of them which has the minimal norm.