|
NUMERICAL METHODS AND THE BASIS FOR THEIR APPLICATION
The error accumulation in the conjugate gradient method for degenerate problem
A. B. Ryabtsev National Research University “Moscow Institute of Physics and Technology”,
9 Institutskiy per., Dolgoprudny, Moscow Region, 141701, Russia
Abstract:
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.
Received: 06.04.2020 Revised: 06.02.2021 Accepted: 16.03.2021
Citation:
A. B. Ryabtsev, “The error accumulation in the conjugate gradient method for degenerate problem”, Computer Research and Modeling, 13:3 (2021), 459–472
Linking options:
https://www.mathnet.ru/eng/crm896 https://www.mathnet.ru/eng/crm/v13/i3/p459
|
Statistics & downloads: |
Abstract page: | 92 | Full-text PDF : | 32 | References: | 12 |
|