The error accumulation in the conjugate gradient method for degenerate problem

Ryabtsev A.B.
 pdf (555K)

In this paper, we consider the conjugate gradient method for solving the problem of minimizing a quadratic function with additive noise in the gradient. Three concepts of noise were considered: antagonistic noise in the linear term, stochastic noise in the linear term and noise in the quadratic term, as well as combinations of the first and second with the last. It was experimentally obtained that error accumulation is absent for any of the considered concepts, which differs from the folklore opinion that, as in accelerated methods, error accumulation must take place. The paper gives motivation for why the error may not accumulate. The dependence of the solution error both on the magnitude (scale) of the noise and on the size of the solution using the conjugate gradient method was also experimentally investigated. Hypotheses about the dependence of the error in the solution on the noise scale and the size (2-norm) of the solution are proposed and tested for all the concepts considered. It turned out that the error in the solution (by function) linearly depends on the noise scale. The work contains graphs illustrating each individual study, as well as a detailed description of numerical experiments, which includes an account of the methods of noise of both the vector and the matrix.

Keywords: conjugate gradient method, degenerate problem, noisy oracle
Citation in English: Ryabtsev A.B. The error accumulation in the conjugate gradient method for degenerate problem // Computer Research and Modeling, 2021, vol. 13, no. 3, pp. 459-472
Citation in English: Ryabtsev A.B. The error accumulation in the conjugate gradient method for degenerate problem // Computer Research and Modeling, 2021, vol. 13, no. 3, pp. 459-472
DOI: 10.20537/2076-7633-2021-13-3-459-472
URL: http://crm-en.ics.org.ru/journal/article/3066/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science