Stochastic Matrices and L_p Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations

¹ Supelec, Plateau de Moulon, 3 rue Joliot-Curie, F-91192 Gif-sur-Yvette Cedex FRANCE
² EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE
³ EDF R&D. 1, avenue du Général de Gaulle, F-92141 Clamart Cedex FRANCE

Corresponding authors: riadh.zorgati@lss.supelec.fr riadh.zorgati@edf.fr wim.van-ackooij@edf.fr marc.lambert@lss.supelec.fr

Abstract

We propose new iterative algorithms for solving a system of linear equations, possibly singular and inconsistent, presenting outstanding performances regarding ill-conditioning and error propagation. The basis of our approach is constructing with the l₁ norm, a preconditioning matrix C (an approximation of a generalized inverse of the matrix) such that the preconditioned matrix CA is stochastic. This property allows us to retrieve, in an original way, the Schultz-Hotelling-Bodewig's algorithm of iterative refinement of the approximate inverse of a matrix. The approach, valid for non-negative matrices, is then generalized to any complex, rectangular matrix. We are then able to compute a generalized inverse of any matrix and this inverse is fit for use in classical solving schemes such as : Richardson-Tanabe, Schultz-Hotelling-Bodewig, preconditioned conjugate gradients and also in the Kaczmarz scheme (that we have generalized using l_p norms). Regarding the obtained results on pathological well-known test-cases such as Hilbert and Nakasaka matrices, some of the proposed algorithms are empirically shown to be more efficient than the known classical techniques.