준몬테카를로법

수치해석에서는 준몬테 카를로 방법은 낮은 점수의 순서(준랜덤 순서 또는 서브랜덤 순서라고도 함)를 이용하여 수치적 통합과 그 밖의 몇 가지 문제를 해결하는 방법이다. 이는 가성수 순서에 기초한 일반 몬테카를로 방식이나 몬테카를로 통합과는 대조적이다.

몬테카를로(Monte Carlo)와 준몬테 카를로(si-Monte Carlo) 방법은 비슷한 방식으로 명시되어 있다. 문제는 함수 f의 적분을 x₁, ..., x_N: 점 집합에서 평가한 함수의 평균으로 근사하는 것이다.

${\displaystyle \int _{[0,1]^{s}f(u)\,{\rm {d}u\ 약 {\frac {1}{N}\,\sum _{i=1}^{{N}f(x_{i})}$

s-차원 단위 큐브를 통해 통합하고 있기 때문에, 각각의 x는_i s 원소의 벡터다. 준몬테 카를로와 몬테 카를로의 차이는 x가_i 선택되는 방식이다. 준몬테 카를로는 할튼 수열, 소볼 수열, 파우레 수열 등 낮은 점수의 수열을 사용하는 반면 몬테 카를로는 가성수열을 사용한다. 낮은 점수의 시퀀스를 사용할 때의 이점은 수렴 속도가 더 빠르다는 것이다. 준몬테 카를로에는 O(1/N)에 가까운 수렴율이 있는 반면 몬테카를로 방법은 O(N^−0.5)에 가깝다.^[1]

준몽테 카를로 방식은 최근 수학금융이나 계산금융 분야에서 인기를 끌었다.^[1] 이러한 영역에서는 임계치 ε 내에서 적분을 평가해야 하는 고차원적 수치적 통합이 빈번하게 발생한다. 따라서 이러한 상황에서는 몬테카를로 방식과 준몬테카를로 방식이 유리하다.

준몬테 카를로의 근사 오차 한계

준몽테 카를로 방법의 근사 오차는 집합 x₁, ..., x의_N 불일치에 비례하는 용어로 한정된다. 구체적으로는 코크스마–Hlawka 불평등에는 오류라고 명시되어 있다.

${\displaystyle \varepsilon =\왼쪽 \int _{[0,1]^{s}f(u)\,{\rm {d}u-{\d}u-{1}{1}{N}\,\sum _{i=1}^{N_{i}f(으)\오른쪽 }}$

에 의해 제한되다

${\displaystyle \varepsilon \leq V(f)D_{N}}$

여기서 V(f)는 함수 f의 Hardy-Krause 변동이다(1995) 자세한 정의는 Morokoff와 Caflisch(1995) 참조. D는_N 집합(x₁,...,x_N)의 이른바 별 불일치로서 다음과 같이 정의된다.

${\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\왼쪽 {\frac {{\text}{{{{N}-\operatorname {volume}(Q)\오른쪽,}$

여기서 Q는 좌표 축에 평행한 면이 있는 [0,1]^s의 직사각형 고형이다.^[2] The inequality ${\displaystyle \varepsilon \leq V(f)D_{N}}$ can be used to show that the error of the approximation by the quasi-Monte Carlo method is ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$, whereas the Monte Carlo method has a probabilistic error of $$${\displaystyle O}$( ${\displaystyle \frac{\sqrt{1}}{}}$ N${\displaystyle \frac{}{}}$) ${\$. 근사오차의 상한만 명시할 수 있지만, 실제로는 준몬테카를로 방식의 수렴 속도는 이론적 한계보다 훨씬 빠르다.^[1] 따라서 일반적으로 준몬테카를로 방법의 정확도는 몬테카를로 방법의 정확도보다 더 빠르게 증가한다. 그러나 이러한 장점은 N이 충분히 크고 변동이 유한한 경우에만 보장된다.

다차원적 통합을 위한 몬테카를로 및 준몬테카를로

1차원 통합의 경우 사다리꼴 규칙, 심슨의 규칙, 또는 뉴턴-코테스 공식과 같은 사다리꼴 방법이 기능이 원활할 경우 효율적인 것으로 알려져 있다. 이러한 접근방식은 다차원 통합에 대해 1차원 통합을 반복함으로써 다차원 통합에도 사용할 수 있다. 그러나 기능 평가의 수는 치수 수인 s가 증가함에 따라 기하급수적으로 증가한다. 따라서 다차원적 통합에는 이러한 차원성의 저주를 극복할 수 있는 방법을 사용해야 한다. 표준 몬테카를로 방식은 사분법 구현이 어렵거나 비용이 많이 들 때 자주 사용된다.^[2] 몬테카를로, 준몬테카를로 방식은 치수가 높을 때 정확하고 속도가 최대 300 이상일 때 비교적 빠르다.^[3]

모로코프와 카플리쉬는 통합을 위한 몬테카를로(Monte Carlo)의 성능과 준몬테 카를로(si-Monte Carlo)의 방법을 연구했다. 논문에서는 준몬트 카를로용 할튼, 소볼, 파우레 시퀀스를 유사 몬테 카를로 표준법(Monte Carlo)과 비교하였다. 그들은 Halton 시퀀스가 최대 6개까지 치수에 대해 가장 잘 수행되고, Sobol 시퀀스는 더 높은 차원에 대해 가장 잘 수행되며, Faure 시퀀스는 다른 두 시퀀스보다 더 뛰어나지만, 여전히 유사 시퀀스보다 더 잘 수행된다는 것을 발견했다.

그러나 모로코프와 카플리쉬는 준몽테 카를로의 장점이 이론적으로 기대 이하인 사례를 들었다. 그래도 모로코프와 카플리쉬가 연구한 사례에서 준몬테 카를로 방법은 같은 수의 점수를 가진 몬테카를로 방법보다 더 정확한 결과를 산출했다. 모로코프와 카플리쉬는 준몬테카를로 방식의 장점은 통합이 원활하면 더 크고 적분자의 치수 s는 적다고 말한다.

준몬테카를로의 단점

Lemieux는 준몽테 카를로의 단점을 언급했다.^[4]

• 주문에 대해 O((통나무 ⁡ N)일상 N){\displaystyle O\left({\frac{(\log N)^{s}}{N}}\right에서)}O(1N){O\left({\frac{1}{\sqrt{N}}}\right)\displaystyle}보다, s{s\displaystyle} 작은 것과 N{N\displaystyle} 클 것(예를 들어 N을 할 필요가 있;2s{\displaystyle N&이 작아질 것.gt, 2^{$s}}).$ 큰 s 값과 실제적인 N 값의 경우, 낮은 점수의 발생기에서 설정된 점의 불일치는 무작위 집합에서보다 작지 않을 수 있다.
• 실제로 발생하는 많은 기능의 경우 $V{\displaystyle }$(${\displaystyle f}$)${\displaystyle }$=${\displaystyle \mathrm{}}$∞ ${\displaystyle V(f)=\infit }($예: 가우스 변수를 사용하는 경우)
• 오류에 대한 상한(즉, ε ≤ V(f) D_N)만 알고 있으며, ${\displaystyle D_{}^{}}$ N ${\displaystyle {}_{}^{}}$ ${\$ 및 $V$ (${\displaystyle f}$) ${\displaystyle V(f)}$을(를) 계산하기가 어렵다$.$

이러한 어려움의 일부를 극복하기 위해서는 임의의 준몬테 카를로 방법을 사용할 수 있다.

준몬테카를로 임의화

낮은 불일치 순서는 무작위가 아니라 결정론적이기 때문에 준몬테 카를로 방법은 결정론적 알고리즘이나 탈환 알고리즘으로 볼 수 있다. 이 경우 오류에 대한 바운드(예: ε ≤ V(f_N) D)만 있을 뿐 오차는 추정하기 어렵다. 분산을 분석하고 추정하는 능력을 회복하기 위해 방법을 랜덤화할 수 있다(일반적인 아이디어는 랜덤화 참조). 그 결과의 방법을 임의의 준몬테 카를로법이라고 하며, 표준 몬테 카를로법에 대한 분산 저감 기법으로도 볼 수 있다.^[5] 여러 방법 중 가장 간단한 변환 절차는 무작위 이동을 통한 것이다. {x₁,...,x_N}을(를) 낮은 불일치 시퀀스에서 설정된 점으로 두십시오. s차원 랜덤 벡터 U를 샘플링하여 {x₁, ..., x_N}과(와) 섞는다. 상세하게 각 x에_j 대해 생성

${\displaystyle y_{j}=x_{j}+U{\pmod{1}}$

그리고 (${\displaystyle {}_{}}$ ${\displaystyle j_{}}$) ${\displaystyle (x_{j}})$이 아닌$$ 시퀀스$({\displaystyle {}_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle (y_{j})$를 사용하십시오$.$ 몬테카를로에 대한 R 복제가 있는 경우 각 복제에 대해 s차원 랜덤 벡터 U 샘플. 무작위화는 준 랜덤 시퀀스를 사용하는 동안 분산의 추정치를 제공할 수 있다. 순수 유사 몬테카를로와 비교했을 때 준 무작위 시퀀스의 표본 수는 등가 계산 비용에 대해 R로 나누어 이론적 수렴률을 낮춘다. 표준 몬테카를로와 비교했을 때, Tuffin(2008)의 실험 결과보다 분산과 계산 속도가 약간 더 좋다.

참고 항목

• 몬테카를로법
• 몬테카를로 금융법
• 금융의 준몬테 카를로 방법
• 생물 몬테카를로 방법
• 계산물리학
• 점유가 적은 시퀀스
• 불일치 이론
• 마르코프 체인 몬테카를로

참조

• R. E. Caflisch, Monte Carlo 및 준-Monte Carlo 방법, Acta Numerica vol. 7, Cambridge University Press, 1998, 페이지 1–49.
• 요제프 딕과 프리드리히 필리히샤머, 디지털 네트와 시퀀스. 불일치 이론과 준몬테 카를로 통합, 캠브리지, 캠브리지, 2010, ISBN 978-0-521-19159-3
• 군터 레오바허와 프리드리히 필리히샤머, 준몽테 카를로 통합과 응용, 수학의 콤팩트 교과서, 비르케호저, 2014, ISBN 978-3-319-03424-9
• 마이클 드모타와 로버트 F. 티치, 시퀀스, 불일치 및 애플리케이션, 수학 강의 노트, 1651, 스프링어, 베를린, 1997, ISBN 3-540-62606-9
• William J. Morokoff와 Russel E. Caflisch, 준랜덤 시퀀스 및 불일치 SIAM J. Sci. 계산. 15 (1994), 6, 1251–1279 (CiteSeer:[2])
• 하랄드 니더레이터. 무작위 번호 생성 및 준몬테 카를로 방법. 공업 및 응용 수학 협회, 1992. ISBN 0-89871-295-5
• 하랄드 G. 니더레이터, 준몬테 카를로 방법과 사이비 난수, 불. 아머. 수학. Soc. 84 (1978), No. 6, 957–1041
• Oto Strauch 및 Schtefan Porubský, 시퀀스 분포: A Sampler, Peter Lang 출판사, Frankfurk am Main 2005, ISBN 3-631-54013-2

외부 링크

• MCQMC 위키 페이지에는 몬테카를로(Monte Carlo)와 준몬테 카를로(Si-Monte Carlo) 방법에 관한 무료 온라인 자료가 많이 실려 있다.
• 준몬트 카를로 방법에 대한 매우 직관적이고 포괄적인 도입