Optimization of the quasi-Monte Carlo algorithm for solving systems of linear algebraic equations (Q946046)

The Quasi-Monte Carlo algorithm is an effective method of solving linear algebraic systems of equations. In the present paper problems of optimization of a method of solving system of linear algebraic equations, suggested by Ermakov and the author [Monte Carlo Methods Appl. 12, No. 5--6, 363--384 (2006; Zbl 1121.65003)], are considered. The essence of the proposed optimization is the decrease of the constructive dimension of the integrals, which makes it easier to apply the Quasi-Monte Carlo (QMC) method. In Introduction the concept of QMC method of solving systems of the form \(X = A X + F\) is reminded. The solution is given in the form of a Markov chain. The recurrence relation for the error of this method is given. In Section 2 the problem of choosing optimal parameters of the Markov chain in the modified Monte Carlo (MC) method is solved. The calculated scheme of the modified MC method is given step-by-step. The components of all estimates are non-calculated one by one. At each step the optimal matrix \(P\) of transition probabilities is chosen. Theorem 1 confirms that the constructed estimate is nonbiased. Theorem 2 states that the constructed estimate is optimal in a sense that the estimate components have minimum variance. Corollary 1 gives the condition in which all estimate components have variance equals to zero.