Estimating error norms in CG-like algorithms for least-squares and least-norm problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F24%3A00587710" target="_blank" >RIV/67985840:_____/24:00587710 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/24:10490854

Výsledek na webu

<a href="https://doi.org/10.1007/s11075-023-01691-x" target="_blank" >https://doi.org/10.1007/s11075-023-01691-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11075-023-01691-x" target="_blank" >10.1007/s11075-023-01691-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Estimating error norms in CG-like algorithms for least-squares and least-norm problems

Popis výsledku v původním jazyce

In Meurant et al. (Numer. Algorithms 88(3), 1337–1359, 2021), we presented an adaptive estimate for the energy norm of the error in the conjugate gradient (CG) method. Here we consider algorithms for solving linear approximation problems with a general, possibly rectangular matrix that are based on applying CG to a system with a positive (semi-)definite matrix built from the original matrix. We discuss algorithms based on Hestenes–Stiefel-like implementation (often called CGLS and CGNE in the literature) as well as on bidiagonalization (LSQR and CRAIG), and both unpreconditioned and preconditioned variants. Each algorithm minimizes a certain quantity at each iteration (within the current Krylov subspace), that is related to some error norm. We call this “the quantity of interest”. We show that the adaptive estimate used in CG can be extended for these algorithms to estimate the quantity of interest. Throughout, we emphasize the applicability of the estimate during computations in finite-precision arithmetic. We carefully derive the relations from which the estimate is constructed, without exploiting the global orthogonality that is not preserved during computation. We show that the resulting estimate preserves its key properties: it can be cheaply evaluated, and it is numerically reliable in finite-precision arithmetic under some mild assumptions. These properties make the estimate suitable for use in stopping the iterations. The numerical experiments confirm the robustness and satisfactory behaviour of the estimate.

Název v anglickém jazyce

Estimating error norms in CG-like algorithms for least-squares and least-norm problems

Popis výsledku anglicky

In Meurant et al. (Numer. Algorithms 88(3), 1337–1359, 2021), we presented an adaptive estimate for the energy norm of the error in the conjugate gradient (CG) method. Here we consider algorithms for solving linear approximation problems with a general, possibly rectangular matrix that are based on applying CG to a system with a positive (semi-)definite matrix built from the original matrix. We discuss algorithms based on Hestenes–Stiefel-like implementation (often called CGLS and CGNE in the literature) as well as on bidiagonalization (LSQR and CRAIG), and both unpreconditioned and preconditioned variants. Each algorithm minimizes a certain quantity at each iteration (within the current Krylov subspace), that is related to some error norm. We call this “the quantity of interest”. We show that the adaptive estimate used in CG can be extended for these algorithms to estimate the quantity of interest. Throughout, we emphasize the applicability of the estimate during computations in finite-precision arithmetic. We carefully derive the relations from which the estimate is constructed, without exploiting the global orthogonality that is not preserved during computation. We show that the resulting estimate preserves its key properties: it can be cheaply evaluated, and it is numerically reliable in finite-precision arithmetic under some mild assumptions. These properties make the estimate suitable for use in stopping the iterations. The numerical experiments confirm the robustness and satisfactory behaviour of the estimate.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/GA23-06159S" target="_blank" >GA23-06159S: Vírové struktury: pokročilé metody identifikace a efektivní numerické simulace</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Numerical Algorithms

ISSN

1017-1398

e-ISSN

1572-9265

Svazek periodika

97

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

28

Strana od-do

1-28

Kód UT WoS článku

001394187000001

EID výsledku v databázi Scopus

2-s2.0-85175989927