We consider the problem of optimizing the parameter of a two-stage algorithm for approximate solution of a system of linear algebraic equations with a sparse \(n\times n\) -matrix, i.e., with one in which the number of nonzero elements is \(m\!=\!O(n)\) . The two-stage algorithm uses conjugate gradient method at its stages. At the 1st stage, an approximate solution with accuracy \(\varepsilon _1\) is found for zero initial vector. All numerical values used at this stage are represented as single precision numbers. The obtained solution is used as initial approximation for an approximate solution with a given accuracy \(\varepsilon _2\) that we obtain at the 2nd stage, where double precision numbers are used. Based on the values of some matrix parameters, computed in a time not exceeding O(m), we need to determine the value \(\varepsilon _1\) which minimizes the total computation time at two stages. Using single precision numbers for computations at the 1st stage is advantageous, since the execution time of one iteration will be approximately half that of one iteration at the 2nd stage. But using machine numbers with half the mantissa length accelerates the growth of the rounding errors per iteration at the 1st stage, which entails an increase in the number of iterations performed at 2nd stage. To determine \(\varepsilon _1\) for the input matrix, we use n, m, an estimation of the diameter of the graph associated with the matrix, an estimation of the spread of the matrix’ eigenvalues, and estimation of its maximum eigenvalue. The optimal or close to the optimal value of \(\varepsilon _1\) can be determined for matrix with such a vector of parameters using the nearest neighbor regression.