The behavior of the Gauss-Radau upper bound of the error norm in CG

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10472974" target="_blank" >RIV/00216208:11320/23:10472974 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_hhocVg9B1" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_hhocVg9B1</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

The behavior of the Gauss-Radau upper bound of the error norm in CG

Popis výsledku v původním jazyce

Consider the problem of solving systems of linear algebraic equations Ax = b with a real symmetric positive definite matrix A using the conjugate gradient (CG) method. To stop the algorithm at the appropriate moment, it is important to monitor the quality of the approximate solution. One of the most relevant quantities for measuring the quality of the approximate solution is the A-norm of the error. This quantity cannot be easily computed; however, it can be estimated. In this paper we discuss and analyze the behavior of theGauss-Radau upper bound on the A-norm of the error, based on viewing CG as a procedure for approximating a certain Riemann-Stieltjes integral. This upper bound depends on a prescribed underestimate mu to the smallest eigenvalue of A. We concentrate on explaining a phenomenon observed during computations showing that, in later CG iterations, the upper bound loses its accuracy, and is almost independent of mu. We construct amodel problem that is used to demonstrate and study the behavior of the upper bound in dependence of mu, and developed formulas that are helpful in understanding this behavior. We show that the above-mentioned phenomenon is closely related to the convergence of the smallest Ritz value to the smallest eigenvalue of A. It occurs when the smallest Ritz value is a better approximation to the smallest eigenvalue than the prescribed underestimate mu. We also suggest an adaptive strategy for improving the accuracy of the upper bounds in the previous iterations.

Název v anglickém jazyce

The behavior of the Gauss-Radau upper bound of the error norm in CG

Popis výsledku anglicky

Consider the problem of solving systems of linear algebraic equations Ax = b with a real symmetric positive definite matrix A using the conjugate gradient (CG) method. To stop the algorithm at the appropriate moment, it is important to monitor the quality of the approximate solution. One of the most relevant quantities for measuring the quality of the approximate solution is the A-norm of the error. This quantity cannot be easily computed; however, it can be estimated. In this paper we discuss and analyze the behavior of theGauss-Radau upper bound on the A-norm of the error, based on viewing CG as a procedure for approximating a certain Riemann-Stieltjes integral. This upper bound depends on a prescribed underestimate mu to the smallest eigenvalue of A. We concentrate on explaining a phenomenon observed during computations showing that, in later CG iterations, the upper bound loses its accuracy, and is almost independent of mu. We construct amodel problem that is used to demonstrate and study the behavior of the upper bound in dependence of mu, and developed formulas that are helpful in understanding this behavior. We show that the above-mentioned phenomenon is closely related to the convergence of the smallest Ritz value to the smallest eigenvalue of A. It occurs when the smallest Ritz value is a better approximation to the smallest eigenvalue than the prescribed underestimate mu. We also suggest an adaptive strategy for improving the accuracy of the upper bounds in the previous iterations.

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/GA20-01074S" target="_blank" >GA20-01074S: Adaptivní metody pro numerické řešení parciálních diferenciálních rovnic: analýza, odhady chyb a iterativní řešiče</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

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

94

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

30

Strana od-do

847-876

Kód UT WoS článku

000973631900002

EID výsledku v databázi Scopus

2-s2.0-85153079846