Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404361" target="_blank" >RIV/00216208:11320/19:10404361 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11075-018-0634-8" target="_blank" >10.1007/s11075-018-0634-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG

Popis výsledku v původním jazyce

In practical conjugate gradient (CG) computations, it is important to monitor the quality of the approximate solution to Ax = b so that the CG algorithm can be stopped when the required accuracy is reached. The relevant convergence characteristics, like the A-norm of the error or the normwise backward error, cannot be easily computed. However, they can be estimated. Such estimates often depend on approximations of the smallest or largest eigenvalue of A. In the paper, we introduce a new upper bound for the A-norm of the error, which is closely related to the Gauss-Radau upper bound, and discuss the problem of choosing the parameter mu which should represent a lower bound for the smallest eigenvalue of A. The new bound has several practical advantages, the most important one is that it can be used as an approximation to the A-norm of the error even if mu is not exactly a lower bound for the smallest eigenvalue of A. In this case, mu can be chosen, e.g., as the smallest Ritz value or its approximation. We also describe a very cheap algorithm, based on the incremental norm estimation technique, which allows to estimate the smallest and largest Ritz values during the CG computations. An improvement of the accuracy of these estimates of extreme Ritz values is possible, at the cost of storing the CG coefficients and solving a linear system with a tridiagonal matrix at each CG iteration. Finally, we discuss how to cheaply approximate the normwise backward error. The numerical experiments demonstrate the efficiency of the estimates of the extreme Ritz values, and show their practical use in error estimation in CG.

Název v anglickém jazyce

Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG

Popis výsledku anglicky

In practical conjugate gradient (CG) computations, it is important to monitor the quality of the approximate solution to Ax = b so that the CG algorithm can be stopped when the required accuracy is reached. The relevant convergence characteristics, like the A-norm of the error or the normwise backward error, cannot be easily computed. However, they can be estimated. Such estimates often depend on approximations of the smallest or largest eigenvalue of A. In the paper, we introduce a new upper bound for the A-norm of the error, which is closely related to the Gauss-Radau upper bound, and discuss the problem of choosing the parameter mu which should represent a lower bound for the smallest eigenvalue of A. The new bound has several practical advantages, the most important one is that it can be used as an approximation to the A-norm of the error even if mu is not exactly a lower bound for the smallest eigenvalue of A. In this case, mu can be chosen, e.g., as the smallest Ritz value or its approximation. We also describe a very cheap algorithm, based on the incremental norm estimation technique, which allows to estimate the smallest and largest Ritz values during the CG computations. An improvement of the accuracy of these estimates of extreme Ritz values is possible, at the cost of storing the CG coefficients and solving a linear system with a tridiagonal matrix at each CG iteration. Finally, we discuss how to cheaply approximate the normwise backward error. The numerical experiments demonstrate the efficiency of the estimates of the extreme Ritz values, and show their practical use in error estimation in CG.

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/GC17-04150J" target="_blank" >GC17-04150J: Robustní dvojúrovňové simulace založené na Fourierově metodě a metodě konečných prvků: Odhady chyb, redukované modely a stochastika</a><br>

Návaznosti

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

Rok uplatnění

2019

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

—

Svazek periodika

82

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

32

Strana od-do

937-968

Kód UT WoS článku

000500985000009

EID výsledku v databázi Scopus

2-s2.0-85057083507