蒙特卡罗方法与拟蒙特卡罗方法解线性方程组

The Monte Carlo Methods and Quasi Monte Carlo Methods for Systems of Linear Algebraic Equations

分别介绍蒙特卡罗方法和拟蒙特卡罗方法解线性方程组的基本原理,并对两种方法的误差和收敛速度进行讨论.提出误差由3方面造成:截断误差、方法本身、伪随机数序列和低差异序列分布不均匀.在收敛速度方面:蒙特卡罗法的收敛速度与问题的规模和模拟路径长度无关;拟蒙特卡罗方法的收敛与问题的规模无关,但与模拟路径长度有关.经过对两种方法适用的情况进行讨论及数据测试,认为在一般情况下应选择用拟蒙特卡罗方法解线性方程组.

The Monte Carlo methods,Quasi-Monte Carlo methods for solving Systems of Linear Algebraic Equations（SLAE）,and the error,the convergence rate of each method were analyzed.The error was caused by three aspects：the truncation error,the methods per se,the pseudo-random number and low-discrepancy sequences not uniform.In respect of convergence rate,Monte Carlo methods did not depend on the scale of problems and the number of walks.Quasi-Monte Carlo methods did not depend on the scale of problems either,but depended on the number of walks.In addition,the conditions of using the Monte Carlo methods,Quasi-Monte Carlo methods and the numerical experiments discussed,Quasi-Monte Carlo methods were chosen to solve Linear Algebraic Equations（LAE） in general condition.