OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On Iterative Solution of the Extended Normal Equations

Calandra, Henri and Gratton, Serge and Riccietti, Elisa and Vasseur, Xavier On Iterative Solution of the Extended Normal Equations. (2020) SIAM Journal on Matrix Analysis and Applications, 41 (4). 1571-1589. ISSN 0895-4798

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1137/19M1288644


Given a full-rank matrix $A \in \mathbb{R}^{m\times n}$ ($m\geq n$), we consider a special class of linear systems $A^T\! Ax=A^T\! b+c$ with $x, c \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$, which we refer to as the extended normal equations. The occurrence of $c$ gives rise to a problem with a different conditioning from the standard normal equations and prevents direct application of standard methods for least squares. Hence, we seek more insights on theoretical and practical aspects of the solution of such problems. We propose an explicit formula for the structured condition number, which allows us to compute a more accurate estimate of the forward error than the standard one used for generic linear systems, which does not take into account the structure of the perturbations. The relevance of our estimate is shown on a set of synthetic test problems. Then, we propose a new iterative solution method that, as in the case of normal equations, takes advantage of the structure of the system to avoid unstable computations such as forming $A^T\! A$ explicitly. Numerical experiments highlight the increased robustness and accuracy of the proposed method compared to standard iterative methods. It is also found that the new method can compare to standard direct methods in terms of solution accuracy.

Item Type:Article
HAL Id:hal-02973994
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Other partners > Total (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:21 Oct 2020 12:45

Repository Staff Only: item control page