# Accounting for Round-Off Errors When Using Gradient Minimization Methods
## 2 Problem Statement  
Consider one of the possible implementations of the conjugate gradient method for solving an overdetermined system of linear algebraic equations with a dense matrix:  
\[A\,x=b. \tag{1}\]  
Here, \(A\) is a rectangular matrix of dimension \(M\times N\) (\(M>N\)), and \(b\) is a column vector with \(M\) components. It is necessary to find \(x\), which is a column vector with \(N\) components. When solving real applied problems, the components of the vector \(b\) are usually measured experimentally. Therefore, due to the presence of experimental errors, this system may not have a classical solution. However, with a sufficient number of input data (\(M>N\) and the data do not duplicate each other), it is possible to find a pseudo-solution to this problem using the least squares method:\[x=\operatorname*{argmin}_{x\in\mathbb{R}^{N}}\|Ax-b\|^{2}.\]  
Here, and below \(\|\cdot\|\), is the Euclidean norm. **Remark 1**. : _It is well-known that many real applied problems are ill-posed [23]. When solving them, it is necessary to construct regularizing algorithms. Most often, these algorithms are based on the minimization of some modified functionals. An example of such a functional is the functional of [PERSON] [23]: \(f[x]=\|Ax-b\|^{2}+\alpha\|Rx\|^{2}\) (here, \(\alpha\) is the regularization parameter, and the matrix \(R\) defines a priori constraints). In this paper, to simplify the presentation, we will assume that the problem under consideration is well-posed. However, the formulas obtained below can be easily generalized to the mentioned case._  
There are many ways to find the vector \(x\). We have chosen the one that is the most indicative within the framework of this work. Hence, the vector \(x\) with \(N\) components, which is a solution (pseudo-solution) of system (1), can be found using the following iterative algorithm, which constructs the sequence \(x^{(s)}\). This sequence converges in \(N\) steps to the desired solution (pseudo-solution) of system (1), based on the assumption that all calculations are performed exactly. We set \(p^{(0)}=0,s=1\), and an arbitrary initial approximation \(x^{(1)}\). Then, we repeatedly perform the following sequence of actions:  
\[r^{(s)}= \begin{cases}A^{T}\big{(}A\,x^{(s)}\,-\,b\big{)},&\text{if}\quad s=1,\\ r^{(s-1)}\,-\,\frac{q^{(s-1)}}{\big{(}p^{(s-1)},q^{(s-1)}\big{)}},&\text{if} \quad s\geqslant 2,\\ p^{(s)}=p^{(s-1)}\,+\,\frac{r^{(s)}}{\big{(}r^{(s)},r^{(s)}\big{)}},\\ q^{(s)}=A^{T}\big{(}A\,p^{(s)}\big{)},\\ x^{(s+1)}=x^{(s)}\,-\,\frac{p^{(s)}}{\big{(}p^{(s)},q^{(s)}\big{)}},\\ s=s+1.\end{cases} \]  
We emphasize that in this case, the classical criterion for stopping the iterative process is formulated as follows: calculations are carried out while \(s\leqslant N\). As a result, after \(N\) steps, the vector \(x^{\text{res}}=x^{(N+1)}\) will be regarded as a solution (pseudo-solution) of system (1). **Remark 2**. : _If we do not use the recurrent notation and calculate the residual \(r^{(s)}\) in each iteration in the same way as in the first iteration, then the number of arithmetic operations required to complete the iterative process will double. This is the motivation for using the recurrent form of the conjugate gradient method when solving \"large\" problems._  
Formally, this algorithm with the classical stopping criterion of the iterative process is formulated as follows:  
1. Set \(p^{(0)}:=0\), \(s:=1\), and an arbitrary initial approximation \(x^{(1)}\). 2. Compute \(r^{(s)}:=A^{T}\big{(}A\,x^{(s)}\,-\,b\big{)}\) and go to step 4. 3. Compute \(r^{(s)}:=r^{(s-1)}\,-\,\frac{q^{(s-1)}}{\big{(}p^{(s-1)},q^{(s-1)}\big{)}}\). 4. Compute \(p^{(s)}:=p^{(s-1)}\,+\,\frac{r^{(s)}}{\big{(}r^{(s)},r^{(s)}\big{)}}\). 5. Compute \(q^{(s)}:=A^{T}\big{(}A\,p^{(s)}\big{)}\).