Groupe d’études et de recherche en analyse des décisions

G-2017-05

LSLQ: An iterative method for linear least-squares with an error minimization property

, et

Nous proposons une méthode itérative pour les problèmes aux moindres carrés linéaires \(A x \approx b\) nommée LSLQ. La méthode repose sur le processus de Golub et Kahan (1965), dont le coût est dominé par les produits avec \(A\) et sa transposée. Dans le cas où le rang colonne de $A$ n'est pas maximal, LSLQ identifie la solution de norme minimale. En arithmétique exacte, LSLQ est équivalente à SYMMLQ appliquée aux équations normales, de sorte que la norme Euclidienne de l'itéré courant est croissante et la norme de l'erreur associée est décroissante. Nous fournissons des bornes inférieure et supérieure sur l'erreur en norme Euclidienne au long des itérations de LSLQ. La borne supérieure induit une borne supérieure sur l'erreur au long des itérations de LSQR, laquelle n'était pas disponible auparavant, et fournit ainsi un critère d'arrêt basé sur la réduction de l'erreur lors de la transition vers le point de LSQR. Nos illustrations numériques couvrent des problèmes test standard ainsi qu'un problème inverse provenant d'une application de géophysique dans laquelle une solution approchée au problème aux moindres carrés correspond à un gradient inexact d'une fonction de pénalité à minimiser.

, 24 pages