저불일치 수열 문서 원본 보기

{{위키데이터 속성 추적}}
'''저불일치 수열'''(低不一致數列, low-discrepancy sequence)은 [[수열]]의 N번째항까지의 [[균등분포 수열|불일치측도]](discrepancy)가 작은 수열이다. 이러한 수열을 '''준난수'''열('''quasirandom''' sequence)라고도 한다. 준난수를 일반적인 [[난수]]나 [[의사 난수]] 대신 사용하면 [[수치적분]] 성능이 개선된다.

== 준난수의 장점 ==
난수를 사용하지 않는 분할 방법은 데이터포인트의 수가 늘어나면 기존의 결과를 버리고 다시 계산해야 하는데, 난수를 이용한 [[몬테카를로 방법]]은 그럴 필요는 없지만 데이터포인트가 불균일하게 분포하여 정확도에 문제가 생긴다. 그러나 준난수를 사용하면 기존의 결과를 버리지 않고 다시 데이터포인트를 추가할 수 있어 유리하다. [[준몬테카를로 방법]]에 사용된다.

== 방법 ==
=== 무리수 사용 방법 ===
모든 [[무리수]] <math>\alpha</math>에 대해
: <math>s_n = \{s_0 + n\alpha\}</math>

는 좋은 준난수가 된다.

이것은 a가 1이고 m이 1인 [[선형 합동 생성기]]의 특별한 경우이다.
: <math>r_i = (a r_{i-1} + c) \bmod m</math>
위 식에서 c가 황금비의 소수부일 때 성능이 아주 좋다고 알려져 있으나, [[백은비]]를 사용할 수도 있다. 다차원에서는 [[소수 (수론)|소수]]의 제곱근(의 소수부)를 사용할 수 있다.

=== 기타 ===

네덜란드의 [[요하네스 판데르코르퓟]]이 만든 [[판데르코퓟 수열]](Van der Corput sequence), 영국의 [[d:Q102198313|J. H. Halton]]이 만든 [[홀턴 수열]](Halton sequence), 러시아에서 만들어진 [[소볼 수열]](Sobol sequence) 등이 있다.

== 같이 보기 ==
* [[준몬테카를로 방법]]
* [[마르코프 연쇄 몬테카를로 방법]]
* [[희소 격자]]

[[분류:수치해석학]]
[[분류:수열]]
[[분류:난수]]
[[분류:난수 발생기]]