# Accounting for Round-Off Errors When Using Gradient Minimization Methods
## 2 Problem Statement
\[\sigma_{r_{n}}^{2}=\sum_{k=1}^{M}\sigma_{A_{lk}r_{l}-b_{k}}^{2}=\sum_{k=1}^{M}A_{ lk}^{2}\left(\sum_{l=1}^{N}\Bigl{(}A_{kl}x_{l}^{(s)}\Bigr{)}^{2}+b_{k}^{2}\right).\]  
Next, we will consider the calculation of the error for the components of the vector \(r^{(s)}\) in iterations \(s\geqslant 2\). In these iterations, we rewrite the recurrent formula for calculating the residual \(r^{(s)}\) in the following form:  
\[r_{n}^{(s)}=r_{n}^{(s-1)}-\frac{q_{n}^{(s-1)}}{\sum\limits_{l=1}^{N}p_{l}^{(s- 1)}q_{l}^{(s-1)}}.\]  
The error variance can be calculated using partial derivatives with respect to the independent components. However, taking into account all possible values in previous iterations will lead to an overestimation of the error. To avoid this, we take into account the peculiarity of gradient methods, which consists of the fact that gradient methods are resistant to some parts of rounding errors because in each iteration, some of the errors are compensated. This is due to the fact that each iteration of the gradient method can be interpreted as a way to find the next better approximation of the desired solution based on a previous iteration. **The first way to calculate \(\sigma^{2}_{r_{n}^{(s)}}\)**. We will assume that when calculating the vector \(p^{(s)}\), it does not make sense to take into account all previous errors (because \(p^{(s)}\) is the direction of minimization). Thus, only rounding errors which arise when using the value of \(p^{(s)}\) in further calculations remain. Taking this into account, we get the following equations:  
\[\sigma^{2}_{r_{n}^{(s)}} =\sigma^{2}_{r_{n}^{(s-1)}}+\sum\limits_{n^{\prime}=1}^{N}\left( \frac{\partial r_{n}^{(s)}}{\partial q_{n^{\prime}}^{(s-1)}}\right)^{2}\sigma ^{2}_{q_{n^{\prime}}^{(s-1)}}\] \[=\sigma^{2}_{r_{n}^{(s-1)}}+\left(\frac{1}{\sum\limits_{l=1}^{N}p _{l}^{(s-1)}q_{l}^{(s-1)}}-\frac{p_{n}^{(s-1)}q_{n}^{(s-1)}}{\left(\sum\limits _{l=1}^{N}p_{l}^{(s-1)}q_{l}^{(s-1)}\right)^{2}}\right)^{2}\sigma^{2}_{q_{n}^ {(s-1)}}\] \[+\sum\limits_{n^{\prime}\
eq n}\left(\frac{p_{n^{\prime}}^{(s-1) }q_{n^{\prime}}^{(s-1)}}{\left(\sum\limits_{l=1}^{N}p_{l}^{(s-1)}q_{l}^{(s-1 )}\right)^{2}}\right)^{2}\sigma^{2}_{q_{n^{\prime}}^{(s-1)}}.\]  
Here, the expressions for the error variances of the calculation of the vector \(q^{(s-1)}\) components are calculated using already known formulas, such as:  
\[\sigma^{2}_{q_{n}^{(s-1)}}=\sum\limits_{k=1}^{M}A_{2t}^{2}\sum\limits_{l=1}^ {N}\big{(}A_{kl}p_{l}^{(s-1)}\big{)}^{2}.\]  
**The second way to calculate \(\sigma^{2}_{r_{n}^{(s)}}\)**. To significantly simplify (in terms of the number of operations) the calculation of error variances in each iteration of the gradient method, we can assume that it is not necessary to take into account all previous errors, not only when calculating the vector \(p^{(s)}\), but also when calculating the vector \(q^{(s)}\). Taking this into account, we get the following equation:  
\[\sigma^{2}_{r_{n}^{(s)}}=\sigma^{2}_{r_{n}^{(s-1)}}+\left(\frac{q_{n}^{(s-1) }}{\sum\limits_{k=1}^{N}p_{k}^{(s-1)}q_{k}^{(s-1)}}\right)^{2}.\]  
After calculating \(\sigma^{2}_{r_{n}^{(s)}}\) with any of the methods, the error variance of the residual norm \(\sigma^{2}_{s}\) is calculated as the sum of the variances of the components since they are independent of each other, which is expressed as follows:  
\[\sigma^{2}_{s}=\sum\limits_{n=1}^{N}\sigma^{2}_{r_{n}^{(s)}}.\]  
When the condition  
\[\frac{\sigma^{2}_{s}\Delta^{2}}{\|r^{(s)}\|^{2}}\geqslant 1\]  
is met, the iterative process is interrupted, and the vector \(x^{\text{res}}=x^{(s)}\) is chosen as a solution of the system (1). This is the improved criterion for stopping the iterative process.