Backward pertubation analysis of least squares problems

This thesis is concerned with backward perturbation analyses of the linear least squares (LS) and related problems. Two theoretical measures are commonly used for assessing the backward errors that arise in the approximate solution of such problems. These are called the normwise relative backward error (NRBE) and the minimal backward error (MBE). An important new relationship between these two measures is presented, which shows that the two are essentially equivalent. New upper bounds on the NRBE and MBE for the LS problem are given and related to known bounds and estimates. One important use of backward perturbation analysis is to design stopping criteria for iterative methods. In this thesis, minimum-residual iterative methods for solving LS problems are studied. Unexpected convergence behaviour in these methods is explained and applied to show that commonly used stopping criteria can in some situations be much too conservative. More reliable stopping criteria are then proposed, along with an efficient implementation in the iterative algorithm LSQR. In many applications the data in the LS problem come from a statistical linear model in which the noise follows a multivariate normal distribution whose mean is zero and whose covariance matrix is the scaled identity matrix. A description is given of typical convergence of the error that arises in minimum-residual iterative methods when the data come from such a linear model. Stopping criteria that use the information from the linear model are then proposed and compared to others that appear in the literature. Finally, some of these ideas are extended to the scaled total least squares problem.Nous effectuons une analyse de l'erreur rétrograde des problèmes de moindres carrés. Nous analysons deux méthodes habituellement utilisées pour mesurer l'erreur rétrograde et démontrons que celles-ci sont en fait équivalentes. Nous présentons de nouvelles estimations de l'erreur rétrograde des problèmes de moindres carrés, et nous les comparons aux estimations connues. L'un des usages de ce type d'analyse consiste à établir des critères d'arrêt pour les méthodes itératives. Nous expliquons des phénomènes de convergence inattendus que nous avons observés dans les méthodes itératives de type résidu minimal. Nous démontrons ensuite que les critères d'arrêt habituellement utilisés avec ces méthodes peuvent être trop prudents dans certaines circonstances. Nous proposons donc de nouveaux critères d'arrêt plus fiables, et présentons une implémentation efficace de ceux-ci dans l'algorithme LSQR. La méthode des moindres carrés est souvent utilisée en statistique lorsque les données proviennent d'un modèle linéaire et que le bruit est distribué selon une loi normale dont l'espérance est zéro et la variance est la matrice identité proportionnée. Nous décrivons la convergence de l'erreur qui résulte de ce type de données et proposons des critères d'arrêt adaptés à cette situation. Enfin, nous appliquons une partie de cette analyse aux problèmes de moindres carrés proportionnés