Adaptive Monte Carlo methods for matrix equations with applications

摘要

This paper discusses empirical studies with both the adaptive correlated sequential sampling method and the adaptive importance sampling method which can be used in solving matrix and integral equations. Both methods achieve geometric convergence (provided the number of random walks per stage is large enough) in the sense: eν≤cλν, where eν is the error at stage ν, λ∈(0,1) is a constant, c>0 is also a constant. Thus, both methods converge much faster than the conventional Monte Carlo method. Our extensive numerical test results show that the adaptive importance sampling method converges faster than the adaptive correlated sequential sampling method, even with many fewer random walks per stage for the same problem. The methods can be applied to problems involving large scale matrix equations with non-sparse coefficient matrices. We also provide an application of the adaptive importance sampling method to the numerical solution of integral equations, where the integral equations are converted into matrix equations (with order up to 8192×8192) after discretization. By using Niederreiter’s sequence, instead of a pseudo-random sequence when generating the nodal point set used in discretizing the phase space Γ, we find that the average absolute errors or relative errors at nodal points can be reduced by a factor of more than one hundred.