Кіріспе
Сандық интеграция процесі
Сандық талдауда квази Монте-Карло әдісі – төмен сәйкессіздікті тізбектерді (квази кездейсоқ тізбектер немесе субкезеңсіз тізбектер деп те аталады) пайдаланып, дисперсияны азайту үшін сандық интеграция және кейбір басқа да мәселелерді шешу әдісі болып табылады. Бұл псевдокездейсоқ сандар тізбектеріне негізделген дәстүрлі Монте-Карло әдісі немесе Монте-Карло интеграциясына қарама-қарсы. Монте-Карло және квази-Монте-Карло әдістері ұқсас тұрғыда айтылады. Мәселе f функциясының интегралын x1, …, xN нүктелер жиынтығында есептелген функцияның орташа мәні ретінде жуықтау болып табылады:
Біз s өлшемді бірлік куб бойынша интегралдағандықтан, әр xi – s элементтен тұратын вектор болып табылады. Квази Монте-Карло мен Монте-Карло арасындағы айырмашылық – xi-тің таңдалу әдісінде. Квази Монте-Карло Халтон, Собол немесе Фауре тізбектері сияқты төмен сәйкессіздікті тізбектерді пайдаланады, ал Монте-Карло псевдокездейсоқ тізбектерді қолданады. Төмен сәйкессіздікті тізбектерді пайдаланудың артықшылығы – конвергенция жылдамдығының жоғары болуы. Квази Монте-Карло конвергенция деңгейі O(1/N)-ге жақын, ал Монте-Карло әдісі үшін бұл деңгей O(N−0.5) құрайды. Квази Монте-Карло әдісі соңғы кезде математикалық қаржы немесе есептеу қаржы саласында кең танымал болды. Монте-Карло және квази-Монте-Карло әдістері өлшем жоғары болғанда, 300-ге дейін немесе одан да жоғары дәл және салыстырмалы түрде жылдам жұмыс істейді. Morokoff және Caflisch
үшін кішірек болу үшін , кішірек және үлкен болуы керек (мысалы, ). Үлкен s мәні үшін, N мәніне байланысты, төмен сәйкессіздікті генератордан алынған нүктелер жинағының сәйкессіздігі кездейсоқ жинаққа қарағанда кіші болмауы мүмкін. Іс жүзінде кездесетін көптеген функциялар үшін (мысалы, Гаусс айнымалылары қолданылса). Біз қателік үшін тек жоғарғы шекті білеміз (яғни ε ≤ V(f) DN) және оны есептеу қиын. Осы қиындықтардың кейбірін жеңу үшін біз кездейсоқ квази Монте-Карло әдісін қолдана аламыз.
In order for to be smaller than , needs to be small and needs to be large (e. g. ). For large s, depending on the value of N, the discrepancy of a point set from a low discrepancy generator might be not smaller than for a random set. For many functions arising in practice, (e. g. if Gaussian variables are used). We only know an upper bound on the error (i. e., ε ≤ V(f) DN) and it is difficult to compute and In order to overcome some of these difficulties, we can use a randomized quasi Monte Carlo method.
Квази-Монте-Карлоның кездейсоқтығы
Төмен сәйкессіздікті тізбек кездейсоқ емес, детерминистік болғандықтан, квази Монте-Карло әдісін детерминистік алгоритм немесе дерандомизацияланған алгоритм ретінде қарастыруға болады. Бұл жағдайда қате үшін тек шектеу (мысалы, ε ≤ V(f) DN) бар, ал қатесін бағалау қиын. Вариансты талдау және бағалау қабілетімізді қалпына келтіру үшін әдісті кездейсоқтандыруға болады (жалпы идея үшін кездейсоқтандыруға қараңыз). Нәтижесінде алынған әдіс кездейсоқтандырылған квази Монте-Карло әдісі деп аталады және оны стандартты Монте-Карло әдісі үшін дисперсияны азайту тәсілі ретінде қарастыруға болады. Бірнеше әдістердің ішіндегі ең қарапайым түрлендіру процедурасы кездейсоқ ығысу арқылы жүзеге асырылады. {x1, ..., xN} – төмен сәйкессіздікті тізбектің нүктелік жиынтығы болсын. Біз s өлшемді кездейсоқ вектор U-ді таңдаймыз және оны {x1, ..., xN} жиынтығымен араластырамыз. Нақтырақ айтқанда, әр xj үшін келесіні құрастырамыз:
және орнына осы тізбекті пайдаланамыз. Егер Монте-Карло үшін R репликация болса, әр репликация үшін s өлшемді кездейсоқ вектор U-ді таңдаймыз. Кездейсоқтандыру квази-келтірілген тізбектерді пайдалана отырып, дисперсияның шамасын беруге мүмкіндік береді. Таза квази Монте-Карломен салыстырғанда, квази кездейсоқ тізбектің үлгілерінің саны эквивалентті есептеу шығындары үшін R-ге бөлінеді, бұл теориялық конвергенция жылдамдығын төмендетеді. Стандартты Монте-Карломен салыстырғанда, дисперсия және есептеу жылдамдығы Tuffin (2008) эксперименталды нәтижелерінде сәл жақсырақ.