Stochastic matrices and $L_{p}$ norms: new algorithms for solving ill-conditioned linear systems of equations

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 l1 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 lp 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.
Type de document :
Chapitre d'ouvrage
ESAIM: Proceedings and Surveys, 18, EDP Sciences, pp.70 - 86, 2007, 2267-3059. 〈10.1051/proc:071807〉
Liste complète des métadonnées

https://hal-supelec.archives-ouvertes.fr/hal-01107461
Contributeur : Marc Lambert <>
Soumis le : mardi 20 janvier 2015 - 17:19:53
Dernière modification le : vendredi 19 janvier 2018 - 13:44:04

Identifiants

Collections

Citation

Riadh Zorgati, Wim Stefanus Van Ackooij, Marc Lambert. Stochastic matrices and $L_{p}$ norms: new algorithms for solving ill-conditioned linear systems of equations. ESAIM: Proceedings and Surveys, 18, EDP Sciences, pp.70 - 86, 2007, 2267-3059. 〈10.1051/proc:071807〉. 〈hal-01107461〉

Partager

Métriques

Consultations de la notice

120