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

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

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

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/GC17-04150J" target="_blank" >GC17-04150J: Reliable two-scale Fourier/finite element-based simulations: Error-control, model reduction, and stochastics</a><br>

Continuities

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

Publication year

2019

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

—

Volume of the periodical

82

Issue of the periodical within the volume

3

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

32

Pages from-to

937-968

UT code for WoS article

000500985000009

EID of the result in the Scopus database

2-s2.0-85057083507