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

Result code in 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>

Alternative codes found

RIV/00216208:11320/24:10490854

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

<a href="/en/project/GA23-06159S" target="_blank" >GA23-06159S: Vortical structures: advanced identification and efficient numerical simulation</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

Numerical Algorithms

ISSN

1017-1398

e-ISSN

1572-9265

Volume of the periodical

97

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

28

Pages from-to

1-28

UT code for WoS article

001394187000001

EID of the result in the Scopus database

2-s2.0-85175989927